Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks

This paper considers the problem of finding the shortest path in a dynamic network, where the weights change as yet-to-be-known functions of time. Routing decisions are based on constantly changing predictions of the weights. The problem has some useful applications in computer and highway networks. The Genetic Algorithm (GA) based strategy presented in this paper, adapts to the changing network information by rerouting during the course of its execution. The paper describes the implementation of the algorithm and results of experiments. A brief discussion on potential applications is also provided. (C) 2002 Elsevier Science B.V. All rights reserved.