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
[5] Bullnheimer, B., Hartl, R.F., Strauss, C., 1997. Applying the ant system to the vehicle routing problem. In: Second Metaheuristics International Conference, MIC’97, Sophia-Antipolis, France. · Zbl 0970.90019
[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, Applications of evolutionary computing, (2002), Springer Berlin
[11] Doerner, K.F., Hartl, R.F., Kiechle, G., Lucka, M., Reimann, M., 2004. Parallel ant systems for the capacitated vehicle routing problem. In: Evolutionary Computation in Combinatorial Optimization: 4th European Conference, EvoCOP 2004, LNCS 3004, pp. 72-83. · Zbl 1177.90338
[12] Dongarra, J., 2001. Performance of various computer using standard linear equations software. Report CS-89-85, University of Tennessee.
[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)
[14] Gambardella, L., Taillard, E., Dorigo, M., 1997. Ant Colonies for the QAP, Technical Report 97-4, IDSIA, Lugano, Switzerland. · Zbl 1054.90621
[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
[20] Peng, W., Tong, R.F., Tang, M., Dong, J.X., 2005. Ant colony search algorithms for optimal packing problem. ICNC 2005, LNCS 3611, pp. 1229-1238.
[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, ()
[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
[29] Thangiah, S.R., Osman, I.H., Sun, T., 1994. Hybrid genetic algorithm, simulated annealing and tabu search methods for vehicle routing problems with time windows. Technical Report 27, Computer Science Department, Slippery Rock University.
[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)
[31] Yu, B., Yang, Z.Z., 2007. A dynamic holding strategy in public transit systems with real-time information. Applied Intelligence, (accepted for publication), doi:10.1007/s10489-007-0112-9.
[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.