Skip to main content
SpringerLink
Log in

A New Memetic Algorithm for the Asymmetric Traveling Salesman Problem

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This paper introduces a new memetic algorithm specialized for the asymmetric instances of the traveling salesman problem (ATSP). The method incorporates a new local search engine and many other features that contribute to its effectiveness, such as: (i) the topological organization of the population as a complete ternary tree with thirteen nodes; (ii) the hierarchical organization of the population in overlapping clusters leading to the special selection scheme; (iii) efficient data structures. Computational experiments are conducted on all ATSP instances available in the TSPLIB, and on a set of larger asymmetric instances with known optimal solutions. The comparisons show that the results obtained by our method compare favorably with those obtained by several other algorithms recently proposed for the ATSP.

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

  • Balas, E. and P. Toth. (1985). "Branch-and Bound Methods." In E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan, and D.B. Shmoys (eds.), The Traveling Salesman Problem. John Wiley and Sons.

  • Bentley, J.L. (1990). "Experiments on Traveling Salesman Heuristics." In Proceedings of the First Annual ACM-SIAM Symposium on Computational Geometry, pp. 91–99.

  • Berretta, R. and P. Moscato. (1999). "The Number Partitioning Problem: An Open Challenge for Evolutionary Computation." In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, Chapter 17. McGraw-Hill.

  • Carpaneto, G., M. Dell'Amico, and P. Toth. (1995). "Exact Solution of Large-Scale Asymmetric Traveling Sales-man Problems." ACM Transactions on Mathematical Software21(4), 394–409.

    Google Scholar 

  • Choi, I.-C., S.-I. Kim, and H.-S. Kim. (2003). "A Genetic Algorithm with a Mixed Region Search for the Asym-metric Traveling Salesman Problem." Computers & Operations Research30(5), 773–786.

    Google Scholar 

  • Cirasella, J., D.S. Johnson, L.A. McGeoch, and W. Zhang. (2001). "The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests." In A.L. Buchsbaum and J. Snoeyink, (eds.), Proceedings of ALENEX01, Springer Lecture Notes in Computer Science2153, pp. 32–59.

  • Fiechter, C.-N. (1994). "A Parallel Tabu Search Algorithm for Large Traveling Salesman Problems." Discrete Applied Mathematics51, 243–267.

    Google Scholar 

  • Fischetti, M. and P. Toth. (1997). "A Polyhedral Approach to the Asymmetric Traveling Salesman Problem." Management Science43(11), 1520–1536.

    Google Scholar 

  • Fischetti, M., P. Toth, and D. Vigo. (1994). "A Branch-and Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs." Operations Research42, 846–859.

    Google Scholar 

  • França, P.M., A.S. Mendes, and P. Moscato. (2001). "A Memetic Algorithm for the Total Tardiness Single Machine Scheduling Problem." European Journal of Operational Research132, 224–242.

    Google Scholar 

  • Freisleben, B. and P. Merz. (1996). "A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems." In Proceedings of the IEEE International Conference on Evolutionary Compu-tation, pp. 616–621.

  • Garey, M.R. and D.S. Jonhson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.

  • Glover, F. (1996). "Finding a Best Traveling Salesman 4-opt Move in the Same Time as a Best 2-opt Move." J. Heuristics2(2), 169–179.

    Google Scholar 

  • Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley.

  • Gorges-Schleuter, M. (1989). "ASPARAGOS: An Asynchronous Parallel Genetic Optimization Strategy." In J.D. Schaffer (ed.), Proceedings of the Third International Conference on Genetic Algorithms, pp. 422–427.

  • Gorges-Schleuter, M. (1997). "Asparagos96 and the Traveling Salesman Problem." In T. Baeck, Z. Michalewicz, and X. Yao (eds.), Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 171–174.

  • Gutin, G. and A.P. Punnen. (2002). The Traveling Salesman Problem and Its Variations. Kluwer Academic Publishers.

  • Helsgaun, K. (2000). "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic." European Journal of Operational Research126(1), 106–130.

    Google Scholar 

  • Holstein, D. and P. Moscato. (1999). "Memetic Algorithms Using Guided Local Search: A Case Study." In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization, Chapter 15 McGraw-Hill.

  • Johnson, D.S. and L.A. McGeoch. (1997). "The Traveling Salesman Problem: A Case Study." In E. Aarts and J. K. Lenstra (eds.), Local Search in Combinatorial Optimization. John Wiley & Sons.

  • Johnson, D.S., G. Gutin, L.A. McGeoch, A. Yeo, W. Zhang, and A. Zverovich. (2002). "The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators and Tests." In Gregory Gutin and Abraham P. Punnen (eds.), The Traveling Salesman Problem and its Variations, Chapter 10. Kluwer Academic Publishers, pp. 445–488.

  • Jünger, M., G. Reinelt, and G. Rinaldi. (1995). "The Traveling Salesman Problem." In M. Ball, T. Magnanti, C.L. Monma, and G.L. Nemhauser (eds.), Handbooks in Operations Research and Management Sciences: Networks. North-Holland.

  • Kanellakis, P.C. and C.H. Papadimitriou. (1980). "Local Search for the Asymmetric Traveling Salesman Problem." Operations Research28(5), 1086–1099

    Google Scholar 

  • Karp, R.M. (1977). "Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plane." Math. Operational Research2, 209–224.

    Google Scholar 

  • Karp, R.M. (1979). "A Patching Algorithm for the Nonsymmetric Traveling Salesman Problem." SIAM J. Comput. 8, 561–573.

    Google Scholar 

  • Laporte, G. (1992). "The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms." European Journal of Operational Research59(2), 231–247.

    Google Scholar 

  • Lin, S. and B.W. Kernighan. (1973). "An Effective Heuristic Algorithm for the Traveling Salesman Problem." Operations Research21(2), 498–516.

    Google Scholar 

  • Mendes, A.S., F.M. Müller, P.M. França, and P. Moscato. (2002). "Comparing Metaheuristic Approaches for Parallel Machine Scheduling Problems with Sequence Dependent Setup Times." Production Planning & Control 13, 143–154.

    Google Scholar 

  • Merz, P. and B. Freisleben. (1997). "Genetic Local Search for the TSP: New Results." In Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, pp. 159–164.

  • Merz P. and B. Freisleben. (2001). "Memetic Algorithms for the Traveling Salesman Problem." Complex Systems 13(4), 297–345.

    Google Scholar 

  • Miller, D.L. and J.F. Pekny. (1991). "Exact Solution of Large Asymmetric Traveling Salesman Problems." Science 251, 754–761.

    Google Scholar 

  • Moscato, P. (1989). "On Evolution, Search, Optimization, Genetic Algorithms, and Martial Arts: Towards Memetic Algorithms." Technical Report, Caltech Concurrent Computation Program, C3P Report 826.

  • Moscato, P. and M.G. Norman. (1992). "AMemetic Approach for the Traveling Salesman Problem. Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing Systems." In M. Valero, E. Onate, M. Jane, J.L. Larriba, and B. Suarez (eds.), Parallel Computing and Transputer Applications.IOS Press, pp. 187–194.

  • Moscato, P. and F. Tinetti. (1992). "Blending Heuristics with a Population-Based Approach: AMemetic Algorithm for the Traveling Salesman Problem." CeTAD, Report 92-12. Universidad Nacional de La Plata, Argentina.

    Google Scholar 

  • Moscato, P. (1993). "An Introduction to Population Approaches for Optimization and Hierarchical Objective Functions: A Discussion on the Role of Tabu Search." Annals of Operations Research41, 85–121.

    Google Scholar 

  • Moscato, P. (1999). "Memetic Algorithms: A Short Introduction." In D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization. McGraw-Hill.

  • Nagata, Y. and S. Kobayashi. (1997). "Edge Assembly Crossover: A High-power Genetic Algorithm for the Traveling Salesman Problem." In Proceedings of the Seventh International Conference on Genetic Algorithms, pp. 450–457.

  • Paechter, B., A. Cumming, M.G. Norman, and H. Luchian. (1996). "Extensions to a Memetic Timetabling System." In E.K. Burke and P. Ross (eds.), The Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science,Vol. 1153. Springer Verlag, pp. 251–265.

  • Potvin, J.Y. (1993). "The Traveling Salesman Problem: A Neural Network Perspective." ORSA Journal on Com-puting 5, 328–348.

    Google Scholar 

  • Reinelt, G. (1991). "TSPLIB-A Traveling Salesman Library." ORSA Journal on Computing 3, 376–384.

    Google Scholar 

  • Stützle, T. and M. Dorigo. (1999). "ACO Algorithms for the Traveling Salesman Problem." In K. Miettinen, M. Makela, P. Neittaanmaki, J. Periaux (eds.). Evolutionary Algorithms in Engineering and Computer Science. Wiley.

  • Walters, T. (1998). "Repair and Brood Selection in the Traveling Salesman Problem." In A.E. Eiben, T. Båch, M. Schoenauer, and H.P. Schwefel (eds.), Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature, pp. 813–822.

  • Whitley, D., T. Starkweather, and D. Shaner. (1991). "The Traveling Salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination." In L. Davis (ed.), Handbook of Genetic Algorithms, pp. 350–372.

  • Zhang, W. (1993). "Truncated Branch-and-Bound: A Case Study on the Asymmetric TSP." In Proceedings of Spring Symposium on AI and NP-Hard Problems, pp. 160–166.

  • Zhang, W. (2000). "Depth-First Branch-and-Bound versus Local Search: A Case Study." In Proceedings of 17th National Conf. on Artificial Intelligence (AAAI), pp. 930–935.

Download references

Author information

Authors and Affiliations

  1. Faculdade de Engenharia Elétrica e de Computação, Universidade Estadual de Campinas, UNICAMP, 13083-970, Campinas, SP, Brazil

    Luciana Buriol & Paulo M. França

  2. School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, The University of Newcastle, 2308, Callaghan, NSW, Australia

    Pablo Moscato

Authors
  1. Luciana Buriol
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paulo M. França
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pablo Moscato
    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

Buriol, L., França, P.M. & Moscato, P. A New Memetic Algorithm for the Asymmetric Traveling Salesman Problem. Journal of Heuristics 10, 483–506 (2004). https://doi.org/10.1023/B:HEUR.0000045321.59202.52

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/B:HEUR.0000045321.59202.52

Search

Navigation