A Fast and Scalable Re-routing Algorithm based on Shortest Path and Genetic Algorithms J. Lee, J. Yang Jungkyu Lee
Keywords:
Evolutionary algorithm, routing in dynamic networks, car navigation systemAbstract
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
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
