求解车辆路径问题的改进微粒群优化算法  

Modified particle swarm optimization algorithm for vehicle routing problem1

作　　者：肖健梅[1] 李军军[1] 王锡淮[1] 

机构地区：[1]上海海事大学电气自动化系,上海200135

出　　处：《计算机集成制造系统》2005年第4期577-581,共5页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(60074004);上海市教育委员会科研重点项目(04FA02)。~~

摘　　要：微粒群优化算法是求解连续函数极值的一个有效方法。研究了用该算法求解车辆路径的问题。设计了求解车辆路径问题的一种新的实数编码方案,将车辆路径问题转化成准连续优化问题,并采用罚函数法处理约束条件。应用该微粒群优化算法求解了多个车辆路径问题的算例,并与遗传算法和双种群遗传算法进行了比较。计算结果表明,该算法可以更有效地求得车辆路径问题的优化解,是解决车辆路径问题的有效方法。Particle Swarm Optimization (PSO) algorithm is a powerful method to find the extremum of a continuous numerical function. A method based on PSO was researched to solve the discrete Vehicle Routing Problem (VRP). The VRP was changed into a quasi-continuous problem by designing a new real coding. Constrained terms in VRP were processed by the penalty function. This proposed algorithm was applied to illustrate its higher searching efficiency in comparison with standard genetic algorithm & double populations genetic algorithm for VRP. Simulation results of several VRP examples demonstrated the effectiveness of this algorithm.

关 键 词：车辆路径问题 微粒群优化 实数编码 组合优化 

分 类 号：TP14[自动化与计算机技术—控制理论与控制工程]