Quickest Multistate Flow Networks With the Deterioration Effect

Abstract

In a traditional multistate quickest path problem (MQPP), the system reliability is evaluated based on a strict assumption that the net flow into and out of a system is equal to zero. However, certain networks, which are known as deteriorated networks, suffer a loss due to the deterioration effect, resulting a delivery shortage. For example, the data or goods will deteriorate or decay because the transmission distance is too long, which affects whether the delivered data or goods arrive intact. To provide a practical solution to this problem, a novel MQPP model, known as the deteriorated MQPP (MQPPde) model, is proposed in this work. The goal is to evaluate the system reliability, which is defined as the probability that the end user receives at least d units of data or goods in transmission time T in the case of a MQPP with the deterioration effect. A simple path-based algorithm based on an integer programming model of the flow conservation law is presented to generate all of the lower boundary points (d, T)-MPdes. Next, the reliability of the MQPPde model can be calculated in terms of all of the (d, T)-MPdes.

Keywords

• Multistate flow network (MFN)
• quickest path problem (QPP)
• deteriorated network
• reliability