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

Authors

  • 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

Keywords:

Evolutionary algorithm, routing in dynamic networks, car navigation system

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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.

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

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

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

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

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

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

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.

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.

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

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.