混合优化算法求解同时送取货车辆路径问题  

Hybrid Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery-Pickup

作　　者：李珺[1] 段钰蓉 郝丽艳 张维维 LI Jun;DUAN Yurong;HAO Liyan;ZHANG Weiwei(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《计算机科学与探索》2022年第7期1623-1632,共10页Journal of Frontiers of Computer Science and Technology

基　　金：甘肃省科技厅自然科学基金(1506RJZA084);甘肃省教育厅科研基金(1204-13);兰州市科技局科研基金(2015-2-74)。

摘　　要：为了给各物流企业在车辆配送路径规划方面提供合理有效的决策支持,针对单配送中心的配送模式,研究带时间窗约束的同时送取货车辆路径问题(VRPSDPTW),建立以总配送成本最小化为目标的数学模型。根据模型的特征,提出基于模拟退火(SA)与自适应大规模邻域搜索(ALNS)相结合的混合优化算法(SA-ALNS)。采用基于时间与距离加权的插入启发式算法构造问题的初始解;引入多种删除、插入算子,以自适应选择策略进行路径优化,并通过反馈机制,逐渐调整各操作算子被选择的概率,使算法更倾向于选择寻优效果较好的算子;使用模拟退火机制的Metropolis准则控制解的更新。仿真实验中测试了56个大规模算例,对比了p-SA算法、DCS算法和VNS-BSTS等其他智能优化算法并进行统计分析,结果证明该算法在求解带时间窗约束的同时送取货车辆路径问题的可行性和优越性,研究成果极大丰富了车辆路径问题(VRP)的相关研究。In order to provide reasonable and effective decision support for logistics enterprises in vehicle distribu tion path planning,this paper studies the vehicle routing problem with simultaneous delivery-pickup and time windows(VRPSDPTW)for single distribution center distribution mode,and establishes a mathematical model with the objective of minimizing the total distribution cost.According to the characteristics of the model,a hybrid optimization algorithm(SA-ALNS)based on the combination of simulated annealing(SA)and adaptive large-scale neighborhood search(ALNS)is proposed.An insertion heuristic algorithm based on time and distance weighting is used to construct the initial solution of the problem.A variety of delete and insert operators are introduced to optimize the path with adaptive selection strategy.Through the feedback mechanism,the probability of each operator being selected is gradually adjusted to make the algorithm more inclined to choose the operator with better optimization effect.The Metropolis criterion of simulated annealing mechanism is used to control the solution updating.In the simulation experiment,56 large-scale examples are tested,and other intelligent optimization algori thms such as p-SA algorithm,DCS algorithm and VNS-BSTS are compared and statistically analyzed.The results show that the algorithm is feasible and superior in solving the vehicle routing problem with simultaneous delivery pickup and time windows.The research results greatly enrich the related research of vehicle routing problem(VRP).

关 键 词：车辆路径问题(VRP) 同时送取货 模拟退火算法(SA) 自适应大规模邻域搜索算法(ALNS) 时间窗 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]