An online real-time matheuristic algorithm for dispatch and relocation of ambulances

The Medical System of Transportation deals with two online real-time decisions: ambulance dispatching and relocation. Dispatching consists of selecting which ambulance to send to an emergency call; relocation consists of determining how to modify the location of available ambulances in response to changes in the system’s state. Although the literature regarding this problem is extensive, only a limited number of online real-time approaches for ambulance management have been proposed, much less one taking into consideration different types of emergencies and vehicles. This paper proposes an online real-time matheuristic algorithm that combines: i) a new preparedness index defined as the availability probability of a multi-server queue model which is used as an optimization objective and as a control variable for relocation strategies, ii) two mathematical models to solve the relocation problem, one oriented to the maximization of coverage and other to the minimization of the maximum relocation time, and iii) two heuristic algorithms oriented to the maximization of the preparedness level, one to solve the dispatch problem and other to solve the location problem of one ambulance. The computational experiments, based on discrete event simulation and historical data of Bogotá, Colombia, have shown their capability to adequately respond to the necessities of real-time operation.