Top > JACIII > Global Optimal Routing Algorithm for Traffic Systems with Mult ...

single-jc.php

JACIII Vol.13 No.6 pp. 704-712
doi: 10.20965/jaciii.2009.p0704
(2009)

Paper:

Views over last 60 days: 436

Global Optimal Routing Algorithm for Traffic Systems with Multiple ODs

Yu Wang, Shingo Mabu, Shinji Eto, and Kotaro Hirasawa

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

Received:
December 3, 2008
Accepted:
March 27, 2009
Published:
November 20, 2009
Creative Commons License
Keywords:
global optimal, dynamic programming, multiple ODs, traffic volume
Abstract
Global optimal routing for multiple Origin-Destinations (ODs) in traffic systems becomes extremely complicated when considering the traffic volumes on the road sections. This paper proposes a Combinational Algorithm which is combined by Conventional Method, U Algorithm, SU Algorithm, SRU Algorithm, SAU Algorithm and SRAU Algorithm to solve this problem. Among the above 6 algorithms, SRAU Algorithm contributes to the Combinational Algorithm the most, where firstly, all original ODs are sorted by their traffic volumes, and then the order is randomized to generate some routing candidates. For each candidate, before finding the optimal route of the current OD, the traveling times on the optimal routes calculated by ODs with high priority are adjusted and then Q Value-based dynamic programming is utilized to find the optimal route. Next, an updating process is needed to update the traveling time on the route using the current OD. Finally the best solution can be selected out of all solutions. Sufficient simulations show that the proposed routing algorithm is efficient enough to obtain the near optimal solution even in very large scale traffic systems. Also the consideration of the traffic volumes on the road sections enables our proposal to apply to real traffic systems.
Cite this article as:
Y. Wang, S. Mabu, S. Eto, and K. Hirasawa, “Global Optimal Routing Algorithm for Traffic Systems with Multiple ODs,” J. Adv. Comput. Intell. Intell. Inform., Vol.13 No.6, pp. 704-712, 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 in-vehicle 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] G. R. Jagadeesh, T. Srikanthan, and K. H. Quek, “Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks,” IEEE Trans. on Intelligent Transportation Systems, Vol.3, No.4, pp. 301-309, Dec. 2002.
  4. [4] J. L. Bander and C. C. White, III, “A Heuristic Search Algorithm for Path Determination with Learning,” IEEE Trans. on Systems, Man, and Cybernetics-Part A: Systems and Humans, Vol.28, No.1, pp. 131-134, Jan. 1998.
  5. [5] E. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerische Mathematik, Vol.1, pp. 269-271, 1959.
  6. [6] M. K. Mainali, K. Shimada, S. Mabu, and K. Hirasawa, “Optimal Route of Road Networks by Dynamic Programming,” In Proc. of the IEEE World Congress on Computational Intelligence, Honkong, 2008.
  7. [7] R. Bellman, “The Theory of Dynamic Programming,” Bull. Amer. Math. Soc. 60, pp. 503-515, 1954.
  8. [8] 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.
  9. [9] V. Priwan, H. Aida, and T. Saito, “The multicast tree based routing for the complete broadcast multipoint-to-multipoint communications,” IEICE Trans. Commun., Vol.E78-B, No.5, pp. 720-728, 1995.
  10. [10] Y. Tanaka and P. C. Huang, “Multiple destination routing algorithms,” IEICE Trans. Commun., Vol.E76-B, No.5, pp. 544-552, 1993.
  11. [11] K. J. Lee, A. Gersht, and A. Friedman, “Multiple connection routing,” Int. J. Digital Analog Commun. Syst., Vol.3, pp. 177-186, 1990.
  12. [12] V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, “Multicast routing for multimedia communication,” IEEE/ACM Trans., Networking, Vol.1, No.3, pp. 286-292, 1993.
  13. [13] X. F. Jiang, “Routing broadband multicast streams,” Comput. Commun., Vol.15, No.1, pp. 45-51, 1992.
  14. [14] D. C. Verma and P. M. Gopal, “Routing reserved bandwidth multi-point connections,” Comput. Commun. Rev., Vol.23, No.4, pp. 96-105, 1993.
  15. [15] X. L. Lin and L. M. Ni, “Multicast communication in multicomputer networks,” IEEE Trans., Parallel Distrib. Syst., Vol.4, pp. 1105-1117, Nov. 1993.
  16. [16] B. M. Waxman, “Routing of multipoint connections,” IEEE J. Select, Areas Commun., Vol.6, No.9, pp. 1617-1622, 1988.
  17. [17] M. Imase and B. M. Waxman, “Dynamic Steiner tree problem,” SIAMJ, Discr. Math., Vol.4, No.3, pp. 369-384, 1991.
  18. [18] C. Schiemangk, “Thermodynamically motivated simulation for solving the Steiner tree problem and the optimization of interacting path systems in Optimization of Connection Structures in Graphs,” CICIP, A. Iwainsky, Ed. East Berlin, Germany: GRD, pp. 74-90, 1985.
  19. [19] K. A. Downsland, “Hill-climbing, simulated annealing and the Steiner problem in graphs,” Eng. Optim., Vol.17, pp. 91-107, 1991.
  20. [20] A. Kapsalis, V. J. Rayward-Smith, and G. D. Smith, “Solving the graphical Steiner tree problem using genetic algorithms,” J. Opl. Res. Soc., Vol.44, No.4, pp. 397-406, 1993.
  21. [21] H. Esbensen, “Computing near-optimal solutions to the Steiner problem in a graph using a genetic algorithm,” Networks, Vol.26, pp. 173-185, 1995.
  22. [22] P. Winter, “Steiner problem in networks: A survey,” Networks, Vol.17, pp. 129-167, 1987.
  23. [23] S. VoB, “Steiners problem in graphs: Heuristic methods,” Discr. Applied Math., Vol.40, pp. 45-72, 1992.
  24. [24] F. K. Hwang, D. S. Richards, and P. Winter, “The Steiner Tree Problem,” Amsterdam, the Netherlands: North-Holland, 1992.
  25. [25] S. Yu, H. Wang, F. Ye, S. Mabu, K. Shimada and K. Hirasaw, “A Q value-based Dynamic Programming algorithm with Boltzmann Distribution for optimizing the global traffic routing strategy,” SICE Annual Conf., pp. 619-622, August, 2008.
  26. [26] S. Misra and B. J. Oommen, “Dynamic Algorithms for the Shortest Path Routing Problem: Learning Automata-Based Solutions,” IEEE Trans. on Systems, Man and Cybernetics-Part B: Cybernetics, Vol.35, No.6, pp. 1179-1192, Dec. 2005.
  27. [27] P. Narvaez, K.-Y Siu, and H.-Y Tzeng, “New Dynamic Algorithms for Shortest Path Tree Computation,” IEEE/ACM Trans. on Networking, Vol.8, No.6, pp. 734-746, Dec. 2000.
  28. [28] B. Xiao, Q. ZhuGe, and E. H.-M. Sha, “Minimum Dynamic Update for Shortest Path Tree Construction,” Global Telecommunications Conf., San Antonio, TX, pp. 126-130, 2001.
  29. [29] M. K. Mainali, K. Shimada, S. Mabu, and K. Hirasawa, “Optimal Route Based on Dynamic Programming for Road Networks,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.12 No.4, 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 Dec. 02, 2024