The Traveling Salesman Problem

Rainer E. Burkard

ABSTRACT

This article surveys traveling salesman problems (TSPs). After stating different formulations for the traveling salesman problem, some applications are outlined. Then exact solution procedures like branch and bound, as well as branch and cut, are sketched and heuristics for the TSP are surveyed. Finally, special cases of the TSP that can be solved in polynomial time are addressed.