The traveling salesman problem on grids with forbidden neighborhoods | Journal of Combinatorial Optimization Skip to main content
Springer Nature Link
Log in

The traveling salesman problem on grids with forbidden neighborhoods

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

Abstract

We introduce the traveling salesman problem with forbidden neighborhoods (TSPFN). This is an extension of the Euclidean TSP in the plane where direct connections between points that are too close are forbidden. The TSPFN is motivated by an application in laser beam melting. In the production of a workpiece in several layers using this method one hopes to reduce the internal stresses of the workpiece by excluding the heating of positions that are too close. The points in this application are often arranged in some regular (grid) structure. In this paper we study optimal solutions of TSPFN instances where the points in the Euclidean plane are the points of a regular grid. Indeed, we explicitly determine the optimal values for the TSPFN and its associated path version on rectangular regular grids for different minimal distances of the points visited consecutively. For establishing lower bounds on the optimal values we use combinatorial counting arguments depending on the parities of the grid dimensions. Furthermore we provide construction schemes for optimal TSPFN tours for the considered cases.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23

Similar content being viewed by others

Notes

  1. Note that we rotated the m-n-coordinate system of the Euclidean plane by 90\(^\circ \) in clockwise direction in order to work with the usual matrix numbering of the grid cells later on.

  2. In slight abuse of notation we will often write in this paper that a path has a start (the first node mentioned) and an end vertex (the last node mentioned) although we are in the undirected case.

  3. The only exception is in the upper left corner, when we go from (1, 3) to (1, 1) and then over (2, 2), to (3, 3) and (4, 4).

References

  • Applegate DL, Bixby RE, Chvatal V, Cook WJ (2007) The traveling salesman problem: a computational study (Princeton series in applied mathematics). Princeton University Press, Princeton. ISBN 0691129932

  • Arkin EM, Chiang Y-J, Mitchell JSB, Skiena SS, Yang T-C (1999) On the maximum scatter traveling salesperson problem. SIAM J Comput 29(2):515–544

    Article  MathSciNet  MATH  Google Scholar 

  • Arkin E, Bender M, Demaine E, Fekete S, Mitchell J, Sethia S (2005) Optimal covering tours with turn costs. SIAM J Comput 35(3):531–566

    Article  MathSciNet  MATH  Google Scholar 

  • Arkin EM, Fekete SP, Islam K, Meijer H, Mitchell JS, Núñez-Rodríguez Y, Polishchuk V, Rappaport D, Xiao H (2009) Not being (super)thin or solid is hard: a study of grid hamiltonicity. Comput Geom 42(6–7):582–605

    Article  MathSciNet  MATH  Google Scholar 

  • Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 45(5):753–782

    Article  MathSciNet  MATH  Google Scholar 

  • Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45(3):501–555

    Article  MathSciNet  MATH  Google Scholar 

  • Chiang Y-J (2004) New approximation results for the maximum scatter TSP. Algorithmica 41(4):309–341. doi:10.1007/s00453-004-1124-z

    Article  MathSciNet  MATH  Google Scholar 

  • Christofides, N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, GSIA, Carnegie-Mellon University,

  • Conrad A, Hindrichs T, Morsy H, Wegener I (1994) Solution of the knight’s Hamiltonian path problem on chessboards. Discret Appl Math 50(2):125–134

    Article  MathSciNet  MATH  Google Scholar 

  • Cook WJ (2011) In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University Press, Princeton

    Google Scholar 

  • Cull P, De Curtins J (1978) Knight’s tour revisited. Fibonacci Q 16:276–285

    MathSciNet  MATH  Google Scholar 

  • Dantzig G, Fulkerson R, Johnson S (1954) Solution of a large-scale traveling-salesman problem. Oper Res 2:393–410

    MathSciNet  Google Scholar 

  • Demaine E, Mitchell JSB, O’Rourke J (2004) The open problems project. http://cs.smith.edu/~jorourke/TOPP/

  • Euler L (1759) Solution d’une question curieuse que ne paroit soumiseà aucune analyse. Mem Acad Dessciences Berl 15:310–337

    Google Scholar 

  • Garey MR, Graham RL, Johnson DS (1976) Some NP-complete geometric problems. In: Proceedings of the eighth annual ACM symposium on theory of computing, STOC ’76, pp 10–22, New York, NY, USA. ACM

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

    MATH  Google Scholar 

  • Hoffmann I, Kurz S, Rambau J (2015) The maximum scatter TSP on a regular grid. https://epub.uni-bayreuth.de/2524/

  • Itai A, Papadimitriou C, Szwarcfiter J (1982) Hamilton paths in grid graphs. SIAM J Comput 11(4):676–686

    Article  MathSciNet  MATH  Google Scholar 

  • Jellen A, Fischer A, Hungerländer P (2016) Implementation of algorithms and illustration of optimal tours for the TSPFN with \(r \in \{0,1,\sqrt{2} \}\). http://philipphungerlaender.jimdo.com/tspfn-code/

  • Kordaß R (2014) Untersuchungen zum Eigenspannungs- und Verzugsverhalten beim Laserstrahlschmelzen. Masterarbeit, Technische Universität Chemnitz, Fakultät für Maschinenbau, Professur für Werkzeugmaschinen und Umformtechnik

  • Kozma L, Mömke T (2015) A PTAS for Euclidean maximum scatter TSP. CoRR, arXiv:1512.02963

  • Kozma L, Mömke T (2017) Maximum scatter TSP in doubling metrics, pp 143–153. doi:10.1137/1.9781611974782.10

  • Lin S-S, Wei C-L (2005) Optimal algorithms for constructing knight’s tours on arbitrary chessboards. Discret Appl Math 146(3):219–232

    Article  MathSciNet  MATH  Google Scholar 

  • MATLAB. version 7.10.0 (r2010a) (2010)

  • Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237–244

    Article  MATH  Google Scholar 

  • Parberry I (1997) An efficient algorithm for the knight’s tour problem. Discret Appl Math 73(3):251–260

    Article  MathSciNet  MATH  Google Scholar 

  • Reinelt G (1994) The traveling salesman: computational solutions for TSP applications. Springer, Berlin

    MATH  Google Scholar 

  • Schwenk AJ (1991) Which rectangular chessboards have a knight’s tour? Math Mag 64(5):325–332

    Article  MathSciNet  MATH  Google Scholar 

  • Umans C., Lenhart W (1997) Hamiltonian cycles in solid grid graphs. In: 38th annual symposium on foundations of computer science, pp 496–505

Download references

Acknowledgements

We thank Richard Kordaß and Thomas Töppel from the Fraunhofer IWU in Dresden for introducing us to this optimization problem in laser beam melting and for providing several real-world instances.

Author information

Authors and Affiliations

  1. Institute for Numerical and Applied Mathematics, University of Göttingen, Lotzestrasse 16-18, 37083, Göttingen, Germany

    Anja Fischer

  2. Institute for Mathematics, Alpen-Adria Universität Klagenfurt, Universitätsstrasse 65-67, 9020, Klagenfurt Am Wörthersee, Austria

    Philipp Hungerländer

Authors
  1. Anja Fischer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philipp Hungerländer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anja Fischer.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Fischer, A., Hungerländer, P. The traveling salesman problem on grids with forbidden neighborhoods. J Comb Optim 34, 891–915 (2017). https://doi.org/10.1007/s10878-017-0119-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-017-0119-z

Keywords

Mathematics Subject Classification

Search

Navigation