A Fast and Scalable Re-routing Algorithm based on Shortest Path and Genetic Algorithms J. Lee, J. Yang Jungkyu Lee

  • Jungkyu Lee Cyram Inc., 516 Seoul National University Research Park Naksungdae-dong, Gwanak-gu, Seoul 151-919 Koera
  • Jihoon Yang Department of Computer Science, Sogang University 1 Sinsu-dong, Mapo-gu, Seoul 121-742 Koera

Abstract

This paper presents a fast and scalable re-routing algorithm that adapts to dynamically changing networks. The proposed algorithm, DGA, integrates Dijkstra’s shortest path algorithm with the genetic algorithm. Dijkstra’s algorithm is used to define the predecessor array that facilitates the initialization process of the genetic algorithm. Then the genetic algorithm keeps finding the best routes with appropriate genetic operators under dynamic traffic situations. Experimental results demonstrate that DGA produces routes with less traveling time and computational overhead than pure genetic algorithm-based approaches as well as Dijkstra’s algorithm in largescale routing problems.

References

[1] EBU BPN. 027-1 Transport Protocol Experts Group (TPEG) Specifications.

[2] EBU BPN. 027-2 Transport Protocol Experts Group (TPEG) Specifications.

[3] EBU BPN. 027-3 Transport Protocol Experts Group (TPEG) Specifications.

[4] EBU BPN. 027-4 Transport Protocol Experts Group (TPEG) Specifications.

[5] EBU BPN. 027-5 Transport Protocol Experts Group (TPEG) Specifications.

[6] EBU BPN. 027-6 Transport Protocol Experts Group (TPEG) Specifications.

[7] E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271, 1959.
http://dx.doi.org/10.1007/BF01386390

[8] M. Mitchell. An Introduction to Genetic Algorithms. MIT Press, 1996.

[9] C.W. Ahn and R. S. Ramakrishna. A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Transactions on Evolutionary Computation, 6(6):566–579, 2002.
http://dx.doi.org/10.1109/TEVC.2002.804323

[10] D. E. Goldberg. Genetic Algorithms in Search and Optimization. Addison-wesley, 1989.

[11] Q. Zhang and Y. W. Leung. An orthogonal genetic algorithm for multimedia multicast routing. IEEE Transactions on Evolutionary Computation, 3(1):53–62, 1999.
http://dx.doi.org/10.1109/4235.752920

[12] F. Xiang, L. Junzhou, W. Jieyi, and G. Guanqun. QoS routing based on genetic algorithm* 1. Computer Communications, 22(15-16):1392–1399, 1999.
http://dx.doi.org/10.1016/S0140-3664(99)00113-9

[13] Y. Leung, G. Li, and Z. B. Xu. A genetic algorithm for the multiple destination routing problems. IEEE Transactions on Evolutionary Computation, 2(4):150–161, 1998.
http://dx.doi.org/10.1109/4235.738982

[14] H. Kanoh. Dynamic route planning for car navigation systems using virus genetic algorithms. International Journal of Knowledge-based and Intelligent Engineering Systems, 11:65–78, 2007.

[15] H. Kanoh and K. Hara. Hybrid genetic algorithm for dynamic multi-objective route planning with predicted traffic in a real-world road network. In Proceedings of the Conference on Genetic and Evolutionary Computation, pages 657–664. ACM, 2008.

[16] B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest paths algorithms: theory and experimental evaluation. Mathematical Programming, 73(2):129–174, 1996.
http://dx.doi.org/10.1007/BF02592101

[17] R. B. Dial. Algorithm 360: Shortest-path forest with topological ordering [H]. Communications of the ACM, 12(11):632–633, 1969.
http://dx.doi.org/10.1145/363269.363610

[18] R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87–90, 1958.

[19] R. S. Sutton and A. G. Barto. Reinforcement Learning. MIT Press, 1998.

[20] R. Bellman. A Markovian decision process. Journal of Mathematics and Mechanics, 6, 1957.

[21] L. P. Kaelbling, M. L. Littman, and A. W. Moore. Reinforcement learning: a survey. Journal of Artificial Intelligence Research, pages 237–285, 1996.

[22] J. A. Boyan and M. L. Littman. Packet routing in dynamically changing networks: A reinforcement learning approach. Proceedings of the Advances in Neural Information Processing Systems, pages 671–671, 1994.

[23] M. Stanojevi’c, M. Vujoˇsevi’c, and B. Stanojevi’c. Number of Efficient Points in some Multiobjective Combinatorial Optimization Problems. International Journal of Computers, Communications & Control, 3(Suppl.): 497-502, 2008.

[24] I. Harbaoui Dridi, R. Kammarti, M. Ksouri, and P. Borne. Multi-Objective Optimization for the m-PDPTW: Aggregation MethodWith Use of Genetic Algorithm and Lower Bounds. International Journal of Computers, Communications & Control, 6(2): 246-257, 2011.
Published
2014-09-18
How to Cite
LEE, Jungkyu; YANG, Jihoon. A Fast and Scalable Re-routing Algorithm based on Shortest Path and Genetic Algorithms J. Lee, J. Yang Jungkyu Lee. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 7, n. 3, p. 482-493, sep. 2014. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/1389>. Date accessed: 11 july 2020. doi: https://doi.org/10.15837/ijccc.2012.3.1389.

Keywords

Evolutionary algorithm, routing in dynamic networks, car navigation system