Congestion Avoidance on Road Networks through Adaptive Routing on Contracted Graphs
Public Deposited- Last Modified
- February 27, 2019
- Creator
-
Davis, Bradley H.
- Affiliation: College of Arts and Sciences, Department of Computer Science
- Abstract
- 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.
- Date of publication
- spring 2016
- Keyword
- DOI
- Resource type
- Rights statement
- In Copyright
- Note
- Funding: None
- Advisor
- Pozefsky, Diane
- Degree
- Bachelor of Science
- Honors level
- Highest Honors
- Degree granting institution
- University of North Carolina at Chapel Hill
- Extent
- 30
Relations
- Parents:
This work has no parents.