联盟运输调度问题的粒子群算法研究*

Research on Particle Swarm Optimization for Allied Vehicle Routing Problems

联盟运输调度问题是在基本运输调度问题基础上所发展起来的、具有重要实用价值的一类组合优化难题。粒子群算法(PSO)是一种新兴的基于群智能的演化计算技术,该算法与传统方法相比有着较高的收敛速度和计算精度,可以在解空间内高效地寻找到全局最优解。将其应用于联盟运输调度问题,并针对联盟运输调度问题中最优解的分布特点,对标准粒子群算法进行了改进,克服了标准粒子群算法收敛速度过快且易收敛于局部最优的缺点。对比实验结果表明,改进后的粒子群算法可以快速、有效求得最优解。

The allied vehicle routing problem （AVRP） is a kind of combinatorial optimization problem with important practical value, which developed from the basic vehicle routing problem （VRP）.Particle swarm optimization （PSO） is a newly rising evolution- ary computation technique based on swarm intelligence,PSO possesses the better convergent speed and computational precision compares with the traditional algorithms,it can effectively search out the global optimal solution in the space of solution.The standard PSO is improved in this paper to solve the AVRP by contraposed the distribution attribute of AVRP＇s optimal solutions,which overcomes the shortcomings of the standard PSO quickly and easily constringe local optimal solu- tion.The experimental results of comparison indicate that the improved algorithm of PSO can quickly and effectively get optimal solution to the allied vehicle routing problems.