John Toczekpuzzlor@gmail.com

Placing substations to minimize wiring costs.

Placing substations to minimize wiring costs.

A new city is being built which will include 20 distinct neighborhoods as shown by the house icons in the map. As part of the planning process, electricity needs to be connected to each of the neighborhoods.

The city has been allocated funds to put in three electrical substations to service the electrical needs of the neighborhoods. The substations are represented by the three electrical box icons to the right of the map. Because laying electrical line to each neighborhood is expensive, the placement of the substations on the map requires careful consideration. A neighborhood will be serviced by the nearest electrical substation.

A neighborhood may only be connected to one substation. The substations may be placed in any cell (including the same cell as an existing neighborhood). The cost of electrical wiring is $1 million per kilometer. Distances are measured using a direct line between cells, which are each one kilometer apart. For example, the distance between cell A1 and B2 is 1.41 kilometers.


What is the minimum cost required to connect all neighborhoods to electricity?

Send your answer to puzzlor@gmail.com by Feb. 15, 2015. The winner, chosen randomly from correct answers, will receive a $25 Amazon Gift Card. Past questions can be found at puzzlor.com.

John Toczek is the senior director of Decision Support and Analytics for Aramark Corporation in the Global Operational Excellence group. He earned his BSc. in Chemical Engineering at Drexel University (1996) and his MSc. in Operations Research from Virginia Commonwealth University (2005).