Operational Decision Support for Evacuating Nursing Home Residents: A Hamburg Benchmark and Metaheuristic Comparison Under a 5-Minute Time Budget

Abstract

Evacuating mobility-impaired nursing home residents during urban emergencies requires routing and scheduling heterogeneous vehicles under minute-level deadlines. We introduce the Nursing Home Evacuation Vehicle Routing Problem (NH-Evac-VRP) with open-ended multi-trip shuttling, split pickups, load-dependent service times, and shelter capacities; solutions must be produced within a hard 300 s single-thread budget. We release the Hamburg-NH-Evac benchmark with two expert-specified scenarios: (i) an unexploded-ordnance exclusion-zone evacuation in Altona-Altstadt (479 evacuees, one shelter), (ii) a storm-surge evacuation in Wilhelmsburg (510 evacuees, three shelters), plus (iii) a synthetic stress test (1,348 evacuees, five shelters). Instances use real facility data and asymmetric road-network travel times. Across five scenario-fleet configurations, we compare a constructive dispatcher with a Genetic Algorithm, Memetic Algorithm, and Adaptive Large Neighborhood Search, minimizing demand-weighted average waiting time and makespan with a shelter-overfill penalty. No method dominates: ALNS attains the best makespan in two configurations; in the heterogeneous Flood-Augmented case this advantage is driven by capacity-maximizing "sweeper" tours. MA is best in three configurations by favoring rapid shuttle cycles, outperforming ALNS by 27 min in the synthetic mass-transit case. We also provide a web-based decision support system for scenario configuration, optimization, and schedule visualization.