一种改进粒子群优化算法在车辆路径问题的应用研究  

Research on application of vehicle routing problem usingan enhanced particle swarm optimization

作　　者：文展[1] 唐康健 李文藻[1] WEN Zhan;TANG Kangjian;LI Wenzao(School of Communication Engineering,Chengdu University of Information Technology,Chengdu 610225,P.R.China)

机构地区：[1]成都信息工程大学通信工程学院,成都610225

出　　处：《重庆邮电大学学报（自然科学版）》2020年第5期891-897,共7页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

基　　金：四川省重大科技专项(2019ZDZX0005)。

摘　　要：基于集合的粒子群优化算法(set-based particle swarm optimization,S-PSO)主要用于解决离散域的组合优化问题。但S-PSO只考虑了当前粒子的最优对速度更新的影响,易陷入局部最优解。提出ES-PSO(enhanced S-PSO)算法,重新设计速度更新策略。在速度更新策略中加入了全局最优和邻域最优的影响,同时,修改权重系数,使粒子在更新时优先考虑服务时间较早的粒子,更加合理地安排了节点的服务顺序。使用ES-PSO算法求解带时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW),提出了ES-PSO-VRPTW算法。实验结果表明,基于Solomon数据集,ES-PSO-VRPTW算法在最优路径数目(number of vehicle-route,NV)和总里程(total distance,TD)上的表现比S-PSO-VRPTW更加优越。将ES-PSO-VRPTW用于求解带时间窗的垃圾回收车辆运输问题,得到的路径数目NV和总里程TD相对于S-PSO-VRPTW以及传统的遗传算法(genetic algorithm,GA)和蚁群算法(ant colony optimization,ACO)均有大幅度降低。Set-based particle swarm optimization(S-PSO)is mainly used to solve the combinatorial optimization problem in discrete domain.Since S-PSO only considers the influence of the current particle optimum on the velocity update,it is easy to fall into the local optimal solution.In this paper,we proposed ES-PSO(Enhanced S-PSO)algorithm to redesign speed updating strategy.In new strategy,the influence of global optimization and neighborhood optimization are considered.Furthermore,weight coefficients are modified to update particles with earlier service time.As a result,the service order for nodes is better arranged.ES-PSO algorithm is used to solve Vehicle Routing Problem with Time Windows,and ES-PSO-VRPTW Algorithm is proposed.Based on Solomon data set,the experimental results show that ES-PSO-VRPTW outperforms S-PSO-VRPTW in NV(number of vehicle-route)and TD(Total Distance).We use ES-PSO-VRPTW to solve the problem of urban garbage vehicle transportation with time window.The experimental results NV and TD are both reduced significantly compared with the results of S-PSO-VRPTW,GA and ACO.

关 键 词：粒子群优化算法 时间窗 车辆路径优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]