Informatics Publishing Limited

B. Anil Kumar ¹, Rony Gracious ², Chitrak Gangrade ², Lelitha Vanajakshi ²

Affiliations
1 Department of Civil and Environmental Engineering, IIT Patna, Bihta 801 103, IN
2 Department of Civil Engineering, Indian Institute of Technology Madras, Chennai 600 036, IN

Abstract

The computation of point-to-point shortest paths on time-dependent transportation networks has many practical applications. Finding the shortest path on transportation networks, taking into account prevailing dynamic traffic conditions, can help solve the problem of traffic congestion in urban areas. This study presents a framework for implementation of the shortest path algorithm on static as well as timedependent city networks to identify the correct match between network complexity, computational requirements and scalability. Dijkstra, bidirectional A*, and A* with landmarks and triangle inequality (ALT) algorithms were selected and implemented based on their reported good performance in earlier studies. The algorithm implementation on both static and dynamic networks was tested on selected networks from Chennai city, India. Among the tested algorithms, ALT performed the best in terms of criteria used in this study. This algorithm is shown to be scalable and can be implemented for any other city network with ease, as demonstrated in this study. The study also discusses techniques for data extraction, cleaning and representation in addition to implementation and comparison of algorithms.

Keywords

Dynamic Networks, Shortest Path Algorithms, Time-dependent City Networks, Transport Planning, Traffic Engineering.

Full Text