求解有硬时间窗车辆路径问题的改进遗传算法

摘要

针对军事运输中有硬时间窗的车辆路径问题（vehicle routing problem with hard time windows，VR-PHTW），结合混合交叉运算、改进变异运算和精英保留策略，以所有车辆的配送总时间最少为目标，设计了改进遗传算法。借鉴贪婪思想，提高了初始种群的优越性；构造了迭代种群的入口矩阵和出口矩阵，并以此为基础提出改进交叉算子，期间引入前向插入法设计了混合交叉运算，加快了种群的寻优速度；同时提出改进变异算子，增加了种群的多样性。实验结果表明，改进遗传算法较之基本算法有着更快的收敛速度和更优的收敛效果。%In view of the vehicle routing problem with hard time windows in military transportation,an im-proved genetic algorithm which aims to minimize the vehicles’total delivery time with the combination of hybrid crossover operation,improved mutation operation and an elite reserve strategy is put forward.First,it improves the initial population superiority by the greedy thought.Second,the entrance matrix and export matrix of the convergence population are constructed and the improved crossover operator based on the matrices is proposed. At the same time,the hybrid crossover operation is designed,which speeds up the population optimization through introducing the push forward insertion heuristic algorithm.At last,the population diversity is increased with the introduction of an improved mutation operator.The experimental results show that the improved ge-netic algorithm has a faster convergence speed and a better convergence effect than the basic algorithm.