Capacity reliability under uncertainty in transportation networks: an optimization framework and stability assessment methodology

Abstract

Destruction of the roads and disruption in transportation networks are the aftermath of natural disasters, particularly if they are of great magnitude. As a version of the network capacity reliability problem, this work researches a post-disaster transportation network, where the reliability and operational capacity of links are uncertain. Uncertainty theory is utilized to develop a model of and solve the uncertain maximum capacity path (UMCP) problem to ensure that the maximum amount of relief materials and rescue vehicles arrive at areas impacted by the disaster. We originally present two new problems of $\alpha$-maximum capacity path ($\alpha$-MCP), which aims to determine paths of highest capacity under a given confidence level $\alpha$, and most maximum capacity path (MMCP), where the objective is to maximize the confidence level under a given threshold of capacity value. We utilize these auxiliary programming models to explicate the method to, in an uncertain network, achieve the uncertainty distribution of the MCP value. A novel approach is additionally suggested to confront, in the framework of uncertainty programming, the stability analysis problem. We explicitly enunciate the method of computing the links’ tolerances in ${\mathcal{O}}\left( m \right)$ time or ${\mathcal{O}}\left( {\left| {P^{*} } \right|m} \right)$ time (where $m$ indicates the number of links in the network and $\left| {{\text{P}}^{*} } \right|$ the number of links on the given MCP ${\text{P}}^{*}$). After all, the practical performance of the method and optimization model is illustrated by adopting two network samples from a real case study to show how our approach works in realistic contexts.

1 Introduction

Modern societies are crucially dependent on infrastructure systems, such as electricity, telecommunication, and transportation. Such systems have a networked nature; therefore, natural, internal, or deliberate impairment of one component will cause other components to fail. Studying system-level reliability against disruption will be required. As an aftermath of natural disasters, particularly massive ones like floods and earthquakes, demolished roads may cause serious calamitous events if they lead to an uncertain transportation network. Consequently, the primary issue to address by disaster responders is the problem of system reliability, so that reliable paths may ensure the transmitting relief materials. Therefore, identifying the maximum capacity paths (MCPs) in the network is needed to ensure that the maximum amount of relief materials and the maximum number of rescue vehicles arrive at areas impacted by the disaster.

Transportation networks may be blocked by collapsed buildings, fault rupture, and falling bridges after catastrophes. Consequently, transportation system capacity may decline and the network performance becomes uncertain, complicating dispatch of rescue vehicles and relief materials to impacted areas (Xing and Zhou 2011). Hence, compared with the deterministic transportation networks, an uncertain network is a more realistic depiction of an actual post-disaster transportation network. A considerable degree of uncertainty that may be attributed to factors such as capacity and reliability is disposed on transportation networks especially after disasters. Reliability and functional capacity of post-disaster networks are therefore essential factors to examine since they act as lifelines that make impacted areas reachable and support evacuation, emergency response, and long-term post-disaster recovery activities (Zhu et al. 2018). In the absence of precise information on the links’ functionality and subsequent inability to use random variables to characterize the indeterminacy, it is impossible to estimate the relevant probability distribution. Adverse and unforeseeable system performance, demonstrated in a high degree of variability in system parameters will be the outcomes thereof. Additionally, computationally intractable problems arise due to probabilistic programming approaches that inflict long computational time and more expense to decision-makers. Lack of information and avoiding computational intractability may usually cause inaccurate variables, derived from experts' empirical data, to emerge in the form of 'belief degrees' stated by some domain experts. Nevertheless, since unlikely events are frequent and the variance of belief degree may be greater than real frequency, dealing with belief degree by probability theory or fuzzy theory may result in counterintuitive results. Uncertainty theory is propounded to deal with these uncertain variables and its efficacy has been proved.

The contribution of this paper is twofold. First, it presents a model based on uncertainty theory for the analysis of a version of the capacity reliability problem in an uncertain post-disaster transportation network with ‘unknown’ or ‘not accurate enough’ capacity factors. In the literature, according to the author’s knowledge, there is no example of the MCP problem and its stability analysis in the framework of uncertainty theory, and this type of uncertainty is new to the context of transportation networks that it neither relies on any probability distribution nor fuzzy membership function. The second contribution of this survey is to advance research in stability analysis, also called sensitivity analysis, of transportation networks (Ahuja et al. 1993). If a post-disaster impaired network is considered, network uncertainty and/or stability are the significant problems that have to be assessed in the network. Nevertheless, just a few studies have been conducted on the reliability and stability of networks under extreme conditions and associated problems. At the time of a disaster, network performance in terms of reliability and accessible capacity becomes an uncertain issue because of the uncertainty of the street service situation and the varying travel needs. Therefore, the primary problem to attend to in disaster management is system reliability for dispatching relief materials to the affected areas. Since the transportation network after a disaster becomes an uncertain network, it should come as no surprise that the disaster managers wish to find out the stability of MCPs in the system. In response to such a need, this study examines the network capacity reliability and aims at assessing the transportation network capacity reliability under extreme events and catastrophes. We will let links' capacities be uncertain variables and present the stability analysis in transportation networks in the framework of uncertainty theory. Accordingly, some new programming frameworks, called $\alpha$-maximum capacity path ($\alpha$-MCP) and most maximum capacity path (MMCP) are proposed. Both $\alpha$-MCP and MMCP are intended, though with different decision standards, to situate paths that constitute the safe possible routes for transportation accommodating maximum traffic at a requisite service level. Besides, an approach to get the uncertainty distribution of the uncertain MCP and an algorithm to assess the influence of changes in links' reliabilities on MCPs (yielding the concept of tolerances) are provided.

The study will continue with further sections. A review of literature on reliability problems in transportation networks is presented in Sect. 2, and it is followed by a selective review on different aspects of network reliability problems in different premises and various measures and goes on to describe the research gaps and the contributions of this study. Section 3 develops the necessary definitions, concepts, and preliminary components on uncertainty theory for Sect. 4 to deal with the problem of the uncertain maximum capacity path (UMCP), the proposed models, and the programming models of ${\upalpha }$-MCP and MMCP. Acquiring the uncertainty distribution of the UMCP in uncertain transportation networks is also explicated in this section. The UMCP stability analysis in transportation networks under uncertainty is articulated and formulated in Sect. 5, which comprises mainly the implementation of ${\upalpha }$-MCPs to compute the upper and lower tolerances in uncertain networks. The functionality of the method is validated in Sect. 6 by adopting two samples from a case study to show how our approach works in realistic settings. The conclusion, a summary, and some suggestions for future research are provided in Sect. 7.

2 Related works on network reliability

Different real-life sectors, including transportation, traffic cybernetics, disaster management, communication, and production–distribution systems will benefit from utilizing path finding and reliability problems (Xing and Zhou 2011; Hosseini and Wadbro 2016). Reliability in traffic cybernetics and communication networks is a decisive measure of the quality of service for transportation, avoiding traffic congestion, and has a large effect on route selection. Over the last two decades, therefore, the OR literature has shown substantial interest in network reliability in communication and transportation networks (Zhu et al. 2018). The literature abounds in analytical and modeling approaches to help assess the reliability of road networks with varying metrics. Subsequently, several different aspects of network reliability are reviewed: travel time reliability, connectivity reliability, and capacity reliability.

The issue involved in travel time reliability is the probability of a successful trip between a specific source-sink pair within a specified period. The network performance under normal daily flow variation can be usefully assessed by this measure (Xing and Zhou 2011). Analysis and quantification of travel time variability have been emphasized by researchers to be complicated because it being a function with many factors including congestion, flow, incidents, facility characteristics, and free-flow travel time. Especially, an interrelation between mean and standard deviation, in particular, has been observed. A relaxation-based solution procedure for integer programming formulation was suggested by Seshadri and Srinivasan (2012) using a similar formulation. The formulation is appropriate for correlation structures with cycle covariance property. As suggested by Seshadri and Srinivasan (2012), if Cholesky coefficients of the link covariance matrix are positive, a non-dominance-based method and a heuristic for the mean–variance trade-off problem can be implemented. Two methods to estimate minimum robust cost path with and without link correlations were presented by Xing and Zhou (2011) which incorporate a Lagrangian relaxation approach. The path which, in a specific threshold, optimizes the probability of arrival was specified by Frank (1969) to be the most efficient. The shortest paths are decided through paired difference tests even though a well-defined method has been provided for the calculation of the travel time of their distribution. Another routing procedure under adjustable conditions was suggested by Xiao and Lo (2013) in which the last utility was measured through prospect theory integrating both scheduled travel time and on-time arrival.

Connectivity reliability is the second important concept of reliability that has been adequately investigated in networks. This concept involves the probability of nodes staying connected and indicates the chance of the presence of a minimum of one path having usable capacity between a definite source-sink pair. Connectivity of the links is the main factor determining the connectivity reliability of a network and most researchers have therefore aimed, by different methods, at estimating network reliability based on component reliability. These methods include statistical methods, simulation, and complex network theory (Hosseini and Wadbro 2016). Zhu et al. (2018) quantified the quality of connections by a dynamic weighted model based on NetScan regarding flight capacity and time. Estimation of transit connectivity at different levels was suggested through a graph-theoretic method designed by Mishra et al. (2015). Later, Zhu et al. (2018) bettered a connectivity index and presented it concerning the interaction between transportation networks and the urban environment. Detection of essential nodes has later been done through this index. An integrated port connectivity index was created by Wang et al. (2016) which comprised three layers of the international, inner bay, and hinterland connectivity in addition to providing a detailed overview of port connectivity. Aydin et al. (2018), using the size of a giant connected component, suggested the connectivity of networks whose metrics are used to identify post-disaster networks or assessed with simulations for varying situations. Three operational measures of the total length of the network, distance-based accessibility, and areal distance-based accessibility were suggested by Chang and Nojima (2001) for roads after an earthquake.

Even though the current reliability measures for evaluating different parameters of the performance of transportation networks are practical, none of the above measures assesses the capacity of the network to hold demand/traffic. As of now, the few studies conducted on the reliability of road networks cannot satisfy an extensive network performance measure since they are mostly focused on connectivity and travel time reliability. Consequently, Chen et al. (1999) presented the new index of capacity reliability which is the probability of a network having the capacity to allow a specific traffic demand at a particular service level, and later on proceeded to expand the capacity reliability analysis. To examine the operation of a degradable road network, they provided an extensive methodology by conjoining reliability and uncertainty analysis, network equilibrium models, and sensitivity analysis of equilibrium network flow together with Monte Carlo methods. Kuang et al. (2013) developed a two-level programming model based on travel time reliability, with regard to source-sink traffic demand multiplier, for investigating the interaction between two kinds of reliability and assessing the capacity reliability. Qin et al. (2018) developed an optimization framework for emergency resource layout regarding the extent of emergency resources, reserve capacity, and the number of locations. The objective function of this framework is to reduce the system expenses to the minimum. A recent study by Zhang et al. (2019) has introduced the concepts of emergency reliability and reserve capacity and designed a two-level programming model as a solution for transportation network reliability in an exigency. Such concepts of capacity reliabilities have had a wide application in transport planning and network operations to include the uncertainties in transport networks, including air transportation, public transit, and logistic networks.

2.1 Study objectives

