基于改进蚁群算法的CVRP问题
|
摘要
为了能够更好地求解CVRP问题,对蚁群算法进行了一定程度的改进。改进后的算法更加科学地初始化蚂蚁的位置,使蚂蚁有更大可能性地寻找到最优路径。在搜索的过程中与禁忌搜索算法结合,添加新的参数负信息素来记忆已经访问过的客户。同时,使用局部信息素更新和全局信息素更新相结合的信息素更新方式,并且全局信息素更新添加了动态更新的新模式。使用2-opt搜索对结果进行进一步的探索,扩大搜索的范围,增加了得到最优解的概率。
In order to solve the problem of CVRP better,the ant colony algorithm is improved to some extent. First,the improved algorithm more scientifically initializes the position of the ants,making the ants more likely to find the optimal path. Then,in the search process with the tabu search algorithm,add a new parameter pheromone to remember the customer has been visited. At the same time,the use of local pheromone updates and global pheromone updates are combined with pheromone updating methods,and the global pheromone update adds a new pattern of dynamic updates. Finally,using the 2-opt search to further explore the results,expand the scope of the search,increasing the probability of getting the optimal solution.
In order to solve the problem of CVRP better,the ant colony algorithm is improved to some extent. First,the improved algorithm more scientifically initializes the position of the ants,making the ants more likely to find the optimal path. Then,in the search process with the tabu search algorithm,add a new parameter pheromone to remember the customer has been visited. At the same time,the use of local pheromone updates and global pheromone updates are combined with pheromone updating methods,and the global pheromone update adds a new pattern of dynamic updates. Finally,using the 2-opt search to further explore the results,expand the scope of the search,increasing the probability of getting the optimal solution.
引文
[1]骆剑平,李霞,陈泯融.基于改进混合蛙跳算法的CVRP求解[J].电子与信息学报,2011,33(2):429-434.
[2]张瑞锋,汪同三.新型遗传算法求解车辆路径问题研究[J].湖北大学学报(自然科学版),2012,34(2):239-242.
[3]DANTZING G,RASMER J. The truck dispatching problem[J].Management Science,1959(6):80-91.
[4]陈印,徐红梅.混合算法在车辆路径优化问题中的应用[J].计算机仿真,2012,29(25):357-358.
[5]杨亚萍.基于车辆路径问题的建模及算法的研究[J].电脑开发与应用,2012,25(12):962-963.
[6]杨中秋,张延华.改进蚁群算法在交通系统最短路径问题的研究[J].科学计算与信息处理,2003,32(8):76-78.
[7]刘霞,杨超.最小-最大车辆路径问题的蚁群算法[J].解放军理工大学学报(自然科学版),2012,13(3):340-341.
[8]张思亮,葛洪伟.求解车辆路径问题的一种混合方法[J].计算机工程与应用,2012,48(8):226-227.
[9]李艳琴,张立毅,郭纯生,等.改进蚁群算法在应急VRP问题中的应用研究[J].数学的实践与认识,2012,42(9):133-140.
[10]KAJI T. Approach by ant tabu agents for traveling salesmanproblem[C]//In Proceedings of the IEEE InternationalConference on Systems,Man,and Cybernetics,2001.
[11]KARABOGA N,KALINLI A,KARABOGA D. Designingdigital IIR filters using ant colony optimisation algorithm[J].Engineering Applications of Artificial Intelligence,2004,43(17):301-309.
[12] ROUX O,FONLUPT C,TALBI E G. Technical reportLIL-98-04, laboratoired’inforniatique du littoral[D].Calais. France:University du Littoral,1998.
[13]SOEDERKVIST O. The main algorithm research onfinancialtime series data mining[D].Linkoeping:Linkoeping University of Sweden,2001.
[2]张瑞锋,汪同三.新型遗传算法求解车辆路径问题研究[J].湖北大学学报(自然科学版),2012,34(2):239-242.
[3]DANTZING G,RASMER J. The truck dispatching problem[J].Management Science,1959(6):80-91.
[4]陈印,徐红梅.混合算法在车辆路径优化问题中的应用[J].计算机仿真,2012,29(25):357-358.
[5]杨亚萍.基于车辆路径问题的建模及算法的研究[J].电脑开发与应用,2012,25(12):962-963.
[6]杨中秋,张延华.改进蚁群算法在交通系统最短路径问题的研究[J].科学计算与信息处理,2003,32(8):76-78.
[7]刘霞,杨超.最小-最大车辆路径问题的蚁群算法[J].解放军理工大学学报(自然科学版),2012,13(3):340-341.
[8]张思亮,葛洪伟.求解车辆路径问题的一种混合方法[J].计算机工程与应用,2012,48(8):226-227.
[9]李艳琴,张立毅,郭纯生,等.改进蚁群算法在应急VRP问题中的应用研究[J].数学的实践与认识,2012,42(9):133-140.
[10]KAJI T. Approach by ant tabu agents for traveling salesmanproblem[C]//In Proceedings of the IEEE InternationalConference on Systems,Man,and Cybernetics,2001.
[11]KARABOGA N,KALINLI A,KARABOGA D. Designingdigital IIR filters using ant colony optimisation algorithm[J].Engineering Applications of Artificial Intelligence,2004,43(17):301-309.
[12] ROUX O,FONLUPT C,TALBI E G. Technical reportLIL-98-04, laboratoired’inforniatique du littoral[D].Calais. France:University du Littoral,1998.
[13]SOEDERKVIST O. The main algorithm research onfinancialtime series data mining[D].Linkoeping:Linkoeping University of Sweden,2001.