Suboptimal Q value-based Dynamic Programming for road networks

One of the essential components of vehicle navigation systems is route planning. Q value-based Dynamic Programming using Division Concept (QDPDC) for solving the shortest path problem on road networks has already proposed by our previous work. QDPDC 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. This paper proposes Suboptimal Q value-based Dynamic Programming using Division Concept (SQDPDC) for solving the shortest path problem, which can calculate suboptimal routes in shorter computational time than QDPDC with high enough accuracy. The proposed algorithm is systematically studied in various sizes of road networks. The simulation results shows the efficiency and effectiveness of the proposed algorithm on large-scale road networks.