TSPBIB Home Page

This page intends to be a comprehensive listing of papers, source code, preprints, technical reports, etc, available on the Internet about the Traveling Salesman Problem (TSP) and some associated problems.

Please send us information about any other work you consider it should be included in this page.

Pablo Moscato

email: moscato@cacr.caltech.edu
email: moscato@densis.fee.unicamp.br

The picture above shows an instance of the Euclidean, Planar TSP
and the optimal curve among the set of cities.
This instance has been named MNPeano Order 2.

The material in this page is solely aimed for academic research purposes and we encourage the readers to contact the authors of the papers included to correctly cite their papers. To make contributions for papers, preprints, technical reports, etc., let us know the authors of the paper, its title, a very short abstract (such that we could find out what topic this paper belongs to), and, if you wish to, its current status. If you plan to leave a paper for public domain access and wish to include in our list, please leave the paper as a postscript file in compressed or uncompressed form in a public directory, and let us know the complete address of the file there such that we set a link to the file.

Other pages related to TSPBIB

  • The Hamiltonian Page, by Gregory Gutin and Pablo Moscato.
  • The Vehicle Routing Problem, by Tim Duncan.
  • Fractal Instances of the Traveling Salesman Problem, by Pablo Moscato. Software for the automatic generation of the instances available from Adrian Mariano.

    We try at TSPBIB to comply with the definitions for problems at

  • A compendium of NP optimization problems, by Pierluigi Crescenzi and Viggo Kann.

    Please inform us about any differences in the definitions for problems and subproblems you might detect.

    TSP Instances

    If you are looking for solved instances of the travelling salesman problem you should go to the TSPLIB home page. TSPLIB also has a mirror site at Rice University.

    Fractal TSP Instances

    If you are looking for a complementary set of instances try the Fractal Instances of the Traveling Salesman Problem page where you can find software that generates some of the instances to arbitrarily large size and papers related with them.

    VRP Instances

  • Solomon's instances of VRP with time windows.

    The Vehicle Routing Problem, a similar page to TSPBIB, but for the VRP, is maintained by Tim Duncan and contains many other instances as well as papers for on-line access.

    The Ultimate List of Vehicle Routing References Part I and II, by Karsten Lund.

    Software

  • GATSS, by Thomas Pederson, a Genetic Algorithm based solver of the Traveling Salesman problem written in GNU C++ linked to a user interface in HTML via CGI-script.
  • GAlib, A C++ Genetic Algorithms Library, see in particular the provided examples, the TSP.
  • Maugis TSP solver, a program written in ansi-C, for Symmetric Euclidean TSPs, by Lionnel Maugis.
  • tsp_solve, a collection of heuristics and optimal algorithms for the TSP, by Chad Hurwitz. He does not have a web page or ftp site to put it on, so he asks people to email him for a copy of the software, it's GNU C so it'll run on most unixes.
  • An ATSP code, by Glenn Dicus, Bart Jaworski and Joseph Ou-Yang.
  • A TSP program in Parlog, by Steve Gregory.
  • The Travelling Spider Problem, by Moshe Sniedovich. We expect this page to include TSP codes based on Dynamic Programming.
  • Traveling Salesman Problem solving program (TSPSolver), by Victor V. Miagkikh. TSPSolver is written in Borland C++ and Borland Delphi for MS Windows. Some benchmarks are enclosed.
  • Traveling Salesman Java Applet, by Martin Hagerup. The author comments that the applet has been selected to appear in the book ``Java Programming for Dummies'' (please, send me one) . Requires Netscape 2.0 in 32 bits or other Java-browser.
  • Simple Closed Paths, from the book: Introduction to Programming with Mathematica, 2nd Edition , 1995, TELOS/Springer-Verlag. The page includes a Mathematica notebook.
  • tsp1.gms, a page related with GAMS, the General Algebraic Modeling System which is a high-level modeling system for mathematical programming problems.
  • A Java TSP demo program using Kohonen's neural network formulation.
  • A Simple TSP-Solver: An ABACUS Tutorial, by Stefan Thienel, 1996.
  • A Guided Local Search demo for TSP, by Christos Voudouris, (it requires Microsoft Windows 3.1.).
  • Another Guided Local search demo, this one requires SunOS (precompiled for SunOS 5.3) and XView, by Christos Voudouris.
  • A heuristic and a brute force method, Java programs by Aaron Passey.
  • BOB: Branch-and-bound Optimization liBrary, a general-purpose parallel Branch-and-Bound algorithm library being developed at PRiSM Laboratory of University of Versailles-Saint Quentin en Yvelines. They provide examples for QAP, TSP and VCP. It is freely available via anonymous ftp from ftp.prism.uvsq.fr in the file pub/software/BoBL1.0.tar.Z. Click here to get a copy of it.

    Open problems and challenges

    The purpose of this section is to link to other pages which contain information about open problems and challenges. It will serve as a forum of discussion for interested readers.

  • Help solve the Mystery !, by Chris Jones. He says:

    ``If you are able to show that any of these tours is not optimal, I will reward you with a case of your favorite beverage. Those who confirm the results receive a basic unit (e.g., bottle, can, etc) of your favorite beverage.''

    I hope his offer is not illigal in your country !

  • Polynomial transformations and the TSP, by Tore Gruenert.

    Heuristic approaches

  • Combining Simulated Annealing with Local Search Heuristics , by O. Martin and S.W. Otto.
  • A new hybrid heuristic for large geometric Traveling Salesman Problems based on the Delaunay Triangulation. N. Krasnogor, P. Moscato and M.G Norman ``Anales del XXVII Simposio Brasileiro de Pesquisa Operacional'', Vitoria, Brazil, 6-8 Nov. 1995.
  • An Analysis of the Performance of Traveling Salesman Heuristics on Infinite-Size Fractal Instances in the Euclidean Plane. P. Moscato and M.G. Norman, submitted,
  • ``Algoritmos Geneticos'', M. Laguna and P. Moscato, Chapter 3, from the book ``Optimizacion Heuristica y Redes Neuronales'' , edited by B. A. Diaz, Ed. Paraninfo, Madrid, Espanya, (1996).
  • Sensitivity Analysis for the Euclidean Traveling Salesman Problem, by Chris Jones.
  • Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem, by David P. Williamson, Master's Thesis, MIT Computer Science, June 1990.
  • Combining Simulated Annealing with Local Search Heuristics , by O. Martin and S.W. Otto.
  • Guided Local Search , an earlier Technical Report by C. Voudoris and E.P.K. Tsang. They maintain a home page for Guided Local Search at: http://cswww.essex.ac.uk/Research/CSP/gls.html.
  • Improving the efficiency of limited-memory heuristic search , by Subrata Ghosh, Ambuj Mahanti and Dana S. Nau.
  • An efficient parallel cluster-heuristic for large TSPs , by B. Steckemetz and M. Wottawa.
  • Efficient Clustering Techniques for the Geometric Traveling Salesman Problem, B. Codenotti and L. Margara.
  • Peturbation: An Efficient Technique for the Solution of Very Large Instances of the Euclidean TSP, B. Codenotti, G. Manzini, L. Margara and G. Resta.
  • An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics, by Shumeet Baluja.
  • The Traveling Salesman Problem: A Case Study in Local Optimization, by David S. Johnson and Lyle A. McGeoch. The paper will appear as a chapter in the book Local Seach in Combinatorial Optimization edited by E.H.L. Aarts and J.K. Lenstra.
  • Cost Versus Distance In the Traveling Salesman Problem, by K. D. Boese, Technical Report CSD-950018 , UCLA Computer Science Department, May 1995.
  • Scan Chain Optimization: Heuristic and Optimal Solutions, by K.D. Boese and R.-S. Tsay, submitted to ACM/IEEE Design Automation Conf., 1995.
  • Models for Iterative Global Optimization, PhD Thesis, Kenneth D. Boese, UCLA, 1996.
  • Parallele Heuristiken fuer sehr grosse Traveling Salesman Probleme, also gzipped here Diplom Thesis (in German), by André Rohe, Univerisity of Bonn, 1997.
  • Parallel Lower and Upper Bounds for Large TSPs, a summary of André Rohe's thesis (in English), will appear in ZAMM Volume 77, Supplement 2, pp. 429-432, 1997.
  • Exponential neighbourhoods local search for the Traveling Salesman Problem, by Gregory Gutin, 1997.
  • Small diameter neighbourhood graphs for the TSP: at most four moves from tour to tour, by Gregory Gutin, 1997.
  • Asynchronous Teams: A Multi-Algorithm Approach for Solving Combinatorial Multiobjective Optimization Problems, by R. de Freitas Rodrigues and P.S. de Souza, 1995.
  • Data Structures for Traveling Salesmen, M. L. Fredman, D. S. Johnson, L. A. McGeoch and G. Ostheimer, J. Algorithms, 18:3 (1995), pp. 432-479. [Preliminary version: Proc. 4th Ann. ACM-SIAM Symp. on Discrete Algorithms (1993), 145-154.]
  • Traveling Salesman mit Iteriertem Matching, thesis by Frank Lauxtermann, check also his page on the thesis subject.
  • Fast hierarchical clustering and other applications of dynamic closest pairs , by D. Eppstein, in 9th ACM-SIAM Symp. Discrete Algorithms, San Francisco (1998) to appear.

    Memetic Algorithms

    For more information about them you can visit the Memetic Algorithms' Home Page

  • On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms , P. Moscato, Caltech Concurrent Computation Program, C3P Report 826, (1989).
  • On Genetic Crossover Operators for Relative Order Preservation , P. Moscato, Caltech Concurrent Computation Program, C3P Report 778, (1989).
  • Evolution in Time and Space - The Parallel Genetic Algorithm , by Heinz Mühlenbein, appeared in: Foundations of Genetic Algorithms, G. Rawlins (ed.), pp. 316-337, Morgan-Kaufman, 1991.
  • A `Memetic' Approach for the Traveling Salesman Problem. Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing Systems, P. Moscato and M.G. Norman, Parallel Computing and Transputer Applications , edited by M. Valero, E. Onate, M. Jane, J.L. Larriba and B. Suarez, Ed. IOS Press, Amsterdam, pp. 187-194, 1992.
  • Parallel Genetic Algorithms in Combinatorial Optimization , by Heinz Mühlenbein, appeared in: Computer Science and Operations Research O. Balci, R. Sharda and S. Zenios (eds.), pp. 441-456, Pergamon Press, New York 1992.
  • An Introduction to Population Approaches for Optimization and Hierarchical Objective Functions: A Discussion on the role of Tabu Search, P. Moscato, Annals of Operations Research , Vol. 41, Number 1-4, pp. 85-121, 1993.Please check the home page of this volume of the journal which is available here.
  • Blending Heuristics with a Population-Based Approach: A Memetic Algorithm for the Traveling Salesman Problem , P. Moscato and F. Tinetti, Dec. 1992.
  • Formal memetic algorithms, N.J. Radcliffe and P.D. Surry, in ``Evolutionary Computing: AISB Workshop'', (Ed: T. Fogarty, Springer-Verlag), 1994.
  • Fitness Variance of Formae and Performance Prediction, N.J. Radcliffe and P.D. Surry, in Foundations of Genetic Algorithms 3 , 1995.
  • Genetic Operators, the Fitness Landscape and the Traveling Salesman Problem, by D. Whitley and K. Mathias, appeared in Parallel Problem Solving from Nature-PPSN 2. R. Ma:nner and B. Manderick, eds., pp. 219-228. North Holland-Elsevier, 1992
  • Advance Correlation Analysis of Operators for the Traveling Salesman Problems by D. Whitley with J. Dzubera, appeared in Parallel Problem Solving from Nature-PPSN III. Y. Davidor, H.P. Schwefel and R. Manner, eds. pp. 68-77. Springer-Verlag, 1994.
  • A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems, by B. Freisleben and P. Merz, appeared in Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan, pp. 616-621, 1996.
  • New Genetic Local Search Operators for the Traveling Salesman Problem by B. Freisleben and P. Merz, in Proceedings of the 4th Conference on Parallel Problem Solving from Nature - PPSN IV, (H.-M. Voigt, W. Ebeling, I. Rechenberg, H.-P. Schwefel, eds.), Volume 1141 of Lecture Notes in Computer Science, pp. 890-899, Springer, 1996.
  • Genetic Algorithms and the Traveling Salesman Problem, by Karan Bhatia, Class Report for Papadimitriou's CSE292 Course, Spring 94, at UCSD.
  • Genetic Local Search for the TSP: New Results, by P. Merz and B. Freisleben, in Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, IEEE Press, pp. 159-164, Indianapolis, USA, 1997.
  • Asparagos96 and the Traveling Salesman Problem, M. Gorges-Schleuter, In Proceedings of the IEEE Int. Conf. on Evolutionary Computation, IEEE Press (1997).
  • On the power of evolutionary optimization at the example of ATSP and large TSP Problems, M. Gorges-Schleuter. In European Conference on Artificial Life `97, Brighton, U.K., (1997)

    Ant Colony Optimization

    More information about this subject can be found in the Ant Colony Optimization Page maintained by Marco Dorigo.

  • The Ant System: Optimization by a colony of cooperating agents , M. Dorigo, V. Maniezzo & A. Colorni, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 1, 29-41, 1996. IJ.10-SMC96.ps.gz (105K).
  • Distributed Optimization by Ant Colonies , A. Colorni A., M. Dorigo & V. Maniezzo (1991), Proceedings of ECAL91 - European Conference on Artificial Life, Paris, France , F. Varela and P. Bourgine (Eds.), Elsevier Publishing, 134-142. IC.06-ECAL91.ps.gz (52K).
  • An Investigation of some Properties of an Ant Algorithm, A. Colorni, M. Dorigo & V. Maniezzo (1992), Proceedings of the Parallel Problem Solving from Nature Conference (PPSN 92), Brussels, Belgium, R.Männer and B.Manderick (Eds.), Elsevier Publishing, 509-520, IC.08-PPSN92.ps.gz (45K).
  • Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem, by L.M. Gambardella and M. Dorigo, Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 252-260, 1995.
  • The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem, by Thomas Stützle and Holger Hoos, (to appear - ICEC 1997).
  • Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, by M. Dorigo M. and L.M. Gambardella, Tecnical Report TR/IRIDIA/1996-5, IRIDIA, Université Libre de Bruxelles, will appear in IEEE Transactions on Evolutionary Computation, 1, 1, (1997) (in press).
  • Ant Colonies for the Traveling Salesman Problem, by M. Dorigo and L.M. Gambardella, Tecnical Report TR/IRIDIA/1996-3, IRIDIA, Université Libre de Bruxelles, BioSystems, (in press).

    Tabu Search

  • Tabu Search on the Geometric Traveling Salesman Problem , by M. Zachariasen and M. Dam, Presented at Metaheuristics International Conference 95, Breckenridge, Colorado, USA.
  • An Introduction to Population Approaches for Optimization and Hierarchical Objective Functions: A Discussion on the role of Tabu Search, P. Moscato, Annals of Operations Research , Vol. 41, Number 1-4, pp. 85-121, 1993.Please check the home page of this volume of the journal which is available here.
  • La Tabu Search e il Problema del Commesso viaggiatore, by Renato Del Balio.

    Simulated Annealing

  • Combining Simulated Annealing with Local Search Heuristics , by O. Martin and S.W. Otto.
  • A `Memetic' Approach for the Traveling Salesman Problem. Implementation of a Computational Ecology for Combinatorial Optimization on Message-Passing Systems, P. Moscato and M.G. Norman, Parallel Computing and Transputer Applications , edited by M. Valero, E. Onate, M. Jane, J.L. Larriba and B. Suarez, Ed. IOS Press, Amsterdam, pp. 187-194, 1992.
  • Improved Algorithms for Global Optimization, by Rachel Moldover and Paul Coddington.

    Genetic Algorithms

  • On Genetic Crossover Operators for Relative Order Preservation , P. Moscato, Caltech Concurrent Computation Program, C3P Report 778, (1989).
  • ``Algoritmos Geneticos'', M. Laguna and P. Moscato, Chapter 3, from the book ``Optimizacion Heuristica y Redes Neuronales'' , edited by B. A. Diaz, Ed. Paraninfo, Madrid, Espanya, (1996).
  • Some New Features in Genetic Solution of the Traveling Salesman Problem, by V.M. Kureichik, A.N. Melikhov, and V.V. Miagkikh.
  • Genetic Algorithm for Solution of Traveling Salesman Problem with New Features agains Premature Convergence, by V.M. Kureichik, V.V. Miagkikh, and A.P. Topchy.
  • Genetic Operators, the Fitness Landscape and the Traveling Salesman Problem, by D. Whitley and K. Mathias, appeared in Parallel Problem Solving from Nature-PPSN 2. R. Ma:nner and B. Manderick, eds., pp. 219-228. North Holland-Elsevier, 1992
  • Advanced Correlation Analysis of Operators for the Traveling Salesman Problems by J. Dzubera and D. Whitley, appeared in Parallel Problem Solving from Nature-PPSN III. Y. Davidor, H.P. Schwefel and R. Manner, eds. pp. 68-77. Springer-Verlag, 1994.

    Neural Networks

  • Learning Topology-Preserving Maps Using Self-Supervised Backpropagation on a Parallel Machine , A. Ossen, TR-92-059, International Computer Science Institute, Berkeley, CA, September 1992.
  • A neural network for the Traveling Salesman Problem with linear time and space complexity .
  • Initializing the Hopfield-Tank Network for the TSP using a convex hull: A Computational Study, by Kedar S. Naphade and Dilek Tuzun, Proceedings of the Artificial Neural Networks in Engineering (ANNIE'95) conference, v. 5, pp. 399-404, St. Louis, November 1995.
  • A Neuro-Ethological Approach for the TSP: Changing Methaphors in Connectionist Models, by O. Miglino, D. Menczer and P. Bovet, Journal of Biological Systems, Vol. 2, Number 3, (1994), pp. 357-366.

    Space-filling heuristics

  • On the Spacefilling Curve Heuristic for the Euclidean Traveling Salesman Problem , by D. Bertsimas and M. Grigni.
  • A routing system based on spacefilling curves, by John Bartholdi.

    Approximation Algorithms

  • Approximation algorithms for planar traveling salesman tours and minimum-length triangulations , by K.L. Clarkson.
  • Faster Geometric k-point MST Approximation , by David Eppstein.
  • An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane, by N. Garg and D.S. Hochbaum. The authors present an O(log N)-approximation algorithm for a variant of the Euclidean Planar TSP, given n cities in the Euclidean plane and a bound B the problem is to find a cycle of length at most N that includes the maximum number of points.

    Polinomial-time Approximation Schemes (PTAS)

  • An Approximation Scheme for Planar Graph TSP , by M. Grigni, E. Koutsoupias and C. Papadimitriou.
  • Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems , by Sanjeev Arora, 1996.
  • Guillotine Subdivisions Approximate Polygonal Subdivisions: Part II -- A simple polynomial-time approximation scheme for geometric k-MST, TSP, and related problems , by J.S.B. Mitchell, April 30, 1996.
  • When Hamming Meets Euclid: the Approximability of Geometric TSP and MST, by Luca Trevisan, November 1996, (first verision August 1996).
  • Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems, by Sanjeev Arora, January 1997, (added to TSPBIB on May 2, 1997).
  • A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP, Sanjeev Arora, Michelangelo Grigni, David R. Karger and Philip Klein, to appear in SODA 1998 (added to TSPBIB on Dec. 5, 1997).

    Hardness of approximation

  • Bounded Queries, Approximations and the Boolean Hierarchy, by Richard Chang, Electronic Colloquium on Computational Complexity Report TR97-035 (accepted on Sep. 10, 1997).
  • On Approximation Hardness of Dense TSP and other Path Problems, by W. Fernandez de la Vega and M. Karpinski, ECCC Report TR98-024, May. 1998.

    Branch-and-Bound & Branch-and-Cut

  • Solving Traveling Salesman Problems using a Parallel Synchronized Branch and Bound Algorithm , by Claude G. Diderich and Marc Gengler.
  • Solving large-scale traveling salesman problems with parallel Branch-and-Cut , by M. Jünger and P. Störme.
  • Solving the Traveling Salesman Problem with a Distributed Branch-and-Bound Algorithm on a 1024 Processor Network by S. Tschöke, R. Lüling and B. Monien.
  • Provably Good Solutions for the Traveling Salesman Problem, by M. J"unger, G. Reinelt, S. Thienel, Preprint 94-31, IWR Heidelberg, 1994.
  • A Simple TSP-Solver: An ABACUS Tutorial, by Stefan Thienel, 1996.

    Computational Complexity ``Phase Transitions''

  • A study of complexity transitions on the asymmetric traveling salesman problem , by W. Zhang and R.E. Korf.
  • The TSP Phase Transition , by Ian Gent and Toby Walsh, Presented at the First Workshop on AI and OR, 1995. Research Report/95/178, Department of Computer Science, Univeristy of Strahclyde.
  • Criticality and Parallelism in Combinatorial Optimization by W.G. Macready, A.G. Siapas and S.A. Kauffman.

    General Issues

  • The Travelling Salesman Problem, an introductory page by Robert Dakin with some programs.
  • Mark's Thesis Page, by Mark Noschang, who has made good use of TSPBIB for his thesis work.

    Formulations

  • Formulations , by Kevin Ruland.
  • Graphical TSP: A Relaxation of the original problem , by Kevin Ruland.
  • TSP facets, from Christof & Reinelt, U.Heidelberg.
  • The Circuit Polytope: Facets, by P. Bauer.
  • Worst-case Comparison of Valid Inequalities for the TSP, M.X. Goemans.
  • A unified Approach to Simple Special Cases of Extremal Permutation Problems, R. E. Burkard, E. Cela, V. Demidenko, N. Metelski and G. Woeginger, Technische Universität Graz, SFB-Report 44, September 1995.
  • Local Properties of Some NP-Complete Problems, B. Codenotti and L. Margara.
  • All 0-1 Polytopes are Traveling Salesman Polytopes, by Louis J. Billera and A. Sarangarajan, Combinatorica (3) 1996, p175--188, Technical Report 1086, ORIE Cornell.

    Asymptotic expected length formulae - Average case complexity

  • The Euclidean Traveling Salesman Problem and a Space-Filling Curve. M. G. Norman and P. Moscato, Chaos, Solitons and Fractals, Vol. 6, pages 389-397, 1995.
  • Traveling Salesman Constants, by S. Finch, who maintains pages of the Favourite Mathematical Constants page, has created a page dedicated to our open conjecture regarding the MNPeano curve.
    S. Plouffe, creator of the Inverse Symbolic Calculator, has calculated the constant to 10,000 digits !
  • Worst-case bounds for subadditive geometric graphs, M. Bern and D. Eppstein, 9th ACM Symp. Comp. Geom., San Diego (1993) 183-188.
  • The random link approximation for the Euclidean traveling salesman problem, by N.J. Cerf, J. Boutet de Monvel, O. Bohigas, O.C. Martin and A.G. Percus, Published in Journal de Physique I 7:1 (1997) 117-136. (Note that this paper was previously referenced in TSPBIB as Scaling laws in the Euclidean and random link Traveling Salesman Problem, by N.J. Cerf, J. Boutet de Monvel, O. Bohigas, O.C. Martin and A.G. Percus, Preprint IPNO/TH 96-06).
  • Finite size and dimensional dependence of the Euclidean traveling salesman problem, by A.G. Percus and O.C. Martin, Published in Physical Review Letters 76:8 (1996) 1188-1191.
  • Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem, by David P. Williamson, Master's Thesis, MIT Computer Science, June 1990.
  • Asymptotic Experimental Analysis for the Held-Karp Traveling Salesman Bound, by D.S. Johnson, L.A. McGeoch and E.E. Rothberg, Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, 1996, pp. 341-350.
  • "Collapse" in the average case of combinatorial optimization problems, by Alexander Barvinok, 1996.

    Special Cases

  • The N-line Traveling Salesman Problem, by G. Rote, Technische Universität Graz, Institut für Mathematik B, Report 109, June 1991.
  • The Convex-Hull-and-Line Traveling Salesman Problem: A Solvable Case, by V. G. Deineko, R. van Dal, and G. Rote, Technische Universität Graz, Institut für Mathematik B, Report 233, September 1992.
  • Polynomially Solvable Cases of the Traveling Salesman Problem and a New Exponential Neighbourhood, by R.E. Burkard and V.G. Deineko, Technische Universität Graz, SFB-Report 1, July 1994.
  • Sometimes Travelling is Easy: The Master Tour Problem, V.G. Deineko, R. Rudolf and G.J. Woeginger, Technische Universität Graz, SFB-Report 13, December 1994.
  • Three Easy Special Cases of the Euclidean Travelling Salesman Problem, by V.G. Deineko, R. Rudolf, J.A.A. van der Veen, G.J. Woeginger, Technische Universität Graz, SFB-Report 17, January 1995.
  • The Traveling Salesman Problem on Permuted Monge Matrices, R.E. Burkard, V.G. Deineko and G.J. Woeginger, Technische Universität Graz, SFB-Report 31, May 1995.
  • Sequencing Jobs that Require Common Resources on a Single Machine: A Solvable Case of the TSP, J.A.A. van der Veen, G.J. Woeginger and S. Zhang, Technische Universität Graz, SFB-Report 21, March 1995.
  • The Quadratic Assignment Problem with an Anti-Monge and A Toeplitz Matrix: Easy and Hard Cases, R. E. Burkard, E. Cela, G. Rote and G. Woeginger, Technische Universität Graz, SFB-Report 34, June 1995.
  • Long-Chord-Free and Fence-Free Tours for the Travelling Salesman Problem, V.G. Deineko and G.J. Woeginger, Technische Universität Graz, SFB-Report 46, October 1995.
  • Well-Solvable Special Cases of the TSP: A Survey, R.E. Burkard, V.G. Deineko, R. van Dal, J.A.A. van der Veen and G.J.~Woeginger, Technische Universität Graz, SFB-Report 52, December 1995.
  • Angle-Restricted Tours in the Plane, S.P. Fekete and G.J. Woeginger, Technische Universität Graz, SFB-Report 62, March 1996.
  • On the TSP with a Relaxed General Distribution Matrix, V.G. Deineko, Technische Universität Graz, SFB-Report 100, January 1996.
  • Efficiently Solvable Special Cases of Hard Combinatorial Optimization Problems, R.E. Burkard, Technische Universität Graz, SFB-Report 105, February 1997.

    Fractal Instances

  • The Euclidean Traveling Salesman Problem and a Space-Filling Curve. M. G. Norman and P. Moscato, Chaos, Solitons and Fractals, Vol. 6, pages 389-397, 1995.
  • Using L-Systems to generate arbitrarily large instances of the Euclidean Traveling Salesman Problem with known optimal tours. A. Mariano, P. Moscato and M.G Norman, ``Anales del XXVII Simposio Brasileiro de Pesquisa Operacional'', Vitoria, Brazil, 6-8 Nov. 1995.
  • An Analysis of the Performance of Traveling Salesman Heuristics on Infinite-Size Fractal Instances in the Euclidean Plane. P. Moscato and M.G. Norman, submitted, Oct. 1994.
  • Worst-case bounds for subadditive geometric graphs, M. Bern and D. Eppstein, 9th ACM Symp. Comp. Geom., San Diego (1993) 183-188.
  • The Dimension of the Brownian Frontier is Greater than 1, by C. Bishop, P. Jones, R. Pemantle, and Y. Peres, Institute for Mathematical Sciences, Stony Brook, Preprint IMS95-9, (1995). Thanks to Melvyn Laffitte, who has pointed out this reference.
  • Arbitrarily large planar ETSP instances with known optimal tours, by A. Mariano, P. Moscato, and M.G. Norman, expanded version of the paper presented at Vitoria, ES, Brazil, 1995. Paper accepted in the journal ``Pesquisa Operacional''.

    TSP Games

  • On approximately fair cost allocation in Euclidean TSP games , by U. Faigle and S. P. Fekete.

    Physical Optimization and the TSP

  • Physical Optimization .
  • Elastic Net Method for the TSP, by Alexander Budnik and Tatyana Filipova.

    Asymmetric Traveling Salesman Problem

  • A study of complexity transitions on the asymmetric traveling salesman problem , by W. Zhang and R.E. Korf.
  • Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem, by L.M. Gambardella and M. Dorigo, Proceedings of ML-95, Twelfth International Conference on Machine Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 252-260, 1995.
  • A Complete and irredundant linear description of the asymmetric traveling salesman polytope on 6 nodes , L. Verge, RR-1791, 1992.
  • When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem ? , by Alan Frieze, Richard Karp and Bruce Reed.
  • Sequencing Jobs that Require Common Sources on a Single Machine: A Solvable Case of the TSP, by. J.A.A. Van Der Ween, G.J. Woeginger and S. Zhang.
  • The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem, by Thomas Stützle and Holger Hoos, (to appear - ICEC 1997).
  • Near-optimal Intraprocedural Branch Alignment, by C. Young, D. S. Johnson, D. R. Karger, and M. D. Smith, Proceedings 1997 Symp. on Programming Languages, Design, and Implementation, to appear. From Johnson's page we can read: ``Covers an application of the asymmetric TSP to code optimization. Instances of the asymmetric TSP were solved using the symmetric algorithm ``Iterated 3-Opt'' by means of the NP-completeness transformation from the asymmetric to the symmetric TSP.''
  • All 0-1 Polytopes are Traveling Salesman Polytopes, by Louis J. Billera and A. Sarangarajan, Combinatorica (3) 1996, p175--188, Technical Report 1086, ORIE Cornell.

    TSP with distances 1 and 2, TSP(1,2)

    The TSP(1,2) involves the complete graph between the cities where all edge weights are either 1 or 2. Papadimitriou and Yannakakis have shown that this problem is hard for MAX-SNP. Khanna, Motwani, Sudan and Vazirani have proved that a 4-local search algorithm using the oblivious weight function achieves a 3/2 performance ratio for this problem. Non-Oblivious Local Search is discussed in:

  • On Syntactic versus Computational views of Approximability, by Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani, ECCC Report TR95-023, accepted on May 17, 1995.

    see also the new results in

  • When Hamming Meets Euclid: the Approximability of Geometric TSP and MST, by Luca Trevisan, November 1996.
  • On the Complexity of Approximating Euclidean Traveling Salesman Tours and Minimum Spanning Trees, by Gautam Das, Sanjiv Kapoor and Michiel Smid.
  • On Approximation Hardness of Dense TSP and other Path Problems, by W. Fernandez de la Vega and M. Karpinski, ECCC Report TR98-024, May. 1998.
  • Graph Properties that Facilitate Travelling, by Dimitris Fotakis and Paul Spirakis, ECCC Report TR98-031, June 1998.

    K-template Traveling Salesman Problem

  • An O(n log(n)) Algorithm for the K-template Traveling Salesman Problem , by J.A.A. Van Der Veen, G.J. Woeginger and S. Zhang.

    Prize-Collecting Traveling Salesman Problem (PCTSP)

    In the standard TSP problem you have a map and a starting point and would like a route that visits all the cities in as short a total distance as possible. But, what if you only need to visit, say, k out of the n cities? In this case, before even deciding on the route, there is the more fundamental question: which k cities do I visit in the first place? This is the most basic case of the PCTSP. Here's a similar question: the Minimum Spanning Tree problem has many simple algorithms, but what if you only need a tree that spans k of the n vertices --- which vertices should you include so that you get the shortest tree? Both of these problems are NP-hard.

  • Approximation algorithms for the k-MST Problem and Prize-Collecting Traveling Salesman Problem, by Avrim Blum, R. Ravi and Santosh Vempala, gives an O(log^2 k) approximation algorithm for these problems. They now have a new constant factor approximation (current constant: 17).
  • Improved approximation guarantees for minimum-weight k-trees and Prize-collecting salesmen , by Baruch Awerbuch, Yossi Azar, Avrim Blum and Santosh Vempala.

    The Euclidean Traveling Salesman Selection Problem

    In this paper , by A. Hamacher and C. Moll, a generalization of the TSP, called the traveling salesman selection problem (TSSP) is introduced. The problem is restricted to the Euclidian case where the TSP can be formulated as follows: Given n cities in the plane and their Euclidian distances, the problem is to find the shortest TSP-tour, i.e. a closed path visiting each of the n cities exactly once. In addition to that the TSSP specifies a number k < n of cities and the shortest TSP--tour through any subset of k cities shall be found. Existing heuristics are based on approximations for the k-Minimal Spanning Tree to find the node cluster containing the shortest k-tour. Unlike many related problems, the TSSP does not include a depot that has to be visited by the k-tour. The main purpose of this paper is the presentation of an exact algorithm for the TSSP. It is based on a geometrical procedure searching for all clusters of about k nodes which can contain the shortest k-tour. These clusters are the start set for a branch and bound procedure that determines the shortest k-tour in each cluster and therefore the exact solution of the TSSP. A dynamic programming approach for calculating shortest t-chains is used to obtain a lower bound for the branch and bound algorithm.

    Circulant Travelling Salesman Problem

    The Circulant Travelling Salesman Problem (CTSP) is the problem of finding a minimum weight Hamiltonian cycle in a weighted graph with circulant distance matrix. The computational complexity of this problem is not known. In fact, even the complexity of deciding Hamiltonicity of the underlying graph is unkown.

  • Hamiltonian Cycles in Circulant Digraphs with Two Stripes, Q. F. Yang, R. E. Burkard, E. Cela, G. J. Woeginger, Technische Universität Graz, SFB-Report 20, March 1995.

    On-line Traveling Salesman Problem

  • Serving Request with On-line Routing , G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie y M. Talamo, in Proceedings of the Fourth Scandinavian Workshop on Algorithm Theory (SWAT'94), Aarhus, Dinamarca, July 1994, LNCS 824, Springer Verlag.
  • Competitive Algorithms for the Traveling Salesman, G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie y M. Talamo, in Workshop on Algorithms and Data Structures (WADS'95).

    Time-dependent TSP

  • An Exact Solution Approach for the Time-Dependent Traveling Salesman Problem, b