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
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.