Reconfiguring a set of coverage-providing facilities under travel time uncertainty

We study networks of facilities that must provide coverage under conditions of uncertainty with respect to travel times and customer demand. We model this uncertainty through a set of scenarios. Since opening new facilities and/or closing existing ones is often quite expensive, we focus on optimal re-configuration of the network, that is finding a facility set that achieves desired thresholds with respect to expected and minimal coverage, while retaining as many of the existing facilities as possible. We illustrate our model with an example of Toronto Fire Service. We demonstrate that relocating just a few facilities can have the same effect as opening a similar number of new ones. We develop exact and approximate solution approaches and test them with computational experiments. Algorithm based on Tabu Search (with certain novel components) appears to be particularly successful for this problem. We also analyze the multi-objective version of the problem, where the expected and minimum coverage levels are treated as objectives in addition to the objective of maximizing the number of pre-existing facilities in the final location set.