Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
28. August 2009 17:54

In the current issue of OR/MS Today, I came across this nice optimization puzzle, “Bridges to Somewhere”. There are these two islands. Five people A, B, C, D and F live on the first island, and need to commute to work to the second island. Individual A lives in the spot marked A, and needs to go to spot A on the second island – and so on for the 4 others. People can travel only vertically and horizontally (no diagonals), and will always take the shortest path available.

There is currently no bridge between the islands, but a budget for 2 bridges has been approved (the island just received a stimulus package). There are 4 bridge proposals to chose from (One, Two, Three and Four on the map). Which 2 bridges should be built to minimize the travel distance of the population?

Before trying to figure out which 2 bridges are best, I thought it would be interesting to investigate a simpler problem: if you could build one bridge anywhere, where should you build it?

There are a number of ways you could resolve this using Excel; I will illustrate how to find the best solution, using Excel Data Tables.

What makes a bridge better or worse for an islander?

see more Fail Blog

First, note that no matter where the bridge is located, C (who I will call Charlie) needs to travel the same distance horizontally (8 squares, or 7 moves). What this means is that the horizontal position of each individual doesn’t matter: the only thing which matters is where the bridge is located, on the vertical axis.

Then, any bridge located in the yellow rectangle is optimal for Charlie, who needs to travel only 4 squares down, and 8 squares right. Bridges which are located outside the bounds of the rectangle require extra vertical travel – in our example, an extra 3 squares up and 3 squares down.

Working the math, you can check that the extra travel a bridge requires from Charlie can be written as

Extra Travel = vertical distance from home to brige + vertical distance from work to bridge – vertical distance from home to work.

In our example, the Good bridge has an extra travel of 3+1-4=0 (no extra travel required), and the Bad bridge has an extra travel of 3+7-4=6.

## The best bridge

Using this formula, we can now compute the extra cost of a bridge for each islander, and set up a worksheet to compute the total extra travel for each possible bridge.

In cell B1, we enter the vertical position of the bridge, and name the range “Bridge” (I am using the coordinates that are on the first map).

In range B4:C8, we enter the vertical position of the home and workplace of each of the 5 islanders.

In columns D and E, we compute the vertical distance from home and work to the bridge as shown, and we compute the vertical distance from work to home in column F.

In column G, we compute the extra travel as G4 = D4+E4-F4, and we compute the total extra travel in G9. Entering various values in B1 will show you the value of each possible location of the bridge.

You could now use a variety of approaches to find the best solution, from trying out all solutions manually, to using the solver. I’ll illustrate how you could find the optimal solution using Data Table, one of the What-If Analysis features of Excel.

In a nutshell, a Data Table allows you to specify a range of values, and record the result of a formula in your worksheet using each of them as an input.

What we will do here is try every possible location for a bridge, from 1 to 13, and record the Total Extra Travel for each scenario. First, let’s create the range of locations we want to try out:

Then, one column to the right, and one row above the input values, let’s set the formula we want to evaluate. In this case, I want to see the impact on the total extra travel, so that’s what I will set it equal to.

Next, select the range containing your input values and the formula:

Almost there! Let’s go to Data Table in What-If Analysis…

Your input data is organized in columns, so use “Column Input Cell”, and select B1, the bridge location, which is the input value you want to replace.

Press OK, and voila! Range B12:B24 has now been filled with data, which are the extra cost computed for each possible bridge value.

If you had one bridge to build only, you should locate it at position 7 or 8, which have the lowest extra travel for the population. Neat, no? In this example, this approach is probably not much faster that trying out various solutions by hand, but if there were more possible locations (and a less obvious solution…), this would prove very handy.

Next time, we’ll see how we would go about figuring out which 2 bridges are best!

8/18/2009 6:30:23 AM #

The Data Table approach may not be much faster here, as you point out. But if you have any assumption that you want to change, you only have to change that cell and recalc the data table, not manually go through all of the bridge options again.

8/18/2009 1:48:07 PM #

Very good point, John! If for instance the location of the 5 individuals were changed, a manual search would require to re-compute every scenario manually, whereas the data table is updated automatically.

9/7/2009 1:10:36 PM #

The PuzzlOR

The PuzzlOR

3/15/2010 12:21:32 PM #

Hi Mathias,

I can see that Maths is in your name
I had just learnt about using Data Table and was browsing something about it. Thus came to your site.  I was glad that you had converted such a puzzle to the way you have analysed it.  Thanks for sharing it. Now this will help me triggering such thoughts when i get similar problems...

Thanks
Joe

3/17/2010 7:22:42 AM #

Hi Joe,
Thank you for the positive feedback, and I am glad this post stimulated your ideas!
Weirdly enough, your comment about my first name may be the illustration of an odd phenomenon: apparently, people who have chosen a certain profession are much more likely to have a first name that begins with the same letters. For instance, your dentist is much more likely to be named "Dennis" than a random person in the street...
www.stat.columbia.edu/.../why_its_not_so.html

3/18/2010 1:58:56 AM #

You can also optimise for the total dist travelled rather than the extra dist travelled..
I mean G4 = D4+E4.

11/30/2010 11:54:20 PM #

Pingback from copious-systems.com

RealTime - Questions: "In excel: count number of times when a value appears in one column and the cell next to it is less than 2?"

7/7/2011 10:13:02 AM #

Hey Joe thanks that really helped me a lot

7/7/2011 10:16:10 AM #

thats a really good way to find an optimal solution with excel, thanks!

• Comment
• Preview

#### Need help with F#?

The premier team for
F# training & consulting.