2. 辽宁科技大学研究生院, 辽宁 鞍山 114051
2. Graduate School, University of Science and Technology Liaoning, Anshan 114051, China
1 引言
车辆运输调度问题(vehicle routing and scheduling problems，VRSP)是物流配送研究领域中一个具有重要理论和现实意义的研究方向. VRSP是指在给定的约束条件下，为了减少运输成本，满足客户要求，尽可能给出最优的车辆行车路线和最好的出行时间安排[1]. 在实际调度问题中，约束条件包括车辆的装载量、 车辆的运输时间、 运输工人的工作时间及运输路线的长度等. 由于该问题属于求解较为困难的组合优化NP-hard问题而且具有强有力的应用背景，长期以来吸引着大量学者对其进行不断地研究与探索，其中包括模拟退火算法、 神经网络和遗传算法等[2].
根据蚂蚁“寻找食物”的群体行为，1991年意大利学者Dorigo等[3]在法国巴黎召开的第一届欧洲人工生命会议(European conference on artificial life，ECAL)上最早提出了一种新型的仿生算法——蚁群算法. 蚁群算法是一种源于自然界中生物世界的新的仿生类随机型搜索算法，通过其内在的搜索机制，已在一系列困难的组合优化问题，如旅行商问题TSP(traveling salesman problem)的求解中取得了成效[4]. 蚁群算法虽然具有分布式并行计算机制、 易与其它方法结合和较强的鲁棒性等优点，但搜索时间长、 易陷入局部最优是其最为突出的特点[5].
针对VRSP问题和上述蚁群算法存在的缺陷，首先针对传统蚁群算法在构造解的过程中存在收敛速度慢且容易陷入局部最优的问题，通过建立α(信息素启发式因子)和β(期望启发式因子)的互锁关系，动态自适应调整α和β从而提高算法收敛速度； 其次对距离启发式因子ηij(t)进行重新定义，通过引入不同客户间的“偏好力”，增强算法的实用性；最后将改进蚁群算法成功应用于解决VRSP问题.
2 蚁群算法基本原理及数学模型蚁群算法是科学家受到自然界中真实蚁群觅食行为的启发，经过长期研究发现： 单个蚂蚁虽没有视觉，也无法掌握附近地理信息，但运动时会通过在路径上释放出一种特殊的分泌物——信息素——来寻找路径[6]. 当蚁群在运动路径上突然出现障碍物时，蚂蚁也可以通过信息素相互传递最终找到一条躲避障碍物的最优路径[7]. 蚁群算法具有分布式并行计算机制、 易与其它方法相结合、 实现简单的优点. 这也正是其最早成功应用于解决著名TSP问题的原因.
蚂蚁k(k=1，2，…，m)在运动过程中，根据各条路径上的信息量决定其转移方向. 用禁忌表tabuk(k=1，2，…，m)来记录k当前所走过的节点，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率，设C=｛c1，c2，…，cn｝是n个城市的集合. t时刻蚂蚁k由节点i转移到节点j的状态转移概率pijk (t)[8]如式(1)所示：
Δτkij(t)定义如下：
车辆运输调度问题是指在给定的约束条件下，为了减少运输成本满足客户要求，尽可能给出最优的车辆行车路线. 即考虑在约束条件下，某个地区有一个车场(中心仓库)和N个客户点. 运输车辆从车场出发，服务若干客户点后，返回车场，则形成一条回路[11]，如图 1所示.
 |
