Abstract
Emergency service providers are supposed to locate ambulances such that in case of emergency patients can be reached in a time-efficient manner. Two fundamental decisions and choices need to be made real-time. First of all immediately after a request emerges an appropriate vehicle needs to be dispatched and send to the requests’ site. After having served a request the vehicle needs to be relocated to its next waiting location. We are going to propose a model and solve the underlying optimization problem using approximate dynamic programming (ADP), an emerging and powerful tool for solving stochastic and dynamic problems typically arising in the field of operations research. Empirical tests based on real data from the city of Vienna indicate that by deviating from the classical dispatching rules the average response time can be decreased from 4.60 to 4.01 minutes, which corresponds to an improvement of 12.89%. Furthermore we are going to show that it is essential to consider time-dependent information such as travel times and changes with respect to the request volume explicitly. Ignoring the current time and its consequences thereafter during the stage of modeling and optimization leads to suboptimal decisions.
1. Introduction and related work
Emergency service providers are supposed to locate ambulances such that in case of emergency patients can be reached in a time-efficient manner. Two fundamental decisions and choices need to be made real-time. First of all immediately after a request emerges an appropriate vehicle needs to be dispatched and send to the requests’ site. Ambulances, when idle, are located at designated waiting sites. Hence after having served a request the vehicle needs to be relocated (i.e. its next waiting site has to be chosen). For a close match to reality, time-dependent information for both traveling times and the request volume will be considered explicitly. We are going to solve the underlying optimization problem using approximate dynamic programming (ADP), an emerging and powerful tool for solving stochastic and dynamic problems typically arising in the field of operations research.
6. Conclusion and outlook
In this paper we formulate a dynamic version of the ambulance dispatching and relocation problem, which has been solved using ADP. Extensive testing and comparison with real-world data have shown that ADP can provide high-quality solutions and is able to outperform policies that are currently in use in practice. The average response time can be decreased by 12.89%. This improvement is due to two main sources for improvement: the dispatching and relocation decisions involved. By deviating from the traditional rule of dispatching the closest ambulance available and relocating them to their home base after having finished serving a request we are able to make high-quality dispatching decisions in an anticipatory manner. By explicitly taking into account the current state of the system we are able to improve the performance thereafter. Due to regulatory reasons ambulances are not allowed to travel around empty and to be relocated from one waiting location to another one in order to response to potentially undercovered areas. But we are able to compensate for that by locating ambulances after becoming available again in a reasonable way.
