交通予測を組み込んだ動的重み付きダイクストラ法による車両経路計画
Vehicle Route Planning using Dynamically Weighted Dijkstra's Algorithm with Traffic Prediction
交通流理論に基づく予測モデルをダイクストラ法の計画段階に組み込み、時間変化する交通状況に応じて将来を見据えた最適経路を選ぶ動的経路計画手法を提案した論文。
著者: Piyush Udhan, Akhilesh Ganeshkar, Poobigan Murugesan, Abhishek Raj Permani, Sameep Sanjeeva, Parth Deshpande
分類: math.OC, cs.RO, cs.SY, eess.SY
原文アブストラクト
Traditional vehicle routing algorithms do not consider the changing nature of traffic. While implementations of Dijkstra's algorithm with varying weights exist, the weights are often changed after the outcome of algorithm is executed, which may not always result in the optimal route being chosen. Hence, this paper proposes a novel vehicle routing algorithm that improves upon Dijkstra's algorithm using a traffic prediction model based on the traffic flow in a road network. Here, Dijkstra's algorithm is adapted to be dynamic and time dependent using traffic flow theory principles during the planning stage itself. The model provides predicted traffic parameters and travel time across each edge of the road network at every time instant, leading to better routing results. The dynamic algorithm proposed here predicts changes in traffic conditions at each time step of planning to give the optimal forward-looking path. The proposed algorithm is verified by comparing it with conventional Dijkstra's algorithm on a graph with randomly simulated traffic, and is shown to predict the optimal route better with continuously changing traffic.