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

JungKyu Lee | Zendy; Jihoon Yang | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

JungKyu Lee,

Jihoon Yang

Publication year - 2014

Publication title -

international journal of computers communications and control

Language(s) - English

Resource type - Journals

eISSN - 1841-9844

pISSN - 1841-9836

DOI - 10.15837/ijccc.2012.3.1389

Subject(s) - suurballe's algorithm , dijkstra's algorithm , computer science , yen's algorithm , algorithm , shortest path faster algorithm , initialization , genetic algorithm , k shortest path routing , shortest path problem , scalability , overhead (engineering) , path (computing) , routing (electronic design automation) , theoretical computer science , machine learning , computer network , graph , database , programming language , operating system

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research