Probabilistic Envelope Constrained Multiperiod Stochastic Emergency Medical Services Location Model and Decomposition Scheme

This paper considers a multiperiod emergency medical services (EMS) location problem and introduces two two-stage stochastic programming formulations that account for uncertainty about emergency demand. Whereas the first model considers both a constraint on the probability of covering the realized emergency demand and minimizing the expected cost of doing so, the second one employs probabilistic envelope constraints that allow us to control the degradation of coverage under the more severe scenarios. These models give rise to large mixed-integer programs, which can be tackled directly or by using a conservative approximation scheme. For the former, we implement the branch-and-Benders-cut method, which improves significantly the solution time when compared with using both a recently proposed state-of-the art branch-and-bound algorithm and the CPLEX solver. Finally, a practical study is conducted using historical data from the Northern Ireland Ambulance Service and sheds some light on optimal EMS location configuration for this region and on necessary trade-offs that must be made between emergency demand coverage and expected cost. These insights are confirmed through an out-of-sample performance analysis.