Time consuming commodity flows in transport networks with vertex buffering

摘要

Transport networks can be often modeled by graphs in which commodity units are to be transported between two excellent vertices, a source vertex and a terminal vertex. If the links between the vertices in the transport network are subject to failure then the probability to transport the commodity units successfully depends on the operating probabilities of the links. For networks, in which transport times of the commodity units can be neglected, the problem to compute this probability can be solved in most cases using well-known and broadly discussed results from network reliability (see e.g. Colbourn (1987) for connectivity problems or Ford & Fulkerson (1962) for flow problems in graphs). This does not hold for networks, in which commodity unit transport is time consuming. Here, the probability to transport commodity units from the source to the terminal vertex within a given time depends not only on the (time-dependent) operating probabilities of the links but also on the decision, along which (of the possible) operating links the commodity units are to be transported. Different decisions lead to different probabilities for a successful transport. The present analysis examines this peculiarity. In the end, an efficient algorithm for computing the probability of a successful transport of a single commodity unit is rendered as well as an efficient algorithm for computing this probability by means of an optimum decision strategy.