The stochastic nature of the network is gaining popularity for reliability and pathfinding problems. However, the researchers still employ probability or fuzzy theories for travel time reliability or connectivity reliability (with different assumptions) (Xing and Zhou 2011). A practical indeterminacy, however, about the parameters (e.g., link capacities) of transportation networks is present which, in the absence of any samples, random variables are unable to describe. In case of disaster (e.g., earthquakes), it would not be possible to get probability distributions of links' capacities if transportation networks are dramatically affected. It would be unreasonable to continue to use probability theory to handle such indeterminacy. Yet, specialists have the experience to assess the belief degree that the values of links' capacities are less than or equal to a specific value. Liu in 2007 introduced the uncertainty theory as a new branch of mathematics to deal with this kind of human uncertainty. New programming models are required to find paths of more reliability and functional capacity to improve the performance of rescue work. This becomes even more important after a disaster when information is not sufficient for estimating the probability distributions and using random variables to specify the indeterminacy in detail.

In summary, it can be concluded that the current literature does not contain enough analytical and modeling attitudes to the synchronous study of the capacity and the stability of paths (affected by disasters) in the framework of uncertainty programming. This paper, therefore, aims to disclose the previously undescribed characteristics; i.e. the capacity reliability and stability in an uncertain environment. An uncertain transportation network is discussed in which roads (shown as links) and intersections (shown as by nodes) are disrupted, leading to uncertain variables for the capacity of links in the network. The aim here is to find the most commodious paths to the specified destination to guarantee the arrival of maximum rescue vehicles and materials. To achieve this goal, the uncertain maximum capacity path (UMCP) programming model, which accommodates reliability and capacity requirements, is presented and explicated to ensure that the maximum relief materials reach the afflicted areas. The uncertain variable that represents each link is not fuzzy or stochastic, and MCP cannot be found in the normal sense because of the uncertainty. MCP's objective functions and constraint functions are monotonic regarding the uncertain capacity parameters. The MCP uncertain programming model was consequently converted to some new mathematical programming models. The second goal of this study is to assess the influence of changes in various links' reliabilities on MCPs, yielding the concept of tolerance. In addition, our goal is to ascertain the effect of each corresponding link's capacity on the MCPs in the system. In an associated deterministic network, the presence of an equivalence relation between the tolerances in an uncertain network and the tolerances of an ${\upalpha }$-MCP programming model is shown. This relation, using the operational law of uncertainty theory, will help to calculate the links' tolerances. As a result, this paper also marginally contributes to the thriving body of knowledge about uncertainty programming.

3 Preliminaries of uncertainty theory and concepts

There usually exists insufficient data on an unknown state of nature because of maintenance, technical complications, or economic problems and it has been discussed that the imprecise data behave in neither a fuzzy nor a random pattern (Liu 2010, 2013, 2021; Qing and Yuhong 2012; Hosseini 2015). Domain experts and their evaluation of belief degree for events’ occurrence are required in such cases. However, dealing with belief degree by probability theory or fuzzy theory may result in counterintuitive outcomes, since unlikely events are often and thus the variance of belief degree may be much larger than real frequency. This situation calls for inventing a new mathematical tool that is the uncertainty theory. Liu provided the axiomatic system of uncertainty theory unrelated to probability or fuzzy theories, for a better description of human decisions in the state of uncertainty (Liu 2021). The uncertainty theory challenges the dominance of standard probability approaches in decision theory and risk analysis, and consequently, has undergone numerous expansive researches and has gathered enormous attention. The efficiency of uncertainty theory has been observed in theory and practice as a tool to handle nondeterministic information, especially subjective estimation (Liu 2010, 2013, 2021; Qing and Yuhong 2012; Hosseini 2015; Gao 2012).

The belief degree that each event will occur needs to be indicated by a set function. ${\mathcal{M}}$ is an uncertain measure if it follows the under-mentioned axioms of uncertainty. To rationally cope with belief degrees, let ${\Gamma }$ be a non-empty set (universal set), and ${\mathcal{L}}$ a $\sigma$-algebra over ${\Gamma }$. The pair $\left( {\Gamma , {\mathcal{L}}} \right)$ is called a measurable space, the triplet $\left( {\Gamma , {\mathcal{L}}, {\mathcal{M}}} \right)$ is called an uncertainty space, and each element $E \in {\mathcal{L}}$ is a measurable set that is referred to as an event. We will associate each element $E \in {\mathcal{L}}$ with a number ${\mathcal{M}}\left( E \right)$ indicating the level that $E$ will occur. That is ${\mathcal{M}}$ is a set function. There is no doubt that the assignment is not arbitrary, and the uncertain measure ${\mathcal{M}}$ must have certain mathematical properties. If ${\mathcal{M}}$ satisfies the following axioms, then it is an uncertain measure (Liu 2021).

• Normality: ${\mathcal{M}}\left\{ {\Gamma } \right\} = 1$ for the universal set $\Gamma$,

• Duality: ${\mathcal{M}}\left\{ {\text{E}} \right\} + {\mathcal{M}}\left\{ {E^{c} } \right\} = 1$ for any event $E \in {\mathcal{L}}$,

• Subadditivity: ${\mathcal{M}}\left\{ {\bigcup\nolimits_{i = 1}^{\infty } {E_{i} } } \right\} \le \sum\nolimits_{i = 1}^{i = \infty } {\mathcal{M}} \left\{ {E_{i} } \right\}$ for any sequence of events $\left\{ {E_{i} } \right\}$,

• Product measure: ${\mathcal{M}}\left\{ {\prod\nolimits_{i = 1}^{n} {E_{i} } } \right\} = \wedge_{{i \in \left\{ {1, \ldots ,n} \right\}}} {\mathcal{M}}_{i} \left\{ {E_{i} } \right\}$ for uncertainty spaces $\left( {{\Gamma }_{i} ,{\mathcal{L}}_{i} ,{\mathcal{M}}_{i} } \right)$ and $E_{i} \in {\mathcal{L}}_{i}$.

It follows from Normality and Duality axioms that the empty set has an uncertain measure of zero. Therefore, for any event $E \in {\mathcal{L}}$, we have $0 \le {\mathcal{M}}\left\{ {\text{E}} \right\} \le 1$. The uncertain measure is to be described as the personal belief degree, not the frequency, of an uncertain event, which can occur. Hence, it is commonly based on personal knowledge about the event. The uncertain measure can vary if the state of knowledge varies. The frequency of an event (which is the building block of probability theory) is, on the contrary, a factual attribute that is not dependent on knowledge about the event. To put it simply, the frequency, irrespective of being observed or not, is present throughout and is comparatively invariant (Liu 2010, 2021).

Definition 1

(Liu 2021) The uncertain variable ${\upxi }$ is defined as a measurable function from $\left( {{\Gamma },{\mathcal{L}},{\mathcal{M}}} \right)$ to the set of real numbers such that $\left\{ {\xi \in B} \right\} = {\text{\{ }}\gamma \in \Gamma {|} \xi \left( \gamma \right) \in B\}$ is an event for any Borel set ${\text{B}}$ of real numbers. The uncertain variable ${\upxi }$ is referred as to nonnegative if ${\mathcal{M}}\{ {\upxi } < 0\} = 0$, and positive if ${\mathcal{M}}\left\{ {{\upxi } \le 0} \right\} = 0$.

Definition 2

(Liu 2010) The uncertain variables $\xi_{1} ,\xi_{2} ,...,\xi_{m}$ are said to be independent if

$$ {\mathcal{M}}\left\{ {\bigcap\limits_{i = 1}^{m} {\left\{ {\xi_{i} \in B_{i} } \right\}} } \right\} = \mathop \wedge \limits_{{i \in \left\{ {1, \ldots ,m} \right\}}} {\mathcal{M}}\left\{ {\xi_{i} \in B_{i} } \right\}, $$

for any family of Borel sets $B_{1} ,B_{2} ,...,B_{m}$ of real numbers.

Definition 3

(Liu 2021) The uncertainty distribution of an uncertain variable ${\upxi }$ is defined by a function $\Phi \left( x \right) = {\mathcal{M}}\left\{ {\xi \le x} \right\}$ for any real number $x$.

Definition 4

(Liu 2021) A distribution $\Phi$ can be named regular if it is a continuous and strictly increasing function to $x$ at all $x$ satisfying $0 < \Phi \left( x \right) < 1$. Namely, $\Phi \left( {x_{1} ,x_{2} , \ldots ,x_{m} } \right) \ge \Phi \left( {y_{1} ,y_{2} , \ldots ,y_{m} } \right)$ whenever $x_{i} \ge y_{i}$ for $i = 1,2, \ldots ,m$, and $\Phi \left( {x_{1} ,x_{2} , \ldots ,x_{m} } \right) > \Phi \left( {y_{1} ,y_{2} , \ldots ,y_{m} } \right)$ whenever $x_{i} > y_{i}$ for $i = 1,2,...,m$.

Considering any variable $\xi$ with regular uncertainty distribution $\Phi \left( x \right)$, there exists a well-defined continuous and strictly increasing inverse uncertainty distribution $\Phi^{ - 1} \left( \alpha \right)$ over the open interval $\left( {0,1} \right)$ for which ${\mathcal{M}}\{ {\upxi } \le \Phi^{ - 1} \left( \alpha \right)\} = \alpha$ (Liu 2021).

Theorem 1

(Liu 2021) A function $\Phi :{\mathbb{R}} \mapsto \left[ {0,1} \right]$ stands as an uncertainty distribution if and only if it is a monotone increasing function except for $\Phi \left( x \right) \equiv 0$ and $\Phi \left( x \right) \equiv 1$. Moreover, a function $\Phi :\left( {0,1} \right) \mapsto {\mathbb{R}}$ is an inverse uncertainty distribution if and only if it is a continuous and strictly increasing function.

Theorem 2

(Liu 2010) Let $\xi_{1} ,\xi_{2} , \ldots ,\xi_{n}$ be independent uncertain variables with regular uncertainty distributions $\phi_{1} ,\phi_{2} , \ldots ,\phi_{n}$. If the function $\xi = f\left( {\xi_{1} ,\xi_{2} , \ldots ,\xi_{n} } \right)$ is strictly increasing to $\xi_{1} ,\xi_{2} , \ldots ,\xi_{m}$ and strictly decreasing to $\xi_{m + 1} ,\xi_{m + 2} , \ldots ,\xi_{n}$, then

• (a) $\xi$ is also an uncertain variable with inverse uncertainty distribution

  $$ \psi^{ - 1} \left( \alpha \right) = f\left( {\phi_{1}^{ - 1} \left( \alpha \right), \ldots ,\phi_{m}^{ - 1} \left( \alpha \right),\phi_{m + 1}^{ - 1} \left( {1 - \alpha } \right), \ldots ,\phi_{n}^{ - 1} \left( {1 - \alpha } \right)} \right). $$

• (b) The chance constraint ${\mathcal{M}}\left\{ {f\left( {x,\xi_{1} ,\xi_{2} , \ldots ,\xi_{n} } \right) \le 0} \right\} \ge \alpha$ holds if and only if

  $$ f\left( {x,\phi_{1}^{ - 1} \left( \alpha \right), \ldots ,\phi_{m}^{ - 1} \left( \alpha \right),\phi_{m + 1}^{ - 1} \left( {1 - \alpha } \right), \ldots ,\phi_{n}^{ - 1} \left( {1 - \alpha } \right)} \right) \le 0. $$

Remark 1

