Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 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.

image

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.

Good bridges, bad bridges

What makes a bridge better or worse for an islander?

 failbridge.jpg
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.

image

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.

image

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:

image 

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.

image

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

image

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

image

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.

image

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

image 

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!

Comments

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

Jon Peltier

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.

Jon Peltier United States | Reply

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

Mathias

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.

Mathias | Reply

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

trackback

The PuzzlOR

The PuzzlOR

Clear Lines Blog | Reply

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

Joe

Hi Mathias,

I can see that Maths is in your name Smile
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

Joe India | Reply

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

mathias

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

mathias United States | Reply

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

Joe

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

Joe | Reply

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

pingback

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?"

copious-systems.com | Reply

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

Rick

Hey Joe thanks that really helped me a lot

Rick United States | Reply

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

John

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

John Lao P.D.R. | Reply

Add comment




  Country flag

biuquote
  • Comment
  • Preview
Loading



Comments

Comment RSS