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.
Tabu Search-based hyper-heuristic for Solving the Heterogeneous Ambulance Routing Problem with Time Windows
Int. J. ITS Res.
International Journal of Intelligent Transportation Systems Research ; 22 , 2 ; 446-461
2024-08-01
16 pages
Article (Journal)
Electronic Resource
English
Emergency medical services , Hyper-heuristic , Heterogeneous ambulance routing problem , Hybrid tabu search Engineering , Electrical Engineering , Automotive Engineering , Robotics and Automation , Computer Imaging, Vision, Pattern Recognition and Graphics , Civil Engineering , User Interfaces and Human Computer Interaction
A parallel tabu search heuristic for the vehicle routing problem with time windows
Online Contents | 1997
|A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows
British Library Online Contents | 1997
|A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows
Online Contents | 1997
|