(Liu 2021) A real number $c$ can be considered as a constant function ${\upxi }\left( {\upgamma } \right) \equiv {\text{c}}$ that is independent of any uncertain variable on the uncertainty space $\left( {{\Gamma },{\mathcal{L}},{\mathcal{M}}} \right)$. Moreover, for practical purposes, we can consider all uncertainty distributions as regular. Otherwise, a small perturbation can be given to get a regular distribution.

4 Uncertain maximum capacity path (UMCP)

The maximum capacity path (MCP) problem is the earliest combinatorial optimization problem whose primary objective is to detect the maximum attainable flow that a transportation network can carry. This problem is the core of determining the capacity reliability of a network or system and provides prominent information for efficient control of flow, capacity expansion, and other relevant works to improve the reliability of a network. It also has the potential of devising tools for designing transportation networks that are resistant to traffic disasters.

Let $N = \left( {V,A} \right)$ be a transportation network with $V$ and $A$ denoting the set of nodes and links. $n = \left| V \right|$ and $m = \left| A \right|$ are defined to be the number of nodes and links, respectively. In the whole of the paper, we let $s \in V$ and $t \in V$ denote the source node and the sink node, respectively. A path $P$ from $v_{1}$ to $v_{k}$ is defined by a sequence of nodes $v_{1} ,v_{2} , \ldots ,v_{k - 1} ,v_{k}$ with the property that every consecutive pair of nodes $v_{i}$ and $v_{i + 1}$ is connected by a link. We let ${\mathcal{P}} = \left\{ {P_{k} } \right\}$ show the set of all $s$–$t$-paths in $N$; that is, ${\mathcal{P}}$ contains whole paths from $s$ to $t$ in $N$.

4.1 Deterministic settings

We consider that each link $\left( {i,j} \right) \in A$ possesses a capacity parameter $c_{ij} \in \left( {0,\infty } \right]$ in the deterministic setting. The capacity calculates the maximum value of flow, which may be transmitted via the link. The MCP problem is to find a path connecting the source and sink nodes in the network, such that the minimum link capacity on this path is maximized. More precisely, we wish to find a path $P$ that has the highest capacity, and thus we attempt to maximize the objective function $c_{P} = {\text{min}}_{{\left( {i,j} \right) \in P}} c_{ij}$ over the set of whole paths from $s$ to $t$ in $N$, where $c_{p}$ denotes the capacity of path $P$. Therefore, the MCP problem in the deterministic setting is of the following form.

$$ \begin{array}{*{20}l} {{\text{max}}\left\{ {c_{P} |P \in {\mathcal{P}} {\text{and}} c_{P} = \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} c_{ij} } \right\}.} \hfill \\ \end{array} $$

(1)

4.2 Uncertain settings

We investigate the case where we are given an uncertain measure ${\mathcal{M}}$. Besides, each link is associated with an uncertain capacity variable. Formally, for any link $\left( {i,j} \right) \in A$ there is an uncertain capacity variable $\xi_{ij}$. A path $P$ in an uncertain network with uncertain capacity variables $\{ \xi_{ij} |\left( {i,j} \right) \in A\}$ can be represented as an uncertain family by $\xi_{P} = \{ \xi_{ij} |\left( {i,j} \right) \in P\}$. The uncertain capacity variable associated with path $P$ is then represented by

$$ f\left( {\xi_{P} } \right) = \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} = \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in A}} \left\{ {\xi_{ij} x_{ij} + M\left( {1 - x_{ij} } \right)} \right\} $$

(2)

where $x_{ij} = 1$ if the link $\left( {i,j} \right)$ belongs to path $P$ and zero otherwise, and $M$ is a constant such that $M > {\text{max}}_{{\left( {i,j} \right) \in A}} \left\{ {\xi_{ij} } \right\}$. The capacity of each path is in the form of Eq. (2) which is a monotonically increasing, measurable function from the uncertainty space to the set of real numbers. Therefore, $f\left( {\xi_{P} } \right)$ is additionally an uncertain variable. Moreover, it has an inverse uncertainty distribution as Theorem 2. In other words, Expression (2) represents the objective function which shall be maximized in the uncertain MCP problem (to find the paths with highest capacities); i.e.,

$$ \begin{array}{*{20}l} {{\text{max}}\left\{ {f\left( {\xi_{P} } \right){ }|{ }P \in {\mathcal{P}}\, {\text{and}}\, f\left( {\xi_{P} } \right) = \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} } \right\}.} \hfill \\ \end{array} $$

(3)

The $f\left( {\xi_{P} } \right)$ value is uncertain; we should specify what we intend with “maximizing objective function (2)”.

Lemma 1

(Existence of uncertainty distribution) $N = \left( {V,A} \right)$ is an uncertain transportation network that consists of independent uncertain variables $\{ \xi_{ij} |\left( {i,j} \right) \in A\}$ along with its links having distributions $\{ \Phi_{ij} |\left( {i,j} \right) \in A\}$. For the objective function of the UMCP problem in (3), there is the uncertainty distribution $\Psi$. For any arbitrary $s$–$t$-path $P$ as well as for any real number $x$, we have:

$$ \Psi \left( x \right) = {\mathcal{M}}\left\{ {f\left( {\xi_{P} } \right) \le x} \right\} = \mathop {sup}\limits_{{miny_{ij} = x}} \mathop {min}\limits_{{\left( {i,j} \right) \in P}} \Phi_{ij} \left( {y_{ij} } \right). $$

Proof

The function $f\left( {\xi_{P} } \right)$ is a continuous and strictly increasing function of uncertain capacity factors; thus, it follows from the Polyrectangular (Liu 2021) that

$$ \begin{aligned} {\mathcal{M}}\left\{ {f\left( {\xi_{P} } \right) \le x} \right\} & = {\mathcal{M}}\left\{ {\mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} \le x} \right\} \\ & = {\mathcal{M}}\left\{ {\mathop \cup \limits_{{{\text{min}}y_{ij} = x}} \mathop \cap \limits_{{\left( {i,j} \right) \in P}} \left( {\xi_{ij} \le y_{ij} } \right)} \right\} \\ & = \mathop {{\text{sup}}}\limits_{{{\text{min}}y_{ij} = x}} {\mathcal{M}}\left\{ {\mathop \cap \limits_{{\left( {i,j} \right) \in P}} \left( {\xi_{ij} \le y_{ij} } \right)} \right\} \\ \end{aligned} $$

(4)

As the uncertain variables $\xi_{ij}$ are independent, it is concluded that:

$$ \begin{array}{*{20}l} {\Psi \left( x \right) = \mathop {sup}\limits_{{miny_{ij} = x}} \mathop {min}\limits_{{\left( {i,j} \right) \in P}} {\mathcal{M}}\left\{ {\xi_{ij} \le y_{ij} } \right\} = \mathop {sup}\limits_{{miny_{ij} = x}} \mathop {min}\limits_{{\left( {i,j} \right) \in P}} \Phi_{ij} \left( {y_{ij} } \right). } \hfill \\ \end{array} $$

□

Corollary 1

If the uncertain capacity variables $\{ \xi_{ij} |\left( {i,j} \right) \in A\}$ are independent with uncertainty distributions $\{ \Phi_{ij} |\left( {i,j} \right) \in A\}$ , then for any real number $x$ and arbitrary $s$ – $t$ -path $P \in {\mathcal{P}}$ , the uncertainty distribution function $\Psi$ may be calculated by $\Psi \left( x \right) = {\mathcal{M}}\left\{ {f\left( {\xi_{P} } \right) \le x} \right\} = max_{{\left( {i,j} \right) \in P}} \Phi_{ij} \left( x \right)$ .

4.3 Mathematical programming models

Utilizing uncertainty programming, we introduce different approaches, as it is not proper to use the classical deterministic approach while dealing with uncertain variables for attacking the uncertain MCP problem and create some novel equivalent optimization exact solution techniques. In an uncertain world, we do have not a natural ordership distinct from the situation of real numbers. Therefore, a significant issue rising in this area is how to rank uncertain variables. Uncertainty programming which utilizes critical value criteria is commonly named chance-constrained programming. In uncertain networks, we begin by presenting a definition of the α-maximum capacity path.

Definition 5

$[{{\varvec{\upalpha}}}$-maximum capacity path $({{\varvec{\upalpha}}}\hbox{-MCP})]$ We consider ${\text{N}} = \left( {{\text{V}},{\text{ A}}} \right)$ as an uncertain network, ${\upalpha } \in \left( {0,1} \right]$ stands as a given confidence level, and $P$ indicates any $s$–$t$-path. After that, the ${\upalpha }$-critical value associated with $\xi_{P}$ can be presented as follows:

$$ \xi_{P}^{\alpha } = sup\left\{ {c|{\mathcal{M}}\left\{ {f\left( {\xi_{P} } \right) \ge c} \right\} \ge \alpha } \right\}. $$

(5)

It shows that the uncertain variable ${\upxi }_{{\text{P}}}$ will reach upwards of the ${\upalpha }$-critical value $\xi_{P}^{\alpha }$ with uncertain measure ${\upalpha }$. We name an uncertain $s$–$t$-path $\xi_{{P^{*} }}$ as an ${\upalpha }$-MCP if $\xi_{{P^{*} }}^{\alpha } \ge \xi_{P}^{\alpha }$ for any other ${\text{s}}$–${\text{t}}$-path $\xi_{P}$. i.e.,

$$ \sup \left\{ {c{|}{\mathcal{M}}\left\{ {f\left( {\xi_{{P^{*} }} } \right) \ge c} \right\} \ge \alpha } \right\} \ge \sup \left\{ {c{|}{\mathcal{M}}\left\{ {f\left( {\xi_{P} } \right) \ge c} \right\} \ge \alpha } \right\}. $$

It follows from Definition 5 that for any predestined confidence level $\alpha \in \left( {0,1} \right]$, the $\alpha$-critical value is a decreasing and left-continuous function of $\alpha$. Also, the following holds for any positive number $\varepsilon$:

$$ {\mathcal{M}}\left\{ {\xi_{ij} \ge \xi_{ij}^{\alpha } - \varepsilon } \right\} \ge \alpha {\text{and }}{\mathcal{M}}\left\{ {\xi_{P} \ge \xi_{P}^{\alpha } - \varepsilon } \right\} \ge \alpha . $$

As a result, the $\alpha$-MCP programming model for an uncertain MCP problem may be formulated as a maximization problem over $c$ (given a confidence level $\alpha \in \left( {0,1} \right]$) as

$$ \begin{array}{*{20}l} {\mathop {{\text{max}}}\limits_{{c \in {\mathbb{R}},P \in {\mathcal{P}}}} } \hfill & {c,} \hfill \\ {\text{subject to}} \hfill & {{\mathcal{M}}\left\{ {\mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} \ge c} \right\} \ge \alpha .} \hfill \\ \end{array} $$

(6)

In the following, we demonstrate that the $\alpha$-MCP is the MCP of the uncertain network under some confidence level $\alpha$. Besides, we show that when the uncertain capacity variables $\xi_{ij}$ are independent and regular how to compute the inverse uncertainty distribution ${\Psi }^{ - 1}$ of the MCP value in an uncertain network; i.e., for any $\alpha \in \left( {0,1} \right)$, we calculate ${\Psi }^{ - 1} \left( \alpha \right)$. We get the uncertainty distribution ${\Psi }\left( x \right)$ by repeating this process in a numerical sense that can satisfy any predestined precision given by the network planner.

Theorem 3

