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....

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2003, Vol.144 (1), p.27-38
Main Authors: Davies, Cedric, Lingras, Pawan
Format: Article
Language:English
Subjects:
Algorithms
Dynamic and stochastic networks
Genetic algorithms
Operations research
Optimization
Routing
Shortest path
Studies
Systems analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(01)00354-X