A metaheuristic based on principles of noisy genetic algorithms is proposed to address the minimum time network flow problem, in which arc traversal times and capacities are random variables with time-varying distribution functions. A specialized encoding scheme exploits the problem's structure. To assess the fitness of solutions at each generation, multiple sampling fitness evaluations are considered. A stratified sampling technique is used in the selection of sample sets for this purpose. Such an approach ensures that scenarios with low probability but high consequence are taken into consideration in evaluating possible solutions and simultaneously accounting for the low likelihood of such events. This work has application in many arenas but was motivated specifically by the need to determine optimal instructions for the evacuation of a geographic region, building, or other large structure in the event of circumstances warranting quick escape.
Get full access to this article
View all access options for this article.
References
1.
AhujaR., MagnantiT., and OrlinJ.Network Flows: Theory, Algorithms and Applications.Prentice-Hall, Inc., Englewood Cliffs, N.J., 1993.
2.
AronsonJ.A Survey of Dynamic Network Flows. Annals of Operations Research, Vol. 20, 1989, pp. 1–66.
3.
FordL., and FulkersonD.Flows in Networks.Princeton University, Princeton, N.J., 1962.
4.
CaiX., ShaD., and WongC.Time-Varying Minimum Cost Flow-Problems. European Journal of Operational Research, Vol. 131, 2001, pp. 352–374.
5.
CaiX., ShaD., and WongC.Time-Varying Universal Maximum Flow Problems. Mathematical and Computer Modelling, Vol. 33, 2001, pp. 407–430.
6.
Miller-HooksE., and Stock PattersonS.On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks. Journal of Mathematical Modeling and Algorithms, Vol. 3, No. 1, 2004, pp. 39–71.
7.
ChenL., and Miller-HooksE.The Building Evacuation Problem with Shared Information. Naval Research Logistics, Vol. 55, No. 4, 2008, pp. 363–376.
8.
FrankO., and GaulW.On Reliability in Stochastic Graphs. Networks, Vol. 12, 1982, pp. 119–126.
9.
LinY.A Simple Algorithm for Reliability Evaluation of a Stochastic-Flow Network with Node Failure. Computers and Operations Research, Vol. 28, 2001, pp. 1277–1285.
10.
LinY.Using Minimal Cuts to Evaluate the System Reliability of a Stochastic-Flow Network with Failures at Nodes and Arcs. Reliability Engineering and System Safety, Vol. 75, 2002, pp. 41–46.
11.
NagamochiH., and IbarakiT.Maximum Flows in Probabilistic Networks. Networks, Vol. 21, 1991, pp. 645–666.
12.
TalebiK., and MacGregor SmithJ.Stochastic Network Evacuation Models. Computers & Operations Research, Vol. 12, No. 6, 1985, pp. 559–577.
13.
GlocknerG., and NemhauserG.A Dynamic Network Flow Problem with Uncertain Arc Capacities: Formulation and Problem Structure. Operations Research, Vol. 48, No. 2, 2000, pp. 233–242.
14.
GlocknerG., NemhauserG., and ToveyC.Dynamic Network Flow with Uncertain Arc Capacities: Decomposition Algorithm and Computational Results. Computational Optimization and Applications, Vol. 18, 2001, pp. 233–250.
15.
KarbowiczC., and MacGregor SmithJ.A K-Shortest Path Routing Heuristic for Stochastic Evacuation Networks. Engineering Optimization, Vol. 7, 1984, pp. 253–280.
16.
OpasanonS., and Miller-HooksE.The Safest Escape Problem. Journal of the Operational Research Society, Vol. 60, 2009, pp. 1749–1759.
17.
HollandJ.Adaptation in Natural and Artificial Systems.MIT Press, Cambridge, Mass., 1975.
18.
VignauxG., and MichalewiczZ.A Genetic Algorithm for the Linear Transportation Problem. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 21, No. 2, 1991, pp. 445–452.
19.
MunakataT., and HashierD.A Genetic Algorithm Applied to the Maximum Flow Problem. The Fifth International Conference on Genetic Algorithms, Urbana–Champaign, Ill., 1993, pp. 488–493.
20.
SadekA. W., SmithB. L., and DemetskyM. J.Dynamic Traffic Assignment: Genetic Algorithms Approach. In Transportation Research Record 1588, TRB, National Research Council, Washington, D.C., 1997, pp. 95–103.
21.
GenM., ChengR., and OrenS.Network Design Techniques Using Adapted Genetic Algorithms. Advances in Engineering Software, Vol. 32, 2001, pp. 731–744.
22.
DaviesC., and LingrasP.Genetic Algorithms for Rerouting Shortest Paths in Dynamic and Stochastic Networks. European Journal of Operational Research, Vol. 144, 2003, pp. 27–38.
23.
FitzpatricJ., and GrefenstetteJ.Genetic Algorithm in Noisy Environments. Machine Learning, Vol. 3, 1988, pp. 101–120.
24.
Miller-HooksE. D., and SorrelG.Maximal Dynamic Expected Flows Problem for Emergency Evacuation Planning. In Transportation Research Record: Journal of the Transportation Research Board, No. 2089, Transportation Research Board of the National Academies, Washington, D.C., 2008, pp. 26–34.
25.
GoldbergD.Genetic Algorithms in Search, Optimization and Machine Learning.Addison-Wesley, New York, 1989.
26.
SmalleyJ., MinskerB., and GoldbergD.Risk-Based In Situ Bioremediation Design Using a Noisy Genetic Algorithm. Water Resources Research, Vol. 36, No. 20, 2000, pp. 3043–3052.
27.
BratleyP., FoxB., and SchrageL.A Guide to Simulation, 2nd ed.Springer-Verlag, New York, 1987.
28.
MarnayC., and StraussT.Effectiveness of Antithetic Sampling and Stratified Sampling in Monte Carlo Chronological Production Cost Modeling. IEEE Transactions on Power Systems, Vol. 6, No. 2, 1991, pp. 669–675.
29.
ZiliaskopoulosA.Optimum Path Algorithms on Multidimensional Networks: Analysis and Design, Implementation and Computational Experience. PhD dissertation. Department of Civil Engineering, University of Texas at Austin, 1994.
30.
Miller-HooksE.Optimal Routing in Time-Varying, Stochastic Networks: Algorithms and Implementation. PhD dissertation. Department of Civil Engineering, University of Texas at Austin, 1997.
