Multi-agent evolutionary algorithm of VRP problem with time window
Article Text (Baidu Translation)
-
摘要: 基于实用性和合理性的角度, 研究了单个配送中心带时间窗的车辆路径问题。以行驶时间最短和客户等待时间最小为目标函数, 以服务时间窗与车辆载质量为约束条件, 建立了双目标优化模型, 采用基于整数编码的多智能体进化算法求解模型, 并将计算结果与利用遗传算法求得的结果进行对比。计算结果表明: 当客户需求点的数量为13, 需求点的服务时间为5min, 车辆最大载质量为3t, 初始智能体个数为49, 最大进化代数为200次时, 经过30次计算后, 采用遗传算法的最差值为121.8min, 最优值为110.3min, 采用提出多智能体进化算法的最差值为113.6min, 最优目标值为103.6min。可见, 采用多智能体进化算法能够获得更高质量的最优解, 而且经过多次反复试验, 最终解的变化不大。Abstract: Based on the angle of practicality and rationality, the vehicle routing problem with time window for single distribution center was studied.The shortest driving time and the minimum customer waiting time were taken as objective functions, the service time window and vehicle load were taken as constraint conditions, and the bi-objective optimization model was constructed. The Multi-agent evolutionary algorithm based on number coding (NC-MAEA) was used to solve the model, and the calculation result was compared with the calculation result solved by genetic algorithm.Calculation result shows that when the number of customer demand point is 13, the service time of demand point is 5 min, the maximum vehicle load is 3 t, the number of initial agent is 49 and the maximum evolution iterations is 200, the worst value is 121.8 min and the optimal value is 110.3 min calculated by using genetic algorithm after 30 calculation times.The worst value is 113.6 min and the optimal value is 103.6 min calcuated by using the propsed algorithm.It is clear that the higher quality optimal result can be gotten by using the multi-agent evolutionary algorithm, the results change little after repeated tests.
-
[1] CHIEN S, GAO Sheng-yan, MEEGODA J N, et al. Fleet size estimation for spreading operation considering road geometry, weather and traffic[J]. Journal of Traffic and Transportation Engineering: English Edition, 2014, 1 (1): 1-12. doi: 10.1016/S2095-7564(15)30084-2 [2] KALLEHAUGE B. Formulations and exact algorithms for the vehicle routing problem with time windows[J]. Computers and Operations Research, 2008, 35 (7): 2307-2330. doi: 10.1016/j.cor.2006.11.006 [3] RALPHS T K, KOPMAN L, PULLEYBLANK W R, et al. On the capacitated vehicle routing problem[J]. Mathematical Programming, 2003, 94 (2): 343-359. [4] KOHL N, MADSEN O B G. An optimization algorithm for the vehicle routing problem with time windows based on lagrangian relaxation[J]. Operations Research, 1997, 45 (3): 395-406. doi: 10.1287/opre.45.3.395 [5] JULIEN B, DAVID S. On the effectiveness of set covering formulations for the vehicle routing problem with time windows[J]. Operations Research, 1997, 45 (2): 295-301. doi: 10.1287/opre.45.2.295 [6] 吴勇, 叶春明, 马慧民, 等. 基于并行粒子群算法的带时间窗车辆路径问题[J]. 计算机工程与应用, 2007, 43 (14): 223-226. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200714065.htmWU Yong, YE Chun-ming, MA Hui-min, et al. Parallel particle swarm optimization algorithm for vehicle routing problems with time windows[J]. Computer Engineering and Applications, 2007, 43 (14): 223-226. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200714065.htm [7] 刘霞, 齐欢. 带时间窗的动态车辆路径问题的局部搜索算法[J]. 交通运输工程学报, 2008, 8 (5): 114-120. http://transport.chd.edu.cn/article/id/200805023LIU Xia, QI Huan. Local search alogrithm of dynamic vehicle routing problem with time window[J]. Journal of Traffic and Transportation Engineering, 2008, 8 (5): 114-120. (in Chinese). http://transport.chd.edu.cn/article/id/200805023 [8] 刘志硕, 申金生, 柴跃廷. 基于自适应蚁群算法的车辆路径问题研究[J]. 控制与决策, 2005, 20 (5): 562-566. doi: 10.3321/j.issn:1001-0920.2005.05.018LIU Zhi-shuo, SHEN Jin-sheng, CHAI Yue-ting. Vehicle routing problem based on an adaptive ant colony algorithm[J]. Control and Decision, 2005, 20 (5): 562-566. (in Chinese). doi: 10.3321/j.issn:1001-0920.2005.05.018 [9] 潘立军, 符卓. 求解带硬时间窗车辆路径问题的时差插入启发式算法[J]. 计算机应用, 2012, 32 (11): 3042-3043, 3070. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201211019.htmPAN Li-jun, FU Zhuo. Time difference insertion heuristics algorithm for vehicle routing problem with hard time window[J]. Journal of Computer Applications, 2012, 32 (11): 3042-3043, 3070. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201211019.htm [10] BANOS R, ORTEGA J, GIL C, et al. A simulated annealingbased parallel multi-objective approach to vehicle routing problems with time windows[J]. Expert System with Application, 2013, 40 (5): 1696-1707. doi: 10.1016/j.eswa.2012.09.012 [11] GILLETT B E, MILLER L R. A Heuristic algorithm for the vehicle-dispatch problem[J]. Operations Research, 1974, 22 (3): 340-349. [12] GLOVER F. Tabu search—part Ⅰ[J]. QRSA Journal on Computing, 1989, 1 (3): 190-206. [13] 周屹, 李海龙, 王锐. 遗传算法求解物流配送中带时间窗的VRP问题[J]. 吉林大学学报: 理学版, 2008, 46 (2): 300-303. https://www.cnki.com.cn/Article/CJFDTOTAL-JLDX200802029.htmZHOU Yi, LI Hai-long, WANG Rui. VRP problem with time windows in the logistics and distribution solved by genetic algorithm[J]. Journal of Jilin University: Science Edition, 2008, 46 (2): 300-303. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JLDX200802029.htm [14] 龚延成, 郭晓汾, 尤晓铃, 等. 基于遗传算法的物流配送车辆调度问题研究[J]. 数学的实践与认识, 2004, 34 (6): 93-97. https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200406016.htmGONG Yan-cheng, GUO Xiao-fen, YOU Xiao-ling, et al. Solving the vehicle routing and scheduling problems by genetic algorithms[J]. Mathematics in Practice and Theory, 2004, 34 (6): 93-97. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200406016.htm [15] 郎茂祥, 胡思继. 用混合遗传算法求解物流配送路径优化问题的研究[J]. 中国管理科学, 2002, 10 (5): 51-56. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200205010.htmLANG Mao-xiang, HU Si-ji. Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm[J]. Chinese Journal of Management Science, 2002, 10 (5): 51-56. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200205010.htm [16] 马宇红, 姚婷婷, 张浩庆. 基于分区的多配送中心多车型车辆调度问题与遗传算法设计[J]. 科技导报, 2013, 31 (2): 61-67. https://www.cnki.com.cn/Article/CJFDTOTAL-KJDB201302024.htmMA Yu-hong, YAO Ting-ting, ZHANG Hao-qing. Multidelivery centre multi-type vehicle scheduling problem based on the partition and the design of genetic algorithm[J]. Science and Technology Review, 2013, 31 (2): 61-67. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-KJDB201302024.htm [17] 袁志. 解排列优化的整数编码多智能体进化算法[J]. 软件, 2011, 32 (5): 24-26. https://www.cnki.com.cn/Article/CJFDTOTAL-RJZZ201105009.htmYUAN Zhi. Number coding multi-agent evolutionary algorithm for deployment optimization[J]. Computer Engineering and Software, 2011, 32 (5): 24-26. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-RJZZ201105009.htm [18] 曾聪文, 古天龙. 求解装配序列规划的一种多智能体进化算法[J]. 计算机集成制造系统, 2009, 15 (9): 1803-1808. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200909020.htmZENG Cong-wen, GU Tian-long. Multi-agent evolutionary algorithm for assembly sequence planning[J]. Computer Integrated Manufacturing Systems, 2009, 15 (9): 1803-1808. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200909020.htm [19] 边霞, 米良. 遗传算法理论及其应用研究进展[J]. 计算机应用研究, 2010, 27 (7): 2425-2429, 2434. https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201007006.htmBIAN Xia, MI Liang. Developmenton genetic algorithm theory and its applications[J]. Application Research of Computers, 2010, 27 (7): 2425-2429, 2434. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201007006.htm -
下载:
点击查看大图
图(6) / 表(3)
计量
- 文章访问数: 713
- HTML全文浏览量: 159
- PDF下载量: 1244
- 被引次数: 0
