Paper:

# 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

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.13 No.6, pp. 704-712, 2009.

- [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] 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] 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] 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] E. Dijkstra, “A Note on Two Problems in Connection with Graphs,” Numerische Mathematik, Vol.1, pp. 269-271, 1959.
- [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] R. Bellman, “The Theory of Dynamic Programming,” Bull. Amer. Math. Soc. 60, pp. 503-515, 1954.
- [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] 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] Y. Tanaka and P. C. Huang, “Multiple destination routing algorithms,” IEICE Trans. Commun., Vol.E76-B, No.5, pp. 544-552, 1993.
- [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] 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] X. F. Jiang, “Routing broadband multicast streams,” Comput. Commun., Vol.15, No.1, pp. 45-51, 1992.
- [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] 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] B. M. Waxman, “Routing of multipoint connections,” IEEE J. Select, Areas Commun., Vol.6, No.9, pp. 1617-1622, 1988.
- [17] M. Imase and B. M. Waxman, “Dynamic Steiner tree problem,” SIAMJ, Discr. Math., Vol.4, No.3, pp. 369-384, 1991.
- [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] K. A. Downsland, “Hill-climbing, simulated annealing and the Steiner problem in graphs,” Eng. Optim., Vol.17, pp. 91-107, 1991.
- [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] 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] P. Winter, “Steiner problem in networks: A survey,” Networks, Vol.17, pp. 129-167, 1987.
- [23] S. VoB, “Steiners problem in graphs: Heuristic methods,” Discr. Applied Math., Vol.40, pp. 45-72, 1992.
- [24] F. K. Hwang, D. S. Richards, and P. Winter, “The Steiner Tree Problem,” Amsterdam, the Netherlands: North-Holland, 1992.
- [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] 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] 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] 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] 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.

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