计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (7): 1623-1632.DOI: 10.3778/j.issn.1673-9418.2105024

• 人工智能 • 上一篇    下一篇

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

李珺+,(), 段钰蓉, 郝丽艳, 张维维   

  1. 兰州交通大学 电子与信息工程学院,兰州 730070
  • 收稿日期:2021-05-10 修回日期:2021-07-26 出版日期:2022-07-01 发布日期:2021-07-29
  • 作者简介:李珺(1974—),女,辽宁辽阳人,博士,副教授,主要研究方向为智能计算、图像处理。
    LI Jun, born in 1974, Ph.D., associate professor. Her research interests include intelligent compu-ting and image processing.
    段钰蓉(1997—),女,山西运城人,硕士研究生,主要研究方向为智能计算。
    DUAN Yurong, born in 1997, M.S. candidate. Her research interest is intelligent computing.
    郝丽艳(1994—),女,山西吕梁人,硕士研究生,主要研究方向为智能计算。
    HAO Liyan, born in 1994, M.S. candidate. Her research interest is intelligent computing.
    张维维(1996—),女,河南洛阳人,硕士研究生,主要研究方向为智能计算。
    ZHANG Weiwei, born in 1996, M.S. candidate. Her research interest is intelligent computing.
  • 基金资助:
    甘肃省科技厅自然科学基金(1506RJZA084);甘肃省教育厅科研基金(1204-13);兰州市科技局科研基金(2015-2-74)

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

LI Jun+,(), DUAN Yurong, HAO Liyan, ZHANG Weiwei   

  1. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
  • Received:2021-05-10 Revised:2021-07-26 Online:2022-07-01 Published:2021-07-29
  • Supported by:
    the Natural Science Foundation of Science and Technology Department of Gansu Province(1506RJZA084);the Scie.pngic Research Fund of Gansu Provincial Department of Education(1204-13);the Scie.pngic Research Fund of Lanzhou Science and Technology Bureau(2015-2-74)

摘要:

为了给各物流企业在车辆配送路径规划方面提供合理有效的决策支持,针对单配送中心的配送模式,研究带时间窗约束的同时送取货车辆路径问题(VRPSDPTW),建立以总配送成本最小化为目标的数学模型。根据模型的特征,提出基于模拟退火(SA)与自适应大规模邻域搜索(ALNS)相结合的混合优化算法(SA-ALNS)。采用基于时间与距离加权的插入启发式算法构造问题的初始解;引入多种删除、插入算子,以自适应选择策略进行路径优化,并通过反馈机制,逐渐调整各操作算子被选择的概率,使算法更倾向于选择寻优效果较好的算子;使用模拟退火机制的Metropolis准则控制解的更新。仿真实验中测试了56个大规模算例,对比了p-SA算法、DCS算法和VNS-BSTS等其他智能优化算法并进行统计分析,结果证明该算法在求解带时间窗约束的同时送取货车辆路径问题的可行性和优越性,研究成果极大丰富了车辆路径问题(VRP)的相关研究。

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

Abstract:

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).

Key words: vehicle routing problem (VRP), simultaneous delivery-pickup, simulated annealing (SA), adaptive large-scale neighborhood search (ALNS), time windows

中图分类号: