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

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

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

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.