带时间窗的车辆路径问题的混合粒子群优化算法

Hybrid particle swarm algorithm for vehicle routing problems with time windows

针对带时间窗的车辆路径问题(Vehicle Routing Problems with Time Windows,VRPTW),提出了一种混合粒子群优化算法(Hybrid Particle Swarm Optimization,HPSO)进行求解。所提出的算法设计了一种高效的编解码策略,以此搭建HPSO算法解空间到VRPTW解空间的桥梁。同时为了提高算法的寻优能力,设计了由单点插入策略以及双点交换策略组成的局部搜索策略。通过solomon-50标准数据集中的九个算例进行仿真实验,实验结果证明了所提出算法的寻优能力和稳定性均优于对比算法,最优解误差相较于对比算法最多降低了38.32%。

A Hybrid Particle Swarm Optimization(HPSO)algorithm is proposed to solve the Vehicle Routing Problems with Time Windows(VRPTW).The proposed algorithm designs an efficient encoding and decoding strategy to build a bridge from the solution space of HPSO algorithm to the solution space of VRPTW.At the same time,in order to improve the optimization ability of the algorithm,a local search strategy composed of single point insertion strategy and double point exchange strategy is designed.The simulation experiments are carried out with 9 examples in the solomon-50 standard data set.The experimental results show that the proposed algorithm is superior to the comparison algorithm in terms of optimization ability and stability,and the optimal solution error is reduced by 38.32%compared with the comparison algorithm at most.