Issue |
RAIRO-Oper. Res.
Volume 51, Number 4, October-December 2017
|
|
---|---|---|
Page(s) | 1317 - 1330 | |
DOI | https://doi.org/10.1051/ro/2016073 | |
Published online | 27 November 2017 |
Algorithms for the quickest time distribution of dynamic stochastic-flow networks
1 Department of Business Administration, Ling Tung University 1, Lingtung road, Taichung 40852, Taiwan.
mrjane@teamail.ltu.edu.tw
2 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
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.
Mathematics Subject Classification: 05C21 / 90B15 / 90B25
Key words: Dynamic stochastic-flow network / quickest time distribution / decomposition algorithm / reliability
© EDP Sciences, ROADEF, SMAI 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.