Spare Routing Reliability for a Stochastic Flow Network Through Two Minimal Paths Under Budget Constraint

Reducing the transmission time is an imperative issue for many real-life systems such as computers, telecommunication networks, and transportation systems. For a deterministic flow network, the well-known quickest path problem is to find a path with minimum time for sending a specified amount of data through a single minimal path. A stochastic-flow network (SFN) composed by multistate arcs is more suitable to describe some real systems. The minimum transmission time through a SFN is thus not fixed. Allowing the data to be sent through two disjoint minimal paths simultaneously will shorten the transmission time. Hence, this paper is concerned with evaluating the reliability defined as when a SFN can transmit a given amount of data through a specified pair of minimal paths simultaneously under both time and budget constraints. In terms of subsets-union methods, a solution procedure is first proposed to calculate the reliability. Furthermore, a spare routing for boosting the reliability is established in advance to indicate the first pair, and the spare pairs of minimal paths. The corresponding reliability can be subsequently computed. An easy criterion is finally proposed to derive an ideal spare routing with higher reliability.