多车型车辆路径问题的量子遗传算法研究

Abstract

Abstract: Based on analysis of using the priority principle in the problem of multi-vehicle scheduling in the available literature, the using cost of vehicle is divided into consumption costs and fixed costs. A mathematical model is established for the target of minimum total distribution cost. Then Quantum genetic algorithm is designed to solve the model, the chromosome structure is designed by quantum bits, and the crossover and mutation operators are improved in the genetic algorithm to avoid the destruction of good genes. The rapid searching mechanism and best preservation mechanism are designed in the evolution of the quantum rotation gate to accelerate the convergence speed. Finally, the model and algorithm are analyzed and tested by examples.

Key words: quantum genetic algorithm, vehicle routing problem, most retain mechanism, population expansion mechanism

CLC Number:

F274

GE Xian-long, XU Mao-zeng, WANG Wei-xin. Study on Multi-types Vehicle Routing Problem and Its Quantum Genetic Algorithm[J]. Chinese Journal of Management Science, 2013, (1): 125-133.

References

[1] 郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究 [J].中国管理科学, 2002, 10(5):51-56.
[2] 宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法 [J].东北大学学报, 2006, 27 (1): 65-68.
[3] 张海刚,吴燕翔,顾幸生.基于免疫遗传算法的双向车辆调度问题实现 [J].系统工程学报, 2007, 22(6): 649-654.
[4] Branchini R M,Armentano V A. Adaptive granular local search heuristic for a dynamic vehicle routing problem[J]. Computers & Operations Research, 2009, 36(11): 2955- 2968.
[5] Müller J. Approximative solutions to the bicriterion vehicle routing problem with time windows [J]. European Journal of Operational Research, 2010, 202(1): 223-231.
[6] Schǒnberger J, Kopfer H. Online decision making and automatic decision model adaptation[J].Computers & Operations Research, 2009, 36(6): 1740-1750.
[7] Novoa C, Storer R. An approximate dynamic programming approach for the vehicle routing problem with stochastic demands [J].European Journal of Operational Research, 2009, 196(2): 509-515.
[8] 王晓博,李一军.多车型单配送中心混合装卸车辆路径问题研究 [J].系统工程学报, 2010, 25(5): 629-637.
[9] 李冰. 多车型确定性动态车辆调配问题 [J].管理工程学报, 2006, 20(3): 52-56.
[10] 陈萍,黄厚宽,董兴业.求解多车型车辆路径问题的变邻域搜索算法 [J].系统仿真学报, 2011, 23(9): 1945-1951.
[11] 马建华,房勇,袁杰.多车场多车型最快完成车辆路径问题的变异蚁群算法 [J].系统工程理论与实践, 2011, 31(8): 1508-1517.
[12] 张景玲,赵燕伟,王海燕,等. 多车型动态需求车辆路径问题建模及优化 [J].计算机集成制造系统, 2010, 16(3): 543-550.
[13] 陈美军,张志胜,史金飞. 多约束下车场车辆路径问题的蚁群算法研究 [J].中国机械工程, 2008, 19(16): 1939-1944.
[14] 李建,张永,达庆利. 第三方物流多车型硬时间窗路线问题研究 [J].系统工程学报, 2008, 23(1):74-80.
[15] 熊浩,胡列格. 多车型动态车辆调度及其遗传算法 [J].系统工程, 2009, 27(10): 21-24.
[16] Subramanian A, Penna P H V, Uchoa E,et al. A hybrid algorithm for the heterogeneous fleet vehicle routing problem [J].European Journal of Operational Research, 2012, 3(7):1021-1032.
[17] Brandao J. A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem [J].Computers & Operations Research, 2008, 38(1): 140-151.
[18] Li Xiangyong, Tian Peng. An adaptive memory programming meta heuristic for the heterogeneous fixed fleet vehicle routing problem[J].Transportation Research Part E-Logistics and Transportation Review, 2010, 46(6): 1111-1127.
[19] Pessoa A,Uchoa E. A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem [J].Networks, 2009, 54(4): 167-177.
[20] Yazgi T G. An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls[J].European Journal of Operational Research, 2009, 201(20): 593-600.
[21] Repoussis P P,Tarantilis C D.Solving the fleet size and mix vehicle routing problem with time windows via adaptive memory programming [J].Transportation Research Part C, 2010, 18(5): 695-712.
[22] Narayanan A,Moore M. Quantum-inspired genetic algorithms[C].Proceedings of IEEE International Conference on Evolutionary Computation. Piscataway:IEEE Press, 1996.
[23] 施朝春,王旭,葛显龙.带有时间窗的多配送中心车辆调度问题研究 [J].计算机工程与应用, 2009, 45(34): 21-24.
[24] 邢文训,谢金星. 现代优化计算方法 [M].北京:清华大学出版社, 2009.

