求解1-PDTSP问题的改进蚁群系统

An Improved Ant Colony System for Solving1-PDTSP

摘要

摘要:提出了一种解决同类商品集送一体化旅行商问题(1-PDTSP)的改进蚁群系统.首先,根据1-PDTSP问题的特点,对蚁群系统中的信息素初始化和更新规则进行了改进,并采用“最优替换原则”解决停止现象; 然后,设计了有载重约束的变量邻域搜索算法,以提高解的质量和加快收敛速度; 最后,通过实例验证该算法在求解1-PDTSP问题时的求解质量和稳定性.结果表明:该算法求解质量高,稳定性好

Abstract:An improved ant colony system optimization algorithm is proposed to solve One-Commodity Pickup-and-Delivery Traveling Salesman Problem. Firstly, the initializing method and updating rules of pheromone in ACS are improved according to the characteristic of 1-PDTSP; next, the stop phenomenon is solved by adopting the principle of “current optimal replacement”; straight after, to improve the solution quality and accelerate the convergence speed of algorithm, a variable neighborhood search algorithm with the capacity constraint is designed. And eventually, the experimental results indicate the improved ant colony system boasts its high precision and nice stability in solving 1-PDTSP