Reference no: EM133169176

A firm wants to set up electric vehicle charging stations across Metairie. In particular, the candidate neighborhoods to set up charging stations are: Bonnabel place, Bucktown, Shrewsbury, Jefferson, Elmwood, Harahan, River ridge, Kenner, Westgate, Willowdale. These are also all the neighborhoods they want to serve. For the convenience of the customers, neighborhood A is considered to be "served" by a particular charging station located in neighborhood B only if A and B are "near" to each other. Also, of course, A is near to itself. The location information is given in the table. The firm now needs to decide where to set up the charging stations among these neighborhoods. However, there are several restrictions they need to follow. Residents in Kenner do not want any station to be set up in their neighborhood, but they still want to be served. Jefferson and Shrewsbury make a pact, that either both of them have a station set up in their neighborhood or neither will set up. Among Willowdale and River ridge, River ridge will only set up a station if Willowdale sets up a station. For the three big neighborhoods, Bonnabel place needs to be served by at least three stations, while Bucktown and Willowdale need to be served by at least two stations while the other neighborhoods are fine with just served by one station. What is the least number of charging stations that will satisfy all the above requirements?