Vehicle Route Planning Using Dynamically Weighted Dijkstra Algorithm and Traffic Prediction
Abstract - In this paper, we propose a novel method based on Dijkstra algorithm for dynamic routing using a traffic prediction model based on traffic flow theory in a road network. The approach taken has been to modify traditional Dijkstra algorithm, which is a common way to solve the shortest path problem, by making it dynamic and time dependent. We then formulated a prediction model based on traffic flow theory principles. The model provides predicted traffic parameters and travel time across each edge of the road network at every time instant. The work herein presented shows how the dynamic Dijkstra algorithm that we designed manages the change in traffic conditions across the graph, at each time step, to give the optimal forward-looking path. We verified the proposed method by comparing results of conventional Dijkstra against our implementation on a graph with randomly simulated traffic.
Keywords - Dijkstra Algorithm, Vehicle Routing, Traffic Flow Theory, Traffic Prediction Model