基于粒子碰撞的粒子群算法求解带时间窗车辆调度问题*

带时间窗车辆调度问题属于离散NP-hard组合优化问题,传统的粒子群算法在离散域上表现了一定的劣性,对此提出了一种基于粒子碰撞的离散PSO算法来求解该问题。受物体相互碰撞之后物体的速度和位置会发生改变的现象启发,使当前粒子与个体最优和全局最优粒子发生碰撞来更新粒子的位置,以避免传统更新操作中的取整,保证种群的进化能力。采用Solomon’s VRP标准问题集的实例来对算法进行测试,实验结果数据表明了该算法的有效性。

Based on particles collision PSO for vehicle routing problem with time windows

The vehicle routing problem with time windows(VRPTW) is the NP-hard combinatorial optimization discrete problem.There was certain inferiority performance on solving it with traditional PSO,so this paper proposed a particles collision discrete PSO to solve it.Inspired by the physical phenomena of the velocity and position changed after objects collision,it made the current particle collided with the personal best particle and global best particle to avoid the tradition rounding operating in updating,and kept particles swarm evolutional capability.It used the Solomon’s VRP instance to test.The results of experiments show that the algorithm has good performance.