Robust and stochastic formulations for ambulance deployment and dispatch

In Emergency Medical Systems, operators deploy a fleet of ambulances to a set of locations before dispatching them in response to emergency calls, with the goal of minimizing the fraction of calls with late response times. We propose stochastic and robust formulations for the ambulance deployment problem that use data on emergency calls to model uncertainty. By incorporating advances in column and constraint generation, our formulations are solved to exact optimality within minutes. In extensive computational experiments on Washington DC, our approach outperforms previous approaches (i.e. the MEXCLP and MALP) that rely on probabilistic assumptions about the availability of ambulances. Our formulations achieve a reduction of 19 to 28% in number of shortfalls, requiring only 70% of the total number of ambulances required in probabilistic models to attain comparable out-of-sample performance.