Fast computation of Q-value-based dynamic programming on road networks

• Published in: IEEJ transactions on electrical and electronic engineering 2012-07, Vol.7 (4), p.408-414
• Main Authors: Wen, Feng, Zhang, Deng, Mabu, Shingo, Mainali, Manoj Kanta, Hirasawa, Kotaro
• Format: Article
• Language: English
• Subjects: Applied sciences; dynamic programming; Exact sciences and technology; Organization and planning of networks (techniques and equipments); Q value; Radiolocalization and radionavigation; shortest path; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory
• ISSN: 1931-4973; 1931-4981
• DOI: 10.1002/tee.21748

One of the essential components of vehicle navigation systems is route planning. The single shortest path problem and multiple shortest path problem have been widely studied for route planning. This paper introduces a Q‐value‐based dynamic programming using the division concept for solving both single and multiple shortest path problems on road networks. The proposed algorithm divides the whole network into different divisions, and the updating of Q values in each division is one stage for searching the optimal routes on road networks. The proposed algorithm can greatly save the computational time without any preprocessing on the road networks. The proposed algorithm is also systematically studied in various sizes of road networks. The simulation results show the efficiency and effectiveness of the proposed algorithm on large‐scale road networks. © 2012 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.