带时间窗车辆路径问题的分布式多agent蚁群算法

摘要

Because of the disadvantage in the previous research of the vehicle routing problem with time windows (VRPTW),like limited solving efficiency,limited complexity,and difficulty to solve large-scale problems,this paper proposed a distributed multi agent ant colony algorithm which aimed at improving the accuracy and speed of the algorithm.Based on the traditional ant colony algorithm,this paper improved the state transition rule and combined the neighborhood search algorithm to improve the accuracy.At the same time,it designed the algorithm as a distributed structure to improve the speed.So,it could utilize multi agent distributed system to distributed solve the VRPTW problem.The results of four experiments which designed for the international standard show that this algorithm has obvious advantages in accuracy,speed,reliability and solving largescale problems.This research provides a new idea and a feasible method for solving large-scale and complex VRPTW problems.%针对带时间窗车辆路径问题(VRPTW)算法在求解效率、求解复杂度、求解大规模问题方面存在的不足,提出一种改进的分布式多agent蚁群算法,以提高算法精度和速度为研究目的.本算法在传统蚁群算法的基础上,为提高算法精度,改进了状态转移规则,结合了邻域搜索算法;为提高算法速度,将本算法设计为分布式结构,利用多分布式agent系统实现了分布式求解VRPTW问题.针对国际标准算例设计了四个实验,结果表明,本算法在精度、速度、可靠性以及求解大规模问题方面具有明显优势.本研究为有效求解大规模、复杂VRPTW问题提供了一种新思路和可行的方法.