单位车辆管理 [基于改进MMAS的多配送中心车辆调度问题研究]
[摘 要]针对城市多配送中心车辆调度问题，在分析最大最小蚁群算法的基础上，提出了改进MMAS算法，该算法重点对信息素的挥发机制进行探讨，并引入自适应机制对信息素的确定方案进行改进。实验结果证明，改进MMAS算法对于优化多配送中心物流车辆路径问题是有效的。
[关键词]多配送中心 最大最小蚁群算法 车辆调度
车辆凋度问题(Vehicle Scheduling Problem，VSP)是物流研究中的一个重要的领域，对于减少企业物流配送成本，提高服务品质有很重要的意义。如何在达到客户满意度的同时通过路径优化降低运送成本，成为多配送中心车辆调度问题研究的一个重要方面。目前，在解决路径优化等问题时，蚁群算法是理论和实践关注的焦点，本文研究了最大最小蚁群算法（MMAS，max-min ant system），并对信息素的计算公式进行改进，达到在多配送中心车辆调度中确保解的全局性，构造以降低配送总费用为目标的配送方案。
一、多配送中心车辆调度问题描述
在城市尤其是大规模城市的车辆调度中，由于节点规模都比较大，物流配送车辆又受到交通拥挤等因素的影响，如果每个节点只有一个配送中心，难以保证配送的及时性，容易导致整个服务水平降低，进而降低客户满意度。同时，从配送成本上考虑，在规模大的节点内单一配送中心的成本也较高。为了解决以上问题，多数物流公司在同一个大节点内一般设立多个配送中心，如图1，其中矩形代表仓库，椭圆形代表配送中心，圆点代表客户。由图1可知，从物流公司仓库到配送中心的距离是不变的，可变的是循环到不同客户配送线路距离。
二、蚁群算法描述
由于受到自然界真实蚁群集体行为的启发，由意大利学者M．Dorigo等人首先提出了一种基于种群的模拟优化算法—蚁群算法(ant system,AS)，该算法在物流配送路径优化应用过程中，存在的问题是车辆选择路径时容易陷入局部最优解，MMAS算法在一定程度上消除了基本蚁群算法中的停滞现象。
1. 最大最小蚁群算法
设m是蚁群中蚂蚁的总数，n是节点的总数，dij(i,j=1,2,...,n)表示节点i和节点j之间的距离。假设目前蚂蚁处于节点i，以τij（t）表示t时刻节点i与节点j之间的信息素浓度，ηij（t）表示t时刻蚂蚁由节点i转移到节点j的期望程度（可见度），则t时刻蚂蚁k由节点i转移到节点j概率为：
(1)
0 ，其他
其中，使用禁忌集合tabuk(k=1,2,...,m) 记录蚂蚁k当前走过的节点，则式中allowedk={1,2,...,n}-taubk表示允许蚂蚁k下一步走过节点的集合；α表示路径上的信息量对蚂蚁选择路径所起作用的大小；β表示在选择公式中两点间可见度对蚂蚁选择路径所起作用的大小；ηij（t）取值一般为1/dij。
为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每个蚂蚁完成对所有n个节点的访问后(即一个循环)，需对路径上的信息素浓度进行如下调整：①一次循环中只有最短路径的蚂蚁才可以进行信息素修改增加；②把信息素的取值范围限制在一个特定区间[τmin,τmax]内，超出这个范围的值被强制设为τmin或τmax，避免了信息素的无限制累加和可能出现的信息素为零的现象；③设信息素的初始值设为τmax，这样可以使算法遍历搜索空间，不致早熟，同时把信息素残留系数ρ设置较小，以便蚂蚁在开始搜索时选择更多路径；④采用了平滑机制（pheromone trail smoothing,PTS）,当系统停滞时，所有的信息素重新被初始化,当所有蚂蚁完成一次迭代后，蚂蚁释放的信息素为
(2)
其中参数δ决定了对以前信息素保留的多少：δ=0是完全保留，PTS不起作用；δ=1则完全去掉以前的信息素分布，重新开始计算。这种机制在较长时间计算中对于消除停滞现象有比较好的作用。
2. MMAS算法的改进
MAS中仅对最好路径上的信息素进行全局更新，而蚂蚁在行进过程中常常选择信息量较大的路径，当许多蚂蚁选中同一条路径时，该路径中的信息量就会陡然增大，从而造成堵塞现象，表现在使用该算法解决问题时就容易导致早熟和局部收敛。目前，我国大部分城市规模的不断扩张和电子商务的迅速发展，使得企业面对的顾客群体日益壮大，道路容量超负荷，车辆堵塞成为常见现象。为了解决这类较大规模的问题，本文从解的分布状态入手，提出了一种新的自适应改变τ值的方法：在每次迭代后对所有路径上的信息素 进行判断，如果在[τmin,τmax]内，按公式（3）进行计算；如果τij超出[τmin,τmax]界限，则按照公式（4）和公式（5）对 值进行修正。
(3)
(4)
(5)
(6)
其中 是一个与收敛次数m"成正比的函数，收敛次数m"越多， 的取值越大，这里c为常数,△τij的计算参照公式(6)，公式（6）中Q代表的是总信息量。该方案根据解的分布情况自适应地进行信息素的更新，从而动态地调整所有路径上的信息素强度，既避免了MMAS算法中易出现的早熟和局部收敛，又提高了全局搜索能力，更大程度的降低了运送成本。
三、实例分析
哈尔滨市L乳业有限公司位于松北区，在生产车间旁建有立体仓库，公司先将产品运送至仓库，再由该仓库向市区的配送中心送货，然后由配送中心向各大超市进行货物的配送。本文主要研究L乳业有限公司向哈尔滨市区各大型超市配送袋装鲜牛奶的情况，目的是合理地安排公司配送车辆在哈尔滨市区的行车路线，在准时到达的基础上使总运输成本最低。该企业在哈尔滨市有两个配送中心，每个配送中心有3台配送车辆，每台车载重量均为10t，配送的最大行驶距离为50km。共有20个客户（超市），每个客户的货物需求量都小于或等于2t。在运送车辆相同的情况下，设运输费用与路程成正比，所以要求组织适当的行车路线，使总的运送路程最短。其中两个配送中心的地址坐标分别为：配送中心I(6，9.2)、配送中心II(14.2，12)，20个客户的坐标及其货物需求量见表1。为了方便描述问题，在这里对两点间距离取直线距离。
表1 已知条件表
使用C语言对MMAS算法和改进的MMAS算法编程，分别在相同配置的P-C机上运算，初始参数设置为：α=1,β=1,ρ=0.3，NC=800。表2是两种算法运行结果的比较。
表2 算法的比较
通过实验结果比较，改进的MMAS算法得到的最短路径优于MMAS算法，搜索成功率高。虽然改进的MMAS教MMAS算法运行时间长，但该类问更注重经济成本的优化，所以在时间上的增量是可以接受的。总之，改进的MMAS算法对于解决多配送中心物流车辆路径问题是有效的，它解决了局部收敛，确保车辆调度的全局性，并且可有效降低全局配送费用，节约经济成本，具有一定的实用性和推广价值。
参考文献:
[1]施朝春.带有时间窗的多配送中心车辆调度问题研究[J].计算机工程与应用,2009，45(34) :21.
[2]Dorigo M，Gambar D．Ant colony algorithm for the traveling salesman problems in biological systems[J]．IEEE Transactions on Evolutionary Computation,1997，43(2)：73—81．
[3]Johnson D S，McGeoch L A．The travelling salesman problem：A case study in local optimization[M]．New York：Wilgy and Sons，1997：215—310．
[4]张强，熊盛武.多配送中心粮食物流车辆调度混合蚁群算法[J].计算机工程与应用,2011,47(7) :4 1
[5]胡小兵，袁锐等．蚁群算法原理的仿真研究[J]．计算机仿真，2004，21(8)：125—128．
[6]张纪会，高齐圣等．自适应蚂蚁群算法[J]．控制理论与应用，2000，17(1)：1-3．