City-level route planning with time-dependent networks

摘要

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 time-dependent 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.