Voir la notice de l'article provenant de la source Numdam
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 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 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.
Jane, Chin-Chia 1 ; Laih, Yih-Wenn 2
@article{RO_2017__51_4_1317_0,
author = {Jane, Chin-Chia and Laih, Yih-Wenn},
title = {Algorithms for the quickest time distribution of dynamic stochastic-flow networks},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1317--1330},
publisher = {EDP-Sciences},
volume = {51},
number = {4},
year = {2017},
doi = {10.1051/ro/2016073},
mrnumber = {3783947},
zbl = {1392.05049},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2016073/}
}
TY - JOUR AU - Jane, Chin-Chia AU - Laih, Yih-Wenn TI - Algorithms for the quickest time distribution of dynamic stochastic-flow networks JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2017 SP - 1317 EP - 1330 VL - 51 IS - 4 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2016073/ DO - 10.1051/ro/2016073 LA - en ID - RO_2017__51_4_1317_0 ER -
%0 Journal Article %A Jane, Chin-Chia %A Laih, Yih-Wenn %T Algorithms for the quickest time distribution of dynamic stochastic-flow networks %J RAIRO - Operations Research - Recherche Opérationnelle %D 2017 %P 1317-1330 %V 51 %N 4 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2016073/ %R 10.1051/ro/2016073 %G en %F RO_2017__51_4_1317_0
Jane, Chin-Chia; Laih, Yih-Wenn. Algorithms for the quickest time distribution of dynamic stochastic-flow networks. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 4, pp. 1317-1330. doi: 10.1051/ro/2016073
Cité par Sources :