Skip to main content
SpringerLink
Log in

An improved Ant System algorithm for theVehicle Routing Problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The Ant System is a distributed metaheuristic that combines an adaptive memory with alocal heuristic function to repeatedly construct solutions of hard combinatorial optimizationproblems. In this paper, we present an improved ant system algorithm for the Vehicle RoutingProblem with one central depot and identical vehicles. Computational results on fourteenbenchmark problems from the literature are reported and a comparison with five othermetaheuristic approaches for solving Vehicle Routing Problems is given.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. Bullnheimer, R.F. Hartl and C. Strauss, A new rank based version of the ant system: A computational study, Working Paper No. 1, SFB Adaptive Information Systems and Modelling in Economics and Management Science, Vienna, 1997, to appear in CEJOR

    Google Scholar 

  2. B. Bullnheimer, R.F. Hartl and C. Strauss, Applying the Ant System to the vehicle routing problem, in: Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, eds. S. Voss, S. Martello, I.H. Osman and C. Roucairol, Kluwer, Boston, 1998.

    Google Scholar 

  3. B. Bullnheimer, G. Kotsis and C. Strauss, Parallelization strategies for the Ant System, in: High Performance Algorithms and Software in Nonlinear Optimization, eds. R. De Leone, A. Murli, P.M. Pardalos and Toraldo, Kluwer Academic, Dordrecht, 1998.

    Google Scholar 

  4. N. Christofides, A. Mingozzi and P. Toth, The Vehicle Routing Problem, in: Combinatorial Optimization, eds. N. Christofides, A. Mingozzi, P. Toth and C. Sandi, Wiley, Chichester, 1979.

    Google Scholar 

  5. G. Clarke and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res. 12(1964)568.

    Google Scholar 

  6. A. Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies, in: Proceedings of the European Conference on Artificial Life, eds. F. Varela and P. Bourgine, Elsevier, Amsterdam, 1991.

    Google Scholar 

  7. A. Colorni, M. Dorigo, V. Maniezzo and M. Trubian, Ant System for job-shop scheduling, Belgian Journal of Operations Research, Statistics and Computer Science 34(1994)39.

    Google Scholar 

  8. D. Costa and A. Hertz, Ants can colour graphs, J. Oper. Res. Soc. 48(1997)295.

    Google Scholar 

  9. G.A. Croes, A method for solving traveling salesman problems, Oper. Res. 6(1958)791.

    Google Scholar 

  10. M. Dorigo, Optimization, learning and natural algorithms, Doctoral Dissertation, Politecnico di Milano, Italy, 1992 (in Italian).

    Google Scholar 

  11. M. Dorigo and L.M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans. Evol. Comput. 1(1997)53.

    Google Scholar 

  12. M. Dorigo, V. Maniezzo and A. Colorni, Ant System: Optimization by a colony of cooperating agents, IEEE Trans. Sys., Man, Cybernetics 26(1996)29.

    Google Scholar 

  13. M. Gendreau, A. Hertz and G. Laporte, A tabu search heuristic for the Vehicle Routing Problem, Manag. Sci. 40(1994)1276.

    Google Scholar 

  14. H. Ghaziri, Supervision in the self-organizing feature map: Application to the Vehicle Routing Problem, in: Meta-Heuristics: Theory and Applications, eds. I. Osman and J. Kelly, Kluwer, Boston, 1996.

    Google Scholar 

  15. B.E. Gillett and L.R. Miller, A Heuristic algorithm for the Vehicle Dispatch Problem, Oper. Res. 22(1974)340.

    Google Scholar 

  16. H. Kopfer, G. Pankratz and E. Erkens, Entwicklung eines hybriden Genetischen Algorithmus zur Tourenplanung, Oper. Res. Spekt. 16(1994)21.

    Google Scholar 

  17. S. Lin and B.W. Kernighan, An effective heuristic algorithm for the Traveling Salesman Problem, Oper. Res. 21(1993)498.

    Google Scholar 

  18. V. Maniezzo, A. Colorni and M. Dorigo, The Ant System applied to the Quadratic Assignment Problem, Technical Report IRIDIA/94-28, Université Libre de Bruxelles, 1994.

  19. I. Osman, Metastrategy simulated annealing and tabu search algorithms for the Vehicle Routing Problem, Ann. Oper. Res. 41(1993)421.

    Google Scholar 

  20. H. Paessens, The savings algorithm for the Vehicle Routing Problem, Eur. J. Oper. Res. 34(1988)336.

    Google Scholar 

  21. C. Rego and C. Roucairol, A parallel tabu search algorithm using ejection chains for the Vehicle Routing Problem, in: Meta-Heuristics: Theory and Applications, eds. I. Osman and J. Kelly, Kluwer, Boston, 1996.

    Google Scholar 

  22. Y. Rochat and E.D. Taillard, Probabilistic diversification and intensification in local search for vehicle routing, J. Heuristics 1(1995)147.

    Google Scholar 

  23. T. Stuetzle and H. Hoos, The MAX-MIN Ant System and local search for the Traveling Salesman Problem, in: Proceedings of the ICEC'97-IEEE 4th International Conference on Evolutionary Computation, 1997, p. 308.

  24. E. Taillard, Parallel iterative search methods for Vehicle Routing Problems, Networks 23(1993)661.

    Google Scholar 

Download references

Authors
  1. B. Bullnheimer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R.F. Hartl
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. Strauss
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bullnheimer, B., Hartl, R. & Strauss, C. An improved Ant System algorithm for theVehicle Routing Problem. Annals of Operations Research 89, 319–328 (1999). https://doi.org/10.1023/A:1018940026670

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018940026670

Keywords

Search

Navigation