Fundamentals of Supply Chain Theory, 2nd Edition

Chapter 10 The Traveling Salesman Problem

10.1 Supply Chain Transportation

Transportationis arguably the largest component of total supply chain costs. In 2017, United States businesses spent $966 billion moving freight along roads, rails, waterways, air routes, and pipelines (Council of Supply Chain Management Professionals, 2018a). Even small improvements in transportation efficiency can have a huge financial impact. A transportation system has many aspects to optimize, from mode selection to driver staffing to contract negotiations, and mathematical models have been used for all of these issues and more. In this chapter and the next, we cover one important aspect of the transportation‐related decisions a firm must make, namely, routing vehicles among the locations they must visit.

We discuss the famous traveling salesman problem (TSP) in this chapter. The TSP is important not only because of its practical utility but also because, over the past several decades, the study of the TSP has spurred many fundamental developments in the theory of optimization itself. Then, in Chapter 11, we discuss the vehicle routing problem (VRP), which generalizes the TSP by adding constraints that necessitate the use of multiple routes.

10.2 Introduction to the TSP

10.2.1 Overview

The TSP involves finding the shortest route through n nodes that begins and ends at the same city and visits every node. The TSP is perhaps the best‐known combinatorial optimization problem and has been ...