[Existence of inverse uncertainty distribution] $N = \left( {V,A} \right)$ is an uncertain network with independent uncertain capacity variables $\{ \xi_{ij} |\left( {i,j} \right) \in A\}$ that have regular distributions $\{ \Phi_{ij} |\left( {i,j} \right) \in A\}$. After that, $\Psi^{ - 1}$ exists for the uncertain MCP problem’s objective function (in (3)). Besides, it is a continuous and strictly decreasing function of the confidence level.

Proof

In the optimization framework (3), the objective function of the MCP problem is sequential and strictly rising. Accordingly, it has an inverse uncertainty distribution (Theorem 2). If $P^{*}$ be a $\alpha$-MCP and also ${\Psi }^{ - 1}$ be the inverse uncertainty distribution of the objective function for any given confidence level $\alpha \in \left( {0,1} \right)$ considering $x = {\Psi }^{ - 1} \left( {1 - \alpha } \right)$, we have:

$$ \begin{array}{*{20}l} {{\Psi }\left( x \right) = } \hfill & {{\mathcal{M}}\left\{ {f\left( {\xi_{{P^{*} }} } \right) \le x} \right\} = {\mathcal{M}}\left\{ {f\left( {\xi_{{P^{*} }} } \right) \le {\Psi }^{ - 1} \left( {1 - \alpha } \right)} \right\} = {\Psi }\left( {{\Psi }^{ - 1} \left( {1 - \alpha } \right)} \right) = 1 - \alpha .} \hfill \\ \end{array} $$

We conclude that they all have inverse uncertainty distributions ${\Phi }_{ij}^{ - 1}$ because whole $\xi_{ij}$ are uncertain variables by regular uncertainty distributions (${\Phi }_{ij}$). It follows $\xi_{ij}^{\alpha } = {\Phi }_{ij}^{ - 1} \left( {1 - \alpha } \right)$ for any link $\left( {i,j} \right) \in A$ and $\alpha \in \left( {0,1} \right)$ of the definition of $\alpha$-critical value. Hence, we create the following for any $P \in {\mathcal{P}}$ by selecting the Monotonicity Theorem from uncertainty theory (Liu 2021),

$$\begin{aligned} & {\mathcal{M}}\left\{ {\mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} \le \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } } \right\} \ge {\mathcal{M}}\left\{ {\mathop \cap \limits_{{\left( {i,j} \right) \in P}} \left\{ {\xi_{ij} \le \xi_{ij}^{\alpha } } \right\}} \right\}\\ & = \mathop \wedge \limits_{{\left( {i,j} \right) \in P}} {\mathcal{M}}\left\{ {\xi_{ij} \le \xi_{ij}^{\alpha } } \right\} = 1 - \alpha . \end{aligned} $$

Besides, while $f$ is strictly increasing and considering Axiom 2 and the independence of uncertain variables $\xi_{ij}$, it can be concluded that

$$ \begin{aligned} {\mathcal{M}}\left\{ {\mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} \le \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } } \right\} & \le {\mathcal{M}}\left\{ {\mathop \cup \limits_{{\left( {i,j} \right) \in P}} \left\{ {\xi_{ij} \le \xi_{ij}^{\alpha } } \right\}} \right\} \\ & = 1 - {\mathcal{M}}\left\{ {\mathop \cap \limits_{{\left( {i,j} \right) \in P}} \{ \xi_{ij} > \xi_{ij}^{\alpha } \} } \right\} \\ & = 1 - \mathop \wedge \limits_{{\left( {i,j} \right) \in P}} {\mathcal{M}}\left\{ {\xi_{ij} > \xi_{ij}^{\alpha } } \right\} \\ & = 1 - \mathop \wedge \limits_{{\left( {i,j} \right) \in P}} \left\{ \alpha \right\} = 1 - \alpha . \\ \end{aligned} $$

By combining the above-mentioned inequalities, we find that

$$ \begin{array}{*{20}l} {{\mathcal{M}}\left\{ {\mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} \le \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } } \right\} = 1 - \alpha .} \hfill \\ \end{array} $$

Eventually, by the definition of $\alpha$-critical value, we conclude that ${\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha }$ is a strictly decreasing continuous function of the confidence level. It proves that ${\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha }$ is the inverse uncertainty distribution, taking into consideration the definition of inverse uncertainty distribution as well as the $\alpha$-critical value of $f\left( {\xi_{P} } \right)$, i.e.,

$$ \begin{array}{*{20}l} {\xi_{f}^{\alpha } = \Psi^{ - 1} \left( {1 - \alpha } \right) = \mathop {min}\limits_{{\left( {i,j} \right) \in P}} \Phi_{ij}^{ - 1} \left( {1 - \alpha } \right) = \mathop {min}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } .} \hfill \\ \end{array} $$

□

Theorem 4

The $\alpha$-MCP programming model for a given $\alpha$ is equivalent to the following model

$$ \mathop {max}\limits_{{P \in {\mathcal{P}}}} \mathop {min}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } \equiv \mathop {max}\limits_{{P \in {\mathcal{P}}}} \mathop {min}\limits_{{\left( {i,j} \right) \in P}} \Phi_{ij}^{ - 1} \left( {1 - \alpha } \right), $$

(7)

where $\xi_{ij}^{\alpha }$ stands as the $\alpha$-critical value of the uncertain variable $\xi_{ij}$ and $\{ \Phi_{ij}^{ - 1} |\left( {i,j} \right) \in A\}$ shows the inverse uncertainty distributions of links.

Proof

One can replace the constraint of ${\mathcal{M}}\left\{ {f\left( {\xi_{P} } \right) \ge c} \right\} \ge \alpha$ (in problem (6)) with ${\mathcal{M}}\left\{ {f\left( {\xi_{P} } \right) \ge c} \right\} = \alpha$ because of $f\left( {\xi_{P} } \right) = {\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}$ has an inverse uncertainty distribution and whole $\xi_{ij}$ are regular. Therefore, condition ${\mathcal{M}}\left\{ {{\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij} \ge c} \right\} \ge \alpha$ remains constant if and only if ${\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } \ge c$ holds. Thereupon, the $c$ maximization boils down to the maximization of ${\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha }$. □

For the capacity of the transmission path, the transport planner may predestinate a benchmark $c$ and wishes the capacity of the obtained path not to fall below the given benchmark value. We suggest the concept of a most maximum capacity path (MMCP) for modeling this sort of uncertain network capacity problem. In this concept, the underlying philosophy is to select the path with a maximal chance to meet the pre-given value; i.e., the aim is to maximize the confidence level under a certain threshold of capacity.

Definition 6

[Most maximum capacity path (MMCP)] We consider ${\text{N}} = \left( {{\text{V}},{\text{A}}} \right)$ as an uncertain network with independent uncertain capacity variables $\xi_{ij}$ and $\xi_{{P^{*} }} = \{ \xi_{ij} |\left( {i,j} \right) \in P^{*} \}$ as an ${\text{s}}$–${\text{t}}$ path, and ${\text{c}}$ as a benchmark value determined by the planner. We introduce ${\text{P}}^{*}$ as the MMCP if

$$ {\mathcal{M}}\left\{ {\mathop {min}\limits_{{\left( {i,j} \right) \in P^{*} }} \xi_{ij} \ge c} \right\} \ge {\mathcal{M}}\left\{ {\mathop {min}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij} \ge c} \right\}, $$

(8)

or, equivalently

$$ {\mathcal{M}}\left\{ {f\left( {\xi_{{P^{*} }} } \right) \ge c\} \ge {\mathcal{M}}\{ f\left( {\xi_{P} } \right) \ge c} \right\}, $$

(9)

for any $s$–$t$-path $P \in {\mathcal{P}}$. In other words, given a predestined capacity level $c$, the MMCP is the optimal path with a capacity of more than $c$ with the largest confidence level. The $\alpha$-MCP and the MMCP are dual. Hence, the following outcomes are obtained.

Theorem 5

We consider $N = \left( {V,A} \right)$ as an uncertain transportation network along with independent uncertain capacity variables $\{ \xi_{ij} \}$ that can associate with links having distributions $\Phi_{ij}$ . $c$ is a given capacity threshold amount. If $\Psi$ shows the distribution function of the objective function of MCP and also the distributions $\left\{ {\Phi_{ij} } \right\}$ are regular, then the MMCP may be computed with solving an $\alpha$ -MCP problem by taking into account setting $\alpha = \Psi \left( c \right)$ .

Proof

The MMCP problem may be formulated (such a maximization problem) over $P \in {\mathcal{P}}$, and $\alpha$ included ${\mathcal{M}}\left\{ {{\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij} \ge c} \right\} \ge \alpha$. All functions ${\Phi }_{ij}$ are considered regular; thus, choosing Theorems 3 and 4, the expression of ${\mathcal{M}}\left\{ {{\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij} \ge c} \right\} \ge \alpha$ retains if and only if the condition ${\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } \ge c$ retains. Consequently, the MMCP problem can be seen as a maximization problem with $\alpha$ as objective function and ${\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } \ge c$ as a constraint. Let $\xi_{{P^{*} }} = \{ \xi_{ij} |\left( {i,j} \right) \in P^{*} \}$ and assume that $\alpha^{*} = {\Psi }\left( c \right)$ stands as the $\alpha^{*}$-MCP of $N = \left( {V,A} \right)$. It is clear that for the MMCP problem, $P^{*}$ is a practical solution by objective function value ${\Psi }^{ - 1} \left( {\alpha^{*} } \right) = c$ and $\alpha^{*}$. It is demonstrated that $\alpha^{*}$ is the proper value for the MMCP problem. For this purpose, suppose any $\alpha > \alpha^{*}$. We can obtain $\xi_{ij}^{\alpha } < \xi_{ij}^{{\alpha^{*} }}$ for any $\left( {i,j} \right) \in A$ based on $\alpha$-critical is a reducing function. Hence, for any $s$–$t$-path $P \in {\mathcal{P}}$, the following expression can be obtained:

$$ \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } \le \mathop {{\text{max}}}\limits_{{P \in {\mathcal{P}}}} \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } < c. $$

(10)

Equation (10) causes an inconsistency by the constraints in the problem of MMCP. It follows that there does not exist a practical solution for the problem of MMCP for any $\alpha > \alpha^{*}$, after that $\alpha^{*}$ has to be optimal.□

Remark 2

We attend the following uncertainty distribution function if some link $\left( {i,j} \right) \in A$ occurs to have a capacity parameter $\xi_{ij} \equiv c_{ij}$, rather than an uncertain variable.

$$ {\Phi }_{ij} \left( x \right) = 1I_{{\left\{ {x \ge c_{ij} } \right\}}} + 0I_{{\left\{ {x < c_{ij} } \right\}}} . $$

(11)

It is a regular and strictly increasing function to $x$ ($0 < {\Phi }_{ij} \left( x \right) < 1$). Also, we state the value $c_{ij}$ possesses an inverse uncertainty distribution ${\Phi }_{ij}^{ - 1} \left( \alpha \right) = c_{ij}$ that is a continuous and strictly increasing function of $\alpha \in \left( {0,1} \right)$ even though it is not. Hence, we obtain $\xi_{ij}^{\alpha } = \xi_{ij} = {\Phi }_{ij}^{ - 1} \left( \alpha \right) = c_{ij}$ for any level of $\alpha \in \left( {0,1} \right)$.

Example 1