Study on Multi-types Vehicle Routing Problem and Its Quantum Genetic Algorithm

PDF (PC)

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 14

Metrics

Comments

Recommended 10

[1]	GUO Fang, YANG Jun, YANG Chao. Study on Heterogeneous Electric Vehicle Routing and Batterycharging Problem with the Consideration of Differentiated Service Cost [J]. Chinese Journal of Management Science, 2019, 27(8): 118-128.
[2]	FANG Wen-ting, AI Shi-zhong, WANG Qing, FAN Jun-bo. Research on Cold Chain Logistics Distribution Path Optimization Based on Hybrid Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2019, 27(11): 107-115.
[3]	PAN Wen-wen, GUO Hai-xiang, DU Tian-song, LIU Xiao, WANG De-yun. The Vehicle Routing Problem with the Recycling of Oil Pipelines and Oil Casings and the Differential Evolution Algorithm based on Niching Clearing [J]. Chinese Journal of Management Science, 2018, 26(5): 118-128.
[4]	YAN Rui, ZHU Xiao-ning, ZHANG Qun, QI Yao-yuan, LIN Yu-zheng. Research ofthe Model and Algorithm for Two-dimensional Multi-depots Capacitated Vehicle Routing Problem with Time Window Constrain [J]. Chinese Journal of Management Science, 2017, 25(7): 67-77.
[5]	FU Zhuo, LIU Wen, QIU Meng. A Tabu Search Algorithm for the Vehicle Routing Problem with Soft Time Windows and Split Deliveries by Order [J]. Chinese Journal of Management Science, 2017, 25(5): 78-86.
[6]	LI Jin, FU Pei-hua, LI Xiu-lin, ZHANG Jiang-hua, ZHU Dao-li. Study on Vehicle Routing Problem and Tabu Search Algorithmunder Low-carbon Environment [J]. Chinese Journal of Management Science, 2015, 23(10): 98-106.
[7]	ZHANG Jiang-hua, LI Jin, GAO Min-Gang. Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups [J]. Chinese Journal of Management Science, 2013, 21(4): 187-192.
[8]	ZHANG Qun, YAN Rui. Hybrid Vehicle Routing Problem Based on Improved Fuzzy Genetic Algorithm [J]. Chinese Journal of Management Science, 2012, (2): 121-128.
[9]	WANG Zheng, ZHANG Jun, WANG Xu-ping. A Modified Variable Neighborhood Search Algorithm for the Multi Depot Vehicle Routing Problem with Time Windows [J]. Chinese Journal of Management Science, 2011, 19(2): 99-109.
[10]	WANG Xu-ping, WU Xu, MA Chao, YANG De-li. Study on Disruption Management for Vehicle Routing Problem with Break-down Vehicle [J]. Chinese Journal of Management Science, 2010, 18(6): 82-88.
[11]	YU Ming-zhu, LI Jian-bin, LEI Dong. The Research of VRP with Pick-up and Delivery and a New Tabu Search Based on Insertion Method [J]. Chinese Journal of Management Science, 2010, 18(2): 89-95.
[12]	HOU Li-wen, TAN Jia-mei, ZHAO Yuan. Solving Vehicle Routing Problem with Split Deliveries and Time Window Constraints [J]. Chinese Journal of Management Science, 2007, 15(6): 46-51.
[13]	WANG Xiao-bo, LI Yi-jun. Research on Optimization of VRPTW Based on Improved Two Phase Algorithm under Electronic Commerce [J]. Chinese Journal of Management Science, 2007, 15(6): 52-59.
[14]	LU Lin, TAN Qing-mei. Vehicle Routing Problem with Simultaneous Delivery and Pick-up Studied Based on Self-telepathy Ant Colony Algorithm [J]. Chinese Journal of Management Science, 2007, 15(2): 97-103.