求解车辆路径问题的一种混合方法

摘要

提出一种求解带软时间窗车辆路径问题的混合算法.采用蚁群系统算法产生阶段最优解,以此作为粒子模板,随机生成粒子群,利用粒子群算法在阶段最优解基础上进一步优化.且在蚁群系统算法中,当容量超过限制后,从剩余的客户里选择需求量最大的作为新的起点继续探索路径,直到所有客户都被访问一遍.实验表明,该混合算法是解决带软时间窗车辆路径问题的一个有效算法.%A modified Particle Swarm Optimization(PSO) algorithm is adopted to deal with Vehicle Routing Problem with Time Win-dows(VRPTW). Ant Colony System(ACS) algorithm is adopted to produce a stage solution as a template. PSO algorithm is used to optimize the template. And in the ACS, ant chooses client that unvisited and capacity is ultimate as start, when capacity is overrunned. From the test results, it shows that this algorithm is effective and practicable.