Top > JACIII > Q Value-Based Dynamic Programming with Boltzmann Distribution ...

single-jc.php

JACIII Vol.13 No.5 pp. 581-591
doi: 10.20965/jaciii.2009.p0581
(2009)

Paper:

Views over last 60 days: 494

Q Value-Based Dynamic Programming with Boltzmann Distribution for Global Optimal Traffic Routing Strategy

Shanqing Yu, Shingo Mabu, Fengming Ye, Hongqiang Wang,
Kaoru Shimada, and Kotaro Hirasawa

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

Received:
August 14, 2008
Accepted:
March 18, 2009
Published:
September 20, 2009
Creative Commons License
Keywords:
Q value, dynamic programming, Boltzmann distribution, Greedy strategy, global optimum
Abstract
In this paper, we propose a heuristic method -- Boltzmann Optimal Route Method trying to find a good approximation to the global optimum route for Origin-Destination pairs through iterations until the total traveling time converges. The overall idea of our method is to update the traveling time of each route section iteratively according to its corresponding traffic volume, and continuously generate a new global route by Q value-based Dynamic Programming combined with Boltzmann distribution. Finally, we can get the global optimum route considering the traffic volumes of the road sections. The new proposed method is compared with the conventional shortest-path method- Greedy strategy both in the static traffic system where the volumes of all the given Origin-Destination pairs of road networks are constant and in the dynamic traffic system in which changing traffic volumes are constantly provided. The results demonstrate that the proposed method performs better than the conventional method in global perspective.
Cite this article as:
S. Yu, S. Mabu, F. Ye, H. Wang, K. Shimada, and K. Hirasawa, “Q Value-Based Dynamic Programming with Boltzmann Distribution for Global Optimal Traffic Routing Strategy,” J. Adv. Comput. Intell. Intell. Inform., Vol.13 No.5, pp. 581-591, 2009.
Data files:
References
  1. [1] M. A. P. Taylor, J. E. Woolley, and R. Zito, “Integration of the global positioning system and geographical information systems for traffic congestion studies,” Transportation Research, Vol.8, pp. 1-6, 2000.
  2. [2] H. Al-Deek, M. Martello, A. D. May, and W. Sanders, “Potential benefits of invehicle information systems in a real life freeway corridor under recurring and incident induced congestion,” In Proc. of the IEEE First VNIS Conf., Toronto, 1989.
  3. [3] L. Breheret, N. B. Hounsell, and M. McDonald, “The simulation of route guidance and traffic incidents,” In Proc. of the UTSG Conf., Hatfield Polytechnic, UK, 1990.
  4. [4] D. E. Boyce, “Route guidance systems for improving urban travel and location choices,” Transportation Research, Vol.22A(4), pp. 275-282, 1988.
  5. [5] B. J. Kanninen, “Intelligent transportation systems : an economic and environmental policy assessment,” Transportation Research, Vol.30A(1), pp. 1-10, 1996.
  6. [6] M. Ben-Akiva, “Dynamic network models and driver information systems,” Transportation Research, Vol.25A(5), pp. 251-266, 1991.
  7. [7] R. Arnott, “Does providing information to drivers reduces traffic congestion?,” Transportation Research, Vol.25A(5), pp. 309-318, 1991.
  8. [8] M. K. Mainali, K. Shimada, S. Mabu, and K. Hirasawa, “Optimal Route Based on Dynamic Programming for Road Networks,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.12, No.4, pp. 546-553, 2008.
  9. [9] E. A. Guggenheim, “Boltzmann’s Distribution Law,” North-Holland Publishing Comp., Amsterdam, 1955.
  10. [10] E. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerische Mathematik, Vol.1, pp. 269-271, 1959.
  11. [11] 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.
  12. [12] 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.
  13. [13] S. Yu, H. Wang, F. Ye, S. Mabu, K. Shimada, and K. Hirasawa, “A Q value-based Dynamic Programming algorithm with Boltzmann distribution for optimizing the global traffic routing strategy,” In Proc. of the SICE 2008 Annual Conf., pp. 619-622, Tokyo, Aug. 2008.
  14. [14] S. Yu, F. Ye, H. Wang, S. Mabu, K. Shimada, S. N. Yu, and K. Hirasawa, “A global routing strategy in dynamic traffic environments with combination of Q value-based Dynamic Programming algorithm and Boltzmann distribution,” In Proc. of the SICE 2008 Annual Conf., pp. 623-627, Tokyo, Aug. 2008.

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

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Apr. 19, 2024