求解车辆路径问题的多邻域下降搜索蚁群优化算法*

南京大学学报(自然科学版) ›› 2012, Vol. 48 ›› Issue (1): 91–98.

求解车辆路径问题的多邻域下降搜索蚁群优化算法*

张泽彬^1**，郝志峰¹，黄翰^2.3，李学强²

出版日期:2015-05-20 发布日期:2015-05-20
作者简介: (1.广东工业大学计算机学院，广州，510006;2.华南理工大学软件学院，广州，510006
3.南京大学计算机软件新技术国家重点实验室，南京，210093)
基金资助:
国家自然科学基金(61003066，61070033)教育部博士点基金(200901721200365)，中央科研业务费
(2009ZM0052)，广东省自然科学基金(251009001000005)，广东省科技计划(2010B05400011,
201013080701070,200813080701005)，广东省析学社会科学规划“十一五”规划项口(08O一01)，信息安全国家乖
点实验室开放课题基金(04一01)

Ant colony optimization algorithm for capacitated vehicle routing problem
based on multiple neighborhood descent searching

Zhang Ze-Bin¹,Hao Zhi-Feng¹,Huang Han ^2,3,Li Xue-Qiang²

Online:2015-05-20 Published:2015-05-20
About author: (1 .School of Computer, Guangdong University of Technology, Guangdong, 510006 , China;
2. School of Softwarc,South China University of Technology, Guangdong, 510006 , China;
3. Nanjing Univcrsity,Software Technology of State Key Laboratory,Nanjing, 210093,China)

摘要/Abstract

摘要： 本文提出一种结合改进蚁群优化算法和多邻域下降搜索的混合启发式算法IACO-MND,求解运力限制的车辆路径问题.利用改进的蚁群系统算法构造为一法产牛多个可行解，再将产牛的解作为多
邻域下降搜索的初始解.在搜索过程中使用三种不同的邻域结构:插人，交换和2 - opt以扩大局部搜素的范围.实验对不同规模的benchmark算例进行求解，结果表明本文算法能在较短的时间内获得若十算
例的已知最好解，求解效率高，收敛速度快，稳定性强.

Abstract: routing problem, which combines two meta-heuristics, i, e.，ant colony optimization(ACO)and multiple neighborhood descent(MND). Capacitated vehicle routing problem is a non-deterministic polynomial problem. With
the increase of the number of customers, the optional number of vehicle routing solutions will grow exponentially. Ant colony optimization is a meta-heuristics groups algorithm, and it is good at finding area may be the optimal
solution. However, multiple neighborhood descent is the locus method，and it is good at finding a better solution in the region. So, take full advantage of the two algorithms can improve the algorithm’s search efficiency and
performance. First of all，several feasible solutions arc built by an insertion based improved ACO(IACO) solution construction method，which is taken as the initial solution of the MND procedure. IACO is have some different with
ACO. In our algorithm, a distance-based greedy method is used to create a strong feasible solution.Then one heuristic based on backpack is used to create a weakly feasible solution. We also make some improvement in local
pheromone update and global pheromone update. During the MND procedure, three different neighborhood structures, i, c.，insertion, swap and 2一opt arc successively used. Computational results on the benchmark
problems with the size ranging from 20 to 100，show that the proposed hybrid algorithm can find the best known solution for some problems in a short time, which indicates that the proposed IACO一MND outperforms other
algorithms in literatures. However, we also find some problem in the experimental procedure. First one is the execution time increases significantly as the model of the increasing trend.That is because we carry out local search
in each iteration. Second one is the algorithm iterations is less，and we think that is because we can obtained the better solution after several iterations, but it will lead to we cannot make full use of the advantages of ACO. In the
further, we will further balance the advantage of the ACO and MND.

张泽彬^1**，郝志峰¹，黄翰^2.3，李学强². 求解车辆路径问题的多邻域下降搜索蚁群优化算法*
[J]. 南京大学学报(自然科学版), 2012, 48(1): 91–98.

Zhang Ze-Bin¹,Hao Zhi-Feng¹,Huang Han ^2,3,Li Xue-Qiang²
. Ant colony optimization algorithm for capacitated vehicle routing problem
based on multiple neighborhood descent searching
[J]. Journal of Nanjing University(Natural Sciences), 2012, 48(1): 91–98.

参考文献

[1]Dantizig G B, Ramser J H.The truck dispatc hing problem. Management Science，1959，6:80~91
[2]Bell J E, McMullen P R. Ant colony optimiza- tion techniques for the vehicle routing problem. Advanced Engineering informatics, 2004，1 (8):4l一48.
[3]Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle rou ting problem. Annals of Operations Research 1993，41:421一451.
[4]Tavakkoli-Moghaddam R，Safaei N，Gholipour Y. A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Compu- tation, 2006，176:445一454.
[5]Baker B M，Ayechew M A. A genetical gorithm for the vehicle routing problem. Computers and Operations Research, 2003，30:787一800.
[6]Osman M S, Abo-Sinna M A，Mousa A A. An effective genetical gorithm approach to multi ob- jective routing problems(morps).Applied Mathematics and Computation, 2005，163: 769-781
[7]Renaud J，Laporte G, Boctor F F. A tabu search heuristic for the multi-depot vehicle rou- ting problem. Computers and Operations Re- search, 1996，23(3):229一235.
[8]Brandao J，Mercer A. A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. European Journal of Operational Re search, 1997，100:180一191.
[9]Doerner K F, Gronalt M, Hartl R F, et al. Savings ants for the vehicle routing problem. Applications of Evolutionary Computing, Ber- lin; Springer, 2002.
[10]Reimann M, Stummer M，Docrncr K. A sav- ings based ant system for the vehicle routing problem. Langdon W B. Proceedings of the Ge netic and Evolutionary Computation Conference，San Francisco; Morgan Kaufmann, 2003.
[11]Mazzco S, Loiseau 1. An ant colony algorithm for the capacitated vehicle routing. Electronic Notesin Discrete Mathematics, 2004，18:181一 186.
[12]Bullnheimer B, Hartl R F, Strauss C. Applying the ant system to the vehicle routing problem. The 2^nd Metahcuristics International Confer- ence，Sophia-Antipolis, France, 1997.
[13]Bullnheimer B, Hartl R F, Strauss C. An im proved ant system algorithm for the vehicle rou ting problem. Annals of Operations Research 1999，89:319一328.
[14]Doerner K F, Hartl R F, Kiechle G, et al. Par- allclant systems for the capacitated vehicle rou- ting problem. Evolutionary Computationin Combinatorial Optimization;The 4^th European Conference，EvoCOP，2004，72一83.
[15]Chen C H，Ting C J. An improved ant colony system algorithm for the vehicle routing prob- lem. Journal of the Chinese institute of Indus- trial Engineers, 2006，23(2):115一126.
[16]Yua Y, Yanga Z Z，Yao B Z. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 2009，196:171一176.
[17]Zhang X X,Tang I. X. A new hybrid ant colo- ny optimization algorithm for the vehicle routing problem. Pattern Recognition Letters，2009，30:848一B55.
[18]Dorigo M，Maniczzo V, Colorni A. Ant sys- tem; Optimization by a colony of Cooperating a- gents, IEEE Transactions on Systems，Mans and Cybernetics, 1996026):29一41.
[19]Mladenovic N，Hansen P. Variable neighboi- hood search:Principles and applications. Euro- pean Journal of Operational Research, 2001，130(3):449一467.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed