On determining the weight of edges in map-representing graphs-applications of heuristic methods in 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 changi...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
KeAi Communications Co., Ltd.
2022-12-01
|
| Series: | Journal of Traffic and Transportation Engineering (English ed. Online) |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2095756422001039 |
| _version_ | 1797960980145111040 |
|---|---|
| author | Marta Borowska-Stefańska Michał Kowalski Filip Turoboś Szymon Wiśniewski |
| author_facet | Marta Borowska-Stefańska Michał Kowalski Filip Turoboś Szymon Wiśniewski |
| author_sort | Marta Borowska-Stefańska |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T00:53:23Z |
| format | Article |
| id | doaj.art-81e8ffad0ae64ac7afc06e6daadf27e4 |
| institution | Directory Open Access Journal |
| issn | 2095-7564 |
| language | English |
| last_indexed | 2024-04-11T00:53:23Z |
| publishDate | 2022-12-01 |
| publisher | KeAi Communications Co., Ltd. |
| record_format | Article |
| series | Journal of Traffic and Transportation Engineering (English ed. Online) |
| spelling | doaj.art-81e8ffad0ae64ac7afc06e6daadf27e42023-01-05T08:36:37ZengKeAi Communications Co., Ltd.Journal of Traffic and Transportation Engineering (English ed. Online)2095-75642022-12-019610271043On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routesMarta Borowska-Stefańska0Michał Kowalski1Filip Turoboś2Szymon Wiśniewski3Institute of the Built Environment and Spatial Policy, Faculty of Geographical Sciences, University of Lodz, Łódź 90–137, Poland; Corresponding author. Tel.: +48 42 6354564.Institute of the Built Environment and Spatial Policy, Faculty of Geographical Sciences, University of Lodz, Łódź 90–137, PolandInstitute of Mathematics, Lodz University of Technology, Łódź 90–924, PolandInstitute of the Built Environment and Spatial Policy, Faculty of Geographical Sciences, University of Lodz, Łódź 90–137, PolandIn 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.http://www.sciencedirect.com/science/article/pii/S2095756422001039A∗ algorithmDijkstraHeuristic methodsMathematical modellingQuasimetric spacesPlanning escape routes |
| spellingShingle | Marta Borowska-Stefańska Michał Kowalski Filip Turoboś Szymon Wiśniewski On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routes Journal of Traffic and Transportation Engineering (English ed. Online) A∗ algorithm Dijkstra Heuristic methods Mathematical modelling Quasimetric spaces Planning escape routes |
| title | On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routes |
| title_full | On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routes |
| title_fullStr | On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routes |
| title_full_unstemmed | On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routes |
| title_short | On determining the weight of edges in map-representing graphs-applications of heuristic methods in planning escape routes |
| title_sort | on determining the weight of edges in map representing graphs applications of heuristic methods in planning escape routes |
| topic | A∗ algorithm Dijkstra Heuristic methods Mathematical modelling Quasimetric spaces Planning escape routes |
| url | http://www.sciencedirect.com/science/article/pii/S2095756422001039 |
| work_keys_str_mv | AT martaborowskastefanska ondeterminingtheweightofedgesinmaprepresentinggraphsapplicationsofheuristicmethodsinplanningescaperoutes AT michałkowalski ondeterminingtheweightofedgesinmaprepresentinggraphsapplicationsofheuristicmethodsinplanningescaperoutes AT filipturobos ondeterminingtheweightofedgesinmaprepresentinggraphsapplicationsofheuristicmethodsinplanningescaperoutes AT szymonwisniewski ondeterminingtheweightofedgesinmaprepresentinggraphsapplicationsofheuristicmethodsinplanningescaperoutes |