《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (4): 1187-1194.DOI: 10.11772/j.issn.1001-9081.2023101512

• 先进计算 • 上一篇    

面向多行程取送货车辆路径问题的混合NSGA-Ⅱ

李建强, 何舟()   

  1. 陕西科技大学 电气与控制工程学院,西安 710021
  • 收稿日期:2023-11-06 修回日期:2024-01-10 接受日期:2024-01-12 发布日期:2024-04-22 出版日期:2024-04-10
  • 通讯作者: 何舟
  • 作者简介:李建强(1998—),男,甘肃定西人,硕士研究生,主要研究方向:车辆路径规划、组合优化
    何舟(1990—),男,陕西安康人,副教授,博士,主要研究方向:多移动机器人系统协同控制与优化、离散型智能制造系统建模和仿真、生产管控决策优化。hezhou@sust.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(62373234)

Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery

Jianqiang LI, Zhou HE()   

  1. College of Electrical and Control Engineering,Shaanxi University of Science and Technology,Xi’an Shaanxi 710021,China
  • Received:2023-11-06 Revised:2024-01-10 Accepted:2024-01-12 Online:2024-04-22 Published:2024-04-10
  • Contact: Zhou HE
  • About author:LI Jianqiang, born in 1998, M. S. candidate. His research interests include vehicle path planning, combinatorial optimization.
    HE Zhou, born in 1990, Ph. D., associate professor. His research interests include cooperative control and optimization of multiple mobile robot system, modeling and simulation of discrete intelligent manufacturing system, optimization of production management and control decision making.
  • Supported by:
    National Natural Science Foundation of China(62373234)

摘要:

针对多行程取送货车辆路径问题(VRP)收敛性与多样性相互制约的问题,提出一种融合自适应大邻域搜索(ALNS)算法和自适应邻域选择(ANS)的混合快速非支配排序遗传算法(NSGA-Ⅱ-ALNS-ANS)。首先,考虑初始解对算法收敛速度的影响,提出一种改进的后悔插入法以获得高质量初始解;其次,结合取送货问题特性,设计多组破坏和修复算子,以及多种邻域结构,提高算法的全局搜索能力和局部搜索能力;最后,设计基于随机采样的最佳拟合下降(BFD)算法与高效的可行解评价标准,生成路径分配方案。采用不同规模的标准公开算例进行仿真实验,与模因算法(MA)相比,所提算法的最优解质量提升了27%。实验结果表明,所提算法可快速得到满足多重约束的高质量车辆多行程路径分配方案,并在收敛性与多样性上优于对比算法。

关键词: 路径规划, 车辆路径问题, 取送货, 多行程, 多目标优化, NSGA-Ⅱ

Abstract:

Concerning the trade-off between convergence and diversity in solving the multi-trip pickup and delivery Vehicle Routing Problem (VRP), a hybrid Non-dominated Sorting Genetic Algorithm Ⅱ (NSGA-Ⅱ) combining Adaptive Large Neighborhood Search (ALNS) algorithm and Adaptive Neighborhood Selection (ANS), called NSGA-Ⅱ-ALNS-ANS, was proposed. Firstly, considering the influence of the initial population on the convergence speed of the algorithm, an improved regret insertion method was employed to obtain high-quality initial population. Secondly, to improve global and local search capabilities of the algorithm, various destroy-repair operators and neighborhood structures were designed, according to the characteristics of the pickup and delivery problem. Finally, a Best Fit Decreasing (BFD) algorithm based on random sampling and an efficient feasible solution evaluation criterion were proposed to generate vehicle routing schemes. The simulation experiments were conducted on public benchmark instances of different scales, in the comparison experiments with the MA (Memetic Algorithm), the optimal solution quality of the proposed algorithm increased by 27%. The experimental results show that the proposed algorithm can rapidly generate high-quality vehicle routing schemes that satisfy multiple constraints, and outperform the existing algorithms in terms of both convergence and diversity.

Key words: path planning, Vehicle Routing Problem (VRP), pickup and delivery, multi-trip, multi-objective optimization, NSGA-Ⅱ (Non-dominated Sorting Genetic Algorithm Ⅱ)

中图分类号: