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.