基于混合粒子群算法的多目标车辆路径研究  

Hybrid particle swarm optimization for vehicle routing problem with multiple objectives

作　　者：徐杰[1] 黄德先[1] 

机构地区：[1]清华大学自动化系,北京100084

出　　处：《计算机集成制造系统》2007年第3期573-579,584,共8页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(60574072)~~

摘　　要：为解决多目标下带时间窗车辆路径的优化问题,提出了将粒子群算法与变异操作相结合的求解方式。设计了一个随迭代次数增加而变化的变异算子,采用轮盘选择机制,以使多目标离散问题能收敛到Pareto最优解集,并在Pareto曲线上有均匀的分布。采用随机键,将连续的粒子位置向量转化为离散的解向量,并通过提出相对最短距离法来评价解集的优劣。所提出的无间隔编码方式,减少了算法的无效迭代。通过实验,验证了该方法的简单有效性。In order to solve the Vehicle Routing Problem with Time Windows （VRPTW） with multiple objectives, a solution was proposed by combining Particle Swarm Optimization （PSO） with mutation operator. In the solution, with the help of roulette-wheel selection and mutation operator, the discrete problem with multiple objectives could be converged to optimal Pareto set and equally distributed along Pareto curve. The random key was adopted to change from continuous particle position vectors to discrete solution vectors. And the method of relatively minimum distance was proposed to evaluate the Pareto muster. In addition, no-interval coding method was put forward to reduce invalid iteration. Result of the experiments showed that the algorithm was simple and effective.

关 键 词：车辆路径问题 粒子群优化算法 多目标 PARETO最优集 

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