Models and algorithms for location and relocation of ambulances

We present two optimization problems related to optimal location and dynamic relocation of ambulances, arisen in the context of a larger project we are developing for the emergency health care system in Milan, Italy. The first problem is a strategic one and involves the selection of suitable parking areas to be built in the city in order to allow the ambulances to cover the urban territory. When the spatial distribution of the population changes, the optimal location of the ambulances should also change accordingly, but the constraint is that this reallocation must be possible exploiting a constrained number of parking areas. The second problem is meant as an ideal approximation of the re-location problem encountered at the operational level. When the number of the available ambulances changes, their optimal location also changes, but here the constraint is on the number of allowed re-locations. Both problems are solved with branch-and-bound and Lagrangian relaxation. In the former case the problem is decomposed into several independent sub-problems, one for each time period (a time period corresponds to a stable distribution of the population: night, working hours, week-ends...). In the latter case the problem is decomposed into several sub-problems, one for each number of available ambulances. In both cases the optimal solutions of the sub-problems are synchronized by Lagrange multipliers in order to make them consistent as parts of an overall optimal solution. We present computational results on real instances taken from the above mentioned project under development in Milan. We also describe the integration of these location models into a hypercube-like model, which takes into account the temporal distribution of the calls for service as well as the integration of the resulting decision support system into a geographical information system in use a the operating center of the emergency health care system in Milan.