Decision Support Puzzles for Applied Mathematicians
August 2010 - Bridges
The five residents of Hometown live in houses represented by the letters "A" through "E" as shown on the left side of Figure 1. The offices where they will be working are represented by their matching letters on the island of Worktown.
Because a river lies between Hometown and Worktown, the residents are unable to get to work. They have in their budget enough funds to build two bridges that could connect Hometown to Worktown. The locations where these bridges could be built are indicated by the brown 1x3 hashed tiles. The two bridges can only be built in these approved areas.
Once the bridges are built, the residents would then be able to commute to work. A commuter will always take the shortest path from home to work and can only travel in up, down, left or right directions (no diagonals). Each tile represents a 1-km-by-1-km distance. As an example, if bridge four were built, resident "E" would have to travel 10 km to reach his workplace.
Question: Which two bridges should be built in order to minimize the total commuting distance of all residents?