Congestion Avoidance on Road Networks through Adaptive Routing on Contracted Graphs

We have developed a method of integrating live traffic information into preprocessed graphs of large road networks in order to adaptively route autonomous vehicles. Our intent is to reduce congestion caused by fleets of centrally-routed vehicles being assigned overlapping routes and to help those vehicles avoid already congested areas. Recent developments in shortest-path routing, namely Contraction Hierarchies, are used in conjunction with a modified bidirectional Dijkstra search algorithm to ensure fast route computations despite frequent graph updates. We introduce a novel heuristic for graph reprocessing that enables quick updates alongside a simple approach to computing appropriate edge weights based on substantial amounts of feedback received from vehicles on the road. Our approach is tested on a developed simulation platform using real road data and a Nagel-Schreckenberg traffic model. Results show that vehicles experience an overall speedup in travel time and adeptly react to unforeseen conditions by using alternative routes to avoid further congestion.Bachelor of Scienc