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.

email: mos@ada.info.unlp.edu.ar
email: pmoscato@volta.ing.unlp.edu.ar

TSP Instances

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

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.

    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.
  • An ATSP code, by Glenn Dicus, Bart Jaworski and Joseph Ou-Yang.
  • A TSP program in Parlog, by Steve Gregory.

    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 , by C. Voudoris and E.P.K. Tsang.
  • 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.

    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. 1993.
  • 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.

    Ant Colony Optimization

  • 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.

    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.

    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.

    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).

    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 .

    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.

    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.

    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.

    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.

    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.

    Asymptotic expected length formulae

  • 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.
  • 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.
  • Analysis of the Held-Karp Heuristic for the Traveling Salesman Problem, by David P. Williamson, Master's Thesis, MIT Computer Science, June 1990.

    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.

    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.

    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.
  • 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.

    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.

    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, by Russ J. Vander Wiel and Nikolaos V. Sahinidis, accepted in Naval Research Logistics, March 1996.

    Pablo Moscato
    Comision de Investigaciones Cientificas de la Provincia de Buenos Aires
    C.C. 75
    1900 La Plata
    ARGENTINA
    email: mos@ada.info.unlp.edu.ar
    email: pmoscato@volta.ing.unlp.edu.ar

    Click here for my complete address and contact information.

    Page created Feb. 29, 1996
    Last update August 8, 1996