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

Distributed multiagent-based ant colony algorithm for vehicle routing problem with time windows

作　　者：金淳[1] 张雨 王聪 Jin Chun;Zhang Yu;Wang Cong(Institute of Systems Engineering,Dalian University of Technology,Dalian Liaoning 116024,China)

机构地区：[1]大连理工大学系统工程研究所,辽宁大连116024

出　　处：《计算机应用研究》2018年第3期666-670,共5页Application Research of Computers

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

摘　　要：针对带时间窗车辆路径问题(VRPTW)算法在求解效率、求解复杂度、求解大规模问题方面存在的不足,提出一种改进的分布式多agent蚁群算法,以提高算法精度和速度为研究目的。本算法在传统蚁群算法的基础上,为提高算法精度,改进了状态转移规则,结合了邻域搜索算法;为提高算法速度,将本算法设计为分布式结构,利用多分布式agent系统实现了分布式求解VRPTW问题。针对国际标准算例设计了四个实验,结果表明,本算法在精度、速度、可靠性以及求解大规模问题方面具有明显优势。本研究为有效求解大规模、复杂VRPTW问题提供了一种新思路和可行的方法。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 traditio-nal 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 large-scale problems.This research provides a new idea and a feasible method for solving large-scale and complex VRPTW problems.

关 键 词：带时间窗车辆路径问题 蚁群算法 分布式算法 代理 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]