Algorithms for the quickest time distribution of dynamic stochastic-flow networks

¹ Department of Business Administration, Ling Tung University 1, Lingtung road, Taichung 40852, Taiwan.
mrjane@teamail.ltu.edu.tw
² Department of Finance, Ling Tung University 1, Lingtung road, Taichung 40852, Taiwan.
rubylai@teamail.ltu.edu.tw.

Received: 20 March 2016
Accepted: 1 November 2016

Abstract

Quickest time, which is the least possible time necessary to transmit a fixed amount of data from a source node to a destination node, has been widely explored in the past few years. A quickest path transmits data via a single path, whereas a quickest flow transmits data via all possible paths. In a dynamic stochastic-flow network in which each arc capacity is a discrete random variable having several possible integer values, the quickest time is not a fixed value. Existing literature computes the reliability that the specified amount of flow can be sent simultaneously from the source to the destination through multiple k disjoint minimal paths within a given time horizon. This article presents a decomposition algorithm to compute the probability distribution of the quickest time of a dynamic stochastic-flow network from the viewpoint of flow (all disjoint and non-disjoint minimal paths simultaneously) rather than of k disjoint minimal paths only. The distribution of quickest time is important for the design and analysis of evacuation systems, as they are generally analyzed and optimized via the quickest flow models. As a result, the expected quickest time and the probability that the quickest time is no larger than a specified time threshold can be determined directly. The proposed algorithm can be easily modified to approximate the probability distribution by trading off accuracy for execution time when the network system is large. Computational experiments are conducted to illustrate the proposed algorithms.