An improved ant colony optimization for vehicle routing problem. (English) Zbl 1156.90434

Yu, Bin; Yang, Zhong-Zhen; Yao, Baozhen

Eur. J. Oper. Res. 196, No. 1, 171-176 (2009).

Summary: The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. This paper proposes an improved ant colony optimization (IACO), which possesses a new strategy to update the increased pheromone, called ant-weight strategy, and a mutation operation, to solve VRP. The computational results for fourteen benchmark problems are reported and compared to those of other metaheuristic approaches.

MSC:

90C27	Combinatorial optimization
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

vehicle routing problem; improved ant colony optimization; ant-weight strategy; mutation operation

Software:

OR-Library

References:

[1]	Baker, B. M.; Ayechew, M. A., A genetic algorithm for the vehicle routing problem, Computers & Operations Research, 30, 787-800 (2003) · Zbl 1026.90013
[2]	Beasley, J. E., OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990)
[3]	Bell, J. E.; McMullen, P. R., Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics, 1, 8, 41-48 (2004)
[4]	Brandao, J.; Mercer, A., A tabu search algorithm for the multi-trip vehicle routing and scheduling problem, European Journal of Operational Research, 100, 180-191 (1997) · Zbl 0947.90578
[6]	Bullnheimer, B.; Hartl, R. F.; Strauss, C., An improved ant system algorithm for the vehicle routing problem, Annals of Operations Research, 89, 319-328 (1999) · Zbl 0937.90125
[7]	Chen, C. H.; Ting, C. J., An improved ant colony system algorithm for the vehicle routing problem, Journal of the Chinese Institute of Industrial Engineers, 23, 2, 115-126 (2006)
[8]	Chiang, W. C.; Russell, R., Simulated annealing meta-heuristics for the vehicle routing problem with time windows, Annals of Operations Research, 93, 3-27 (1996) · Zbl 0849.90054
[9]	Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job-shop scheduling, Jorbel-Belgian Journal of Operations Research Statistics and Computer Science, 34, 1, 39-53 (1994) · Zbl 0814.90047
[10]	Doerner, K. F.; Gronalt, M.; Hartl, R. F.; Reimann, M.; Strauss, C.; Stummer, M., Savings ants for the vehicle routing problem. Savings ants for the vehicle routing problem, Applications of Evolutionary Computing (2002), Springer: Springer Berlin
[13]	Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Mans, and Cybernetics, 1, 26, 29-41 (1996)
[15]	Gendreau, M.; Laporte, G.; Musaraganyi, C.; Taillard, E. D., A tabu search heuristic for the heterogeneous fleet vehicle routing problem, Computers & Operations Research, 26, 1153-1173 (1999) · Zbl 0967.90019
[16]	Koulamas, C.; Antony, S.; Jaen, R., A survey of simulated annealing applications to operations research problems, Omega, 22, 1, 41-56 (1994)
[17]	Mazzeo, S.; Loiseau, I., An ant colony algorithm for the capacitated vehicle routing, Electronic Notes in Discrete Mathematics, 18, 181-186 (2004) · Zbl 1075.90568
[18]	Osman, I. H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41, 421-451 (1993) · Zbl 0775.90153
[19]	Osman, M. S.; Abo-Sinna, M. A.; Mousa, A. A., An effective genetic algorithm approach to multiobjective routing problems (morps), Applied Mathematics and Computation, 163, 769-781 (2005) · Zbl 1060.65606
[21]	Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & Operations Research, 31, 1985-2002 (2004) · Zbl 1100.90504
[22]	Reimann, M.; Stummer, M.; Doerner, K., A savings based ant system for the vehicle routing problem, (Langdon, W. B.; etal., GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference (2002), Morgan Kaufmann: Morgan Kaufmann San Francisco)
[23]	Renaud, J.; Laporte, G.; Boctor, F. F., A tabu search heuristic for the multi-depot vehicle routing problem, Computers & Operations Research, 23, 3, 229-235 (1996) · Zbl 0855.90055
[24]	Rochat, Y.; Taillard, R. E., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 147-167 (1995) · Zbl 0857.90032
[25]	Schoonderwoerd, R.; Holland, O.; Bruten, J.; Rothkrantz, L., Ant-based load balancing in telecommunications networks, Adaptive Behavior, 5, 2, 169-207 (1997)
[26]	Semet, F.; Taillard, E. D., Solving real-life vehicle routing problems efficiently using taboo search, Annals of Operations Research, 41, 469-488 (1993) · Zbl 0775.90156
[27]	Taillard, R. E., Parallel iterative search methods for vehicle routing problems, Networks, 23, 661-673 (1993) · Zbl 0804.90045
[28]	Tavakkoli-Moghaddam, R.; Safaei, N.; Gholipour, Y., A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length, Applied Mathematics and Computation, 176, 445-454 (2006) · Zbl 1149.90312
[30]	Yang, Z. Z.; Yu, B.; Cheng, C. T., A parallel ant colony algorithm for bus network optimization, Computer-Aided Civil and Infrastructure Engineering, 22, 44-55 (2007)
[32]	Yu, B.; Yang, Z. Z.; Cheng, C. T., Optimizing the distribution of shopping centers with parallel genetic algorithm, Engineering Applications of Artificial Intelligence, 20, 2, 215-223 (2007)