643369cvr.inddWe’re excited to announce that Microsoft Excel 2010: Data Analysis and Business Modeling, by Wayne L. Winston (ISBN 9780735643369; 720 pages) is now available for purchase!  

In today’s post, please enjoy an excerpt from Chapter 37, “The Travelling Salesperson Problem,” which describes how Excel can help solve sequencing problems and traveling salesperson problems (TSP).

Chapter 37 - The Traveling Salesperson Problem

 

Questions answered in this chapter:

How can I use Excel to solve sequencing problems?

How can I use Excel to solve a traveling salesperson problem (TSP)?

 

Answers to This Chapter’s Questions

 

· How can I use Excel to solve sequencing problems?

Many business problems involve the choice of an optimal sequence. Here are two examples:

In what order should a print shop work on 10 jobs to minimize the total time by which jobs fail to meet their due dates? Problems of this type are called job shop scheduling problems.

A salesperson lives in Boston and wants to visit 10 other cities before returning home. In which order should he visit the cities to minimize the total distance he travels? This is an example of the classic traveling salesperson problem (TSP).

Here are two other examples of a TSP:

A UPS driver needs to make twenty stops today. In which order should she deliver packages to minimize her time on the road?

A robot must drill 10 holes to produce a single printed circuit board. Which order of drilling the holes minimizes the total time needed to produce a circuit board?

The new and improved Excel 2010 Solver makes tackling sequencing problems very easy. Simply choose Evolutionary Solver, select your changing cells, and then select Dif. Setting the All Different option ensures that if you have 10 changing cells, Excel will assign the values 1, 2, …10 to the changing cells with each value occurring exactly once. In general, if you select a range of n changing cells to be different, Excel ensures that the changing cells assume the values 1, 2, …, n, with each possible value occurring exactly one. Let’s see how to use the Dif option to easily solve a traveling-salesperson problem.

· How can I use Excel to solve a traveling salesperson problem (TSP)?

Let’s try and solve the following problem.

Willie Lowman is a salesman who lives in Boston. He needs to visit each of the cities listed in Figure 37-1 and then return to Boston. In what order should Willie visit the cities to minimize the total distance he travels? Our work is in file Tsp.xlsx.

clip_image002

Figure 37-1 Data for TSP

To model this problem in a spreadsheet, you should note that any ordering or permutation of the numbers 1–11 represents an order for visiting cities. For example, the ordering 2-4-6-8-10-1-3-5-7-9-11 can be viewed as traveling from Boston (City 1) to Dallas (City 3), to LA (City 5), and finally to SF (City 10) before returning to Boston. Since the ordering is viewed from the location of City 1, there are 10! = 10´9´8´7´6…´2´1 = 3,628,800 possible orderings for Willie to consider.

To begin you need to determine the total distance traveled for any given order for visiting the cities. The INDEX function is perfect for this situation. Recall from Chapter 4, “The INDEX Function,” that the syntax of the INDEX function is INDEX(Range, row#, column#). Excel looks in the range of cells named Range and picks out the entry specified in row# and column# of Range. In this case, you can use the INDEX function to find the total distance traveled in visiting all cities.

I began by entering in the range F16:F26 in order of the integers 1–11. Next, I named the range G4:Q14 distances, and entered in cell G16 the formula INDEX(distances,F26,F16). This formula determines the distance between the last city listed (in F26) and the first city listed (in F16). Next I enter the formula INDEX(Distances,F16,F17) in cell G17 and copy it to the range G18:G26. In G17 the formula computes the distance between the first and second city listed, and so on. Now I can compute the target cell (total distance traveled) in cell G27 with the formula SUM(G16:G26).

At this point, I’m ready to invoke the Evolutionary Solver. I choose to minimize cell G27, and then I click Add Constraint and select the range F16:F26. Then I select Dif for All Different. This ensures that Solver always keeps the changing cells in the selected range, assuming the values 1, 2, up to 11. Each value will occur exactly once. The Solver Parameters dialog box is shown in Figure 37-2. Before running Solver, I increased the Mutation rate to .5.

clip_image004

Figure 37-2 Solver set up for a traveling salesperson problem.

The minimum possible distance to travel is 8,995 miles. To see the order in which the cities are visited, simply begin in the row with a 1 (corresponding to Willie’s home, Boston) and follow the cities in the listed sequence. The cities are visited in the following order: Boston-NY-Pittsburgh-Chicago-Denver-Seattle-SF-LA-Phoenix-Dallas-Miami-Boston. There are many other sequences for visiting the cities that also yield the minimum total travel distance of 8,995 miles.

 

Problems

 

1. A small job shop needs to schedule six jobs. The due date and days needed to complete each job are given below. In what order should the jobs be scheduled to minimize the total days the jobs are late?

Job

Processing time

Due date(measured from today)

1

9

32

2

7

29

3

8

22

4

18

21

5

9

37

6

6

28

2. The file Nbamiles.xlsx contains the distance between all NBA arenas. Suppose we live in New York and want to visit each arena once and return to New York. In what order should we visit the cities to minimize total distance traveled?

3. Suppose now we live in Atlanta and we are driving 29 General Managers. Each GM wants to return to his home. Each time we visit an arena we drop a person off at their home arena. In what order should we drop off the GM’s in order to minimize the total distance traveled by the GM’s.

4. In the Willy Loman Problem suppose we must visit NY immediately after Denver. What is the solution to the problem?