The Traveling Salesman Problem

Abstract

This chapter covers one important aspect of the transportation-related decisions a firm must make, namely, routing vehicles among the locations they must visit. It discusses the famous traveling salesman problem (TSP). The TSP is perhaps the best-known combinatorial optimization problem and has been intensely studied by researchers in supply chain management, operations research, computer science, and other fields. The chapter also discusses exact algorithms for the TSP, and construction heuristics for the TSP. The chapter considers improvement heuristics for the TSP that begin with a complete tour and perform operations on it to try to make it shorter. The first branching algorithm for the TSP was the branch-and-bound algorithm proposed by Little et al.; in fact, their paper was the first to introduce the term branch-and-bound. The heuristic finds an Eulerian tour and converts it to a TSP tour by shortcutting, exactly as in the minimum spanning tree heuristic.