Lexicographically minimizing axial motions for the Euclidean TSP | Journal of Combinatorial Optimization Skip to main content
Springer Nature Link
Log in

Lexicographically minimizing axial motions for the Euclidean TSP

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

A variant of the Euclidean traveling salesman problem (TSP) is defined and studied. In the three-dimensional space, the objective function is to lexicographically minimize the x-moves, then the y-moves and finally the z-moves. The 2D and 3D cases are first studied and solved as a shortest path problem. Then the approach is generalized to the d-dimensional case.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Applegate DL, Bixby RE, Chvátal V, Cook WJ (2006) The traveling salesman problem: a computational study. Princeton University Press, Princeton

    MATH  Google Scholar 

  • Arkin EM, Chiang YJ, Mitchell JSB, Skiena SS, Yang TC (1997) On the maximum scatter TSP. In: Proceedings of the eighth annual ACM-SIAM Symposium on Discrete Algorithms, pp 211–220

  • Bentley JL (1990) Experiments on traveling salesman heuristics. In: Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms, pp 91–99

  • Burkard RE, Deineko VG, van Dal R, van der Veen JAA, Woeginger GJ (1998) Well-solvable special cases of the TSP: A survey. SIAM Rev 40:496–546

    Article  MATH  MathSciNet  Google Scholar 

  • Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge

    MATH  Google Scholar 

  • Cutler M (1980) Efficient special case of algorithms for the N-line planar traveling salesman problem. Network 10:183–195

    Article  MATH  MathSciNet  Google Scholar 

  • Gutin G, Punnen AP (eds) (2002) The traveling salesman problem and its variations. Springer, Berlin

    MATH  Google Scholar 

  • Kabadi SN (2002) Polynomially solvable cases of the TSP. In: Gutin G, Punnen AP (eds) The traveling salesman problem and its variations. Springer, Berlin, pp 489–584

    Google Scholar 

  • Papadimitriou CH, Steiglitz K (1976) Some complexity results for the traveling salesman problem. In: Proceedings of the eighth annual ACM symposium on theory of computing, pp 1–9

Download references

Author information

Authors and Affiliations

  1. CNRS, LIP6 laboratory, Université Pierre et Marie Curie, Paris, France

    Francis Sourd

Authors
  1. Francis Sourd
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francis Sourd.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sourd, F. Lexicographically minimizing axial motions for the Euclidean TSP. J Comb Optim 19, 1–15 (2010). https://doi.org/10.1007/s10878-008-9154-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-008-9154-0

Keywords

Search

Navigation