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

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

作　　者：秦家娇 张勇[2] 毛剑琳[1] 付丽霞[1] 

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650500 [2]昆明理工大学津桥学院,昆明650106

出　　处：《计算机应用研究》2012年第4期1253-1255,共3页Application Research of Computers

基　　金：云南省应用基础研究基金资助项目(2009ZC050M);云南省教育厅科学研究基金资助项目(08Y0093)

摘　　要：带时间窗车辆调度问题属于离散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.

关 键 词：带时间窗车辆调度问题 粒子碰撞 离散粒子群算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]