Ambulance Routing Optimization Problem with Patient Triage Priority
Journal
International Journal of Intelligent Transportation Systems Research
ISSN
1348-8503
1868-8659
Date Issued
August 24, 2026
Abstract
Emergency medical services (EMS) face critical challenges in efficiently allocating and routing ambulances to minimize response times, particularly in scenarios where high-risk patients must be prioritized under limited resources. This study investigates an ambulance routing problem (ARP) with patient triage priority, where the objective is to jointly assign ambulances to patients and determine their routes so as to minimize total travel time, defined as the sum of the ambulance-to-patient and patient-to-hospital travel times. A mixed-integer linear programming (MILP) model is proposed that integrates assignment and routing decisions, while capturing realistic EMS operational constraints such as patient prioritization and heterogeneous travel times. The proposed MILP is formulated as a multi-criteria optimization problem that prioritizes the transportation service of red-code patients while minimizing total travel time. To address the computational complexity of solving large-scale ARP instances, a metaheuristic based on Tabu Search (TS) is developed, incorporating a set of problem-specific local search operators. To evaluate the effectiveness of the MILP model and TS algorithm, a new set of benchmark instances is generated for the ARP with triage-based patient priority. Computational experiments demonstrate that the MILP model solves small-scale instances (up to 40 patients) optimally in less than one minute, but requires up to 32 minutes to solve large-scale instances (up to 150 patients) and more than 5 hours for instances up to 250 patients. The proposed TS algorithm finds optimal solutions for 20 of the 39 benchmark instances and achieves an average optimality gap below 0.7% in the remaining 19 instances, while requiring less than 42 seconds, on average, to solve the largest instances.
Funding
This research is funded by the European Union Recovery and Resilience Facility of the NextGenerationEU instrument through the Research and Innovation Foundation under the Grant Agreement No CODEVELOPAG-SH-HE/0823/0112 and the ‘EXCELSIOR’: ERATOSTHENES: Excellence Research Centre for Earth Surveillance and Space-Based Monitoring of the Environment H2020 Widespread Teaming project (www.excelsior2020.eu). The ‘EXCELSIOR’ project has received funding from the European Union’s Horizon 2020 research and innovation programme under Grant Agreement No 857510, from the Government of the Republic of Cyprus through the Directorate General for the European Programmes, Coordination and Development and the Cyprus University of Technology.
File(s)![Thumbnail Image]()
Name
s13177-026-00713-x.pdf
Size
5.5 MB
Format
Adobe PDF
Checksum (MD5)
4474142041d41609c59c51a01c6b229f