| 图 1 车辆调度路线Fig. 1 The route of vehicle scheduling |
当车辆速度及单位距离成本一定时，车辆的运输时间及运输成本与客户的距离成正比，此时一种常见的处理方式是将此约束条件归一化为距离启发式因子. 这种方法可以有效引入距离约束，但忽略了车辆在调度过程中，不同客户点的VIP等级(即优先等级).
鉴于以上问题，通过引入改进蚁群算法，提高蚁群收敛速度，扩大蚁群搜索空间和增强算法的实用性是非常有必要和有意义的.
首先做如下假设：
(1)中心仓库拥有车辆载重、 容积统一的运输车m辆，V=｛k｝(k=1，2，…，m)且m为待定车辆数，其中每辆车容量为q[12].
(2)客户集为C=｛i｝(i=1，2，…，n)，由m辆车为其运输，客户i的需求量为qi.
(3) 各客户点与车场均有道路连通，车辆无需按原路返回.
(4)从客户i到客户j的费用为Cij(如时间、 路程、 花费等).
3.2 目标函数模型及相关约束目标函数模型：
相关约束条件如下：
定义1 α、 β的动态自适应调整是指通过建立α和β的互锁关系，即对不同的迭代次数NC，α和β对应取不同的值，进而在整个过程中提高收敛速度，扩大搜索空间，使蚁群算法跳离局部最优.
根据蚁群算法搜索情况来自适应动态调整α和β. 采用关于迭代次数NC的阶梯函数α(NC)和β(NC)来代替常数项α和β.
在搜索过程中为了达到一定平衡，式中α和β是互锁的关系，即αi+βi=M(其中M为一定值，在本次实验中M取10). 由于α值和β值过大或过小都易使蚁群的搜索过早陷入局部最优[15]. 结合其它改进算法中α和β的取值经验与分析，同时通过多次仿真实验分析，确定当1≤α≤9，1≤β≤9时更有利于整个改进算法动态调整. 开始时信息素浓度差别不大，以各个节点之间的距离为主要调整因素，这样有利于提高路径搜索速度，即信息启发式因子α(1≤α1<5)取值较小，相对应的期望启发式因子β(5<β1≤9)取值较大[16]； 随着迭代次数增加，各条路径的信息素也得到了积累，此时选择信息素浓度为主要调整因素进行全局搜索，即信息启发式因子α(5<α2≤9)先取较大值，相对应的期望启发式因子β(1≤β2<5)取较小值； 随着迭代次数的继续增加，为了防止由于信息素积累的正反馈机制作用而导致陷入局部最优，进而改为以各个节点距离为主要调整因素，即信息启发式因子α(1<α3≤5)先取值较小，相对应的期望启发式因子β(5≤β3<9)取值较大.
定义2 距离启发式因子的重新约定是指结合车辆调度问题，通过引入各个客户点之间的“偏好力”，对蚁群算法中的距离启发式因子ηij(t)进行重新定义，此处“偏好力”为不同客户点之间的距离及VIP等级，对调度车辆产生的一种吸引力. 其中既包括各客户点间的距离约束，同时又引入了各客户点的VIP等级约束.
具体操作如下，令：
Step 1：对蚁群规模m，改进蚁群算法的最大迭代次数NCmax及ρ、 Q等参数进行初始化.
Step 2：将m只蚂蚁随机均匀分布在各个目标节点上，若蚂蚁k随机地处于节点i，则其禁忌表为tabuk=｛i｝.
Step 3：根据与i相连各条路径｛(i，j1)，(i，j2)，…，(i，jm)上的信息素，按转移概率式(1)选择下一个候选节点，其中α和β的值按式(18)和式(19)进行动态自适应调整，距离启发函数ηij(t)按式(20)进行确定，并将已选择节点jl(l=1，2，…，m)放入禁忌表.
Step 4：判断点i与j连接后的线路上总货物量Q，若Q≤q，则转Step 3，否则修改禁忌表tabuk，删除已选节点jl且转到Step 5.
Step 5： 按式(3)～式(5)对已访问节点的路径信息素进行更新.
Step 6：NC←NC+1，若NC≤NCmax，返回Step 3； 否则寻优结束，退出程序输出最优解.
4 仿真实验及其分析为了验证改进算法的可行性和实用性，针对传统蚁群算法在车辆运输调度过程中搜索时间长、 易陷入局部最优且忽略客户VIP等级等缺点，将其分别与传统蚁群算法及文[8]改进算法进行对比，基于不同规模VRSP仿真算例在Matlab 7.0环境中进行仿真实验分析. 实验中重要参数设置如表 1所示.
| 算法 | 参数 | |||||
| m | α | β | ρ | Q | NCmax | |
| 传统蚁群算法 | 32 | 1 | 5 | 0.5 | 0.5 | 200 |
| 改进蚁群算法 | 32 | 按式(18)~式(19)进行调整 | 0.5 | 0.5 | 200 | |
案例1 某配送中心有3辆额定载重量为8×103 kg的汽车对客户配送货物，配送中心与客户、 客户与客户的距离及各客户的VIP等级(0代表配送中心，1～8代表8个客户点)如表 2所示[17]. 为了方便起见，此处设定qij=qji即客户i对客户j的VIP等级与客户j对客户i的客户等级相等且级别q∈(0，1).
| 客户i | 客户j | ||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 0 | 18 | 30 | 38 | 66 | 16 | 68 | 10 | 24 |
| 1 | 18 | 0 | 31 | 15 | 29 | 21 | 43 | 64 | 35 |
| 2 | 30 | 31 | 0 | 22 | 26 | 9 | 11 | 13 | 6 |
| 3 | 29 | 15 | 22 | 0 | 8 | 27 | 25 | 39 | 26 |
| 4 | 66 | 29 | 26 | 8 | 0 | 29 | 20 | 48 | 32 |
| 5 | 16 | 21 | 9 | 27 | 27 | 0 | 32 | 15 | 23 |
| 6 | 68 | 43 | 11 | 25 | 20 | 32 | 0 | 35 | 30 |
| 7 | 10 | 64 | 13 | 39 | 48 | 15 | 35 | 0 | 14 |
| 8 | 24 | 35 | 6 | 26 | 32 | 23 | 30 | 14 | 0 |
| VIP | - | 0.3 | 0.6 | 0.4 | 0.5 | 0.7 | 0.1 | 0.2 | 0.4 |
将本文改进蚁群算法与文[8]改进蚁群算法和传统蚁群算法在基于VRSP仿真算例下进行比较，具体实验结果如图 2和图 3所示.
 |
