《计算机应用研究》|Application Research of Computers

带时间窗车辆路径问题的分布式多agent蚁群算法

Distributed multiagent-based ant colony algorithm for vehicle routing problem with time windows

免费全文下载 (已被下载 次)  
获取PDF全文
作者 金淳,张雨,王聪
机构 大连理工大学 系统工程研究所,辽宁 大连 116024
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)03-0666-05
DOI 10.3969/j.issn.1001-3695.2018.03.006
摘要 针对带时间窗车辆路径问题(VRPTW)算法在求解效率、求解复杂度、求解大规模问题方面存在的不足,提出一种改进的分布式多agent蚁群算法,以提高算法精度和速度为研究目的。本算法在传统蚁群算法的基础上,为提高算法精度,改进了状态转移规则,结合了邻域搜索算法;为提高算法速度,将本算法设计为分布式结构,利用多分布式agent系统实现了分布式求解VRPTW问题。针对国际标准算例设计了四个实验,结果表明,本算法在精度、速度、可靠性以及求解大规模问题方面具有明显优势。本研究为有效求解大规模、复杂VRPTW问题提供了一种新思路和可行的方法。
关键词 带时间窗车辆路径问题;蚁群算法;分布式算法;代理
基金项目 国家自然科学基金资助项目(71271041)
本文URL http://www.arocmag.com/article/01-2018-03-006.html
英文标题 Distributed multiagent-based ant colony algorithm for vehicle routing problem with time windows
作者英文名 Jin Chun, Zhang Yu, Wang Cong
机构英文名 InstituteofSystemsEngineering,DalianUniversityofTechnology,DalianLiaoning116024,China
英文摘要 Because of the disadvantage in the previous research of the vehicle routing problem with time windows (VRPTW), like limited solving efficiency, limited complexity, and difficulty to solve large-scale problems, this paper proposed a distributed multi agent ant colony algorithm which aimed at improving the accuracy and speed of the algorithm. Based on the traditio-nal ant colony algorithm, this paper improved the state transition rule and combined the neighborhood search algorithm to improve the accuracy. At the same time, it designed the algorithm as a distributed structure to improve the speed. So, it could utilize multi agent distributed system to distributed solve the VRPTW problem. The results of four experiments which designed for the international standard show that this algorithm has obvious advantages in accuracy, speed, reliability and solving large-scale problems. This research provides a new idea and a feasible method for solving large-scale and complex VRPTW problems.
英文关键词 vehicle routing problem with time windows(VRPTW); ant colony algorithm; distributed algorithm; agent
参考文献 查看稿件参考文献
  [1] 张媛媛, 李建斌. 动态车队组合优化模型及精确算法[J] . 系统工程理论与实践, 2007, 27(2):83-91.
