Premium
Dynamic optimal route search algorithm for car navigation systems with preferences by dynamic programming
Author(s) -
Mainali Manoj Kanta,
Mabu Shingo,
Yu Shanqing,
Eto Shinji,
Hirasawa Kotaro
Publication year - 2011
Publication title -
ieej transactions on electrical and electronic engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 30
eISSN - 1931-4981
pISSN - 1931-4973
DOI - 10.1002/tee.20601
Subject(s) - dijkstra's algorithm , dynamic programming , computer science , travel time , computation , mathematical optimization , turn by turn navigation , shortest path problem , algorithm , real time computing , engineering , transport engineering , mathematics , theoretical computer science , graph , robot , artificial intelligence , robot control , mobile robot
Optimal route search to the destination is one of the most important functions of car navigation devices. The development of road traffic infrastructure has made it possible to receive real‐time information of the traffic situation. Route search algorithms for car navigation devices make use of this information to avoid the traffic congestions. Such algorithms should find the new optimal route efficiently when the traffic situation changes. Usually, the minimum traveling time or distance is considered to define the optimal route. However, the minimum traveling time or distance is not always what the user is looking for. The user may prefer to travel on a certain route even at the cost of traveling time or distance. Car navigation devices should consider such preferences when finding the optimal route. In this paper, we propose a dynamic programming algorithm to find the optimal route considering that it should deal with the changes of the traffic situation and multiple criteria. The proposed method uses the information from the previous computation to find the new optimal route considering user preferences when the traveling time of the road section changes. The proposed method was applied to a real road network to find the optimal route. Results show that the proposed method can find the user‐preferred optimal route. Simulation results also show better calculation time of the proposed method compared to the Dijkstra algorithm. Copyright © 2010 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.