摘要
带时间窗车辆调度问题属于离散NP-hard组合优化问题,传统的粒子群算法在离散域上表现了一定的劣性,对此提出了一种基于粒子碰撞的离散PSO算法来求解该问题。受物体相互碰撞之后物体的速度和位置会发生改变的现象启发,使当前粒子与个体最优和全局最优粒子发生碰撞来更新粒子的位置,以避免传统更新操作中的取整,保证种群的进化能力。采用Solomon’s VRP标准问题集的实例来对算法进行测试,实验结果数据表明了该算法的有效性。
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.
出处
《计算机应用研究》
CSCD
北大核心
2012年第4期1253-1255,共3页
Application Research of Computers
基金
云南省应用基础研究基金资助项目(2009ZC050M)
云南省教育厅科学研究基金资助项目(08Y0093)
关键词
带时间窗车辆调度问题
粒子碰撞
离散粒子群算法
vehicle routing problem with time windows(VRPTW)
particles collision
discrete PSO