丁宗闯
（安徽建筑大学土木工程学院 安徽省 合肥市 230601）
摘要：本文主要针对牛奶配送最优路线进行了相关研究，利用蚂蚁算法，研究出牛奶配送最快的方案。首先在给定牛奶站和给定配送点的条件下，综合考虑配送成本、牛奶新鲜度及每次运载量，确定配送员的最佳配送路线。其次根据题目所给信息利用Matlab绘制牛奶站及需求点分布图，先几何分割再多次关键点优化将分布图分成四个区域，转化为四次TSP问题，最后利用蚁群算法求出最佳路线。
关键词：配送问题；TSP问题；蚁群算法
引言：
物流配送的许多环节都造成巨大的成本、人力、时间浪费，如何合理的安排配送任务和设计配送路线是物流公司面临的一个实际难题以来降低物流成本。现针对某市区的鲜牛奶配送需求，建立数学模型。根据给出的某城区 92 个牛奶配送点的坐标、需求量及相互之间的连接道路信息，假设以牛奶站的位置坐标为原点，牛奶配送车的载货量为 400 瓶，速度是 20 公里/小时，每个需求点的下货时间为 1 分钟，配送车辆送完牛奶后需返回牛奶站。基于以上条件设计一个运输成本最低的配送方案。由于鲜奶的保鲜要求，需要尽快的完成配送，在考虑成本的前提下，设计出一个最快的配送方案。
1、问题分析
物流配送与我们的生活密切相关，所以合理的安排配送任务和设计配送路线是快递公司面临的一个实际难题。根据信息利用 Matlab 绘制牛奶站及需求点分布图，经过实验对比,在求解 TSP 时蚂蚁循环系统性能好,因而本文采用它作为基本
模型。算法停止条件可以用固定循环次数或者当解的变化不明显时便停止计算。再多次几何分割将分布图分成四个区域，接着是转化为四次 TSP 问题，利用蚁群算法求出最佳路线。
2、模型建立与求解
根据牛奶配送点之间的道路，经过 MATLAB 处理转化到二维坐标系中（如图 1）
.png)
图1 各点位置与连通情况
本题在短时间内进行 TSP 问题分析，按照一定规则就几何划分不失为一种好方法，虽然相比较于其他算法分割质量较差，可多次优化来提高分割质量。题中未考虑牛奶站与配送区域的线路，根据牛奶配送点的数据表示出在不考虑实际情况下的连接牛奶站与最近配送点的可能路线模拟图，以订奶量为基准，沿 X 轴使 1245 瓶牛奶平均分到四个区域。TSP问题就是给定一组城市,求得一条遍历所有城市的最短回路的问题，该问题空间可以用一个静态图来描述，并且可以用距离矩阵来描述问题空间本身的特征。在 TSP 中，城市数目称为该问题的阶数，为了模拟实际蚂蚁的行为，首先引进如下符号:d(i,j=1,2,…,n)代表城市τ和城市φ之间的距离(欧式空间的距离);ηij= 1/dij,为边(i,j)的自启发量，表示由城市i转移到城市j的期望程度;M是蚁群算法的蚂蚁数量;τ(t)表示t时刻边(i,j)上信息激素浓度。蚂蚁完成一次循环(即找到了-条遍历所有城市节点的回路)，各路径上信息激素要根据公式作调整:
.png)
各路径上信息激素要根据公式作调整:
τ(t+n)=ρxij(t)+∆τij(t)
∆τ(t)=ΣM∆t(t)
式中∆τ(tij)表示第k只蚂蚁t时刻在城市i和j之间留下的信息素增量,对第k只蚂蚁来说，它在所走过的边上引起的信息激素增量技公式计算:
.png)
其中，Q 称为总信息量,为一个给定的常数:若采用在线更新方式，则Lk为第k只蚂蚁到目前所走过路径的长度;若采用延迟更新方式,则Lk为第k只蚂蚁遍历所有城市节点后得到的回路的距离。
M.Dorigo 曾给出三种不通模型，分别称之为蚂蚁循环系统(ant-cycle system)、蚂蚁数量系统(ant-quantity system)、蚂蚁密度系统(ant-density system)。它们的差别在于公式的不同，在蚂蚁数量系统模型中：
.png)
在蚂蚁密度系统模型中:
.png)
这三种模型的区别在于后两种模型中利用的是局部信息,而前者利用的是全局信息,经过实验对比,在求解 TSP 时蚂蚁循环系统性能好,因而本文采用它作为基本模型，算法停止条件可以用固定循环次数或者当解的变化不明显时便停止计算，基本蚁群算法实现步骤如下:设置路径(i,j)上的初始信息量τij(0)=c(c为常数)，∆τk(0)=0,将M只蚂蚁随机放置在n个城市，同时为每只蚂蚁建立禁忌列表tabu,将初始节点置入禁忌列表，为参数.png)
设定初始值;设定算法迭代次nc=0;While not 约束条件do
for i=1 to n - 1 do（遍历所有城市）
for K=1 to M do（对M只有蚂蚁循环）
for j=1 to n don（对n个城市循环）
蚂蚁k选择下一个城市j,将蚂蚁k移动到城市j,把城市j置入禁忌列表 tabak;
end
end
end
计算所有蚂蚁求得的回路距离,根据公式更新路径(i,j)上的信息激素; nc=nc+1;
end while输出结果，结束算法。
结论：
本文首先根据牛奶配送员送牛奶路线的优化设计问题，即在给定牛奶站和给定配送点的条件下，综合考虑确定配送员的最佳配送路线，牛奶配送点之间的道路，经过 MATLAB 处理转化，其次在短时间内进行 TSP 问题分析，根据牛奶配送点的数据表示出在不考虑实际情况下的连接牛奶站与最近配送点的可能路线模拟图，最后利用蚂蚁算法求出最佳路线。
参考文献：
[1]司守奎, 孙玺菁. 数学建模算法与应用[M]. 国防工业出版社, 2011.
[2]姚路. 图分割算法及其在大规模数值并行计算中的应用研究[D]. 国防科学技术大学.
[3]刘银春, 郑汉富, 王宜怀, et al. 电磁辐射灭菌牛奶保鲜及其营养成分的研究[J]. 森林与环境学报, 2000, 20(3):245-247.
[4]劳眷. TSP 问题中的蚁群优化算法研究[D]. 湖南大学.
[5]叶明基. 基于嵌套分割算法的复杂物流系统库存仿真优化[D]. 华中科技大学, 2009.