开放式带时间窗车辆路径问题及变邻域搜索算法

Solving open vehicle routing problem with time windows based on variable neighborhood search algorithm

针对配送服务中开放式带时间窗车辆路径问题,构建了最小化车辆行驶成本的集分割模型,并提出变邻域搜索算法进行求解。该算法包括抖动和邻域搜索两个阶段,其中,抖动阶段通过当前解与种群历史最优、与个体历史最优之间的路径重连来实现,邻域搜索阶段通过同一条路径内以及不同路径间的交换、插入、2-opt三个操作算子来实现。通过与已有文献进行对比,结果表明该算法在求解开放式带时间窗车辆路径问题时,能得到更高质量的解,而且算法的收敛性和稳定性均较好。由此验证了该算法的可行性和有效性。

Aiming at the Open Vehicle Routing Problem with Time Windows(OVRPTW)in delivery service,a set partition model was built to minimize the costs of travelling,and the Variable Neighborhood Search(VNS)algorithm was proposed to solve this problem.This algorithm included two stages:shaking and neighborhood search.The shaking was realized by path relinking between the current solution,the population historical optimal solution and the individual historical optimal solution.The neighborhood search was implemented by three operators that were exchange,insertion and 2-opt within the same path and between different paths.The comparison with the existing literature showed that the proposed algorithm could obtain not only higher quality solutions,but also better convergence and stability,which verified the feasibility and effectiveness of the proposed algorithm.