Shortest Alternate Path Discovery through Recursive Bounding Box Pruning

Abstract

Congestion is a dynamic phenomenon and hence efficiently computing alternate shortest route can only help expedite decongestion. This research is aimed to efficiently compute shortest path for road traffic network so that congestion can be eased resulting in reduced CO 2 emission and improved economy. Congestion detection is achieved after evaluating road capacity and road occupancy. Congestion index, a ratio of road occupancy to road capacity is computed, congestion index higher than 0.6 necessitates computation of alternate shortest route. Various algorithms offer shortest alternate route. The paper discusses minimization of graph based by removing redundant nodes which don’t play a role in computation of shortest path. The proposal is based on continuous definition of a bounding box every time a next neighboring node is considered. This reduces maximum number of contentious nodes repeatedly and optimizes the network. The algorithm is deployed from both the ends sequentially to ensure zero error and validate the shortest path discovery. While discovering shortest path, the algorithm also offers an array of shortest path in ascending order of the path length. However, vehicular traffic exhibits network duality viz. static and dynamic network graphs. Shortest route for static distance graph is pre-computed and stored for look-up, alternate shortest path based on assignment of congestion levels to edge weights is triggered by congestion index. The research also supports directed graphs to address traffic rules for lanes having unidirectional and bidirectional traffic.