基于混合NSGA-Ⅱ的有硬时间窗的多目标 车辆路径问题

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (2): 176-183.

基于混合NSGA-Ⅱ的有硬时间窗的多目标车辆路径问题

吴天羿¹，刘建永^*1，许继恒¹，翁杰² ,昝良¹

1.解放军理工大学，南京210007；2南京军区工程环境质量监督站南京210012

收稿日期:2013-08-05 修回日期:2013-11-19 出版日期:2014-04-25 发布日期:2014-07-07
作者简介:吴天羿（1984-），男，江苏南通人，博士生.

Multi-objective Vehicle Routing Problem with Hard Time Windows Based on Hybrid NSGA-Ⅱ

WU Tian-yi¹，LIU Jian-yong ¹，XU Ji-heng ¹，WENG Jie²，ZAN Liang ¹

1.PLA University of Science and Technology, Nanjing210007, China；2Nanjing Military Region Engineering Environmental Quality Supervision Station, Nanjing,210012

Received:2013-08-05 Revised:2013-11-19 Online:2014-04-25 Published:2014-07-07

摘要/Abstract

摘要：

针对有硬时间窗的多目标车辆路径问题，本文采取交叉、变异和精英保留相结合的选择策略，分别以配送总时间、调用车辆数和配送总费用为决策目标，设计了混合 NSGA-Ⅱ.首先，为提高初始种群的优越性，引入了时差插入法；其次，以继承父代的优秀基因、加快种群的寻优速度为目的，提出了新颖交叉算子并设计了新颖交叉运算；再次，通过子路径变异运算以增加种群的多样性；最后，构造了基于密度的Pareto排序以保证种群分布的均匀性.本文不仅描述了算法的详细步骤，而且通过实验就收敛代数、目标函数和仿真结果进行了比较与分析.结果表明，混合NSGA-Ⅱ较之基本算法有着更快的收敛速度和更好的收敛效果.

关键词: 物流工程, NSGA-Ⅱ, 多目标, 车辆路径问题, 硬时间窗, 时差插入法

Abstract:

In view of the multi-objective vehicle routing problem with hard time windows, this paper which includes the selection strategy of crossover, mutation and elite reserve designs the hybrid NSGA-Ⅱwith the purpose of short distribution time, small used vehicles and little distribution fee. Firstly, the time difference insertion algorithm is introduced to improve the initial population superiority. Secondly, the novel crossover operator and the novel crossover operation are proposed, in order to inherit the good genes from the parent population and accelerate the optimization speed. Then the sub-paths mutation is introduced to increase the population diversity. At last, the Pareto sorting is constructed based on the density to ensure the uniformity of the population distribution. The paper not only describes the algorithm’s detail steps, but also compares and analyzes the convergence algebra, the objective function and the simulation results through the experiment. The results show that the hybrid NSGA-Ⅱhas a faster convergence speed and a better convergence effect than the basic algorithm.

Key words: logistics engineering, NSGA-Ⅱ, multi-objective, vehicle routing problem, hard time windows, time difference insertion algorithm

中图分类号:

吴天羿，刘建永，许继恒，翁杰. 基于混合NSGA-Ⅱ的有硬时间窗的多目标车辆路径问题[J]. 交通运输系统工程与信息, 2014, 14(2): 176-183.

WU Tian-yi，LIU Jian-yong,XU Ji-heng,WENG Jie，ZAN Liang . Multi-objective Vehicle Routing Problem with Hard Time Windows Based on Hybrid NSGA-Ⅱ[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(2): 176-183.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18766.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I2/176

参考文献

[1] 李军，郭耀煌.物流配送车辆优化调度理论与方法[M]. 北京:中国物资出版社,2001，2.[LI J, GUO Y H. Logis? tics vehicle scheduling theory and methods [M]. Beijing: China Material Press,2001，2.]

[2] Braysy O, Gendreau M. Vehicle routing problem with time windows, Part II: Metaheuristics[J]. Transportation Science,2005,39(1):119-139.
[3] K C Tan, L H Lee, Q L Zhu, et al. Heuristic methods for vehicle routing problem with time windows [J]. Artificial Intelligence in Engineering,2001,15:281-295.
[4] K C Tan, L H Lee, K Ou. Artificial intelligence heuristics in solving vehicle routing problems with time windows constraints[J]. Engineering Applications of Artificial Intelligence,2001,14:825-837.
[5] Berger J, Barkaoui M. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows[J]. Computers and Operations Research, 2004,31:2037-2053.
[6] Braysy O, Dullaert W, Gendreau M. Evolutionary algorithms for the vehicle routing problem with time windows[J]. Journal of Heuristics,2004,10:587-611.
[7] Alvarenga G B ,Mateus G R , Tomi G. A genetic and set partitioning two- phase approach for the vehicle routing problem with time windows[J]. Computers and Operations Research,2007,34:1561-1584.
[8] 谢秉磊,李军,郭耀煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报,2000,15(3): 290-294.[XIE B L, LI J, GUO Y H. Genetic algorithm for vehicle scheduling problem of non-full loads with time windows[J]. Journal of Systems Engineering, 2000, 15(3): 290-294.]
[9] 张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统2002,8(6):451-454.[ZHANG L P, CHAI Y T, CAO R. Improved genetic algorithm for vehicle routing problem with time windows[J]. Computer Integrated Manufacturing Systems, 2002, 8(6):451-454.]
[10] 宋厚冰,蔡远利.带时间窗的车辆路径混合遗传算法[J].交通运输工程学报,2003,3(4):112-115.[SONG H B,CAI Y L. Hybrid genetic algorithm of vehicle routing with time windows [J]. Journal of Traffic and Transportation Engineering,2003,3(4):112-115.]
[11] Horn J, Nafpliotis N, Goldberg D E. A niched pareto genetic algorithm for multiobjective optimization[C]. IEEE World Congress on Computational Intelligence,1994, 1:82-87.
[12] Srinivas N, Deb K. Multiobjective optimization using nondominated sorting in genetic algorithm [J]. Evolutionary Computation,1994,2:221-248.
[13] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization[C]. Proceedings of the Evolutionary Methods for Design, Optimization and Control,2002:19-26.
[14] Deb K. A fast and elitist multi- objective genetic algorithm: NSGA-II [J]. IEEE Trans on Evolutionary Computation,2002,6(2):182-197.
[15] Thibaut V, Teodor G C, Michel G, et al. A Hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time- windows [J]. Computers & Operations Research,2013：475-489.
[16] 潘立军,符卓.求解带时间窗取送货问题的遗传算法[J].系统工程理论与实践,2012,32(1):120-126.[PAN L J, FU Z. Genetic algorithm for the pickup and delivery problem with time windows [J]. Systems EngineeringTheory and Practice,2012,32(1):120-126.]
[17] Deb K. A fast and elitist non-dominated sorting genetic algorithm for multi- objective optimization: NSGA- II[R]. KanGAL Report 200001, Indian Institute of Technology, Kanpur, India.
[18] 文诗华,郑金华.NSGA-Ⅱ中一种改进的分布性保持策略[J].计算机工程与应用,2010,46(33):49-53.[WEN SH, ZHENG J H. Improved diversity maintenance strategy in NSGA-Ⅱ [J].Computer Engineering and Applications,2010,46(33):49-53.]