Multi-agent evolutionary algorithm of VRP problem with time window

LIU Xin-meng; HE Shi-wei; CHEN Sheng-bo; LU Chao

Volume 14 Issue 3

Turn off MathJax

Article Contents

Article Navigation > Journal of Traffic and Transportation Engineering > 2014 > 14(3): 105-110

Next Previous

LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, LU Chao. Multi-agent evolutionary algorithm of VRP problem with time window[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 105-110.

Citation:

LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, LU Chao. Multi-agent evolutionary algorithm of VRP problem with time window[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 105-110.

LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, LU Chao. Multi-agent evolutionary algorithm of VRP problem with time window[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 105-110.

Citation:

LIU Xin-meng, HE Shi-wei, CHEN Sheng-bo, LU Chao. Multi-agent evolutionary algorithm of VRP problem with time window[J]. Journal of Traffic and Transportation Engineering, 2014, 14(3): 105-110.

PDF( 393 KB)

Multi-agent evolutionary algorithm of VRP problem with time window

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

More Information

Author Bio:
LIU Xin-meng (1990-), female, graduate student, +86-10-81687135, 13120872@bjtu.edu.cn

HE Shi-wei (1969-), male, professor, +86-10-81687135, shwhe@bjtu.edu.cn
Received Date: 2014-01-17
Publish Date: 2014-06-25

Abstract

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.
- traffic planning,
- logistics distribution,
- vehicle routing,
- number coding,
- multi-agent evolutionary algorithm,
- time window

FullText(HTML)

References(19)

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. 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]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200714065.htm
[7]	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). http://transport.chd.edu.cn/article/id/200805023
[8]	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). doi: 10.3321/j.issn:1001-0920.2005.05.018
[9]	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). 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]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-JLDX200802029.htm
[14]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200406016.htm
[15]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK200205010.htm
[16]	MA 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]	YUAN 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]	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). https://www.cnki.com.cn/Article/CJFDTOTAL-JSJJ200909020.htm
[19]	BIAN 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