On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routes

Abstract

In the paper we discuss and compare two commonly used methods of finding the shortest paths in networks, namely Dijkstra's and A∗ algorithms. We compare their effectiveness in terms of traversing road network in circumstances that require swift decision making in the event of dynamically changing road conditions on the basis of studies conducted for evacuation plans. To build a proper model of such a network, a method of appropriate edge-weighting is introduced, based on empirical data collected by other researchers. Then, we use the basics of the theory of quasimetric spaces to introduce a heuristic to such graphs, which is easy to calculate metric. The heuristic we obtain is both admissible and consistent, which allows us to use it efficiently in A∗ search algorithms. The developed application can be used in studies into evacuation from hazardous areas. In this case, optimum calculative efficiency is achievable with a simultaneous reduction of calculation time (when compared to Dijkstra's algorithm). Our application can be applied during the first stage, i.e., prior to the occurrence of a disaster, since this is an appropriate time for preparation by planning, drilling, early warning, and designating the rescue services that are to participate in the following stages.

Keywords

• A∗ algorithm
• Dijkstra
• Heuristic methods
• Mathematical modelling
• Quasimetric spaces
• Planning escape routes