Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (20): 216-223.

Previous Articles     Next Articles

Resolving vehicle routing problem with improved sweep-particle swarm optimization algorithm

LI Defu, GUO Haixiang, LIU Longhui, LI Weiwei   

  1. School of Economics and Management, China University of Geosciences, Wuhan 430074, China
  • Online:2012-07-11 Published:2012-07-10

改进型粒子群优化算法求解车辆径优化问题

李德富,郭海湘,刘龙辉,李伟伟   

  1. 中国地质大学(武汉) 经济管理学院,武汉 430074

Abstract: In order to escape local optimum for particle swarm optimization algorithm to solve the vehicle routing problem, this paper proposes a sweep-particle swarm optimization algorithm. It uses the sweep algorithm to get initial feasible solution by sweeping each mineral occurrence. The initial feasible solution is substituted as the particle’s initial position to search into particle swarm. The paper gets the particle swarm history optimal position, which is reversed transcription to the corresponding feasible solution. The vehicle routing problem of Zhengzhou Coal Electricity Material Supply and Marketing Limited Company is solved through the improved swarm optimization algorithm. The sweep-particle swarm optimization algorithm is applied to contrast with classical particle swarm optimization and genetic algorithm, and the result of emulated experiment makes clear that the sweep-particle swarm optimization algorithm is a fast and exact algorithm.

Key words: sweep algorithm, particle swarm optimization, genetic algorithm, vehicle routing problem

摘要: 为了避免粒子群算法求解车辆路径问题容易陷入局部最优,提出了扫描—粒子群算法。运用扫描算法对矿点进行扫描,生成初始可行解链,将其作为粒子的初始位置代入到粒子群中搜索,得到粒子种群历史最优位置,将种群粒子最优位置逆转录生成对应的可行解链。将改进型粒子群算法用于求解郑州煤电物资供销有限公司的车辆调度问题同时将该算法与经典的粒子群算法和遗传算法做了对比实验,仿真实验结果表明,改进型粒子群算法可以更快速、更有效求得车辆路径问题的最优解。

关键词: 扫描算法, 粒子群算法, 遗传算法, 车辆路径问题