带容量约束车辆路由问题的改进蚁群算法  

Improved ant colony algorithm for capacitated vehicle routing problems

作　　者：王沛栋[1,2] 唐功友[1] 李扬[1] 

机构地区：[1]中国海洋大学信息科学与工程学院,山东青岛266100 [2]青岛市产品质量监督检验所,山东青岛266101

出　　处：《控制与决策》2012年第11期1633-1638,1643,共7页Control and Decision

基　　金：国家自然科学基金项目(61074092);山东省自然科学基金项目(ZR2010FM019);山东省科技发展计划项目(2008GGB01192)

摘　　要：提出一种带容量约束车辆路由问题(CVRPs)的改进蚁群算法.该算法使用一种新的蚂蚁位置初始化方式,增加了蚂蚁走出最优路径的可能性.在搜索过程中,以客户之间路径的节省量作为启发式信息.信息素更新采用一种动态更新的方法,能够根据当前车辆所构建路径的情况对信息素进行更新,避免算法陷入停滞状态.局部搜索除使用2-opt方法外,针对不同车辆访问的客户,还增加了交换搜索和插入搜索以扩大搜索范围.仿真实验验证了所提出算法的有效性.An improved ant colony algorithm is proposed for capacitated vehicle routing problems（CVRPs）.A new initialization of vehicle’s position with an optimal and random selection increases the possibility of obtaining the optimal path.In the process of searching,the ants are more sensitive to the optimal path,because the saving path among customers is chosen as the heuristic information.The method of local and global dynamic phenomenon update is used in order to adjust the distribution of phenomenon according to vehicle routes.Except the method of 2-opt,insertion and exchange search methods are also used to expand the scope of the search for the clients on different vehicle visits.The simulation results show the effectiveness of the proposed algorithm.

关 键 词：车辆路由 路径规划 蚁群算法 带容量约束车辆路由问题 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]