Paulina KURZYK, University of Lodz, Poland
Borowska-Stefanska MARTA, University of Lodz, Poland
Wisniewski SZYMON, University of Lodz, Poland
Kowalski MICHAL, University of Lodz, Poland
Turbos FILIP, Lodz University of Technology, Poland
In the poster 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 was an easy to calculate metric. The heuristic we obtain is both admissible and consistent, which allows us to use it e?ciently 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.
The purpose of the study is to indicate the benefits of applying the A* algorithm in view of the issue of dynamically changing accessibility of individual routes. A* is able to show the shortest paths far more effectively than the Dijkstra’s solution, and the nature of the problem forces us to re-generate travel routes by orders of magnitude more often than in the case of a static map. Additionally, at the end of the paper we also provide a more reliable heuristic that takes into account the impact of the remaining factors on speeds achieved by drivers, and which is linked to the model.
Mots clés : A* algorithm|Dijkstra|planning escape routes
A102384PK