Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T10:51:56.443Z Has data issue: false hasContentIssue false
  • English
  • Français

The Travelling Salesman Problem for finite-sized cities†

Published online by Cambridge University Press:  08 November 2010

HUGO FORT ,
MORDECHAI KORNBLUTH  and
FREDY ZYPMAN
HUGO FORT
Affiliation:
Instituto de Física, Facultad de Ciencias, Universidad de la República, Iguá 4225, Montevideo 11400, Uruguay Email: hugo@fisica.edu.uy
MORDECHAI KORNBLUTH
Affiliation:
Department of Physics, Yeshiva University, New York, U.S.A. Email: mkornblu@yu.edu, zypman@yu.edu
FREDY ZYPMAN
Affiliation:
Department of Physics, Yeshiva University, New York, U.S.A. Email: mkornblu@yu.edu, zypman@yu.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider a variation of the Travelling Salesman Problem (TSP) in which the cities visited have non-zero spatial extent, in contrast with the classical TSP, which has destinations that are mathematical points. This new approach opens up both new analyses of the problem and new algorithms for solutions, while remaining an economic first approximation to the standard problem. We present one particular solution that, depending on the number and size of the cities, can improve existing algorithms solving the classical TSP.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 20 , Special Issue 6: Quantum Algorithms , December 2010 , pp. 1067 - 1078
Copyright
Copyright © Cambridge University Press 2010

References

Cheeseman, B., Kanefski, B. and Taylor, W. M. (1991) Where the Really Hard Problems Are. Proceedings of 12th International Joint Conference on AI (IJCAI-91) 1 331–337.Google Scholar
Codenotti, B., Manzini, G., Margara, L. and Resta, G. (1996) Perturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP. INFORMS Journal on Computing 8 (2)125–133.Google Scholar
Dumitrescu, A. and Mitchell, J. S. B. (2003) Approximation algorithms for TSP with neighborhoods in the plane. Journal of Algorithms Archive 48 (1)135–159.CrossRefGoogle Scholar
Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman.Google Scholar
Gent, P. and Walsh, T. (1996) The TSP phase transition. Artificial Intelligence 88 349358.CrossRefGoogle Scholar
Herroelen, W. and de Reyck, B. (1999) Phase transitions in project scheduling. Journal of the Operational Research Society 50 (2)148–156.CrossRefGoogle Scholar
Kirkpatrick, S., Gelatt, C. D. Jr. and Vecchi, M. P. (1983) Optimization by Simulated Annealing. Science 220 (4598)671–680.CrossRefGoogle ScholarPubMed
Percus, A., Istrate, G. and Moore, C. (2006) Where Statistical Physics Meets Computation. Computational Complexity and Statistical Physics (chapter 1), Oxford University Press.Google Scholar