Consider the UMCP problem on network $N$ presented in Fig. 1 with independent uncertain capacity variables associated with links, where $s = 1$ and $t = 4$.

Fig. 1

An uncertain transportation network (used for Example 1)

Network $N$ includes 3 distinct $s$–$t$-paths from $s$ to $t$. The set of all distinct $s$–$t$-paths in $N$ is given by ${\mathcal{P}} = \left\{ {P_{1} :1 - 2 - 3 - 4;P_{2} :1 - 3 - 4;P_{3} :1 - 4} \right\}$. We remark that for a Zigzag uncertain variable $\xi \sim Z\left( {a,b,c} \right)$, the $\alpha$-critical value can be calculated by the following function.

$$ \xi^{\alpha } = \left\{ {\begin{array}{*{20}l} {\left( {2\alpha - 1} \right)a + 2\left( {1 - \alpha } \right)b} \hfill & {{\text{if}}\, \alpha \ge 0.5,} \hfill \\ {2\alpha b + \left( {1 - 2\alpha } \right)c} \hfill & {{\text{if}}\, \alpha < 0.5.} \hfill \\ \end{array} } \right. $$

(12)

Considering the foregoing relation, Table 1 shows, for some amounts of $\alpha ,$ the $\alpha$-critical values $\xi_{ij}^{\alpha }$ as well as the optimal value of the objective function in the $\alpha$-MCP problem.

Table 1 The $\alpha$-critical values of the uncertain variables associated with the network and the optimal value of the objective function in the $\alpha$-MCP problem for some typical values of confidence level $\alpha$

We recall that the optimal values of the objective function come from the inverse distribution of the uncertain MCP in $N$; i.e. ${\Psi }^{ - 1} \left( {\upalpha } \right) = {\text{max}}_{{{\text{P}} \in {\mathcal{P}}}} {\text{min}}_{{\left( {{\text{i}},{\text{j}}} \right) \in {\text{P}}}} {\upxi }_{{{\text{ij}}}}^{{\upalpha }}$. By using the data in Table 1 we conclude that

$$ \begin{array}{*{20}l} {{\Psi }\left( {6.6} \right)} \hfill & { = 0.1{ }\& } \hfill & {{\Psi }^{ - 1} \left( {0.1} \right) = 6.6} \hfill & {\& { }0.1 - {\text{MCP is P}}_{1} :1 - 2 - 3 - 4,} \hfill \\ {{\Psi }\left( {5.8} \right)} \hfill & { = 0.3{ }\& } \hfill & {{\Psi }^{ - 1} \left( {0.3} \right) = 5.8} \hfill & {\& { }0.3 - {\text{MCP is P}}_{2} :1 - 3 - 4,} \hfill \\ {{\Psi }\left( {4.2} \right)} \hfill & { = 0.7{ }\& } \hfill & {{\Psi }^{ - 1} \left( {0.7} \right) = 4.2} \hfill & {\& { }0.7 - {\text{MCP is P}}_{1} :1 - 2 - 3 - 4,} \hfill \\ {{\Psi }\left( {3.5} \right)} \hfill & { = 0.9{ }\& } \hfill & {{\Psi }^{ - 1} \left( {0.9} \right) = 3.5} \hfill & {\& { }0.9 - {\text{MCP is P}}_{3} :1 - 4.} \hfill \\ \end{array} $$

(13)

As demonstrated before, the uncertain MCP problem’s objective function (${\Psi }$), the $\alpha$-critical values $\xi_{ij}^{\alpha }$ and the inverse uncertainty distribution (${\Psi }^{ - 1}$) are strictly decreasing function of the confidence level $\alpha$. We manage to obtain the inverse distribution and the distribution of the UMCP by repeating the process (13) for distinct values of $\alpha$ (Fig. 2).

Fig. 2

The MCP inverse uncertainty distribution ${\Psi }^{ - 1} \left( \alpha \right)$ v.s. the MCP uncertainty distribution ${\Psi }\left( x \right)$

Now, let’s assume that the decision-maker presented benchmark $c = 4.2$ in the case of the transmission path capacity and wished for obtaining a path not violating this determined value (’MMCP problem’). According to Theorem 5, it is clear that the MMCP is identically the ${\Psi }\left( {4.2} \right)$-MCP. Thus, it can be concluded that the MMCP is the $0.7$-MCP that is the path $P_{1} :1 - 2 - 3 - 4$. As seen, P₁, with capacity $c_{{P_{1} }} \ge 4.2$, is the optimal path by the largest confidence level.

5 UMCP stability analysis

Here, we use the concept of $\alpha$-MCP for calculating upper and lower tolerances for an uncertain transportation network. It should be noted that the tolerances and the MCPs can also vary with a variation in confidence level. Nevertheless, for the tolerances, a formula is proposed that is a function of confidence level. In terms of a general MCP problem with MCP $P^{*}$ and deterministic capacity parameters $\left\{ {c_{ij} |\left( {i,j} \right) \in A, c_{ij} \in \left( {0, + \infty } \right)} \right\}$, the lower and upper tolerances may be observed as a value to see how the MCP can be affected with increases and decreases of a link’s capacity, respectively. Predicting the tolerances is known as a combinatorial optimization problem. Thus, we deal with uncertain variables instead of certain parameters in an uncertain network.

Here, we also present a method for coping with the problem of MCP in an uncertain network. The model solution showed in Theorem 5, for a given confidence level $\alpha$, is the $\alpha$-MCP of an uncertain network. The variables of capacity are no more uncertain variables in that setting; instead, they were changed with determined $\alpha$-critical values. For a predetermined confidence level $\alpha$, any uncertain MCP problem on $N$ may be varied to an $\alpha$-MCP problem on a network $N\left( \alpha \right)$. Hence, we require to select the transformations for variables $\left\{ {\xi_{ij} { }|{ }\left( {i,j} \right) \in A} \right\}$, and after that, utilize an algorithm for the MCP, such as modified Dijkstra’s algorithm (refer to Remark 3), for finding an MCP on the converted network.

Definition 7

($\lambda$-added network) We let $N_{{\left( {i,j} \right)}}^{ \pm \lambda } \left( \alpha \right)$ define the network ${\text{N}}^{\prime } = \left( {{\text{V}},{\text{A}}^{\prime } } \right)$ in which the ${\upalpha }$-capacity factor of link $\left( {i,j} \right)^{\prime}$ denoted by $\xi_{{\left( {i,j} \right)^{\prime}}}^{\alpha }$ is

$$ \xi_{{\left( {i,j} \right)^{^{\prime}} }}^{\alpha } = \left\{ {\begin{array}{*{20}l} {\xi_{ij}^{\alpha } } \hfill & { if\left( {i,j} \right)^{^{\prime}} \ne \left( {i,j} \right),} \hfill \\ {\xi_{ij}^{\alpha } \pm \lambda } \hfill & { if\left( {i,j} \right)^{^{\prime}} = \left( {i,j} \right).} \hfill \\ \end{array} } \right. $$

(14)

Note that $N_{{\left( {i,j} \right)}}^{ \pm \lambda } \left( \alpha \right)$ is independent of $\left( {i,j} \right)$ when $\lambda = 0$. We denote this network by $N\left( \alpha \right)$, that is, $N\left( \alpha \right) = N_{{\left( {i,j} \right)}}^{0} \left( \alpha \right)$ for any $\left( {i,j} \right)$. Formally, we let $N_{{\left( {i,j} \right)}}^{ \pm \lambda } \left( \alpha \right)$ denote network $N\left( \alpha \right)$ for $\lambda \in {\mathbb{R}}^{ \ge 0}$, wherein the weight $\xi_{ij}^{\alpha }$ of the link $\left( {i,j} \right)$ is replaced by $\xi_{ij}^{\alpha } \pm \lambda$, while all other weights stay unchanged.

In other words, $N\left( \alpha \right)$ is the transformed version of the uncertain network $N = \left( {V,A} \right)$ in which the uncertain capacity variables $\xi_{ij}$ are replaced by factors $\xi_{ij}^{\alpha }$ for a given confidence level $\alpha$. Therefore, for any given $\alpha$, the $\alpha$-MCP can be found by solving an MCP problem in the auxiliary network $N\left( \alpha \right)$. In this framework, the capacity of a path $P$ in $N\left( \alpha \right)$ is defined by

$$ f\left( P \right) = \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha } = \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in A^{\prime}}} \left\{ {\xi_{ij}^{\alpha } x_{ij} + M\left( {1 - x_{ij} } \right)} \right\}, $$

(15)

where $x_{ij}$ denotes the incidence factor; i.e., $x_{ij} = 1$ if the link $\left( {i,j} \right)$ is contained in path $P$ else $x_{ij} = 0$. Expression (15) represents the objective function, which shall be maximized in the MCP problem in the transformed network $N\left( \alpha \right)$. It is remarked that the value of $f\left( P \right)$ is no-more uncertain.

Remark 3

It is feasible to adapt the shortest path algorithms to compute MCPs, by modifying them to use the bottleneck distance instead of path length. In numerous cases, even faster methods are feasible. To obtain an MCP, an MCP algorithm can be established by modifying, e.g., Dijkstra’s algorithm. To do so, we assume that $d(\cdot )$ represents the distance label function; then, the MCP algorithm is essentially Dijkstra’s with two modifications. We initialize the label $d(\cdot )$ of each node to $0$ and the source node $\mathrm{s}$ to $\infty$. Further, we update the distance label of a node $j$ if and only if for some node $i\in V$, $(i,j)\in A$ and $d(j)<min\{d(i),{\xi }_{ij}^{\alpha }\}$, i.e., we set $d\left( j \right): = max\left\{ {d\left( j \right),\min \left\{ {d\left( i \right),\xi_{ij}^{\alpha } } \right\}} \right\}$. The complexity of this MCP method is $\mathcal{O}(m+nlogn)$ for directed networks using a Fibonacci or hollow heap and $\mathcal{O}(m)$ for undirected networks using Thorup’s algorithm (Ahuja et al. 1993).

Definition 8

(Upper tolerance) Suppose that $\mathrm{\alpha }$ is a determined confidence level as well as ${\mathrm{P}}^{*}$ is an $\mathrm{\alpha }$-MCP. We define the upper tolerance ${u}_{{P}^{*}}(i,j)$ of a link $(i,j)$ with respect to ${\mathrm{P}}^{*}$ as

$${u}_{{P}^{*}}\left(i,j\right)\left(\alpha \right)=\underset{\lambda \in \left[0,\infty \right)}{\mathrm{sup}}\left\{\lambda |{\mathrm{ P}}^{* }\mathrm{is an MCP for}{\mathrm{ N}}_{\left(\mathrm{I},\mathrm{j}\right)}^{+\uplambda }(\mathrm{\alpha })\right\}.$$

(16)

Definition 9

(Lower tolerance) Suppose that $\mathrm{\alpha }$ is a determined confidence level as well as ${\mathrm{P}}^{*}$ is an $\mathrm{\alpha }$-MCP. We define the lower tolerance ${l}_{{P}^{*}}(i,j)$ of a link $(i,j)$ with respect to ${\mathrm{P}}^{*}$ as

$${l}_{{P}^{*}}\left(i,j\right)\left(\alpha \right)=\underset{\lambda \in \left[0,{\xi }_{ij}^{\alpha }\right]}{\mathrm{sup}}\left\{\lambda |{\mathrm{ P}}^{*}\mathrm{ is an MCP for}{\mathrm{ N}}_{\left(\mathrm{I},\mathrm{j}\right)}^{-\uplambda }(\mathrm{\alpha })\right\}.$$

