Computer Engineering and Applications ›› 2024, Vol. 60 ›› Issue (11): 309-318.DOI: 10.3778/j.issn.1002-8331.2306-0383

• Engineering and Applications • Previous Articles     Next Articles

Hybrid Multiple-Objective Grey Wolf Algorithm Solving Multi-Objective Vehicle Routing Problem with Time Windows

CHEN Kai, GONG Yiguang   

  1. School of Automation, Nanjing University of Information Science & Technology, Nanjing 210044, China
  • Online:2024-06-01 Published:2024-05-31

混合多目标灰狼算法求解多目标VRPTW问题

陈凯,龚毅光   

  1. 南京信息工程大学 自动化学院,南京 210044

Abstract: A multi-objective vehicle routing optimization model is established to minimize total cost and equilibrium degree for multi-objective vehicle routing problem with time windows, and a hybrid multi-objective grey wolf algorithm is proposed to solve the problem. Mainly design three strategies: (1) A new encoding and decoding method is designed to achieve the conversion of continuous grey wolf position vectors to discrete customer sequences. (2) Convergence and distribution indicators are used to select decision individuals. (3) Multiple deletion and insertion operators have been designed to implement local routing optimization. To demonstrate the effectiveness of the algorithm, some numerical examples in Solomon are used as examples to experimentally compare the proposed algorithm with MOIGA and improved ACO algorithms. Experimental results show that the hybrid multi-objective grey wolf algorithm proposed in this paper can find a better Pareto solution, and its performance is better than other evolutionary algorithm.

Key words: multi-objective optimization, vehicle routing problem, grey wolf algorithm, time window

摘要: 针对带时间窗的多目标车辆路径规划问题,建立了最小化总成本和均衡度的多目标车辆路径优化模型,并提出了一种混合多目标灰狼算法进行求解。主要设计3点策略:(1)设计新的编码解码方式实现连续灰狼位置向量向离散客户序列的转化。(2)采用收敛性指标和分布性指标来进行决策个体的选择。(3)设计了多种删除、插入算子实施局部路径优化。为说明算法的有效性,以Solomon中的部分算例为例,将该算法与MOIGA和改进的ACO算法进行实验对比。实验结果表明,所提出的混合多目标灰狼算法能找到更好的Pareto解,并且性能优于其他进化算法。

关键词: 多目标优化, 车辆路径规划问题, 灰狼算法, 时间窗