Department of Industrial Management
National Taiwan University of Science and Technology
Taipei 106, Taiwan, Republic of China
The quickest path problem, a version of the shortest path problem, is to find a single quickest path that sends a given amount of data from the source to the sink with minimum transmission time. More specifically, the capacity of each arc in a network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc is stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Therefore, the minimum transmission time is not a fixed number. The transmission time can be reduced if the data are transmitted through several minimal paths simultaneously. Focusing on a stochastic flow network with multistate arcs, this article studies the stochastic quickest path problem. We evaluate the probability that d units of data can be sent through two minimal paths (MPs) simultaneously under time constraint T. Such a probability is named the system reliability. A simple algorithm is proposed to generate all (d, T)-MPs and the system reliability can then be computed in terms of (d,T)-MPs by applying inclusion¡Vexclusion.
Keywords:stochastic quickest path problem; minimal paths; time constraint; (d,T)-MP; inclusion¡Vexclusion
(*Contact: E-mail yklin@mail.ntust.edu.tw )
Cite this article as: Yi-Kuei Lin, "THE STOCHASTIC QUICKEST PATH PROBLEM VIA MINIMAL PATHS," Journal of the Chinese Institute of Industrial Engineers, 27, 132-139 (2010).