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

中国管理科学 ›› 2013, Vol. ›› Issue (1): 125-133.

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

葛显龙¹, 许茂增¹, 王伟鑫²

1. 重庆交通大学管理学院, 重庆 400074;
2. 重庆大学机械工程学院, 重庆 400030

收稿日期:2010-12-07 修回日期:2012-05-10 出版日期:2013-02-28 发布日期:2013-02-26
基金资助:
国家社会科学基金资助项目(11BGL006); 教育部人文社会科学研究青年基金资助项目(10YJC630039).

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

GE Xian-long¹, XU Mao-zeng¹, WANG Wei-xin²

1. School of Management, Chongqing Jiaotong University, Chongqing 400074, China;
2. College of Mechanical Engineering, Chongqing University, Chongqing 400030, China

Received:2010-12-07 Revised:2012-05-10 Online:2013-02-28 Published:2013-02-26

摘要/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

中图分类号:

F274

葛显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学, 2013, (1): 125-133.

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.

参考文献

[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.