Ambulance redeployment and dispatching under uncertainty with personnel workload limitations

Emergency Medical Services (EMS) managers are concerned with responding to emergency calls in a timely manner. Redeployment and dispatching strategies can be used to improve coverage that pertains to the proportion of calls that are responded to within a target time threshold. Dispatching refers to the choice of which ambulance to send to a call, and redeployment refers to repositioning of idle ambulances to compensate for coverage loss due to busy ambulances. Redeployment moves, however, impose additional workload on EMS personnel and must be executed with care. We propose a two-stage stochastic programming model to redeploy and dispatch ambulances to maximize the expected coverage. Our model restricts personnel workload in a shift and incorporates multiple call priority levels. We develop a Lagrangian branch-and-bound algorithm to solve realistic size instances. We evaluate the model performance based on average coverage and average ambulance workload during a shift. Our computational results indicate that the proposed Lagrangian branch-and-bound is significantly more efficient than CPLEX, especially for large problem instances. We also compare our model with benchmarks from the literature and show that it can improve the performance of an EMS system considerably, in particular with respect to mean response time to high-priority calls.