Algorithms for Optimizing Fleet Scheduling of Air Ambulances
This work addresses scheduling inefficiencies for air emergency medical services, which can impact patient survival in dispersed populations, though it is incremental as it builds on existing exact methodologies with custom algorithms.
The researchers tackled the problem of optimizing air ambulance fleet scheduling by developing two custom algorithms, neighborhood search and Tabu search, and compared them to an integer linear programming model solved with Gurobi. The Tabu search achieved results close to Gurobi's solution but in greatly decreased time, with Gurobi failing to reach optimal solutions in larger examples.
Proper scheduling of air assets can be the difference between life and death for a patient. While poor scheduling can be incredibly problematic during hospital transfers, it can be potentially catastrophic in the case of a disaster. These issues are amplified in the case of an air emergency medical service (EMS) system where populations are dispersed, and resources are limited. There are exact methodologies existing for scheduling missions, although actual calculation times can be quite significant given a large enough problem space. For this research, known coordinates of air and health facilities were used in conjunction with a formulated integer linear programming model. This was the programmed through Gurobi so that performance could be compared against custom algorithmic solutions. Two methods were developed, one based on neighbourhood search and the other on Tabu search. While both were able to achieve results quite close to the Gurobi solution, the Tabu search outperformed the former algorithm. Additionally, it was able to do so in a greatly decreased time, with Gurobi actually being unable to resolve to optimal in larger examples. Parallel variations were also developed with the compute unified device architecture (CUDA), though did not improve the timing given the smaller sample size.