Comparative analysis of Bellman-Ford and Dijkstra’s algorithms for optimal evacuation route planning in multi-floor buildings

Abstract

AbstractThis study introduces a groundbreaking application of the Bellman-Ford algorithm for optimizing evacuation routes in multi-floor academic buildings, extending its traditional use in single-source shortest-path problems to address complex multiple- source multiple-exit (MSME) problems. A comprehensive computational model was developed, reflecting real-world evacuation scenarios and incorporating key constraints and assumptions. The model was rigorously benchmarked against a Dijkstra’s algorithm-based model, revealing a 3.5% improvement in the number of evacuees evacuated after the initial 9 seconds. Detailed simulation results and extended data analysis further substantiate these findings. While the current model assumes perfect evacuee compliance and overlooks human behavior, future research could address these limitations to enhance the model’s realism. This study significantly advances the field of emergency evacuation planning, offering valuable insights for emergency response practitioners, facility managers, and policymakers.

Keywords

• Bellman-Ford algorithm
• evacuation planning
• buildings
• multiple-source multiple-exit (MSME) problems
• Emergency management
• optimal route selection