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

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.


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


Full Text: DOI


[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.