| 图 2 基于案例1的本文改进算法与传统算法比较Fig. 2 Comparison between the improved algorithm in this paper and traditional algorithm based on case 1 |
图 2和图 3表示3辆车为8个客户进行物流配送所得到的最终收敛曲线. 图 2中实线为本文所提的改进蚁群算法，图 2中点划线为传统蚁群算法(其中图 2的上半部为本文所提的改进蚁群算法与传统蚁群算法在平均距离上的仿真对比； 下半部为其在最短路径距离上的仿真对比). 图 3中实线为本文所提的改进蚁群算法，图 3中点线为文[8]改进蚁群算法(其中图 3的上半部为本文所提的改进蚁群算法与文[8]改进算法在平均距离上的仿真对比； 下半部为其在最短路径距离上的仿真对比). 图 4为采用本文改进蚁群算法所搜索到的最优车辆调度路线. 具体仿真数据分析如表 3所示.
 |
| 图 4 最优调度路线Fig. 4 The optimal scheduling route |
案例2 某配送中心有5辆额定载重量分别为8×103 kg的汽车对客户配送货物，配送中心与客户、 客户与客户的距离及各客户的VIP等级等相关约定与案例1相仿[18]. 将本文改进蚁群算法与文[8]改进蚁群算法和传统蚁群算法在基于不同规模的客户(此处设定为20个客户)上进行VRSP仿真对比，具体实验结果如图 5和图 6所示.
 |
| 图 5 基于案例2的本文改进算法与传统算法比较Fig. 5 Comparison between the improved algorithm in this paper and traditional algorithm based on case 2 |
图 5和图 6表示5辆车为20个客户进行物流配送所得到的最终收敛曲线. 图 5中实线为本文所提的改进蚁群算法，图中点划线为传统蚁群算法(其中图 5的上半部为本文所提的改进蚁群算法与传统蚁群算法在平均距离上的仿真对比； 下半部为其在最短路径距离上的仿真对比). 图 5中实线为本文所提的改进蚁群算法，图 5中点线为文[8]改进算法(其中图 5的上半部为本文所提的改进蚁群算法与文[8]改进算法在平均距离上的仿真对比； 下半部为其在最短路径距离上的仿真对比). 图 7为采用本文改进蚁群算法所搜索到的最优车辆调度路线. 具体仿真数据分析如表 4所示.
 |
