×

Genetic algorithms for rerouting shortest paths in dynamic and stochastic networks. (English) Zbl 1037.90027

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

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B15 Stochastic network models in operations research

Software:

Algorithm 97; GALib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dijkstra, E. W., A note on two papers in connection with graphs, Numeriske Mathematics, 1, 269-271 (1959) · Zbl 0092.16002
[2] Eppstein, D., Finding the \(k\) shortest paths, SIAM Journal on Computing, 28, 2, 653-674 (1998)
[3] Floyd, R. W., Algorithm 97: Shortest paths, Communications of the ACM, 5, 345 (1962)
[4] Cai, X.; Kloks, T.; Wong, C. K., Time-varying shortest path problems with constraints, Networks, 29, 3, 141-149 (1997) · Zbl 0876.05060
[5] Dreyfus, E. S., An appraisal of some shortest path algorithms, Operations Research, 17, 395-412 (1969) · Zbl 0172.44202
[6] Frank, H., Shortest paths in probabilistic graphs, Operations Research, 17, 583-599 (1968) · Zbl 0176.48301
[7] L. Fu, Real-time vehicle routing and scheduling in dynamic and stochastic networks, Ph.D. Thesis at the University of Alberta, 1996; L. Fu, Real-time vehicle routing and scheduling in dynamic and stochastic networks, Ph.D. Thesis at the University of Alberta, 1996
[8] Orda, A.; Rom, R., Distributed shortest-path protocols for time-dependent networks, Distributed Computing, 10, 1, 49-62 (1996) · Zbl 1448.68153
[9] Orda, A.; Rom, R., Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length, Journal of ACM, 37, 3, 607-625 (1990) · Zbl 0699.68074
[10] Buckley, F.; Harary, F., Distance in Graphs (1990), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0688.05017
[11] Mirchandani, P. B., Shortest distance reliability of probabilistic networks computer, Operations Research, 3, 347-356 (1976)
[12] Gen, M.; Cheng, R.; Wang, D., Genetic algorithms for solving shortest path problems, (Proceedings of 1997 IEEE International Conference on Evolutionary Computing (1997)), 401-406
[13] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor
[14] Buckles, B. P.; Petry, F. E., Genetic Algorithms (1994), IEEE Computer Press: IEEE Computer Press Los Alamitos, CA · Zbl 0942.68695
[15] DeJong, K., (Learning with Genetic Algorithms: An Overview. Learning with Genetic Algorithms: An Overview, Machine Learning, vol. 3 (1998), Kluwer Academic: Kluwer Academic Hingham, MA), 121-138
[16] Philpott, A. B.; Mees, A. I., A finite-time algorithm for shortest path problems with time-varying costs, Applied Mathematics Letters, 6, 2, 91-94 (1993) · Zbl 0770.68095
[17] M. Wall, Galib - A C++ Library of Genetic Components, 1993. http://lancet.mit.edu/ga/; M. Wall, Galib - A C++ Library of Genetic Components, 1993. http://lancet.mit.edu/ga/
[18] The Diebold Institute for Public Policy Studies Inc., Transportation Infostructures: The Development of Intelligent Transportation Systems, Praeger, New York, 1995; The Diebold Institute for Public Policy Studies Inc., Transportation Infostructures: The Development of Intelligent Transportation Systems, Praeger, New York, 1995
[19] Davies, D.; Barber, D.; Prince, W.; Solomonides, C., Computer Networks and Their Protocols (1979), Wiley: Wiley New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.