Multi-period stochastic programming models for two-tiered emergency medical service system

This paper addresses the multi-period ambulance redeployment planning problem in a two-tiered Emergency Medical System (EMS) where two types of ambulances are used to respond to two categories of emergency calls. In order to account for the uncertainty inherent to both categories of demand, we propose a two-stage stochastic programming model that aims at finding a cost-effective ambulance redeployment. The model tries to minimize the total cost, which encompasses ambulance relocation cost, the dispatching cost, and the penalty cost incurred by the unsatisfied demand, over a multi-period planning horizon. In order to overcome the computational complexity of the proposed model, two heuristics are proposed: a Temporal Decomposition Heuristic (HDT), and a Lagrangian Relaxation based Heuristic (SBG). A simulation model is then proposed to evaluate the service level of the EMS system and ambulance utilization while accounting for more realistic features of the problem. The computational experiments are carried out using real-world data provided by the EMS system of the northern region of Tunisia. The results show the excellent performance of HDT as it provides a near-optimal solution within a reasonable computational time. The simulation also demonstrates that the service level of the EMS system is higher if HDT is used.