Lagrangian dual decomposition for the ambulance relocation and routing considering stochastic demand with the truncated Poisson

The pre-hospital Emergency Medical Service (EMS) provides the critical care to the ill or injured patients, and evaluates and manages those patients at scene before their transport to an emergency medical facility. The Time to Arrive at Hospital (TAH) is a useful performance measurement defined as the time interval from the dispatch of an ambulance until the arrival of the patient at the destination facility. By taking into consideration of the short-term demand estimation, there is chance to improve the management of ambulances and reduce the TAH. This study proposes a new stochastic programming model to minimize the TAH within a complete dynamic relocation system. In this system, a truncated Poisson distribution is utilized for forecasting near future EMS requests, and a Lagrangian dual decomposition with branch-and-bound is adapted as the solution methodology. By dynamically generating near future scenarios for the planning of ambulance relocation among bases, we obtain close-to-real-time ambulance relocation decisions. Scenarios collected from New Taipei City, Taiwan have shown that the proposed system has the potential to enhance the performance of the pre-hospital EMS.