(17)

In words, the upper tolerance is the supremum value $\lambda$ by which the capacity factor of $(i,j)$ can be increased such that ${P}^{*}$ remains an MCP, provided that the other capacity factors remain unchanged. Similarly, the lower tolerance is the supremum value $\lambda$ by which the capacity factor of $(i,j)$ can be decreased preserving the optimality of ${P}^{*}$, provided that the other capacity factors remain untouched.

As stated above, we let $\mathcal{P}=\{{P}_{k}\}$ define the all $s$–$t$-paths set in $N=(V,A),$ which means whole paths from source $s$ to sink$t$. The set $\mathcal{P}$ does not depend on the capacity parameters; hence, the set $\mathcal{P}$ in $N(\alpha )$ is the same as that in$N=(V,A)$. We are particularly concerned in two subsets of$\mathcal{P}$, namely the sets ${\mathcal{P}}_{(i,j)}^{+}$ and ${\mathcal{P}}_{(i,j)}^{-}$ that comprise all $s$–$t$-paths in $N$ that do and do not include the link $\left( {i,j} \right)$, respectively. The function amounts $C\left( {{\mathcal{P}}\left( \alpha \right)} \right)$, $C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ + } \left( \alpha \right)} \right)$ and $C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ - } \left( \alpha \right)} \right)$ will be particularly beneficial for the following technical discussion that interpretations come as below:

• $C\left( {{\mathcal{P}}\left( \alpha \right)} \right)$ stands as an MCP value in $N\left( \alpha \right)$ without any variations in $\xi_{ij}^{\alpha }$. In other words, it provides the $\alpha$-MCP value in $N$ for a certain value of $\alpha$.

• $C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ - } \left( \alpha \right)} \right)$ shows an MCP value in $N\left( \alpha \right)$ while link $\left( {i,j} \right)$ is not contained in the network (the MCP not containing $\left( {i,j} \right)$). We concluded the following expressions,

$$ C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ - } \left( \alpha \right)} \right) = \mathop {{\text{lim}}}\limits_{{\lambda \to \xi_{ij}^{\alpha } }} C\left( {N_{{\left( {i,j} \right)}}^{ - \lambda } \left( \alpha \right)} \right). $$

• $C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ + } \left( \alpha \right)} \right)$ stands the MCP value in $N\left( \alpha \right)$ including link $\left( {i,j} \right)$ and is certain with

  $$ C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ + } \left( \alpha \right)} \right) = \mathop {{\text{max}}}\limits_{{P \in {\mathcal{P}}_{{\left( {i,j} \right)}}^{ + } }} \mathop {{\text{min}}}\limits_{{\left( {i,j} \right) \in P}} \left\{ {\xi_{ij}^{\alpha } } \right\}. $$

Observation 1

$N\left( \alpha \right)$ is the transformed version of the uncertain transportation network $N = \left( {V,A} \right)$ for a predestined confidence level $\alpha$ , and $P^{*} \in {\mathcal{P}} \ne \emptyset$ an MCP in $N\left( \alpha \right)$ and link $\left( {i,j} \right) \in P^{*}$ .

• $\left( {i,j} \right) \in \bigcap\limits_{k} {P_{k} }$ $\Leftrightarrow$ $l_{{P^{*} }} \left( {i,j} \right)\left( \alpha \right) = \xi_{ij}^{\alpha }$ .

• $\left( {i,j} \right) \notin \mathop \cup \limits_{k} P_{k}$ $\Rightarrow$ $u_{{P^{*} }} \left( {i,j} \right)\left( \alpha \right) = + \infty$ .

Remark 4

According to Observation 1, we highlight that for any network and any confidence level ${\upalpha }$, the lower and upper tolerances do depend on a particular MCP.

Theorem 6

$N = \left( {V,A} \right)$ is an uncertain network and $N\left( \alpha \right)$ its transformed version for a predestined $\alpha$, and $P^{*}$ an MCP in $N\left( \alpha \right)$.

• (a) If $\left( {i,j} \right) \kern-1pt\in\kern-1pt P^{*}$, then $u_{{P^{*} }} \left( {i,j} \right)\left( \alpha \right) \kern-1pt=\kern-1pt \left\{\kern-1pt {\begin{array}{*{20}l} { + \infty } \hfill & { if C\left( {{\mathcal{P}}\left( \alpha \right)} \right) \ge \mathop {lim}\limits_{\lambda \to + \infty } C\left( {N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)} \right),} \hfill \\ {\mathop {min}\limits_{{\left( {i,j} \right)^{\prime} \in P^{*} \backslash \left( {i,j} \right)}} \left\{ {\xi_{{\left( {i,j} \right)^{\prime}}}^{\alpha } } \right\} - \xi_{ij}^{\alpha } } \hfill & { if C\left( {{\mathcal{P}}\left( \alpha \right)} \right) < \mathop {lim}\limits_{\lambda \to + \infty } C\left( {N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)} \right).} \hfill \\ \end{array} } \right.$

• (b) If $\left( {i,j} \right) \notin P^{*}$, then $u_{{P^{*} }} \left( {i,j} \right)\left( \alpha \right) = \left\{ {\begin{array}{*{20}l} { + \infty } \hfill & { if C\left( {{\mathcal{P}}\left( \alpha \right)} \right) \ge \mathop {lim}\limits_{\lambda \to + \infty } C\left( {N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)} \right),} \hfill \\ {C\left( {{\mathcal{P}}\left( \alpha \right)} \right) - \xi_{ij}^{\alpha } } \hfill & { if C\left( {{\mathcal{P}}\left( \alpha \right)} \right) < \mathop {lim}\limits_{\lambda \to + \infty } C\left( {N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)} \right).} \hfill \\ \end{array} } \right.$

• (c) $l_{{P^{*} }} \left( {i,j} \right)\left( \alpha \right) = \left\{ {\begin{array}{*{20}l} {\xi_{ij}^{\alpha } - C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ - } \left( \alpha \right)} \right)} \hfill & { if \left( {i,j} \right) \in P^{*} ,} \hfill \\ {\xi_{ij}^{\alpha } } \hfill & { otherwise.} \hfill \\ \end{array} } \right.$

Proof

• (a) When dealing with a link $\left( {i,j} \right) \in P^{*}$ there can be only two possibilities: either $P^{*}$ will remain an MCP for $N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)$ when $\lambda \to + \infty$ or will not. $P^{*}$ is an $\alpha$-MCP for $N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)$ (while $\lambda \to + \infty$) if and only if the condition $C\left( {{\mathcal{P}}\left( \alpha \right)} \right) \ge {\text{lim}}_{\lambda \to + \infty } C\left( {N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)} \right)$ holds. By definitions of upper tolerance, $P^{*}$ remains an $\alpha$-MCP under such circumstance, and setting $u_{{P^{*} }} \left( {i,j} \right)\left( \alpha \right) = + \infty$ is supported. The other case is when $P^{*}$ is no longer an $\alpha$-MCP in $N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)$ (while $\lambda \to + \infty$), and this takes place if and only if the condition $C\left( {{\mathcal{P}}\left( \alpha \right)} \right) < {\text{lim}}_{\lambda \to + \infty } C\left( {N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)} \right)$ holds. In such a situation, for $P^{*}$ to stay an $\alpha$-MCP for $N_{{\left( {i,j} \right)}}^{ + \lambda } \left( \alpha \right)$ (justifying the definitions of upper tolerance), an increase larger than ${\text{min}}_{{\left( {i,j} \right)^{\prime } \in P^{*} \backslash \left( {i,j} \right)}} \left\{ {\xi_{{\left( {i,j} \right)^{\prime } }}^{\alpha } } \right\} - \xi_{ij}^{\alpha }$ creates a new $\alpha$-MCP (violating the definition of upper tolerance).

• (b) The proof is established along the same lines as in the proof for the previous part.

• (c) Let’s suppose $\left( {i,j} \right) \in P^{*}$. Thereupon, according to the definition of lower tolerance, we have:

  $$ \begin{aligned} l_{{P^{*} }} \left( {i,j} \right)\left( \alpha \right)& = \mathop {{\text{sup}}}\limits_{\lambda } \left\{ {\lambda \in \left[ {0,\xi_{ij}^{\alpha } } \right]{ }| P^{{* }} {\text{is an MCP in}} N_{{\left( {i,j} \right)}}^{ - \lambda } \left( \alpha \right)} \right\} \hfill \\ &= \mathop {{\text{max}}}\limits_{{\lambda \in {\mathbb{R}}}} \left\{ {\lambda \in \left[ {0,\xi_{ij}^{\alpha } } \right]|\xi_{ij}^{\alpha } - \lambda \ge C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ - } \left( \alpha \right)} \right)} \right\} \hfill \\ &= \xi_{ij}^{\alpha } - C\left( {{\mathcal{P}}_{{\left( {i,j} \right)}}^{ - } \left( \alpha \right)} \right) \hfill \\ &= \xi_{ij}^{\alpha } - \mathop {{\text{lim}}}\limits_{{\lambda \to \xi_{ij}^{\alpha } }} C\left( {N_{{\left( {i,j} \right)}}^{ - \lambda } \left( \alpha \right)} \right). \hfill \\ \end{aligned} $$

  □

According to Theorem 6 and Remark 3, we can obtain the exact values of lower and upper tolerances of any link for a given ${\upalpha }$-MCP in the same asymptotic time complexity as two MCP algorithms in the worst case. Thereupon, the overall computational effort is ${\mathcal{O}}\left( {m^{2} + mnlogn} \right)$ in directed networks and ${\mathcal{O}}\left( {m^{2} } \right)$ in undirected ones. However, we now exploit the previous results to extend the following algorithm for computing the tolerances of all links in even more reduced computational time. To proceed, we introduce an auxiliary network, called the residual network.

Definition 10

(Residual network) ${\text{If}} N\left( \alpha \right)$ is the transformed version of the uncertain network ${\text{N}} = \left( {{\text{V}},{\text{A}}} \right)$ for a predestined confidence level ${\upalpha }$ and ${\text{P}}$ an arbitrary ${\text{s}}$–${\text{t}}$-path with capacity $f\left( P \right)$. The residual network $N_{P}^{r} \left( \alpha \right) = \left( {V,A_{P}^{r} } \right)$ to path ${\text{P}}$ is built on $N\left( \alpha \right)$ where $A_{P}^{r} = \left\{ {\left( {i,j} \right) \in A \left| { \xi_{ij}^{\alpha } } \right\rangle f\left( P \right)} \right\}$.It is concluded that for any $\alpha$-MCP $P^{*}$ the residual network $N_{{P^{*} }}^{r} \left( \alpha \right) = \left( {V,A_{{P^{*} }}^{r} } \right)$ is an $s$–$t$-disconnected network; i.e., the node set $V$ can be partitioned into at least two disconnected components. This, therefore, results in defining a possible cut.

Definition 11

