Optimal Route Based on Dynamic Programming for Road Networks

Manoj Kanta Mainali; Kaoru Shimada; Shingo Mabu; Kotaro Hirasawa

doi:10.20965/jaciii.2008.p0546

single-jc.php

« previous

JACIII Vol.12 No.6 pp. 546-553

doi: 10.20965/jaciii.2008.p0546

(2008)

Paper:

Views over last 60 days: 527

Optimal Route Based on Dynamic Programming for Road Networks

Manoj Kanta Mainali, Kaoru Shimada, Shingo Mabu, and Kotaro Hirasawa

Graduate School of Information, Production and Systems, Waseda University
2-7 Hibikino, Wakamatsu-ku, Kitakyushu, Fukuoka 808-0135, Japan

Received:

December 28, 2007

Accepted:

July 25, 2008

Published:

November 20, 2008

Keywords:

optimal route, Q method, dynamic programming, road networks

Abstract

One of the main functions of the traffic navigation systems is to find the optimal route to the destination. In this paper, we propose an iterative Q value updating algorithm, Q method, based on dynamic programming to search the optimal route and its optimal traveling time for a given Origin-Destination (OD) pair of road networks. The Q method uses the traveling time information available at adjacent intersections to search for the optimal route. The Q value is defined as the minimum traveling time to the destination when a vehicle takes the next intersection. When the Q values converge, the optimal route to the destination can be determined by choosing the minimum Q value at each intersection. The Q method gives us the solutions from multiple origins to a single destination. The proposed method is not restricted to find a single solution, but, if there exist multiple optimal routes with the identical traveling time to the destination, the proposed method can find all of it. In addition to that, when the traveling time of the road sections changes, an alternative optimal route can be found easily starting with the already obtained Q values. We compared the Q method with Dijkstra algorithm and the simulation results showed that the Q method can give better performances, depending on the situations, when the traveling time of the road sections changes.

Cite this article as:

M. Mainali, K. Shimada, S. Mabu, and K. Hirasawa, “Optimal Route Based on Dynamic Programming for Road Networks,” J. Adv. Comput. Intell. Intell. Inform., Vol.12 No.6, pp. 546-553, 2008.

Data files:

References

[1]
E. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerishce Mathematik 1, pp. 269-271, 1959.
G. R. Jagadeesh, T. Srikanthan, and K. H. Quek, “Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks,” IEEE Transactions on Intelligent Transportation Systems, Vol.3, No.4, pp. 301-309, Dec. 2002.
J. L. Bander and C.C. White, III, “A Heuristic Search Algorithm for Path Determination with Learning,” IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, Vol.28, No.1, pp. 131-134, Jan. 1998.
B. Golden, “Shortest-Path Algorithms: A Comparison,” Operations Research, Vol.24, No.6, pp. 1164-1168, 1976.
F. Glover, D. Klingman, and N. Phillips, “A New Polynomially Bounded Shortest Path Algorithm,” Operations Research, Vol.33, No.1, pp. 65-73, Jan./Feb., 1985.
G. Gallo and S. Pallottino, “Shortest Path Algorithms,” Annals of Operations Research, Vol.13, No.1, pp. 1-79, 1988.
S. Namkoong, J.-H. Rho, and J.-U. Choi, “Development of the Tree-Based Link Labeling Algorithm for Optimal Path-Finding in Urban Transportation Networks,” Mathl. Comput. Modelling, Vol.27, No.9-11, pp. 51-65, 1998. S. E. Dreyfus, “An Appraisal of Some Shortest-Path Algorithms,” Operations Research, Vol.17, No.3, pp. 395-412, May/Jun., 1969.
S. Misra and B. J. Oommen, “Dynamic Algorithms for the Shortest Path Routing Problem: Learning Automata-Based Solutions,” IEEE Transactions on Systems, Man and Cybernetics – Part B: Cybernetics, Vol.35, No.6, pp. 1179-1192, Dec. 2005.
P. Narvaez, K.-Y Siu and H.-Y Tzeng, “New Dynamic Algorithms for Shortest Path Tree Computation,” IEEE/ACM Transactions on Networking, Vol.8, No.6, pp. 734-746, Dec. 2000.
B. Xiao, Q. ZhuGe, and E. H.-M. Sha, “Minimum Dynamic Update for Shortest Path Tree Construction,” Global Telecommunications Conference, San Antonio, TX, pp. 126-130, 2001.
R. Bellman, “The Theory of Dynamic Programming,” Bull. Amer. Math. Soc. 60, pp. 503-515, 1954.
C. J. C. H. Watkins and P. Dayan, “Q-learning,” Machine Learning, Vol.8, Issue 3-4, pp. 279-292, 1992.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.