David Neto's TSP reading list

Updated May 30, 1998
New May 30, 1998: Added a link to Mark Noschang's survey paper.
New May 1, 1997: Added a link to the TSPBIB and TSPLIB home pages.

If you're going to do any research into solving the traveling salesman problem (TSP), then you should know about these references. They are in Bibtex format, which is human-readable without too much work.

New 1998/5/30 I just found Mark Noschang's online survey paper about the TSP. It looks pretty good.

An excellent introduction to the TSP in general is the following:

@book { LawlerLRS1985,
    editor = {E.~L.~Lawler and J.~K.~Lenstra and A.~H.~G.~Rinnooy Kan
        and D.~B.~Shmoys},
    title = "The Traveling Salesman Problem",
    publisher = "John Wiley \& Sons Ltd.",
    year = 1985

The best results so far in solving TSPs exactly are in the following sources:

@unpublished{ ApplegateBixbyChvatalCook1994a,
    fullauthor = {David Applegate and Robert Bixby and Va\u{s}ek Chv\'{a}tal
        and William Cook},
    author = {D.~Applegate and R.~Bixby and V.~Chv\'{a}tal and W.~Cook},
    title = "Finding cuts in the {TSP} (a preliminary report)",
    month = "August",
    year = 1994,
    note = "Published electronically, at
    email = "David Applegate is david@research.att.com"
@unpublished{ ApplegateBixbyChvatalCook1994b,
    fullauthor = {David Applegate and Robert Bixby and Va\u{s}ek Chv\'{a}tal
        and William Cook},
    author = {D.~Applegate and R.~Bixby and V.~Chv\'{a}tal and W.~Cook},
    month = "August",
    year = 1994,
    note = "Published electronically, at
    email = "David Applegate is david@research.att.com"

The best approximate solutions are found by the Lin-Kernighan heuristic, especially as implemented in Johnson et.al.'s work:

@article { LinKernighan1973,
    author = "S.~Lin and B.~W.~Kernighan",
    title = {An effective heuristic algorithm for the traveling salesman
    journal = "Operations Research",
    volume = 21,
    year = 1973,
    pages = "498--516"

@inproceedings { Johnson1990,
    fullauthor = "David S.~Johnson",
    author = "D.~S.~Johnson",
    title = "Local optimization and the traveling salesman problem",
    booktitle = "ICALP '90",
    year = 1990,
    note ={Proceedings of the $17^{th}$ Colloquium on Automata, Languages, and
    publisher = "Springer-Verlag",
    pages  = "446-461"
@unpublished { JohnsonMcGeoch1995,
    fullauthor = "David S.~Johnson and Lyle A.~McGeoch",
    author = "D.~S.~Johnson and L.~A.~McGeoch",
    title = {The {Traveling} {Salesman} {Problem}:
            {A} {Case} {Study} in {Local} {Optimization}},
    year = 1995,
    note = {Draft of November 20, 1995.  To appear as a chapter in the book
        {\sl Local Search in Combinatorial Optimization}, E.~H.~L.~Aarts
        and J.~K.~Lenstra (eds.), John Wiley and Sons, New York.}

This last reference can temporarily be found at: ftp://dimacs.rutgers.edu/pub/dsj/temp/chap.ps.Z

The Lin-Kernighan heuristic is suitable for any symmetric TSP.

For a comparison of approximate TSP algorithms on some standard data, see Reinelt's work:

@article { Reinelt1991,
	fullauthor = "Gerhard Reinelt",
	author = "G.~Reinelt",
	title = "{TSPLIB} --- A Traveling Salesman Problem Library",
	journal = "ORSA Journal on Computing",
	year = 1991,
	volume = 3,
	number = 4,
	pages = "376--384"

@book { Reinelt1994,
	fullauthor = "Gerhard Reinelt",
	author = "G.~Reinelt",
	title = {The traveling salesman: Computational solutions for {TSP}
	publisher = "Springer {V}erlag",
	year = 1994,
	isbn = "0-387-58334-3",
	note = "LNCS 840"

Ton Volgenant has published a Pascal program for exactly solving Euclidean TSPs of up to about 200 cities.

@article { Volgenant1990,
	fullauthor = "Ton~Volgenant",
	author = "T.~Volgenant",
	title = "Symmetric {TSP}s ({ORSEP} program)",
	journal = "European Journal of Operational Research",
	year = 1990,
	volume = 49,
	pages = "153--154",
	smail = {Operations research group, 
		Department of Actuarial Sciences and Econometrics,
		Roetersstraat 11, 1018 WB Amsterdam,
		The Netherlands,
		tel 020 5254219 (4217)}

On the web, look at The TSPBIB Home Page. I haven't looked at it much, but what I've seen looks good.

You should also know about the TSPLIB home page.

Back to David Neto's research page
Back to David Neto's home page