改进节约蚁群算法求解物流配送车辆路径问题  

Improved Saving-based Ant System for Vehicle Routing Problems

作　　者：李聚[1] 张葛祥[1] 程吉祥[1] 

机构地区：[1]西南交通大学电气工程学院,成都610031

出　　处：《交通信息与安全》2013年第3期103-107,共5页Journal of Transport Information and Safety

基　　金：国家自然科学基金项目(批准号:61170016);教育部新世纪优秀人才支持计划项目(批准号:NCET-11-0715)及其配套项目(批准号:SWJTU12CX008)资助

摘　　要：针对节约蚁群算法在求解车辆路径问题易陷入局部极值的不足,提出一种基于连接表扰动策略和吸引力因子局部搜索的改进节约蚁群算法。该算法在陷入局部最优后,引入连接表扰动策略以帮助算法跳出局部最优,该策略在每只蚂蚁进行解构建之前,随机禁忌若干条吸引力因子较大的边以增加算法的勘探能力;同时采用吸引力因子局部搜索优化每只蚂蚁的解,该局部搜索利用吸引力因子引导局部搜索。实验结果表明,改进节约蚁群算法求解车辆路径问题时优于原有节约蚁群算法以及多种已有算法。In order to tackle the flaw that Saving-based Ant System(SbAS)algorithm is easy to fall into a local optima when solving vehicle routing problem(VRP),this paper proposes an improved Saving-based Ant System(ISbAS) algorithm on the basis of a connection list perturbation strategy and attractiveness local search.On the one hand,when the algorithm traps in a local optimum,a connection list perturbation strategy is introduced to help the algorithm jump out from the local optima.Before each ant constructs a solution,some randomly selected edges with large attractiveness are forbidden.On the other hand,by using attractiveness local search to improve each ant's solution quality,this local search uses attractiveness to guide the local search.The computational result shows that ISbAS outperforms SbAS and several other algorithms in the literature when solving VRPs.

关 键 词：车辆路径问题 节约蚁群算法 连接表扰动策略 吸引力因子局部搜索 

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