摘要
该文研究带时间窗约束的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),这是一个典型的NP-Hard问题。针对传统粒子群算法求解带时间窗约束的车辆路径问题容易陷入局部最优的缺陷,提出了一种基于多策略方法改进的粒子群算法(Multi-Strategy improved particle Swarm Optimization Algorithm,MSPSO)来解决该问题。该算法采用惯性权重递减策略,使得算法在前期的全局搜索和后期的局部搜索都能够有良好的表现,通过引入随机选择策略更新粒子最优位置,可以增加解空间的多样性,有效避免算法陷入局部最优。最后通过测试Solomon Benchmark算例的结果,在25个客户的C103数据集上MSPSO算法对比RWPSO算法的行驶距离降低了38.29,对比S-PSO算法在C103、R103这两个数据集与最优解误差分别降低了1.76%和3.99%。在50个客户C1系列数据集上MSPSO算法对比PSO算法行驶距离分别减少了14.26、45.66、67.7,与数据集的最优解误差基本能保持在1%以内。从实验结果可以证明MSPSO算法在求解VRPTW问题方面具有优越性和有效性。
We study the Vehicle Routing Problem with Time Windows(VRPTW),which is a typical NP-Hard problem.Aiming at the defect that traditional particle swarm optimization algorithm is easy to fall into local optimization when solving vehicle routing problems with time window constraints,a Multi-Strategy improved particle Swarm Optimization Algorithm(MSPSO) is proposed to solve the problem.This algorithm adopts the inertia weight reduction strategy,which makes it perform well in both global search in the early stage and local search in the late stage.By introducing random selection strategy to update the optimal position of particles,the diversity of solution space can be increased,and the algorithm can effectively avoid falling into local optimal.The performance of MSPSO was tested using the Solomon Benchmark dataset.For the C103 dataset with 25 customers,MSPSO demonstrated a reduction in travel distance by 38.29 compared to the RWPSO algorithm,and a decrease in error against the optimal solution by 1.76% and 3.99% for the C103 and R103 datasets respectively,compared to the S-PSO algorithm.On the C1 series dataset with 50 customers,MSPSO reduced the travel distance by 14.26,45.66,and 67.7 compared to the PSO algorithm,maintaining the error within 1% of the optimal solution.The experimental results prove the superiority and effectiveness of the MSPSO algorithm in solving the VRPTW problem.
作者
谢谢
周欢
杨裕霖
XIE Xie;ZHOU Huan;YANG Yu-lin(Key Laboratory of Manufacturing Industrial and Integrated Automation,Shenyang University,Shenyang 110044,China;School of Information Engineering,Shenyang University,Shenyang 110044,China)
出处
《计算机技术与发展》
2024年第11期186-192,共7页
Computer Technology and Development
基金
国家自然科学基金(71672117)。
关键词
车辆路径问题
粒子群算法
多策略改进
时间窗
组合优化问题
vehicle routing problem
particle swarm optimization
multi-strategy improvement
time windows
combination optimizationproblem
