﻿ 改进蚁群算法在VRP问题中的应用及颜色Petri网实现
 计算机系统应用  2018, Vol. 27 Issue (11): 186-191 PDF

Application of Improved Ant Colony Algorithm in VRP Problem and Its Colored Petri Net Realization
ZHENG Wen-Yan, ZHAO Li-Min
School of Information Management, Dezhou University, Dezhou 253023, China
Abstract: This research has proposed an adaptive ant colony algorithm and its colored Petri net approach, aiming to solve the slow operation problems existed in vehicle routing problems. The new developed method has improved the updating rule of pheromone, changed the formula of transfer probability and the constructed technique of feasible solutions, with the Petri net model conducted accordingly. The proposed method is finally verified compared to GA and some other ACOs through standard test cases, with the results demonstrated that the method developed effectively improves the convergence efficiency, refrains the searching from being trapped in local optima, and ensures the diversity of the final solutions.
Key words: ant colony optimization     vehicle routing problem     colored Petri nets

1 引言

Petri网是1962年德国学者Petri[11]在其博士论文中提出的. Petri网是一个图形化数学化的模型工具, 适用于描述并发、异步、分布式、并行、非确定性或随机的信息处理系统, 应用于各种领域[1215].

2 求解VRP的改进蚁群算法 2.1 可行解构造的改进

Step1. 从蚂蚁集合队列 $an{t_i}$ 的队首取出蚂蚁 $an{t_1}$ , $an{t_1}$ 从当前位置出发(初始位置为配送中心), 按以下两个约束条件生成可选择的客户列表access.

Step2. 从满足约束条件1和2的access列表中, 按照轮盘赌的方式, 随机选择一个客户进行服务.

Step3. 更新蚂蚁 $an{t_1}$ 的位置, 剩余装载量, 服务过的客户列表, access列表.

Step4. 判断access是否为空, 如果为空, 说明蚂蚁 $an{t_1}$ 一次可以服务完所有的客户, 蚂蚁 $an{t_1}$ 放到蚂蚁集合 $an{t_i}$ 的队尾, 同时初始化access列表, 并记录该可行解, 且该可行解只需一辆车即可; 如果access不为空那么跳至并执行约束条件2, 然后更新access, 如果更新后access为空, 说明蚂蚁 $an{t_1}$ 配送一次不足以服务完所有的客户, 需回到配送中心装满货物(第二辆车)并且 $an{t_1}$ 需放置蚂蚁集合 $an{t_i}$ 的队首, 再跳至约束条件2进行循环, 如此, 直至access为空, 形成可行解, $an{t_1}$ 从配送中心出发几次代表需要几辆车才可以服务完所有的客户.

2.2 信息素更新的改进公式

 $Tota{l_m} = \left\{ \begin{array}{l}Tota{l_d},\;Tota{l_d} < Tota{l_m}\\Tota{l_m},\;{\rm {otherwise}}\end{array} \right.$ (1)

 ${\tau _{\rm {new}}}{\rm{ = }}\left\{ \begin{array}{l}{\tau _{\rm {now}}} + \displaystyle\frac{1}{{Tota{l_d}}},\;{\rm {if}}\;Tota{l_d} \le Tota{l_m}\\{\tau _{\rm {now}}} - \displaystyle\frac{1}{{Tota{l_d}}},\;\;{\rm {if}}\;\;Tota{l_d} > Tota{l_m} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm {and}}\;\;\left({\tau _{\rm {now}}} - \displaystyle\frac{1}{{Tota{l_d}}}\right) \ge 0\\0,\;{\rm {if}}\;\;Tota{l_d} > Tota{l_m}\;\;and\left( {{\tau _{\rm {now}}} - \displaystyle\frac{1}{{Tota{l_d}}}} \right) < 0\end{array} \right.$ (2)
2.3 概率选择公式的改进

 ${p_i}_j = \left\{ \begin{array}{l}\displaystyle\frac{{{\tau _{ij}}^\alpha }}{{{d_{ij}}}}\;\;\;\;\;j \in Access\;\;\;{\rm {and}}\;\;{\tau _{ij}} \ne 0\\\displaystyle\frac{1}{{{d_{ij}}}}\;\;\;\;\;j \in Access\;\;\;{\rm {and}}\;\;{\tau _{ij}} = 0\;\end{array} \right.$ (3)

3 改进蚁群算法的颜色Petri网模型 3.1 CPN模型及颜色集描述

 图 1 改进的ACO的CPN模型的top页

3.2 部分模型及主要函数

colset AntCity = product AntN*CurrentCity*PassCity

*LCityNum*REAL;

colset LAntCity = list AntCity;

4 测试实例

1) 案例1[17]: 某配送中心用2辆额定装载量为8×103 kg的汽车对8个客户配送货物, 配送中心与客户、客户与客户之间的距离以及客户的需求量如表1所示, 其中, 0代表配送中心, 其他代表8个客户点. 其余参数的设置详见参考文献[17].

 图 2 可行解生成过程

 图 3 案例1所有可行解的分布情况图

2) 案例2(E016-03m): 某配送中心(编号为0)用3辆装载量为90吨的车辆对15个客户配送货物. 其余参数的设置详见参考文献[18]. 得到的最优解最优路径如图4所示.

