|Table of Contents|

Multi-agent evolutionary algorithm of VRP problem with time window(PDF)

《交通运输工程学报》[ISSN:1671-1637/CN:61-1369/U]

Issue:
2014年03期
Page:
105-110
Research Field:
交通运输规划与管理
Publishing date:

Info

Title:
Multi-agent evolutionary algorithm of VRP problem with time window
Author(s):
LIU Xin-meng;  HE Shi-wei;  CHEN Sheng-bo;  LU Chao
School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China
Keywords:
traffic planning;  logistics distribution;  vehicle routing;  number coding;  multi-agent evolutionary algorithm;  time window
PACS:
U491.12
DOI:
-
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. 3 tabs, 6 figs, 19 refs.

References:

[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.
[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.
[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.
[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.
[6] 吴 勇,叶春明,马慧民,等.基于并行粒子群算法的带时间窗车辆路径问题[J].计算机工程与应用,2007,43(14):223-226.WU 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)
[7] 刘 霞,齐 欢.带时间窗的动态车辆路径问题的局部搜索算法[J].交通运输工程学报,2008,8(5):114-120.LIU 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)
[8] 刘志硕,申金生,柴跃廷.基于自适应蚁群算法的车辆路径问题研究[J].控制与决策,2005,20(5):562-566.LIU 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)
[9] 潘立军,符 卓.求解带硬时间窗车辆路径问题的时差插入启发式算法[J].计算机应用,2012,32(11):3042-3043,3070.PAN 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)
[10] BANOS R, ORTEGA J, GIL C, et al. A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows[J]. Expert System with Application, 2013, 40(5): 1696-1707.
[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 I[J]. QRSA Journal on Computing, 1989, 1(3): 190-206.
[13] 周 屹,李海龙,王 锐.遗传算法求解物流配送中带时间窗的VRP问题[J].吉林大学学报:理学版,2008,46(2):300-303.ZHOU 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)
[14] 龚延成,郭晓汾,尤晓铃,等.基于遗传算法的物流配送车辆调度问题研究[J].数学的实践与认识,2004,34(6):93-97. GONG 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)
[15] 郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学,2002,10(5):51-56.LANG 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)
[16] 马宇红,姚婷婷,张浩庆.基于分区的多配送中心多车型车辆调度问题与遗传算法设计[J].科技导报,2013,31(2):61-67.MA Yu-hong, YAO Ting-ting, ZHANG Hao-qing. Multi-delivery 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)
[17] 袁 志.解排列优化的整数编码多智能体进化算法[J].软件,2011,32(5):24-26.YUAN Zhi. Number coding multi-agent evolutionary algorithm for deployment optimization[J]. Computer Engineering and Software, 2011, 32(5): 24-26.(in Chinese)
[18] 曾聪文,古天龙.求解装配序列规划的一种多智能体进化算法[J].计算机集成制造系统,2009,15(9):1803-1808.ZENG 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)
[19] 边 霞,米 良.遗传算法理论及其应用研究进展[J].计算机应用研究,2010,27(7):2425-2429,2434. BIAN Xia, MI Liang. Developmenton genetic algorithm theory and its applications [J]. Application Research of Computers, 2010, 27(7): 2425-2429, 2434.(in Chinese)

Memo

Memo:
-
Last Update: 2014-06-30