基于改进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 studyin local optimization[M]．New York：Wilgyand 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．