计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (19): 221-229.DOI: 10.3778/j.issn.1002-8331.1803-0155

• 工程与应用 • 上一篇    下一篇

混合粒子群算法求解带软时间窗的VRPSPD问题

范厚明1,2,刘文琪1,徐振林1,耿  静1   

  1. 1.大连海事大学 交通运输工程学院,辽宁 大连  116026
    2.大连海事大学 战略与系统规划研究所,辽宁 大连  116026
  • 出版日期:2018-10-01 发布日期:2018-10-19

Hybrid particle swarm optimization for solving VRPSPD problems with soft time windows

FAN Houming1,2, LIU Wenqi1, XU Zhenlin1, GENG Jing1   

  1. 1.School of Transportation Engineering, Dalian Maritime University, Dalian, Liaoning 116026, China
    2.Institute of Strategy Management and System Planning, Dalian Maritime University, Dalian, Liaoning 116026, China
  • Online:2018-10-01 Published:2018-10-19

摘要: 针对带软时间窗的同时集配货车辆路径问题(VRPSPD),建立了以车辆派遣成本、行驶成本和时间窗惩罚成本之和最小为目标的车辆路径优化模型;设计混合粒子群算法进行求解,该算法结合以变邻域下降搜索为主体的适应性扰动机制,采用适应性选择邻域策略,并在每个邻域搜索中应用可变的循环次数,以此提高对解空间的探测能力和搜索效率。数值实验结果表明了该算法的可行性和有效性。

关键词: 软时间窗, 同时集配货车辆路径, 粒子群算法, 变邻域下降搜索

Abstract: In order to solve the Vehicle Routing Problem with Simultaneous Pickup and Delivery(VRPSPD) with soft windows, a optimization model is developed for minimizing the total cost, which includes the vehicle dispatching cost, driving cost and penalty for time window. The hybrid particle swarm optimization algorithm is proposed to solve this problem, the algorithm is combined with variable neighborhood down search as the main body of the adaptive disturbance mechanism, using adaptive neighborhood strategy choice, and applying a variable number of cycles in each neighborhood search to improve the detection capability and search efficiency of the solution space. The Adaptive Perturbation Mechanism, which is based on the descending search of variable neighborhoods, adapts to the selection of neighborhood strategy and applies a variable number of cycles in each neighborhood search to improve the detection capability and search efficiency of the solution space. Numerical experiments show that the algorithm is feasible and effective.

Key words: soft time window, vehicle routing problem with simultaneous pickup and delivery, particle swarm optimization, variable neighborhood descent