计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (27): 27-30.

• 博士论坛 • 上一篇    下一篇

带时间窗的多车场车辆路径优化的粒子群算法

王铁君1,邬开俊2   

  1. 1.西北民族大学 数学与计算机科学学院,兰州 730030
    2.兰州交通大学 电子与信息工程学院,兰州 730070
  • 出版日期:2012-09-21 发布日期:2012-09-24

Study on multi-depot vehicle routing problem with time windows based on Particle Swarm Optimization

WANG Tiejun1, WU Kaijun2   

  1. 1.School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China
    2.School of Electronic and Information Engineering, Lanzhou Jiaotong Unversity, Lanzhou 730070, China
  • Online:2012-09-21 Published:2012-09-24

摘要: 带时间窗的多车场车辆路径问题在基本车辆路径问题的基础上增加了“多车场”与“时间窗”两个约束条件,是一个典型的NP难解问题。将粒子群算法应用于带时间窗的多车场车辆路径优化问题,构造了一种适用于求解车辆路径问题的粒子编码方法,建立了相应的数学模型,在此基础上设计了相应的算法。算例通过和遗传算法、蚁群算法进行比较,证明了其搜索速度和寻优能力的优越性。

关键词: 时间窗, 多车场, 车辆路径优化, 粒子群算法

Abstract: Multi-depot vehicle routing problem with time windows is a variation of the vehicle routing problem constrained by multi-depot and time windows, which is a typical NP-hard problem. Particle swarm optimization with a particle coding method is designed to solve the problem. The mathematic mode is established and the solution algorithm is developed. The simulation results of example indicate that the algorithm has faster search speed and stronger optimization ability than the GA and ACO.

Key words: time windows, multi-depot, vehicle routing problem, Particle Swarm Optimization(PSO)