[2] 张群, 颜瑞. 基于改进模糊遗传算法的混合车辆路径问题[J] . 中国管理科学, 2012, 20(2):21-128.
[3] 马建华, 房勇, 袁杰. 多车场多车型最快完成车辆路径问题的变异蚁群算法[J] . 系统工程理论与实践, 2011, 31(8):1508-1516.
[4] Mirabi M, Ghomi S M T F, Jolai F. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing problem[J] . Robotics and Computer-Integrated Manufacturing, 2010, 26(6):564-569.
[5] 陈玉光, 陈志祥. 基于准时送货和最小耗油的配送车辆路径问题研究[J] . 中国管理科学, 2015, 23(S1):156-164.
[6] Yang Xinshe. A new metaheuristic bat-inspired algorithm[J] . Computer Knowledge and Technology, 2010, 284:65-74.
[7] 李妍峰, 高自友, 李军. 基于实时交通信息的城市动态网络车辆路径优化问题[J] . 系统工程理论与实践, 2013, 33(7):1813-1819.
[8] 李峰, 魏莹. 易腐货物配送中时变车辆路径问题的优化算法[J] . 系统工程学报, 2010, 25(4):492-519.
[9] Xiao Yiyong, Zhao Qiuhong, Kaku I, et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem[J] . Computers & Operations Research, 2012, 39(7):1419-1431.
[10] Rahimi-Vahed A, Crainic T G, Gendreau M, et al. A path relinking algorithm for a multi-depot periodic vehicle routing problem[J] . Journal of Heuristics, 2013, 19(3):497-524.
[11] 徐云, 刘向彬, 陈晓欣, 等. 固定时间窗快递车辆路径问题建模及求解[J] . 系统工程, 2016, 34(7):97-103.
[12] 马秋卓, 王健, 宋海清. 市区小范围多车辆低碳VRP:以珠海速递公司区域收件网络为例[J] . 管理工程学报, 2016, 30(4):153-159.
[13] Kwon Y J, Choi Y J, LEE D H. Heterogeneous fixed fleet vehicle routing considering carbon emission[J] . Transportation Research Part D:Transport and Environment, 2013, 23(8):81-89.
[14] 饶卫振, 金淳. 求解大规模CVRP问题的快速贪婪算法[J] . 管理工程学报, 2014, 28(2):45-54.
[15] 李净, 袁小华, 朱云飞. 物流配送系统中车辆路径问题的实现[J] . 计算机工程与设计, 2009, 30(16):3783-3786.
[16] 傅成红, 符卓. 一种毗邻信息改进的车辆路径问题禁忌搜索算法[J] . 系统工程, 2010, 28(5):81-84.
[17] 段征宇, 杨东援, 王上. 时间依赖型车辆路径问题的一种改进蚁群算法[J] . 控制理论与应用, 2010, 27(11):1557-1563.
[18] 朱婷, 王旭磊, 赵来军. 带时间窗的时变多目标危险化学品道路运输路径优化[J] . 工业工程, 2016, 19(2):62-67.
[19] 颜瑞, 张群, 胡睿. 考虑三维装箱约束的车辆路径问题研究[J] . 中国管理科学, 2015, 23(1):128-134.
[20] Lin Canhong, Choy K L, Ho G T S, et al. Survey of green vehicle routing problem:past and future trends[J] . Expert Systems with Applications, 2014, 41(4):1118-1138.
[21] 吴耀华, 张念志. 带时间窗车辆路径问题的改进粒子群算法研究[J] . 计算机工程与应用, 2010, 46(15):230-234.
[22] 李军, 郭耀煌. 物流配送车辆优化调度理论与方法[M] . 北京:中国物资出版社, 2001.
[23] 曹庆奎, 赵斐. 基于遗传蚁群算法的港口集卡路径优化[J] . 系统工程理论与实践, 2013, 33(7):1820-1828.
[24] 王征, 张俊, 王旭坪. 多车场带时间窗车辆路径问题的变邻域搜索算法[J] . 中国管理科学, 2011, 19(2):99-109.
[25] Zafar K, Baig R, Bukhari N, et al. Route planning and optimization of route using simulated ant agent system[J] . International Journal of Computer Applications, 2010, 4(8):457-478.
[26] Ilie S, Bdic C. Multi-agent approach to distributed ant colony optimization[J] . Science of Computer Programming, 2013, 78(6):762-774.
[27] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J] . Operations Research, 1987, 35(2):254-265.
[28] Gehring H, Homberger J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows[J] . Proceedings of Eurogen99 Jyvskyl University of Jyvskyl, 1999, 40(1):95-101.
[29] 何小锋, 马良. 带时间窗车辆路径问题的量子蚁群算法[J] . 系统工程理论与实践, 2013, 33(5):1255-1261.
[30] Aras N, Aksen D, Tekin M T. Selective multi-depot vehicle routing problem with pricing[J] . Transportation Research Part C, 2011, 19(5):866-884.
[31] Kuo Yiyo, Wang Chichang. A variable neighborhood search for the multi-depot vehicle routing problem with loading cost[J] . Expert Systems with Applications, 2012, 39(8):6949-6954.
[32] 李宁, 邹彤, 孙德宝. 带时间窗车辆路径问题的粒子群算法[J] . 系统工程理论与实践, 2004, 24(4):130-135.
收稿日期 2016/11/22
修回日期 2017/1/18
页码 666-670
中图分类号 TP301.6
文献标志码 A