Optimal Routing in Urban Road Networks: A Graph-Based Approach Using Dijkstra’s Algorithm

Abstract

This paper presents a new approach to optimizing route selection in urban road networks with sparsely placed traffic counters. By leveraging graph theory and Dijkstra’s algorithm, we propose a new method to determine the shortest path between origins and destinations in city traffic networks with sparsely placed counters. The method is based on the similarities between traffic flows recorded at the counter and the streets that generate traffic for a given counter. The advantage of this method is the use of a secondary counter function to obtain data that are built into the shortest path determination model and the free choice of the time of day for which the path is searched. The proposed method is implemented using the programming language AutoLISP 2022 and program AutoCAD 2022, providing a valuable tool for transportation engineers and urban planners. This paper presents a model of the shortest path that integrates one-way streets, the average speed of the car, as well as the delay time at traffic-lighted and non-traffic intersections. The model was applied to the traffic network of the city of Sarajevo (Bosnia and Herzegovina), but there are no restrictions for application to any network equipped with traffic counters. The obtained results show a high agreement with the Google Maps service as a reference system.

Keywords

• transport network
• transportation planning
• route optimization
• graph theory
• algorithm
• shortest path in a graph