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