计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (21): 230-239.DOI: 10.3778/j.issn.1002-8331.1707-0240

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

粒子群算法求解需求随机的分批配送VRP

石建力1,张  锦2   

  1. 1.西南交通大学 交通运输与物流学院,成都 610031
    2.综合交通运输智能化国家地方联合工程实验室,成都 610031
  • 出版日期:2018-11-01 发布日期:2018-10-30

Particle swarm optimization for split delivery vehicle routing problem with stochastic demands

SHI Jianli1, ZHANG Jin2   

  1. 1.School of Transprotation and Logistics, Southwest Jiaotong University, Chengdu 610031, China
    2.National United Engineering Laboratory of Integrated and Intelligent Transportation, Chengdu 610031, China
  • Online:2018-11-01 Published:2018-10-30

摘要: 对需求随机的分批配送车辆路径问题进行研究,建立带修正的随机规划模型。设计与局部搜索算法相结合的粒子群算法进行求解,算法使用整数编码和基于Bellman方程的允许分割需求的解码方法。并针对允许分批配送时导致的粒子速度、粒子自身最优位置、局部最优位置及全局最优位置等向量非零元素个数不同的问题,设计可行的统一向量长度的方法。算法在调整的Solomon算例测试集和调整的Christiansen和Lysgaard算例测试集上进行测算,测试有效参数、速度长度及速度更新方程。同时与现有结果进行对比,虽然计算效率较低,但在测试的26个算例中,有14个算例的最优解得到更新,剩余的算例最优解与现有最优解相差小于1%。

关键词: 随机需求, 分批配送, 车辆路径问题, 粒子群算法

Abstract: This paper concerns on the split delivery vehicle routing problem with stochastic demands. A stochastic program with recourse is formulated. An PSO based heuristic combined with local search is proposed, in which an integer code method and an decoding method based on the Bellman’s equation is presented. This paper also proposes several ways to deal with the difference between the number of the nonzero elements in the vectors including the velocity, the personal best position, the local best position and the global best position. Extensive experiments are carried on the modified Solomon test instance set and the modified Christiansen and Lysgaard test instance set, better parameters are chosen, including the size of the population, the probability of the local search and the number of iteration. The results also been compared with existing results, and 16 improved solution are obtained out of 26 test instances, with the gap between the solution of the other 10 instances and the existing best solutions less than 1%.

Key words: stochastic demands, split delivery, Vehicle Routing Problem(VRP), Particle Swarm Optimization(PSO)