(Cut) Let $V_{s} \ne \emptyset$ shows the set of nodes reachable from ${\text{s}}$ in $N_{{P^{*} }}^{r} \left( \alpha \right)$ and $V_{t} \ne \emptyset$ the set of nodes reachable from $t$ in $N_{{P^{*} }}^{r} \left( \alpha \right)$. We define $Cut \left( {N_{{P^{*} }}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right)$ as the set of pairs $\left( {i,j} \right)$ that satisfy either $i \in V_{s}$ and $j \in V_{t}$ or $i \in V_{t}$ and $j \in V_{s}$.

We then propose the UMCP Lower–Upper Tolerance Algorithm to efficiently calculate all the links’ tolerances. We represent the algorithm in a pseudo-code which runs in ${\mathcal{O}}\left( m \right)$ (if only upper tolerances are concerned) or ${\mathcal{O}}\left( {\left| {P^{*} } \right|m} \right)$ time (if both the upper and lower tolerances are concerned). It was originally developed to obtain the upper tolerances; however, it is capable to compute the lower tolerances as well.

At Step 2, the algorithm benefits from $Cut \left( {N_{{P^{*} }}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right)$ for any link $\left( {i,j} \right) \in A\backslash P^{*}$ to determine the links whose weights’ changes affect the optimality of $P^{*}$. Those links are exactly the ones that belong to $Cut\left( {N_{{P^{*} }}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right)\backslash P^{*}$ and were discussed in Theorem 6. Any link $\left( {i,j} \right) \in Cut\left( {N_{{P^{*} }}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right)$ can be a bottleneck link whose weight’s increase may influence the optimality of the already calculated $\alpha$-MCP, because it may build a path of capacity strictly larger than $f\left( {P^{*} } \right) = C\left( {{\mathcal{P}}\left( \alpha \right)} \right)$. Thereupon, when those bottleneck links are detected, we correctly set the tolerances’ values for all links $\left( {i,j} \right) \in A\backslash P^{*}$ according to the corresponding results established in Theorem 6.

Analogously, at Step 3, the algorithm sets the lower tolerances for all links $\left( {i,j} \right) \in A \cap P^{*}$ according to Theorem 6. After that, it sets the upper tolerances for links $\left( {i,j} \right) \in A \cap P^{*}$ whose capacities are larger than $C\left( {{\mathcal{P}}\left( \alpha \right)} \right)$. The links in $A \cap P^{*}$ that may affect the optimality of $P^{*}$ are exactly those belonging to $Cut\left( {N_{{P^{*} \backslash \left( {k,l} \right)}}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right)$ with capacity $C\left( {{\mathcal{P}}\left( \alpha \right)} \right)$. In other words, any link $\left( {i,j} \right) \in A \cap P^{*}$ with $\xi_{ij}^{\alpha } = C\left( {{\mathcal{P}}\left( \alpha \right)} \right)$ can be a bottleneck link. Indeed, link $\left( {i,j} \right) \in Cut\left( {N_{{P^{*} \backslash \left( {k,l} \right)}}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right) \cap P^{*}$ whose weight is $C({\mathcal{P}}\left( \alpha \right)$ can build a better $\alpha$-MCP, so we shall limit it (by upper tolerance) using Theorem 6.

Taking $\left( {A\backslash P^{*} } \right) \cup \left( {A \cap P^{*} } \right) = A$ into consideration, the algorithm can compute the upper tolerances of all links in ${\mathcal{O}}\left( m \right)$ time. Hence, if only the upper tolerances are required, the algorithm’s run time is ${\mathcal{O}}\left( m \right)$ that outperforms the naïve ${\mathcal{O}}\left( {m^{2} } \right)$ implementation (which was discussed earlier). On the other hand, if both lower and upper tolerances are concerned, the complexity is ${\mathcal{O}}\left( m \right) + {\mathcal{O}}\left( {\left| {P^{*} } \right|m} \right) = {\mathcal{O}}\left( {\left| {P^{*} } \right|m} \right)$. The bottleneck operation of the algorithm is the scanning of links $\left( {i,j} \right) \in A \cap P^{*}$ (at Step 3) which can take up to ${\mathcal{O}}\left( {\left| {P^{*} } \right|m} \right)$ time. Finally, the algorithm performs the construction step in ${\mathcal{O}}\left( m \right)$ time.

6 Numerical example and results

This chapter involves the description of the general settings applied in our numerical experiments. The rationality of the model and the applicability of the algorithm are explained through a case study with data under two different scenarios (shown in Table 2; Fig. 3). Several computational tests on a variety of problem settings served to analyze the UMCP Lower–Upper Tolerance Method. This way, we could highlight a few features of the optimization model and reach a better understanding of the method’s behavior. The MATLAB software and the optimization modeling language GAMS on an × 64-based PC with Intel(R) Core(TM) i7-6600T CPU @ 2.60 GHz, 16 GB of RAM, and the Microsoft Windows 10 Pro OS were used for the models, figures, and computations.

Table 2 The topology and statistics of the full experimental grids associated with our target areas

Fig. 3

a Topographic map of Gävle, and b street connectivity network of Gävle based on axial lines

Two urban areas in Gävle, the oldest municipality in the historical region of Norrland (the northernmost land of Sweden), were selected to evaluate the suggested strategy. A large body of sample data was gathered for quantitative and topological analyses and OpenStreetMap and Google Map databases were used for the street data of Gävle and the boundary of the city (Fig. 3). These four major steps were taken for the topological analysis: (1) the sample data were pre-processed, (2) streets were transformed into segments, (3) natural roads and axial lines were defined, and (4) capacity parameters were computed. Jiang (2012) used the generated natural roads to provide approximate parameters required for defining axial lines. Figure 4 illustrates these generated natural roads and axial lines in the center of Gävle city. Axial lines illustrate real roads in the form of straight lines and are the longest visible in urban street networks. They often serve as representations of urban structures (Sun 2012).

Fig. 4

a the generated natural roads and b obtained axial lines for the city center of Gävle. (No. of natural roads: 3729) and (No. of axial lines: 5567)

The possible few isolated lines observed after generating axial lines from natural roads might be a result of their straight representation and transforming the curve streets into straight lines; as a result, the lines may not retain their original shapes. Axwoman was utilized to render the visualization of the basic patterns and street representations on the map. A natural road may be formed by merging the adjoining road segments which fit the principle of good continuity within a specified threshold deflection angle. We chose a 45-degree threshold of the deflection angle in our setting to which all the jointed road segments should be adjusted. Domain experts helped provide information on the threshold deflection angle. The interconnections between streets can be obtained using the relevant calculated connectivity parameters. The urban pattern of Gävle is represented in Fig. 3 with a focus on the highly interconnected streets.

Expert assessments were utilized to render the regular independent uncertainty distributions of the links’ factors (made from the axial lines). We assumed different values of confidence level $\alpha$ for the tests. Estimation of a few parameters was required to create the distributions (see Remarks 5 and 6). Three separate domain experts helped provide the required information in full from their investigations and questionnaires, and the mean of all the expert results was used to determine the values. We chose to utilize Linear and Zigzag uncertainty distributions for all cases according to the expert assessments.

Remark 5

The uncertain variable $\xi \sim L\left( {a,b} \right)$ is Linear with parameters $a$ and $b$ if it has the uncertainty distribution as $\phi \left( x \right)$. Moreover, the Linear distribution is regular and its inverse distribution is given by $\phi^{ - 1} \left( \alpha \right)$ for a preset $\alpha$.

$$ \phi \left( x \right) = \left\{ {\begin{array}{ll} 0 & { if x \le a,} \\ {\frac{x - a}{{b - a}}} & { if a \le x \le b,} \\ 1 & { if x \ge b.} \\ \end{array} } \right. $$

$\phi^{ - 1} \left( \alpha \right) = \left( {1 - \alpha } \right)a + \alpha b$.

Remark 6

The uncertain variable ${\upxi } \sim {\text{Z}}\left( {a,b,c} \right)$ is named Zigzag with parameters $a$, $b$, $c$ ($a < b < c$) if it has an uncertainty distribution as $\phi \left( x \right)$. Furthermore, the Zigzag distribution is regular and its inverse distribution is given by $\phi^{ - 1} \left( \alpha \right)$ for a preset $\alpha$.

$$ \phi \left( x \right) = \left\{ {\begin{array}{ll} 0 & if x \le a, \\ \frac{x - a}{{2\left( {b - a} \right)}} & if a \le x \le b, \\ \frac{x + c - 2b}{{2\left( {c - b} \right)}} & if b \le x \le c, \\ 1 & if x \ge c. \end{array} } \right. $$

$$ \phi^{ - 1} \left( \alpha \right) = \left\{ {\begin{array}{*{20}l} {\left( {2\alpha - 1} \right)a + 2\left( {1 - \alpha } \right)b} \hfill & { {\text{if}} \,\alpha \ge 0.5,} \hfill \\ {2\alpha b + \left( {1 - 2\alpha } \right)c} \hfill & { {\text{if}}\, \alpha < 0.5.} \hfill \\ \end{array} } \right. $$

To model and solve the UMCP problem, we applied our proposed method to two real test cases. The two real cases corresponded to different zones of the street network and had a grid plan at their base. This is in line with concurrent city management, which is responsible for finding safe, reliable route plans for a set number of vehicles (accumulated in depots) in a specific target area (especially planned for emergency vehicles). This is essential for safely reaching the predefined points at times of disaster (e.g. earthquake, flood, hurricane). Two source-sinks were also selected. Our test cases (planning areas) are both polygonal (Fig. 3). Paths that can accommodate the highest number of rescue vehicles (in depots) to reach the affected areas during disasters (destination area) are difficult to identify. The location of the depot in both areas is at the lower-left corner of polygons.

In the following, the components of the uncertain capacity variables, the value of uncertain maximum capacity paths, and the other network parameters are discussed in detail. The uncertain capacity of a link $(i,j)$ is represented by the uncertain variable ${\xi }_{ij}$ (with uncertainty distribution${\Phi }_{\mathrm{ij}}$), and $f\left({\xi }_{P}\right)$ measures the value of a UMCP. The variables ${\xi }_{ij}^{\alpha }$ and ${\Phi }_{ij}^{-1}$ indicate the $\alpha$-critical value of the uncertain variable ${\xi }_{ij}$ and the inverse uncertainty distribution of${\Phi }_{\mathrm{ij}}$, respectively. The uncertainty distribution of function f (that is, the distribution of UMCP) is demonstrated through the function$\Psi$. Similarly, the inverse distribution of $\Psi$ for the confidence level $\alpha$ is demonstrated through the function${\Psi }^{-1}(\mathrm{\alpha })$. The value of an $\alpha$-MCP (or, in case of a fixed$\alpha$, the value of a UMCP) is normally calculated through the formula ${\Psi }^{ - 1} \left( \alpha \right) = {\text{max}}_{{P \in {\mathcal{P}}}} {\text{min}}_{{\left( {i,j} \right) \in P}} \xi_{ij}^{\alpha }$. The capacity variables of a sample of links connected to our target areas are presented in Tables 3, 4, and 5 for a clearer view of the street networks’ topologies and variable streets’ capacities. For any $\alpha \in \left( {0,1} \right)$, we set $\xi_{ij}^{\alpha } = \xi_{ij} = {\Phi }_{ij}^{ - 1} \left( \alpha \right) = c_{ij}$ for links $\left( {i,j} \right)$ with a constant capacity parameter $\xi_{ij} \equiv c_{ij}$.

Table 3 List of capacity variables and critical values of a sample of links of the grids for $\alpha = 0.95$

Table 4 List of capacity variables and critical values of a sample of links of the grids for $\alpha = 0.95 {\text{and}} 0.6$

Table 5 List of capacity variables and critical values of a sample of links of the grids for $\alpha = 0.8$

The uncertainty distribution of the UMCP (${\Psi }$), the $\alpha$-critical values $\xi_{ij}^{\alpha }$, and the inverse uncertainty distribution of the UMCP (${\Psi }^{ - 1}$) are all known decreasing functions of the confidence level $\alpha$. Namely, an increase in $\alpha$ decreases the optimal value of uncertain UMCP. From an optimization point of view, this fact can be related to the relationship between the UMCP’s objective function and the inverse uncertainty distributions of uncertain links’ variables. An increase in confidence level $\alpha$ necessitates an optimal UMCP solution in a smaller feasible solution set. The result is either a decrease in the total UMCP value or no change. In other words, a smaller $\alpha$ imposes less restriction on the street network.

The values of the $\alpha$-MCPs of the grid networks shown in Fig. 5 are illustrated in Table 6. The thick red line in Fig. 5 refers to the ${\upalpha } - {\text{MCP}}$ for ${\upalpha } = 0.95$ and is identified by the MCP algorithm (discussed in Remark 3). Moreover, as we are dealing, in this specific example, with vehicles, we need to consider the floor of critical values. These values were further used to illustrate their UMCP uncertainty distributions in Figs. 6 and 7. The method used for relations (13) in Example 1 was adopted to approximate the inverse distribution and the distribution of the UMCP for distinct values of $\alpha \in \left( {0,1} \right)$. As we are dealing, in this specific example, with vehicles, we need to consider the floor of values to better understand the results.

Fig. 5

The example street networks in Gävle are based on axial lines. From left to right: the base grid layouts for scenarios 1–2. For both scenarios, the node furthest down at the left (the square) is the depot (of emergency machines). The destination area is the zone that the emergency vehicles must reach. The thick line represents an $\mathrm{\alpha }-\mathrm{MCP}$ for confidence level $\alpha =0.95$, which is obtained by the MCP algorithm (see Remark 3).

Table 6 List of $\alpha$-MCPs associated with the planning areas

Fig. 6

The UMCP uncertainty distributions associated with the planning area 1

Fig. 7

The UMCP uncertainty distributions associated with the planning area 2

At times, the planner’s subjective experience defines the value of confidence levels, the optimal value of the UMCP problem’s objective function is the best approximate number of emergency vehicles that can be sent from the depot through the transportation network to the destination. The different values of $\alpha \in \left( {0,1} \right)$ can obviously produce different UMCP values. As illustrated in Figs. 6 and 7, it might, therefore, be more practical here to depict the value of the UMCP as a function of parameters (confidence levels).

Different settings for the confidence level $\alpha$ were utilized to work out several medium- and large-scale networks from our case study. The results were then compared for assessing the practicality of the UMCP Lower–Upper Tolerance Method. The behavior of the algorithm in the analyzed networks was generally similar. Parts of the computational results are presented in this study’s tables. The algorithm was primarily introduced because it wasn’t time-consuming and didn’t need a large memory. Yet, its inherent parallelism was another desirable factor for modern computers. It should be noted that setting different values for $\alpha$ may result in different UMCPs; that is, the algorithm can be employed with pre-fixed confidence level ${\upalpha }$. It can therefore be stated that the value of ${\upalpha }$ governs the changes in the values of upper and lower tolerances. Therefore, it is supposedly more reasonable to demonstrate the value of the tolerances as a (not always continuous) function of confidence level ${\upalpha }.$

We begin to utilize the algorithm (to calculate the tolerances) on the networks in Fig. 5 by first determining a value for the confidence level for ${\upalpha } \in \left( {0,1} \right)$. We then calculate the inverse uncertainty distributions (critical values) of all ${ }\xi_{ij}$ and construct the transformed network $N\left( \alpha \right)$. So is the $\alpha$-MCP $\left( {{\text{denoted by P}}^{*} } \right)$ in $N\left( \alpha \right)$, which is obtained by the MCP algorithm (Remak 3). Hence, there must be a close connection between the confidence level value and $\alpha$-MCPs for our results to be reliable. In Fig. 5, there exist several paths from the depot to the destination area. The $\alpha$-MCPs for confidence level $\alpha = 0.95$ are shown in the form of a thick red line in both networks. By finding the links with the minimum and the second minimum critical values as

$f\left( {P^{*} } \right) = min_{{\left( {i,j} \right) \in P^{*} }} \left\{ {\xi_{ij}^{\alpha } } \right\}$ and $f\left( {P^{*} \backslash \left( {k,l} \right)} \right) = min_{{\left( {i,j} \right) \in P^{*} \backslash \left( {k,l} \right)}} \left\{ {\xi_{ij}^{\alpha } } \right\}$,the residual networks ${\text{N}}_{{{\text{P}}^{*} }}^{{\text{r}}} \left( {\upalpha } \right) = \left( {{\text{V}},{\text{A}}_{{{\text{P}}^{*} }}^{{\text{r}}} } \right)$ and ${\text{N}}_{{{\text{P}}^{*} \backslash \left( {{\text{k}},{\text{l}}} \right)}}^{{\text{r}}} \left( {\upalpha } \right) = \left( {{\text{V}},{\text{A}}_{{{\text{P}}^{*} \backslash \left( {{\text{k}},{\text{l}}} \right)}}^{{\text{r}}} } \right)$ are constructed. Consequently, these cuts that are formally articulated in the algorithm can be defined: $Cut\left( {N_{{P^{*} }}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right)$ and $Cut\left( {N_{{P^{*} \backslash \left( {k,l} \right)}}^{r} \left( \alpha \right),V_{s} ,V_{t} } \right)$. Using the search procedure on the algorithm over link sets ${\text{A}}\backslash {\text{P}}^{*}$ and ${\text{A}} \cap {\text{P}}^{*}$ helped in finally calculating all links’ tolerances. In the following Table 7, the mentioned calculations provide lower and upper tolerance values of a sample of links in our target areas.

Table 7 The tolerance values of a sample of links of the grids

After solving the algorithm in all samples and zones of the study region, the numerical results proved that this method has a favorable resolving ability in acceptable computational times (less than one minute in most cases) even on less advanced computers. Higher levels of performance can be achieved by using faster computers and making the algorithm parallel. The benefits of this method include identifying the links of higher risks and links with fewer safety margins; and hence, a more reliable transportation network and a more accurate approximation of the overall network risk without having to sequential re-optimizations. Disaster managers and network planners will find these results of greatest usefulness in designing a transportation network. Conclusively, the reliability and functional capacity of the links determine the post-disaster reliability of the entire transportation network. Therefore, higher road capacities are needed for a higher network post-disaster reliability. It must be ascertained that the rescue vehicles will arrive at the affected areas as soon as possible for post-disaster rescue operations. The safer arrival of rescue services to the affected destinations provided by the UMCP outweighs their longer distances.

7 Discussion and concluding remarks

Real-life applications of indeterminacy parameters are prevalent, for example in network design as well as transportation networks. The stochastic connectivity of links and uncertainty of street service makes the post-disaster performance of the transportation network an uncertain problem in terms of connectivity, functional capacity, and reliability. In the aftermath of a disaster, falling bridges, collapsed buildings, and fault rupture might leave sections of the transportation system blocked, reducing its capacity and reliability which conduces to more complicated dispatch of the relief materials and rescue vehicles to the disaster zones. To afford these non-deterministic parameters fuzzy theory or probability are employed, yet there are many examples with no available samples to produce the probability distribution. Modeling human uncertainty and the use of a decision maker’s experience for non-deterministic parameters necessitated the novel approach integrated into uncertainty theory. Originally, this paper presented a new uncertainty theory-based model for post-disaster rescue work and on-time arrival of vehicles in disaster areas. This model incorporated uncertain capacity variables associated with links to assess the maximum capacity path (MCP) problem in a post-disaster transportation network.

Although the feasibility and correctness of the models and methods were clearly illustrated, the transportation network remains complex. The real-life difficulties, therefore, can be more complicated after heavily devastating events. Therefore, a sensitivity analysis (also referred to as what-if analysis) was further conducted on a post-disaster network and the stability of MCPs in the system was determined thereof. The purpose of sensitivity analysis is to determine how the optimality of a given MCP depends on the input data. Generally, performing sensitivity analysis is important for two main reasons. The input data (e.g. links’ operational capacity) used are usually uncertain. In such cases, such an analysis is compulsory to determine the credibility of the calculated MCP and conclusions based on that path. Another reason for performing sensitivity analysis is that sometimes rather significant considerations (e.g. adverse environmental factors caused by disasters) can not be incorporated into the model due to the difficulty of formulating them. Having solved the simplified transportation model, the decision-maker wants to know how well the obtained MCP fits in with the other considerations. Therefore, a clear, accurate, and solvable problem for certain precision was developed from the original, unsolvable sensitivity analysis. Additionally, a global approach to examine the tolerance/sensitivity of uncertain networks was developed which is employed to suggest a method to calculate all the tolerances of links that is far superior to successive optimization.

It was shown that in transportation networks with regular uncertain capacity variables the maximum capacity path has an inverse uncertainty distribution ${\Psi }^{ - 1} \left( {\upalpha } \right)$. Also, the calculation of the maximum capacity path for any confidence level ${\upalpha }$ was presented and repeated for various values of α to propose to achieve the uncertainty distribution ${\Psi }$. Distinct decision criteria were selected to expound the concepts of ${\upalpha }$-MCP and the most maximum capacity path (MMCP). These concepts helped ascertain, in an uncertain network and those in an auxiliary deterministic network, the presence of an equivalence relation between the MCPs. This relation, using the operational law of uncertainty theory, helped develop a programming model to investigate the stability of an uncertain transportation network post disasters and calculate the links' tolerances. The applicability of the model and the subsequent algorithm was explained through a case study with real data under two different scenarios. In our samples, three separate domain experts helped provide the required information from their investigations and questionnaires. According to the expert assessments, we decided to adopt Linear and Zigzag uncertainty distributions. These distributions were utilized based on the conditions of our network samples and for detailed evaluation and explanation of our proposed method. Therefore, others can indeed adjust our suggested method following their needs and with different uncertainty forms.

This study is among the first to compound the uncertainty theory and capacity reliability; it may then contain some limitations requiring future research that can involve computational improvement of our method. Assessing the intricacy of the approaches was not complete and might need further improvement. A challenge for future researchers is to improve computational complications in novel directions. An improvement is concurrently examining perturbations in a set of links, which might seem self-evident but can be quite difficult. This paper presents methods of computing the single links’ tolerances. To regard novel approaches to find the lower and upper tolerances for a set of links is also appealing. Another challenging effort for later research can be focusing on the computational complexity issue for the sensitivity analysis questions for directed networks (discussed here, rather than undirected networks). There are several ways to develop ${\upalpha }$-MCP and MMCP problems. For instance, this study discusses UMCP problems that are heavily dependent on the reliability of the links of the transportation network. When the center’s facilities are added to those governed by uncertainty, new problems may arise. Another type of network reliability problem may advance the structure in this study extensively, and the uncertain travel time reliability problem can expand our outcomes in post-disaster transportation networks. However, procuring the real data for the travel time distribution after a disaster as well as the time-dependent travel time function must be methodized. Besides, a few more transportation network characteristics (e.g., continuously degradable link capacities and dynamic traffic demand) would be taken into the proposed model to make it applicable for analyzing more practical issues.