Abstract: To improve the solution quality and time-efficiency for solving the vehicle routing problem with time windows(VRPTW), a hybrid memetic genetic algorithm (HMA) is proposed. Firstly, a hybrid insertion method based on sorting time window is used to generate initial population, and an arbitrary selection operation is applied to maintain the intensification and diversification, which achieves the global-space with the intensification and diversification. Secondly, a simplified variable neighborhood search (SVNS) is developed to search the local-space, where a neighborhood size reduction scheme (NERS) and a constraint relaxation mechanism is applied. Finally, a post-learning process with arc is used, where the current population inherits the good genes from the current and global optimal solution. The experimental results on benchmark instances show that the proposed algorithm has better performance in solution quality.

Key words: vehicle routing problem with time windows, Memetic algorithm, neighborhood size reduction scheme, post-learning process

摘要： 为提高带时间窗车辆路径问题的求解精度和求解效率,设计了一种混合Memetic算法。采用基于时间窗升序排列的混合插入法构造初始种群,提高解质量的同时兼顾多样性,扩大搜索空间;任意选择组成父代种群,以维持搜索空间;运用简化的变邻域搜索进行局部开发,引入邻域半径减少策略提高开发效率,约束放松机制开放局部空间;以弧为对象,增加种群向当前最优解和全局最优解的后学习过程。实验结果表明,所提出的算法具有较好的寻优精度和稳定性,能搜索到更好的路径长度结果,更新了现有研究在最短路径长度的目标函数上的下限。

关键词: 带时间窗车辆路径问题, Memetic算法, 邻域减少策略, 后学习算法