3) 案例3(eil22): 某配送中心(编号为0)用4辆装置量为6 ×103 kg的车辆对21个客户配送货物. 其余参数的设置详见参考文献[20]. 得到的最优解最优路径如图5所示.

 图 4 本文算法与其他算法的最优路径

5 结束语

 图 5 本文算法与其他算法的最优路径

 [1] Toth P, Vigo D. Vehicle routing: Problems, methods, and applications. 2nd ed. Philadelphia, American: Society for Industrial and Applied Mathematics, 2014. [2] Dorigo M, Di Caro G. Ant colony optimization: A new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation. Washington, DC, USA. 1999. 1470–1477. [3] Gambardella LM, Taillard É, Agazzi G. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. Corne D, Dorigo M, Glover F. New Ideas in Optimization. London, UK: McGraw-Hill, 1999. 63–76. [4] 赵群. 基于改进混合蚁群算法的车辆路径问题研究[硕士学位论文]. 合肥: 合肥工业大学, 2015. [5] 刘春英. 粒子群融合蚁群算法多配送中心车辆路径研究. 吉林师范大学学报(自然科学版), 2013, 34(3): 88-91. [6] 石华瑀. 改进的蚁群算法在实际VRP中的应用研究[硕士学位论文]. 济南: 山东大学, 2012. [7] Yu B, Yang ZZ, Yao BZ. An improved ant colony op-timization for vehicle routing problem. European Journal of Operational Research, 2009, 196(1): 171-176. DOI:10.1016/j.ejor.2008.02.028 [8] 葛斌. 求解车辆路径问题的蚁群优化算法研究及应用[博士学位论文]. 合肥: 合肥工业大学, 2016. [9] 周和平, 陈亮. 求解CVRP问题的一种改进启发式蚁群算法. 后勤工程学院学报, 2015, 31(4): 80-84, 89. DOI:10.3969/j.issn.1672-7843.2015.04.014 [10] Dhawan C, Kumar Nassa V. Review on vehicle routing problem using ant colony optimization. International Journal of Advanced Research in Computer Science, 2014, 5(6): 74-78. [11] Petri CA. Communication with automata[Ph.D. thesis]. Bonn: University of Bonn, 1962. [12] 郭峰, 魏光. 基于Petri网的Web服务描述及其可替换性分析. 计算机集成制造系统, 2013, 19(6): 1423-1432. [13] 范贵生, 虞慧群, 陈丽琼, 等. 基于Petri网的服务组合故障诊断与处理. 软件学报, 2010, 21(2): 231-247. [14] 曾庆田, 鲁法明, 刘聪, 等. 基于Petri网的跨组织应急联动处置系统建模与分析. 计算机学报, 2013, 36(11): 2290-2302. [15] 陆中, 孙有朝, 吴海桥. 基于着色随机时间Petri网的维修性建模方法. 机械工程学报, 2011, 47(10): 185-191. [16] Westergaard M. CPN tools 4: Multi-formalism and extensibility. Colom JM, Desel J. Application and Theory of Petri Nets and Concurrency. Berlin, Hei-delberg: Springer, 2013. 400–409. [17] 范小宁, 徐格宁, 杨瑞刚. 车辆配送路径优化的新型蚁群算法. 计算机工程与应用, 2011, 47(26): 232-234, 245. DOI:10.3778/j.issn.1002-8331.2011.26.066 [18] 岳苹. 基于改进蚁群算法的车辆路径优化问题研究. 工业控制计算机, 2017, 30(9): 54-55. DOI:10.3969/j.issn.1001-182X.2017.09.025 [19] 闫凯, 李爱光, 郭健. 基于混合算法的单配送中心路径优化方法. 测绘科学技术学报, 2016, 33(6): 650-653. [20] 高明芳. 基于粒子群蚁群混合算法的物流车辆路径问题研究[硕士学位论文]. 内蒙古: 内蒙古农业大学, 2016. [21] 王书勤. 车辆路径问题的蚁群算法研究[硕士学位论文]. 重庆: 重庆大学, 2008.