最小最大车辆路径问题的动态自适应蚁群优化算法  

Dynamic Adaptive Ant Colony Optimization Algorithm for Min-Max Vehicle Routing Problem

作　　者：葛斌[1,2] 韩江洪[1] 魏臻 程磊 韩越[2] 

机构地区：[1]合肥工业大学计算机与信息学院 [2]安徽理工大学计算机科学与工程学院 [3]合肥工大高科信息科技股份有限公司

出　　处：《模式识别与人工智能》2015年第10期930-938,共9页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.61070220);安徽省自然科学基金项目(No.1408085ME110);安徽省高等学校省级自然科学研究重大项目(No.KJ2013ZD09)资助

摘　　要：为求解最小最大车辆路径问题,提出动态自适应蚁群优化算法.该算法采用动态最大最小蚂蚁系统策略调整最优解,每次迭代更新τmin,将τmin作为当前信息素矩阵最大值的函数,根据当前最优弧调整选择弧的概率.采用一种灰色模型预测及控制信息素矩阵的边界,以增强蚁群算法参数的自适应性能.对信息素浓度相对较高的多个节点及其附近的边,利用信息素关联累积规则进行信息素更新.将文中算法进行场景的实例测试,仿真结果表明,该算法与线性规划、其他相关的蚁群算法相比,收敛速度更快,具有更好的优化性能和应用效果.To solve the min-max vehicle routing problem （MMVRP）, a dynamic adaptive ant colony optimization algorithm is proposed. The dynamic max-min ant system is adopted to adjust the optimal solution. τmin is updated per iteration, it is regarded as the function of maximum in the pheromone matrix, and the probability of selecting arc is adjusted according to the optimal arc. A kind of gray model is employed to forecast and control the boundary of pheromone matrix to enhance the self-adaption of parameters in ant colony algorithm. Advantage of pheromone associated with accumulation rules is taken to update multiple nodes with relatively high concentration of pheromone and edges nearby. The proposed algorithm is tested on examples. The simulation results show that compared with linear programming algorithm and other related ant colony algorithms, the proposed algorithm has a higher convergence speed and better optimization performance and applicability.

关 键 词：动态最大最小蚂蚁系统 最小最大车辆路径问题 灰色模型预测 信息素关联累积 车辆距离约束 

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