Home // INTELLI 2024, The Thirteenth International Conference on Intelligent Systems and Applications // View article
Authors:
Masayuki Shimizu
Soichiro Yokoyama
Tomohisa Yamashita
Hidenori Kawamura
Keywords: Road Network Hierachization, Pathfinding, Vehicle Routing Problem.
Abstract:
In this study, we propose a road network hierarchization method for pathfinding that takes into account drivers' avoidance of narrow roads. The proposed method identifies nodes with high betweenness centrality, one of the centrality measures in network analysis, to connect disconnected subnetworks within each hierarchical level. To validate the effectiveness of the proposed method, multiple driver preferences regarding narrow roads are prepared, and computational experiments are conducted on a road network covering a 14 km square area in central Sapporo. Compared to performing pathfinding without hierarchical networks, the calculation time of individual pathfinding was reduced to 4-6% with the previous method and to 3-6% with the proposed method. Additionally, by using the proposed method, the average cost of routes improved compared to the previous method, and even when compared to the minimum cost paths, the worsening of route costs was about 4-9%. From the above, the superiority of the proposed method, which connects disconnected subnetworks using betweenness centrality, was confirmed.
Pages: 25 to 32
Copyright: Copyright (c) IARIA, 2024
Publication date: March 10, 2024
Published in: conference
ISSN: 2308-4065
ISBN: 978-1-68558-132-9
Location: Athens, Greece
Dates: from March 10, 2024 to March 14, 2024