A Novel Approach for Dynamic Ambulance Routing: Integrating K-Means++ Clustering with Time-Variant Multi-Objective SPEA2

This study introduces a novel two-phase approach to tackle the Dynamic Ambu-lance Routing Problem (DARP), a significant issue in emergency services where numerous injured individuals across various areas require immediate medical care. The challenge is intensified by the limited number of ambulances and the fluctuating nature of demand for services. To address this, we propose a hybrid method that combines K-Means++ clustering with a Time-Variant Multi-Objective SPEA2 algorithm. This model classifies patients into two categories: Hard Emergency Injury (HEI) and Soft Emergency Injury (SEI), taking into account the emergence of new demands during ambulance operations.The pro-posed framework frames DARP as a multi-objective optimization issue, focusing on minimizing overall travel distance and patient ride time. In the initial phase, K-Means++ clustering organizes injury locations into spatially coherent groups, enhancing fleet management efficiency. The second phase applies a Time-Variant Multi-Objective SPEA2 algorithm to optimize ambulance routes within these clusters. We evaluate the performance of our approach against leading methods such as NSGA-II, NSGA-III, and traditional SPEA2, using key metrics for Pareto front assessment, including Hypervolume, Spacing, and the R2 Indicator. The findings indicate that our approach effectively balances multiple objectives and significantly enhances ambulance response efficiency.Our proposed K-Means++-TVSPEA2 algorithm demonstrates superior performance in ambulance routing optimization, achieving an average traveled distance reduction of 49.3% compared to K-Means-SA-TS, 8.6% compared to PA-PSO, and 12.2% compared to GA. Additionally, it improves ride time by 9.1% over K-Means-SA-TS and 12.7% over PA-PSO. These results highlight the efficiency of our approach in optimizing emergency response routing.