Congestion Avoidance on Road Networks through Adaptive Routing on Contracted Graphs (2016)

Undergraduate: Bradley Davis

Faculty Advisor: Diane Pozefksy
Department: Computer Science

---

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. Early 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.