A recursive optimization-simulation approach for the ambulance location and dispatching problem

Emergency Medical Services (EMS) have a crucial role in the health care system. Their mission is to provide out-of-hospital acute medical care and transportation to the appropriate health centers for injured and ill people, having a critical impact on their health. However, given the uncertainty of the demand and the limited amount of resources, organizing and managing an EMS system is an extremely challenging and important task; in particular, two factors can have a big impact on the performances of the system: the locations of ambulances and their allocation to the emergency calls. Therefore, the Ambulance Location and Dispatching Problem (ALDP) has been introduced, with the goal of helping the decision makers in improving the system performances. Optimization and simulation have been used in the past to solve location and dispatching problems and, in particular, ALDP. Both approaches present interesting features and using them in a joint framework is very promising. Therefore, in this thesis we discuss a new approach to solve ALDP, using a combination of optimization and simulation techniques: in particular, we choose the Recursive Optimization-Simulation Approach (ROSA). The main idea of ROSA is to iteratively run an optimization phase and a simulation phase: each step consists in solving the problem with the optimization model, then simulating the solution with a discrete-event simulator and finally using the outputs of the simulation to re-run the optimization problem with an improved knowledge of some parameters. The solution provided by this framework consists in the location of the ambulances and ordered dispatching lists for each demand zone. Four different variations of the ROSA approach are introduced and all models are tested and compared using a set of realistic instances from the city of Montreal and its surroundings. The results are positive: with this recursive approach we are able to improve considerably the quality of the solutions and our understanding of the problem.

I Servizi Medici d'Emergenza (SME) sono una componente fondamentale di ogni sistema sanitario. Il loro compito è quello di fornire tempestivamente servizi medici d'urgenza ed eventualmente trasportare i pazienti nei centri ospedalieri appropriati, avendo un impatto critico sulla loro salute. Tuttavia la quantità di chiamate ricevute non è deterministica e spesso gli SME dispongono di risorse limitate: pertanto la loro gestione e organizzazione può essere estremamente complessa e delicata. In particolar modo, due fattori possono avere una fondamentale importanza sulle performance del sistema: il posizionamento delle ambulanze e le decisioni operative di ripartizione con cui esse rispondono alla chiamate. Questi due fattori sono alla base dell'Ambulance Location and Dispatching Problem (ALDP). In passato sia tecniche di ottimizzazione, sia modelli di simulazione sono state utilizzati per risolvere ALDP e problemi simili. Tuttavia questi due metodi, per quanto tra loro differenti, non sono mutualmente esclusivi e possono interagire l'uno con l'altro per migliorarsi a vicenda. Pertanto in questa tesi discutiamo un nuovo approccio per risolvere ALDP, applicando il "Recursive Optimization-Simulation Approach" (ROSA). Questo metodo si basa sull'eseguire ricorsivamente una fase di ottimizzazione ed una di simulazione: l'ottimizzatore risolve il problema, dopo di che si usa il simulatore per ottenere maggiori informazioni sulla soluzione ed infine si ri-esegue il modello di ottimizzazione migliorandone i parametri, sulla base delle nuove informazioni. Una soluzione del modello è costituita da un insieme di stazioni di posizionamento (una per ogni ambulanza) e da un lista ordinata per ogni zona che deve essere servita. In questa tesi, seguendo la metodologia di ROSA, sviluppiamo quattro distinti modelli e li testiamo su un insieme di istanze realistiche basate sulla città di Montreal ed i suoi dintorni. I risultati sono positivi: la qualità delle soluzioni è ampiamente migliorata, così come la nostra conoscenza del problema.