| 图 7 最优调度路线Fig. 7 The optimal scheduling route |
| 算法 | 优化路径 | 最优距离 /km | 平均距离 /km | 耗时 /s |
| 传统蚁群算法 | 0-3-5-6-9-0， 0-4-8-7-2-0， 0-1-17-14-15-0， 0-10-13-11-16-0， 0-12-18-19-20-0 | 337 | 402.761 5 | 43.609 000 |
| 文[8]改进算法 | 0-2-4-3-1-0， 0-5-7-10-12-0， 0-8-13-15-9-0， 0-6-14-17-0， 0-16-19-20-18-0 | 324 | 384.253 1 | 36.358 000 |
| 本文改进蚁群算法 | 0-1-3-5-0， 0-4-6-8-7-2-0， 0-9-17-0， 0-13-14-11-10-0， 0-12-15-16-18-19-20 | 322 | 379.248 6 | 34.297 000 |
通过不同规模VRSP的仿真结果可得出如下结论：
(1) 由图 2、 图 5对比分析可知在不同规模VRSP的问题中，基于改进蚁群算法的车辆调度，所收敛到的最优距离及平均距离明显优于传统蚁群算法，有效地避免算法陷入局部最优[19].
(2) 由图 3、 图 6对比分析可知本文改进算法在收敛速度上稍劣于文[8]中的改进算法，但本文改进算法在跳离局部最优及运行时间上优于文[8]改进算法.
(3) 由表 3、 表 4仿真数据分析可知基于改进蚁群算法的车辆调度，不仅在最优距离及平均距离上得到了明显改善，而且在不同规模的VRSP中明显缩短了运行时间，提高了算法的收敛速度.
(4) 图 4、 图 7的仿真结果进一步验证了改进蚁群算法在车辆调度应用中的可行性、 实用性及在物流配送中寻优的高效性.
5 结论本文在原有蚁群算法的基础上，主要针对两个方面进行了改进，首先针对蚁群算法在构造解的过程中存在收敛速度慢且容易陷入局部最优问题，提出动态自适应调整α、 β策略； 其次对距离启发式因子ηij(t)进行重新定义，根据不同客户的VIP等级引入不同客户间的“偏好力”，提高算法的搜索效率及实用性. 最后通过仿真实验将其与文[8]改进蚁群算法和传统蚁群算法基于不同规模VRSP算例进行对比分析，仿真结果显示该改进算法在一定程度上提高了搜索速度，有效地弥补了传统蚁群算法容易陷入局部最优的劣势. 通过仿真结果也进一步验证了改进算法的可行性，及在不同规模VRSP问题中寻找最优路线的高效性. 但该仿真环境为理想已知环境，在动态未知环境中车辆不一定能成功找出一条高效、 实用的调度路线，因此有待进一步研究.
| [1] | 祝文康, 钟育彬. 基于改进蚁群算法的物流车辆调度问题研究[J]. 江南大学学报, 2012, 11(3): 273-276. Zhu W K, Zhong Y B. Vehicle scheduling based on improved ant colony algorithm[J]. Journal of Jiangnan University, 2012, 11(3): 273-276. |
| [2] | 沈鹏. 物流配送路径优化问题求解的量子蚁群算法[J]. 计算机工程应用, 2013, 49(21): 56-59. Shen P. Quantum ant colony algorithm for optimization of logistics distribution route[J]. Computer Engineering and Applications, 2013, 49(21): 56-59. |
| [3] | Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]//Proceedings of the 1st European Conference on Artificial Life. Paris, France: Elsevier Publishing, 1991: 134-142. |
| [4] | 陈迎欣. 基于改进蚁群算法的车辆路径优化问题研究[J]. 计算机应用研究, 2012, 29(6): 2031-2034. Chen Y X. Study on VRP based on improved ant colony optimization[J]. Application Research of Computers, 2012, 29(6): 2031-2034. |
| [5] | 段海滨. 蚁群算法原理及其应用[M]. 北京: 科学出版社, 2005. Duan H B. Ant colony algorithms: Theory and applications[M]. Beijing: Science Publishing, 2005. |
| [6] | Jackson D E, Holcombe M, Ratnieks F L W. Trail geometry gives polarity to ant foraging networks[J]. Nature, 2004, 432(7019): 907-909. |
| [7] | 孙莹, 连民杰. 基于改进蚁群算法的地下矿车辆生产调度路径优化研究[J]. 金属矿山, 2010, 404(2): 51-54. Sun Y, Lian M J. Research on vehicle routing and scheduling problems based on improved ACA in underground mine[J]. Metal Mine, 2010, 404(2): 51-54. |
| [8] | 戴树贵, 陈文兰, 潘荫荣, 等. 多配送中心车辆路径安排问题混合蚁群算法[J]. 四川大学学报: 工程科学版, 2008, 40(6): 154-158. Dai S G, Chen W L, Pan Y R, et al. A hybrid ant colony algorithm for multiple depot vehicle routing problem[J]. Journal of Sichuan University: Engineering Science Edition, 2008, 40(6): 154-158. |
| [9] | Gutjahr W J. A graph-based ant system and its convergence[J]. Future Generation Computer Systems, 2000, 16(9): 873-888. |
| [10] | 陈美军, 张志胜, 史金飞. 多约束下多车场车辆路径问题的蚁群算法研究[J]. 中国机械工程, 2008, 19(16): 1939-1944. Chen M J, Zhang Z S, Shi J F. Study on ant colonyalgorithm for multi-depots vehicle routing problem with multiple constraints[J]. China Mechanical Engineering, 2008, 19(16): 1939-1944. |
| [11] | Bonabeau E, Dorigo M. Theraulaz G. Inspiration for optimization from social insect behaviour[J]. Nature, 2000, 406(6): 39-42. |
| [12] | 陈美军, 张志胜, 史金飞. 基于自适应多态蚁群算法的多约束车辆路径问题[J]. 东南大学学报: 自然科学版, 2008, 38(1): 37-42. Chen M J, Zhang Z S, Shi J F. Vehicle routing problem with multiple constraints using adaptive and polymorphic ant colony algorithm[J]. Journal of Southeast University: Natural Science Edition, 2008, 38(1): 37-42. |
| [13] | AI-taharwa I, Sheta A, AI-weshah M. A mobile robot path planning using genetic algorithm in static environment[J]. Journal of Computer Sciences, 2008, 4(4): 341-344. |
| [14] | 刘志硕, 申金升, 柴跃廷. 基于自适应蚁群算法的车辆路径问题研究[J]. 控制与决策, 2005, 20(5): 562-566. Liu Z S, Shen J S, Chai Y T. Vehicle routing problem based on an adaptive ant colony algorithm[J]. Control and Decision, 2005, 20(5): 562-566. |
| [15] | Goss S, Aron S, Deneubourg J L, et al. Self-organized shortcuts in the argentine ant[J]. Naturwissenschaften, 1989, 76(12): 579-581. |
| [16] | 李秀娟, 杨玥, 蒋金叶, 等. 蚁群优化算法在物流车辆调度系统中的应用[J]. 计算机应用, 2013, 33(10): 2822-2826. Li X J, Yang Y, Jiang J Y, et al. Application of antcolony optimization to logistics vehicle dispatching system[J]. Journal of Computer Applications, 2013, 33(10): 2822-2826. |
| [17] | Michael J B K, Jean-Bernard B, Laurent K. Ant-like task allocation and recruitment in cooperative robots[J]. Nature, 2000, 406(31): 992-995. |
| [18] | 徐滨, 张亦. 改进的蚂蚁算法车辆运行调度算法研究[J]. 计算机仿真, 2011, 28(10): 366-369. Xu B, Zhang Y. Research on transit routes network design based on improved ant algorithm[J]. Computer Simulation, 2011, 28(10): 366-369. |
| [19] | Emilio F. Real-time motion planning for agile autonomous vehicles[J]. Journal of Guidance, Control and Dynamics, 2002, 25(1): 116-129. |
| [20] | Demirel N C, Toksarı M D. Optimization of the quadratic assignment problem using an ant colony algorithm[J]. Applied Mathematics and Computation, 2006, 183(1): 427-435. |