Tabu Search-based hyper-heuristic for Solving the Heterogeneous Ambulance Routing Problem with Time Windows

The ambulance routing problem (ARP) has always been the main problem of emergency medical services, especially in disaster and pandemic situations when a large number of geographically dispersed patients require medical aid. This problem has recently received significant attention from researchers since the Covid-19 pandemic spread. In this work, we propose an efficient strategy to manage emergency calls and optimize the routes used to rescue people. In the designed model, we distinguish two groups of patients : (1) green-case patients who can be assisted directly in the scene, and (2) red-case patients in critical situations who have to be brought to hospitals. A new mathematical formulation is proposed to find the best sequence of routes for a heterogeneous fleet of ambulances that minimizes the latest service completion time. The goal is to reduce the number of patients whose conditions get worse with an untimely medical response. To solve the ARP with time windows (ARPTW), we implement the mathematical model using the Gurobi solver to generate optimal solutions for small-scaled instances. Besides, we develop two algorithms based on Tabu Search : Hybrid Tabu Search (HTS) and Tabu Search-based Hyper-Heuristic (TSHH). To validate the developed algorithms, a deep experimental study is conducted on a generated dataset. The performed sensitivity analysis and the comparative study proved the effectiveness of the hyper-heuristic to solve the ARPTW, reaching the optimal solution in 83.33% of instances in a reasonable CPU time.