Shortest Path Planning Strategies through Evolutionary Algorithms
K. Ramachandra Rao, Nitish Saini · Journal of Intelligent Systems · 2007
Shortest path planning problems have been studied extensively in the context of transportation planning applications and related areas.The nature of link costs often decides the type of problem.In situations where there are variations in the level of congestion during a certain time of the day in urban road networks, it is often the case that simple shortest paths are irrelevant.Path information will be useful in situations where route guidance is needed.In this paper, stochastic and time dependent link costs are considered.It is also well established that these types of problems are computationally intractable using the traditional shortest path algorithms.Also in this paper, the application of evolutionary algorithm is explored to overcome the computational intractability in finding the paths.Implementation of the algorithm on randomly generated networks of various sizes show that computing times are a bit high for their use in route guidance.However, the real life implementation of the algorithm needs to be explored further.