Date on Master's Thesis/Doctoral Dissertation

5-2014

Document Type

Doctoral Dissertation

Degree Name

Ph. D.

Department

Industrial Engineering

Committee Chair

Heragu, Sunderesh S.

Committee Co-Chair (if applicable)

Bai, Lihui

Committee Member

Usher, John S.

Committee Member

Gupta, Mahesh

Subject

Ambulance service--Dispatching; Communication in emergency medicine; Fire engines--Dispatching

Abstract

We consider the problem of dispatching and relocating EMS vehicles during a pandemic outbreak. In such a situation, the demand for EMS vehicles increases and in order to better utilize their capacity, the idea of serving more than one patient by an ambulance is introduced. Vehicles transporting high priority patients cannot serve any other patient, but those transporting low priority patients are allowed to be rerouted to serve a second patient. We have considered three separate problems in this research. In the first problem, an integrated model is developed for dispatching and relocating EMS vehicles, where dispatchers determine hospitals for patients. The second problem considers just relocating EMS vehicles. In the third problem only dispatching decisions are made where hospitals are pre-specified by patients not by dispatchers. In the first problem, the objective is to minimize the total travel distance and the penalty of not meeting specific constraints. In order to better utilize the capacity of ambulances, we allow each ambulance to serve a maximum of two patients. Considerations are given to features such as meeting the required response time window for patients, batching non-critical and critical patients when necessary, ensuring balanced coverage for all census tracts. Three models are proposed- two of them are linear integer programing and the other is a non-linear programing model. Numerical examples show that the linear models can be solved using general-purpose solvers efficiently for large sized problems, and thus it is suitable for use in a real time decision support system. In the second problem, the goal is to maximize the coverage for serving future calls in a required time window. A linear programming model is developed for this problem. The objective is to maximize the number of census tracts with single and double coverage, (each with their own weights) and to minimize the travel time for relocating. In order to tune the parameters in this objective function, an event based simulation model is developed to study the movement of vehicles and incidents (911 calls) through a city. The results show that the proposed model can effectively increase the system-wide coverage by EMS vehicles even if we assume that vehicles cannot respond to any incidents while traveling between stations. In addition, the results suggest that the proposed model outperforms one of the well-known real time repositioning models (Gendreau et al. (2001)). In the third problem, the objective is to minimize the total travel distance experienced by all EMS vehicles, while satisfying two types of time window constraints. One requires the EMS vehicle to arrive at the patients' scene within a pre-specified time, the other requires the EMS vehicle to transport patients to their hospitals within a given time window. Similar to the first problem, each vehicle can transport maximum two patients. A mixed integer program (MIP) model is developed for the EMS dispatching problem. The problem is proved to be NP-hard, and a simulated annealing (SA) method is developed for its efficient solution. Additionally, to obtain lower bound, a column generation method is developed. Our numerical results show that the proposed SA provides high quality solutions whose objective is close to the obtained lower bound with much less CPU time. Thus, the SA method is suitable for implementation in a real-time decision support system.

Share

COinS