David Neto's TSP reading list

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
        ftp://netlib.att.com/netlib/att/math/applegate/TSP/tsp\_aug23.ps.Z",
    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
        ftp://netlib.att.com/netlib/att/math/applegate/TSP/proofs",
    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
        problem},
    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
        Programming},
    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.}
}

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}
		applications},
	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)}
}

You should also know about the TSPLIB home page.