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

作     者：Marta Borowska-Stefańska MichałKowalski Filip Turoboś Szymon Wiśniewski Marta Borowska-Stefańska;Micha? Kowalski;Filip Turobo?;Szymon Wi?niewski

作者机构：Institute of the Built Environment and Spatial PolicyFaculty of Geographical SciencesUniversity of LodzŁódź90–137Poland Institute of MathematicsLodz University of TechnologyŁódź90–924Poland 

出 版 物：《Journal of Traffic and Transportation Engineering(English Edition)》 (交通运输工程学报（英文版）)

年 卷 期：2022年第9卷第6期

页      面：1027-1043页

核心收录：

学科分类：083002[工学-环境工程] 0830[工学-环境科学与工程（可授工学、理学、农学学位）] 08[工学] 0835[工学-软件工程] 082302[工学-交通信息工程及控制] 0701[理学-数学] 0823[工学-交通运输工程] 

基　　金：the National Science Centre in Poland,grant number 2018/29/B/HS4/01020 o-funded under the framework of the subsidy for tertiary education,aimed at academies and universities which participated in the IDUB Contest(“Inicjatywa Doskona?o sci-Uczelnia Badawcza”)。 

主　　题：A*algorithm Dijkstra Heuristic methods Mathematical modelling Quasimetric spaces Planning escape routes 

摘      要：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.