Excel Optimization Problems: An Example

Mail-box route design

Having previously worked as a postal courier—and having often wondered if the senior management used any kind of cluster optimization model for designing pick-up routes—I once casually asked a friend (who has a Phd in mathematics from Berkeley) about the possibility of deriving an optimal route for emptying mail boxes and collecting office pick-up points. Probably because of the way I framed the problem he told me it was not possible and that it was essentially the “post-round” problem. But last year while studying probability and permutations I thought of a model that might work.

A similar problem

In Provo I used to go and play “pick up” soccer (football) with the Latinos or whoever was playing. The problem was that there were a number of local areas where a game might be going on—and so if you weren’t in the know you just had to scout around until you found a game to join. Maybe I could have saved some time if I’d conceived of this model (below) earlier. Here’s what I have come up with. (I suppose similar models could be applied to various types of problems).

1.      Think of all the locations and then map them to a matrix like the one below

Basically I just considered the driving times (in minutes) between all the locations where there may be a game going on that I could join. I have to start and finish at “home”. In this case it takes the same number of minutes to go from one place to the next in both directions (i.e. “home” to “rock canyon park” = “rock canyon park” to “home”). I’ve indexed each location with a number (1 – 7).

picture72

 

2.      Think about permutations

In this case I always leave from home, and I’ll just say I always return to home (e.g. for a shower). So, I’ll always start at “1” and end at “1”. That leaves a string of six other locations I can scout out in any order I want. How many possible ways can I scout out these locations? Using probability theory’s function or Excel’s =PERMUT(6,6), I get 720 possible combinations. If I can generate a list of all the possible permutations—i.e. {1,2,3,4,5,6}, {1,2,3,4,6,5}, {1,2,3,5,4,6}… then I can link it to the matrix to find the shortest route.

3.      Generate the permutations

The only way I found to do this efficiently is to use VBA code. The following code that I got from walkenbach’s site worked great here. What I got is a list of all 720 possible permutations for the numbers 2,3,4,5,6,7. The reason I used digits 2 – 7 is because 1=home, which is always starting and ending the sequence—so its position is always fixed in the sequence. The list is 720 rows long and looks like this:

picture81

… and so on.

4.      Link each sequence to the time distance matrix (above)

The next thing to do is tack on the home element, creating an permutations array of all possible location sequences…

picture9

… and then link each possible journey to the original distance matrix. To do this I used =VLOOKUP(location#1,initial matrix table,location#2+2,FALSE) to create another array to the right of the permutations array, where “location#1” is the first location in the permutations array and “location#2” is the subsequent location in the permutations array. To see how the formula works for the first cell in this new array consider the following screen shot from Excel:

picture4

You can see that D13 is “home”, the table reference for VLOOKUP is the initial travel time matrix, and since what we want to refer to is the distance between the initial location (“home”) and the next location in the sequence (“2” or “hospital field”) we use E13+2 as the column reference. (The reason for the “+2” here is so that VLOOKUP refers to the correct corresponding column location reference—since it recognizes the first column in the selected [green] array as “1”).

5.      Summing all possible travel routes

Dragging to the right and then down produces a series of calculations showing the distances between each stage of each corresponding permutation. All that is left to do now is sum these distances for each permutation to get a “total scouting time” metric for each scenario. You can then simply sort these (A – Z) to see which route is shortest.

picture101

6.      Some complications

This is not an application where we necessarily need to visit every stop. Basically the goal is to find a game as quickly as possible—so perhaps when deciding on a route more weight should be allocated to the initial stops. This can be done by building a formula to the right that incorporates that consideration (I’ve done so here, where more weight is allocated to the time taken in the initial three stops than the subsequent ones—the result is a new metric to minimize).

picture6

There may also be some locations that are better quality, or where there is a higher probability that people are playing there. So these things could be built in also or just considered intuitively. This technique could easily be replicated for other excel optimization problems.

One thought on “Excel Optimization Problems: An Example”

Share your thoughts below :)