摘要
以著名的车辆路径问题为研究对象,提出了一种基于自适应环交换的ACO&CT混合算法。为了提高蚁群优化算法的搜索能力,将蚁群优化算法的构解机制与环交换的同时移动多个点的邻域结构结合起来。解的改进采用自适应环交换邻域的搜索算法,即当一种长度类型的环交换不能再改进目标函数时,自动转向其它长度类型的环交换开始进行新的搜索。同时针对环交换的大规模邻域,针对问题特征,提出算法加速策略。实验结果证明了基于自适应环交换的混合算法(ACO&CT)在求解车辆路径问题时的有效性。
For the well-known vehicle routing problem,a hybrid algorithm,namely,ACO&CT based on adaptive cyclic transfer is proposed.In order to improve the diversification search ability of ant colony optimization(ACO)algorithm,the main feature of the ACO&CT algorithm is to hybridize the solution construction mechanism of the ACO algorithm with multi-exchange neighborhood structure of cyclic transfer(CT)algorithm.During implementing the hybrid algorithm,the adaptive cyclic transfer algorithm can also be embedded into the ACO algorithm to improve solutions.That is,when a length type of cyclic transfers cannot be modified to improve the objective function,it is automatically switched to another type of the cycle length to start a new search.Despite the size of the cyclic transfer neighborhood is very large,an acceleration strategy is adopted according to the characteristics of the problem.Experimental results have proven that the proposed hybrid algorithm(ACO&CT)is effective for solving the vehicle routing problem.
作者
张晓霞
陈虹羊
沈鑫
杨丹
ZHANG Xiaoxia;CHEN hongyang;SHEN Xin;YANG Dan(School of Software Engineering,University of Science and Technology Liaoning,Anshan 114051,China)
出处
《辽宁科技大学学报》
CAS
2018年第5期381-388,394,共9页
Journal of University of Science and Technology Liaoning
基金
辽宁省自然科学基金(20170540471)
辽宁省教育厅项目(L2015265)
关键词
车辆路径问题
蚁群算法
自适应环交换
动态规划
vehicle routing problem
ant colony optimization
adaptive cyclic transfer
dynamic programming,hybrid algorithm