Analytics Stories

CHAPTER 53How Does the UPS Driver Know the Order to Deliver Packages?

Tom Vanderbilt (author of the great book Traffic, discussed in Chapter 47, “Red Light, Green Light, or No Light?”) tells us that if each UPS driver drove one less mile per year to deliver their packages, UPS would save $50 million (see longitudes.ups.com/unhappy-truckers-and-algorithms/#:~:text =). Vanderbilt also tells us that on an average day, a UPS driver delivers 130 packages. In theory (but not in practice), determining the order in which packages should be delivered that results in the fewest miles traveled is an example of the famous Traveling Salesperson Problem (TSP).

To define the TSP, suppose you are given a starting city and a list of cities to visit. You know the distance between each pair of cities, and you need to visit each city exactly once and return to the starting point. What sequence of visiting the cities requires the smallest distance?

In this chapter, we will show how Excel can quickly solve a 30-city TSP. You will also learn about the struggles UPS had in their attempts to use the TSP to help drivers deliver packages. A University of Waterloo web page (www.math.uwaterloo.ca/tsp/index.html) contains a lot of great information on the TSP, including maps of solutions to many TSPs, including an optimal pub crawl through 49,687 pubs in the United Kingdom. To date, the largest TSP solved involved 85,900 cities (see www.math.uwaterloo.ca/tsp/pla85900/index.html).

Why Is the Traveling ...