A Short History of the Traveling Salesman Problem

The Traveling Salesman Problem (TSP) is arguably the most famous problem in combinatorial optimization. This problem has a rich history and its study has led to several major theoretical and algorithmic developments in operations research. These include local search, branch-and-bound, polyhedral theory and branch-and-cut. This presentation summarizes some of the major developments in the history of the TSP. Its starts from early references found in the work of Euler, and ends with the development of Concorde. It outlines the most important contributions in the recent history of the TSP.