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

Hybrid particle swarm algorithm for vehicle routing problems with time windows

作　　者：吴钧皓 戚远航 罗浩宇 钟日雄 柯炳明 WU Junhao;QI Yuanhang;LUO Haoyu;ZHONG Rixiong;KE Bingming(School of Automation,Guangdong University of Technology,Guangzhou 510006,China;School of Computer Science,University of Electronic Science and Technology of China,Zhongshan Institute,Zhongshan 528402,China;Engineering Department of Guangzhou Depot,Guangshen Railway Company Limited,Guangzhou 510000,China;School of Physics and Optoelectronic Engineering,Shenzhen University,Shenzhen 518060,China)

机构地区：[1]广东工业大学自动化学院,广东广州510006 [2]电子科技大学中山学院计算机学院,广东中山528402 [3]广深铁路股份有限公司广州车辆段技术科,广东广州510000 [4]深圳大学物理与光电工程学院,广东深圳518060

出　　处：《电子设计工程》2024年第6期21-26,共6页Electronic Design Engineering

基　　金：广东省普通高校重点领域专项(2020ZDZX3030,2022ZDZX1045);中山市社会公益与基础研究项目(2021B2063);广州市市场监督管理局科技项目(2022kj24)。

摘　　要：针对带时间窗的车辆路径问题(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.

关 键 词：车辆路径问题 时间窗 混合粒子群优化算法 组合优化问题 

分 类 号：TN-9[电子电信]