2.3 2.2 Traveling Salesman Problem

47

If the only benefit were saving money and time in vacation planning, the difficulty of finding a minimum-cost Hamiltonian circuit in a complete graph with n vertices for large values of n would not be of great concern. However, the problem we are discussing is one of the most common in operations research, the branch of mathematics concerned with getting governments and businesses to operate more efficiently. This problem is usually called the traveling salesman problem (TSP) because of its early formulation.

Traveling Salesman Problem (TSP) DEFINITION

The traveling salesman problem (TSP) involves finding the trip of minimum cost that a salesman can make to visit the cities in a sales territory once and only once (represented by a complete graph with weights on the edges), starting and ending the trip in the same city.

Many situations require in essence solving a TSP:

  1. Physical records generated at automated teller machine (ATM) locations—as backup in case of failure of the electronic systems—must be picked up periodically.
  2. A local ethnic fast-food restaurant must hire someone to deliver the food quickly and while it is still hot, before returning to the restaurant for the next batch of orders to be delivered.
  3. A limousine service with a van located at an airport must pick up five customers and deliver them to the airport in time to catch their flights.
  4. In drilling holes in a series of plates, the drill press operator (perhaps a robot) must drill the holes in a predetermined order.
  5. The electric (or gas) company needs to design a route for its meter readers.
  6. A minibus must pick up six day campers, deliver them to camp, and return them home later in the day.
  7. The telephone company wishes to pick up the coins from its pay telephone booths. (To avoid the high cost of picking up these coins, phone companies in many countries have adopted a system that uses prepurchased phone cards to operate phones. This means that there are no coins to collect.) Due to the increased use of cell phones, fewer pay phones are available.
  8. A lobster fisherman has set out traps at various locations and wishes to pick up his catch.

Perhaps surprisingly, TSPs are also solved regularly in the design of computer chips. The components must be located so that the machines involved in the assembly can insert them on the chips as efficiently as possible. Because many chips are manufactured, even a small improvement in the time needed to make a chip can save a lot of money.

The meaning of cost can vary from one formulation of a TSP to another. We can measure cost as distance, airplane ticket prices, time, or any other factor that is to be optimized. In many situations, the TSP arises as a subproblem of a more complicated problem. For example, a supermarket chain may have a very large number of stores to be served from a single large warehouse. If there are fewer trucks than stores, the stores must be grouped into clusters so that one truck can serve each cluster. If we then solve the TSP for every truck, we can minimize total costs for the supermarket chain. Similar vehicle-routing problems—for dial-a-ride services that transport senior citizens to activity centers, for example, or that deliver children to their schools or camps—often involve solving the TSP as a subproblem.