求解带时间窗车辆路径问题的混合Memetic算法  

Hybrid Memetic Algorithm for Vehicle Routing Problem with Time Windows

作　　者：张晓楠[1] 范厚明 ZHANG Xiao-nan;FAN Hou-ming(College of Mechanical&Electrical Engineering,Shaanxi University of Science&Technology,Xi’an 710021,China;College of Transportation Engineering,Dalian Maritime University,Dalian 116026,China)

机构地区：[1]陕西科技大学机电工程学院,陕西西安710021 [2]大连海事大学交通运输工程学院,辽宁大连116026

出　　处：《运筹与管理》2021年第7期128-135,共8页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71802120);陕西省教育厅专项科研项目(19JK0125);陕西省创新能力支撑计划(2020KRM024)。

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]