Optimizing Dynamic Ambulance Routing Problem: A Two-Phase Strategy Combining K-means Clustering and Multi-Objective Particle Swarm Optimization

In this paper, we propose a novel two-phase approach to solve the Dynamic Ambulance Routing Problem (DARP), where a significant number of injured persons from different regions require treatment and medical assistance. In such cases, many people call for ambulances, but the availability and number of ambulances is insufficient to reach all patients simultaneously. Consequently, managing the ambulance fleet to respond to all demands as quickly as possible is a crucial research area to explore. In this research, we consider two main types of patients (Hard Emergency Injury [HEI] and Soft Emergency Injury [SEI]) in a dynamic context, where new demands may arise after the ambulance service has started. Furthermore, a mathematical model is proposed to formulate the DARP as a multi-objective problem that minimizes both the travel distance and ride time. To solve this NP-hard problem, we propose a two-phase approach, called k-means-MOPSO, which combines k-means clustering to group the injuries into geographic classes with the Multi-Objective Particle Swarm Optimization (MOPSO) heuristic to route the ambulances. To demonstrate the effectiveness of the k-means-MOPSO approach, this approach is compared with well-known state-of-the-art methods (NSGA-III, NSGA-II, and SPEA2) using various Pareto front metrics, such as Hypervolume, Spacing, and R2 Indicator.