A novel method to solve the optimization problem of uncertain network system based on uncertainty theory

1.   Introduction

There are a large number of optimization problems in network systems, and network system optimization is a classic and important branch of operational research. However, in recent years, many new challenges have emerged. In many practical cases, the information which we need to extract is uncertain. The emergence of uncertainty leads to a large number of uncertain factors in the network system. In the network system, uncertain factors are mainly manifested in the uncertainty of network attributes and network structures. However, the traditional approaches for deterministic problems are not suitable for solving uncertain network optimization problems. The deterministic optimization model and intelligent algorithm could not solve the practical problems. Therefore, based on uncertainty theory, we study the optimization problem of a network system with uncertain factors. Only in this way can the optimization model be more in line with the actual situation.

Many experts have studied the optimization problem with uncertain factors. For an interval uncertain optimization problem, Wang et al. ^[1] proposed an interval uncertain optimization method for an engineering uncertain optimization problem. The first-order derivative information may be unavailable in a practical engineering system. To overcome this drawback, the method to calculate the first-order partial derivatives with a back-propagation neural network was investigated, and a numerical example was presented to demonstrate its fine precision. Wang et al. ^[2] proposed a Legendre polynomial expansion method combined with the subinterval technique to evaluate the range enclosure of an interval function, where the expansion coefficients are computed through the collocation method. Wang et al. ^[3] illustrated a new interval uncertainty analysis method for structural response bounds with uncertain-but-bounded parameters by using feed forward neural network (FNN) differentiation. Liu et al. ^[4] introduced a new interval uncertainty analysis method for static response of structures with unknown-but-bounded parameters by using radial basis functions (RBFs).

In recent years, scholars have focused on the research of network systems with uncertain vertex weights and edge weights. As a basic problem in network optimization, the shortest path problem has been studied by many researchers. For the shortest path problem with uncertain factors, Ji et al. ^[5] studied the shortest path problem in random environment and fuzzy environment by using random theory and fuzzy theory, respectively. He et al. ^[6] applied random theory to solve the shortest path problem with constraints. A random optimization model was established, and an annealing genetic algorithm was proposed to solve the model. Sheng et al. ^[7] presented the shortest path problem in an uncertain stochastic network. The uncertainty of its weight was described via various forms, and the uncertain shortest path problem based on granular computing was discussed by Gao ^[8]. M. Guillot ^[9] researched the stochastic shortest path problem from the perspective of a polyhedron, and a new framework for the stochastic shortest path problem in finite state space and action space was proposed. The shortest paths in an uncertain random network were defined, and an improved algorithm was proposed by Jie ^[10]. According to uncertainty theory, Gao ^[11] developed a novel idea for solving the shortest path problem with uncertain factors. He discussed the shortest path problem in an uncertain network and pointed out the equivalent relationship between the shortest path problem in an uncertain network and the shortest path problem in a deterministic network.

The above optimization problem of the uncertain network system has been mainly discussed in random environment and fuzzy environment, and experts mostly focused on the uncertainty of network attributes. However, when the samples in the network are too few, or there are even no samples, experts need to evaluate and give the confidence of event occurrence. Many investigations ^[12] show that the confidence range given by a human is much larger than the actual range, and Liu ^[13] once cited a counter example to illustrate the wrong result of using probability theory and fuzzy theory to deal with expert confidence. Therefore, it is no longer appropriate to employ probability theory or fuzzy theory to deal with the uncertainty.

In order to deal with the uncertainty, uncertainty theory was established by Liu ^[12] in 2007, and it became a mathematical branch of axiomatic uncertainty modeling. In 2010, uncertainty theory was introduced into the network optimization problem, the concept of an uncertain network was proposed for the first time, and the project scheduling problem with uncertain time based on uncertainty theory was studied by Liu et al. ^{[12,13,14,15]}. Then, many scholars committed to the research of uncertain networks. In 2011, Gao et al. ^[16,17] employed the numerical method for solving the shortest path uncertainty distribution function in an uncertain network, and established the model for solving the shortest path problem with maximum uncertainty measure. In Gao's doctoral thesis ^[18], he researched the shortest path problem with uncertain network structures. The uncertainty theory was applied to graph theory, and the relevant theories of uncertain graphs with fixed vertex sets were further improved. The connectivity index and the algorithm of edge connectivity were given by Gao. Luo ^[19] improved the definition of vertices structure uncertain graphs and the uncertain measure matrix. Then, he discussed the network optimization problem of uncertain graphs.

Uncertain network optimization is a hot issue in recent years. Gao ^[18] and Luo ^[19] studied uncertain network optimization problems with uncertain structures. It needs to be pointed out that there are some challenges. In actual situation, sometimes the network attributes are uncertain. Therefore, it is necessary to consider the uncertainty of network structures and attributes. As the uncertainty of network structures has just been proposed in recent years, there are a few research results for the network optimization problem with the uncertainty of network structures and network attributes. Now, the main challenge is how to unify the uncertainty of attributes and structures. Motivated by the idea of Gao ^[18], we research the network optimization problem with uncertain network structures and attributes. In this paper, first, the uncertainty characteristics of a network system are extracted, and the general definition and matrix identification of an uncertain network system are proposed. Second, according to the decision criteria of relevant opportunity programming, we establish a shortest path optimization model based on conditional uncertain measure. Third, combining measure simulation technology with a traditional algorithm, we design a hybrid intelligent algorithm to solve the shortest path problem in an uncertain network system. Finally, we discuss the tunnel planning problem of an underground logistics system. Then, the optimization model and the designed intelligent algorithm are employed to solve the problem of an underground logistics system.

The remainder of this paper is organized as follows. In Section 2, uncertain measure and an uncertain network system are introduced and formulated. It includes the matrix identification of an uncertain network system. In Section 3, we establish a shortest path optimization model based on conditional uncertain measure. In Section 4, we design a hybrid intelligent algorithm to solve the shortest path problem according to measure simulation technology. In Section 5, we study a numerical case to demonstrate the correctness of concepts and methods proposed in this paper. In Section 6, a brief summary is given.

2.   Uncertain network system and conditional uncertain measure matrix

2.1.   Uncertain measure

Definition 1. ^[12,14] Let $\Gamma$ be a nonempty set, and $L$ be a $\sigma -$ algebra over $\Gamma$. Each element $\Lambda$ in $L$ is called an event. The set function $M$ is called an uncertain measure if it satisfies the following three axioms.

Axiom 1. (Normality) $M\left\{ \Gamma \right\} = 1$.

Axiom 2. (Self-Duality) $M\left\{ \Lambda \right\} + M\left\{ {{\Lambda ^c}} \right\} = 1$ for any event $\Lambda$.

Axiom 3. (Subadditivity) For every countable sequence of events $\left\{ {{\Lambda _i}} \right\}_{i = 1}^{ + \infty }$, we have

The set function ${M}$ is called an uncertain measure, and the triplet $(\Gamma, L, {M})$ is called an uncertainty space.

2.2.   Uncertain network system

An network is also called a weighted graph. In 2013, Gao ^[17] first proposed the graph theory problem with uncertain edge structures. When the weight of network attributes was a constant, Gao ^[17] discussed the network optimization problem with uncertain edge structures. In 2018, the matrix representation of a graph with uncertain structures was perfected by Luo ^[19].

The above studies are based on two perspectives: One is to discuss the uncertainty of network structures; the other is to study the uncertainty of network attributes. In a practical problem, there will be such a situation: The weights in the network are uncertain, and the vertices and edges of the network are not fixed. That is, the attributes and structures of the network are uncertain. Obviously, the existing definition of an uncertain network is no longer applicable, and there are few studies on the network optimization problem with uncertainty of attributes and structures.

In order to solve this problem, based on uncertainty theory, we unify the structure uncertainty and attribute uncertainty in the network by the idea of conditional measure, and we define the uncertain network system through a conditional uncertain measure matrix in the form of an adjacency matrix.

An uncertain network system is defined as follows:

Definition 2. An uncertain network system is a four-tuple composed of edge set $E(G)$, vertex set $V(G)$, and uncertain variable set $\xi (G)、\lambda (G)$ corresponding to the vertex and edge set, denoted as

where the vertex set is $V = ({v_1}, {v_2}, {v_3}, \cdot \cdot \cdot, {v_n})$, and the edge set is $E = ({e_1}, {e_2}, {e_3}, \cdot \cdot \cdot, {e_m})$. ${\xi _i}$ is a nonnegative uncertain variable, and $\xi = ({\xi _1}, {\xi _2}, {\xi _3}, \cdot \cdot \cdot, {\xi _m})$ indicates whether the corresponding vertices and edges exist. ${\lambda _i}$ is a nonnegative uncertain variable, and $\lambda = ({\lambda _1}, {\lambda _2}, {\lambda _3}, \cdot \cdot \cdot, {\lambda _m})$ represents the weights of the vertices and edges. ${\xi _i}$ and ${\lambda _i}$ are independent of each other.

According to Definition 2, considering the uncertainty of network attributes and network structures, we propose a new concept of an uncertain network system.

2.3.   Conditional uncertain measure matrix

According to the definition of an uncertain network system, the corresponding network attributes do not exist when the network structures do not exist. For example, for the optimization problem of road transportation, if the road is disrupted due to an emergency, the corresponding edge of the road in the network does not exist. That is, the measure of the edge existence is 0, and the weight corresponding to the edge does not exist. Therefore, in the uncertain network system, the existence of network structures is a necessary condition for the existence of network attributes. Due to this characteristic of an uncertain network system, based on the conditional measure matrix and uncertainty theory, we employ the conditional uncertain measure matrix to identify the proposed uncertain network system.

Definition 3. The uncertain network system uniquely corresponds to a conditional uncertain measure matrix $\Psi = {\left({{\varepsilon _{ij}}} \right)_{n \times n}}$, if and only if ${\varepsilon _{ij}}$ satisfies the following:

When $i = j$ and the vertex ${v_i}$ exists, ${\varepsilon _{ii}}$ represents the uncertain measure when the weight of vertex ${v_i}$ is uncertain variable ${\lambda _{ii}}$, denoted as ${\varepsilon _{ii}}({\lambda _{ii}}\left| {{\xi _{ii}} = 1} \right.) = M\left\{ {{\lambda _{ii}}\left| {{\xi _{ii}} = 1} \right.} \right\}$. ${\xi _{ii}} = 1$ represents the existence of vertex ${v_i}$.

When $i \ne j$ and the edge ${v_{ij}}$ connected by vertex ${v_i}$ and vertex ${v_j}$ exists, ${\varepsilon _{ij}}$ represents the uncertain measure when the weight of edge ${v_{ij}}$ is uncertain variable ${\lambda _{ij}}$, denoted as ${\varepsilon _{ij}}({\lambda _{ij}}\left| {{\xi _{ij}} = 1} \right.) = M\left\{ {{\lambda _{ij}}\left| {{\xi _{ij}} = 1} \right.} \right\}$. ${\xi _{ij}} = 1$ represents the existence of edge ${v_{ij}}$ connected by vertex ${v_i}$ and vertex ${v_j}$.

Matrix $\Psi$ is called a conditional uncertain measure matrix, and then the uncertain network system is identified as the following matrix:

Remark 1. The conditional uncertain measure matrix is used to identify the uncertain network system. The unified identification method can make the storage of network information in the computer more convenient and easy to calculate.

For more intuitively understanding the identification approach of the uncertain network system, we give the theoretical analysis for an uncertain network system with an example. Figure 1 gives vertices A, B, C and edges AB, AC, BC.

In Figure 1 (a), if the vertex O is uncertain, vertex O exists with an uncertain measure ${M_O} = M\left\{ {{\lambda _{44}}\left| {{\xi _{44}} = 1} \right.} \right\}$.${\lambda _{44}}$ is the uncertain variable corresponding to the vertex weight, and ${\xi _{44}}{\text{ = }}1$ represents the existence of vertex O. Then, edges OA, OB, and OC must exist with uncertain measures. Assuming that the edges OA, OB and OC exist with the uncertain measure ${M_a} = M\left\{ {{\lambda _{14}}\left| {{\xi _{14}} = 1} \right.} \right\}, {M_b} = M\left\{ {{\lambda _{24}}\left| {{\xi _{24}} = 1} \right.} \right\}, {M_c} = M\left\{ {{\lambda _{34}}\left| {{\xi _{34}} = 1} \right.} \right\}.\; {\lambda _{14}}, {\lambda _{24}}, {\lambda _{34}}$ are the uncertain variables corresponding to the edge weights. Then, the conditional uncertain measure matrix corresponding to this uncertain network system satisfies:

In Figure 1 (b), if the vertex O is certain (that is ${M_O} = {\text{1}}$), and edges OA, OB and OC exist with the uncertain measures ${M_a} = M\left\{ {{\lambda _{14}}\left| {{\xi _{14}} = 1} \right.} \right\}, {M_b} = M\left\{ {{\lambda _{24}}\left| {{\xi _{24}} = 1} \right.} \right\}, {M_c} = M\left\{ {{\lambda _{34}}\left| {{\xi _{34}} = 1} \right.} \right\}$, respectively, then the conditional uncertain measure matrix corresponding to this uncertain network system satisfies:

If the structures and weights of vertices O, A, B, C and edges OA, OB, OC, AB, AC, BC are all determinate, the conditional uncertain measure matrix corresponding to this uncertain network system satisfies:

Remark 2. Analyzing the above three conditional uncertain measure matrixes, we point out that is a traditional network when the vertices and edges are determinate. We can regard ${\Psi _3}$ as a special case in uncertain network systems. Thus, the concept of an uncertain network system proposed by us extends the previous concepts.

3.   Shortest path problem in uncertain network system

In this section, we discuss the shortest path problem with uncertain network attributes and network structures based on conditional uncertain measure. We establish the shortest path optimization model according to correlation chance programming.

(1) Problem description

The transportation network between multiple cities is given. Due to the influence of road conditions and emergencies, whether each road in the given network is unblocked or not is uncertain, and the distance of each road is also uncertain. They all exist with a certain measure. For the shortest path problem, given an acceptable upper bound of the shortest path length, the aim is to find if the shortest path that satisfies the maximum possibility of connecting each city is not greater than the given upper bound.

(2) Modeling principle

The above problem is to investigate the shortest path problem with uncertainty. It is necessary to consider the uncertainty of network attributes and network structures. According to the idea of conditional uncertain measure in Chapter 2, the uncertainty of network attributes and network structures is unified. The obtained conditional uncertain measure matrix can be regarded as the weights in the network. That is, the shortest path problem with uncertain attributes and structures can be transformed into a common shortest path problem with uncertain attributes. Then, we can model the shortest path model with uncertain attributes and structures.

According to the decision criteria of correlation chance programming, if the upper bound of the acceptable shortest path length (also known as the satisfactory length) is given by the decision-maker, the chance function satisfying that the shortest path length is not greater than the given length is maximized.

(3) Problem analysis

The shortest path problem can be abstracted as finding the shortest path from vertex ${v_1}$ to vertex ${v_n}$ in the uncertain network system $N = (V, E, \xi, \lambda)$. $V = ({v_1}, {v_2}, \cdot \cdot \cdot, {v_n}), E = ({e_1}, {e_2}, \cdot \cdot \cdot, {e_m})$ indicate that there are $n$ vertices and $m$ edges in the network. $\Phi = {\left({{\varphi _{ij}}} \right)_{n \times n}}$ is the uncertain measure matrix of existence of each edge corresponding to the uncertain variable $\xi$, and $\Omega = {\left({{\lambda _{ij}}} \right)_{n \times n}}$ is the uncertain measure matrix corresponding to the distance of each edge corresponding to the uncertain variable $\lambda$. ${T_0}$ is the upper bound of acceptable shortest path length.

According to Definition 3, the uncertain measure matrix with uncertain edge structures is $\Phi = {\left({{\varphi _{ij}}} \right)_{n \times n}}$ while the uncertain measure matrix corresponding to distance (attributes) is $\Omega = {\left({{\lambda _{ij}}} \right)_{n \times n}}$. Then, a conditional uncertain measure matrix in the uncertain network system is obtained as follows:

If $i \ne j$ and under the condition of that the edge ${v_{ij}}$ connected by vertex ${v_i}$ and vertex ${v_j}$ exists, ${\varepsilon _{ij}}$ represents the uncertain measure when the path length of edge ${v_{ij}}$ is the uncertain variable ${\lambda _{ij}}$, denoted as ${\varepsilon _{ij}}({\lambda _{ij}}\left| {{\xi _{ij}} = 1} \right.) = M\left\{ {{\lambda _{ij}}\left| {{\xi _{ij}} = 1} \right.} \right\}$. ${\xi _{ij}} = 1$ represents the existence of edge ${v_{ij}}$ connected by vertex ${v_i}$ and vertex ${v_j}$. If $i = j$, ${\varepsilon _{ii}} = + \infty$.

(4) Model establishment

Determination of decision variable: the following approach is adopted to represent the path $X = \{ {x_{ij}}\left| {i < j = 1, 2, 3, \cdot \cdot \cdot, n} \right.\}$. ${x_{ij}} = 1$ means that edge ${v_{ij}}$ is included in the shortest path, and ${x_{ij}} = 0$ means that edge ${v_{ij}}$ is not included in the shortest path.

Determination of objective function: the shortest path length can be expressed as $l(P) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{x_{ij}}} } {\varepsilon _{ij}}$. If the shortest path length is not greater than the upper bound ${T_0}$, it can be expressed as $l(P) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{x_{ij}}} } {\varepsilon _{ij}} \leqslant {T_0}$. In order to maximize the measure of the occurrence of the event, there is $M\left\{ {l(P) \leqslant {T_0}} \right\}$, and the objective function is:

Determination of constraints: Decision variable ${x_{ij}}$ is 0-1 variable, i.e., ${x}_{ij}\in \left\{0, 1\right\}, {v}_{i}、{v}_{j}\in V$. In order to make each vertex in and out of equilibrium, there is

As there may be cycles in the shortest path, it is necessary to restrict each vertex to go in and out once, that is

To sum up, the maximum chance shortest path network optimization model based on correlation chance programming is as follows:

Remark 3. When the uncertain variable ${\varepsilon _{ij}}$ is a random variable, the objective function corresponding to the random variable ${\varepsilon _{ij}}$ is the maximization of probability measure, that is, max $Pr\left\{ {\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{x_{ij}}} } {\varepsilon _{ij}} \leqslant {T_0}} \right\}$; When the uncertain variable ${\varepsilon _{ij}}$ is a fuzzy variable, the objective function corresponding to the fuzzy variable ${\varepsilon _{ij}}$ is to maximize the credibility measure, i.e., max $Cr\left\{ {\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{x_{ij}}} } {\varepsilon _{ij}} \leqslant {T_0}} \right\}$. When the uncertain variable ${\varepsilon _{ij}}$ is a rough variable, the objective function corresponding to the rough variable ${\varepsilon _{ij}}$ is to maximize the reliability measure, that is, max $Tr\left\{ {\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{x_{ij}}} } {\varepsilon _{ij}} \leqslant {T_0}} \right\}$.

4.   Hybrid intelligence algorithm for solving the shortest path problem

4.1.   Simulation of uncertain function

The objective function max $M\left\{ {\sum\limits_{i = 1}^n {\sum\limits_{j = 1}^n {{x_{ij}}} } {\varepsilon _{ij}} \leqslant {T_0}} \right\}$ contains uncertain variables, and the measure simulation technology is employed to simulate the uncertain function. The uncertain function is denoted as $T(x, \zeta)$, and the uncertain distribution corresponding to the uncertain variable is $\Upsilon (k) = M\left\{ {\zeta \leqslant k} \right\} = ({\Upsilon _1}, {\Upsilon _2}, {\Upsilon _3}, \cdot \cdot \cdot, {\Upsilon _p})$.

The uncertain function $U:x \to M\left\{ {T(x, \zeta) \leqslant {T_0}} \right\}$ is simulated as follows. First, the uncertain variable $\zeta$ is randomly generated, and repeated $N$ times. $N'$ represents the number of times for which inequality $T(x, \zeta) \leqslant {T_0}$ holds. Give the definition:

Then, $E[h({\zeta _n})] = U, N' = \sum\limits_{n = 1}^N {h({\zeta _n})}$. According to the strong law of large numbers ^[20],

It converges to $U$ almost everywhere. If $N$ is large enough, $U \to \frac{{N'}}{N}$.

The measure simulation process is as follows:

Step1. Let $N' = 0$.

Step2. Generate $\Upsilon = ({\Upsilon _1}, {\Upsilon _2}, {\Upsilon _3}, \cdot \cdot \cdot, {\Upsilon _p})$ according to the distribution function of uncertain variables.

Step3. If $T(x, \zeta) \leqslant {T_0}$, then $N' + +$.

Step4. Repeat step 2 and 3 for $N$ times.

Step5. $U(x) = N'/N$.

Based on the above measure simulation, the maximum chance shortest path model in uncertain programming can be transformed into an equivalent deterministic form as follows:

4.2.   Hybrid intelligent algorithm based on measure simulation

Motivated by the idea of a hybrid intelligent algorithm, first, the uncertain function is simulated. Second, the model of uncertain programming is transformed into its equivalent deterministic form, and then we employed the Floyd algorithm, which is a traditional algorithm, to solve the model.

The Floyd algorithm ^[21] can solve the shortest path between vertices in a given weighted graph, and it can correctly deal with the shortest path problem of a directed graph.

The steps of the algorithm are as follows:

Step1. Generate the weight matrix between any two vertices.

Step2. Judge whether there is another vertex $u'$ between any two vertices $v$ and $u$, so that the distance $D'$ from $v$ to $u'$ and then to $u$ is smaller than the weight $D$ in the weight matrix.

Step3. If $D' < D$, then $D = D'$. Otherwise, do not update.

Step4. Stop the algorithm until the weights of any two vertices are updated.

5.   Case study on underground logistics system planning

Underground logistics system (ULS) refers to the transportation and supply system that transports goods between cities through underground pipelines or tunnels similar to a subway ^[22]. It is a plan that developed countries want to adopt to solve the problem of urban freight transportation. For China, the construction of an urban subway network, underground space development, and the construction of an underground logistics system network are essential links in the construction of an "underground logistics system''.

At present, the studies ^[23,24,25] on ULS mainly focus on the following four aspects: (1) Concept and design research. (2) Feasibility study of ULS. (3) Simulation research of ULS. As a forward-looking logistics facility, there is no successful case at home and abroad. Therefore, logistics simulation is particularly important. (4) Research on network layout and optimization of ULS. At present, the research on this aspect is a hot spot. For example, Z. Y. Peng et al. ^[26] established a multi-objective mixed integer programming model for ULS programming problem, and designed a two-stage greedy algorithm to solve the model. W. J. Hu et al. ^[27] comprehensively considered the factors of underground tunnel distance and freight volume, and solved the planning problem of underground logistics based on a simulated annealing clustering algorithm. B. Erkayman et al. ^[28] considered the actual urban environment and the characteristics of logistics pipeline construction, and planned the underground logistics network system based on the fuzzy ideal vertex method.

In the above optimization researches on the ULS problem, its logistics nodes and underground tunnel connection are certain. However, in a practical situation, considering the high cost, high risk and difficult reconstruction of an underground tunnel, it is necessary to consider the uncertainty of an underground tunnel connection. According to the concept of uncertain network system in Section 2 and the optimization of the shortest path problem in Section 3, we investigate the underground tunnel planning with uncertainty in this section.

5.1.   The underground tunnel planning problem with uncertainty

(1) Problem description

Based on the underground logistics system (ULS) mentioned in question F of the 14th "Huawei Cup'' Chinese graduate mathematical modeling competition, the aim is to plan the underground logistics system in the Xianlin area of Nanjing. This section plans the tunnel construction for the second problem on the premise that the node location problem for the first question has been solved.

The central locations of 13 1th level nodes and 32 2th level nodes in the Xianlin area of Nanjing are known (see Figure 2). The real-time freight volume matrix between regions is given (because the real-time freight volume matrix is huge, this matrix is not given here, and the specific data can refer to the appendix of F competition). The construction cost of underground logistics tunnel is as follows: Two-way four track (double tunnel) (10 tons) costs 500 million/km, two-way double track (double tunnel) (10 tons) costs 400 million/km, two-way four track (double tunnel) (5 tons) costs 350 million/km, and two-way double track (double tunnel) (5 tons) costs 300 million/km.

Planning of underground logistics system: How to make the best tunnel planning for each logistics node on the premise of known data? The 1th level nodes can be connected with 1th level nodes, and they are only connected with the 2th level nodes in the region. The 2th level nodes can be connected with the 2th level nodes.

(2) Problem analysis

In order to solve the tunnel planning problem between nodes, it is necessary to comprehensively consider the construction cost and service capacity of the tunnel. Whether to build tunnels between nodes is closely related to the real-time freight volume. If the freight flow between nodes is larger, it is more probable to construct tunnels for meeting the service demand and alleviating the traffic pressure. Moreover, it is uncertain whether the two-way four track or two-way double track is used to construct the logistics tunnel between nodes, so the cost of the tunnel is also uncertain. Based on this situation, we regard the underground logistics system planning problem as the shortest path problem in an uncertain network system.

If the freight volume between nodes is larger, it indicates that tunnels should be more probable to be constructed. If the freight volume between the two places is small, even if the distance between nodes is short, tunnel planning will not be given priority in planning. Therefore, the possibility of the existence of the tunnel can be described by the freight volume, and the freight volume between the two places can describe the uncertain measure of the edge.

If the freight volume from logistics node i to logistics node j is ${h_{ij}}$, the uncertain measure ${\xi _{ij}}$ between vertex i and vertex j satisfies:

where $\mathop {\max }\limits_{i, j \in \{ 1, 2, ..., n\} } \{ {h_{ij}}\}$ and $\mathop {\min }\limits_{i, j \in \{ 1, 2, ..., n\} } \{ {h_{ij}}\}$, respectively, represent the maximum and minimum freight volume of the whole system in a certain period of time.

As the tunnel type is uncertain, the construction cost is uncertain. ${\lambda _{ij}}$ is the construction cost of the tunnel between node i and node j. Obviously, ${\lambda _{ij}}$ is an uncertain variable. Given an acceptable upper bound ${T_0}$, the problem can be transformed into the problem of finding the optimal tunnel from node ${v_1}$ to node ${v_n}$ that satisfies that the maximum possibility of the minimum cost is not greater than the given upper bound ${T_0}$ in the uncertain network system $N = (V, E, \xi, \lambda)$? The existence of each edge is the variable $\xi$, and the uncertain measure matrix corresponding to it is ${\left({{\xi _{ij}}} \right)_{n \times n}}$. The cost of each edge is the variable $\lambda$, and the uncertain measure matrix corresponding to it is ${\left({{\lambda _{ij}}} \right)_{n \times n}}$.

According to Definition 3, the conditional uncertain measure matrix can be obtained as follows:

If $i \ne j$ and under the condition that the edge ${v_{ij}}$ connected by vertex ${v_i}$ and vertex ${v_j}$ exists, ${\varepsilon _{ij}}$ represents the uncertain measure when construction cost of edge ${v_{ij}}$ is the uncertain variable ${\lambda _{ij}}$, denoted as ${\varepsilon _{ij}}({\lambda _{ij}}\left| {{\xi _{ij}} = 1} \right.) = M\left\{ {{\lambda _{ij}}\left| {{\xi _{ij}} = 1} \right.} \right\}$. ${\xi _{ij}} = 1$ represents the existence of edge ${v_{ij}}$ connected by vertex ${v_i}$ and vertex ${v_j}$. If $i = j$, take ${\varepsilon _{ii}} = + \infty$. Let the conditional uncertain distribution function corresponding to the uncertain variable ${\varepsilon _{ij}}$ be ${\Upsilon _{ij}}(k) = M\left\{ {{\varepsilon _{ij}} \leqslant k} \right\} = M\{ {\lambda _{ij}} \leqslant k\left| {{\xi _{ij}} = 1} \right.\}$.

5.2.   Optimal tunnel network planning of ULS

We establish a model for solving the optimal tunnel network planning problem of ULS.

The decision variable: Let path $X = \{ {x_{ij}}\left| {i < j = 1, 2, 3, \cdot \cdot \cdot, n} \right.\}$, where ${x_{ij}} = 1$ indicates that edge ${v_{ij}}$ is included in the optimal tunnel network; ${x_{ij}} = 0$ indicates that edge ${v_{ij}}$ is not included in the optimal tunnel network.

Determination of objective function and constraint conditions: The construction cost should not exceed standard level of 1300 billion. Let ${T_0} = 1300$, and the objective function is

The network optimization model of ULS is:

Next, we employ a hybrid algorithm to solve the model based on measure simulation technology.

Nodes are divided into 1th level and 2th level nodes, and the freight volume of nodes is also significantly different. Therefore, whether there is a route between nodes, the idea of a hierarchical sequence method is considered to plan the underground logistics network. The optimal adjacency matrix satisfying the constraints is sought for the 1th level and 2th level nodes, respectively: the adjacency matrix P1 and the adjacency matrix P2. Then, as the 2th level nodes are only connected with the 1th level nodes in the region, the adjacency matrix is recombined and constructed based on this rule.

Based on measure simulation technology and hybrid intelligent algorithm, the network tunnel planning problem of ULS in the uncertain network system is solved.

The optimal tunnel network is calculated by programming with MATLAB. Due to the length limitation, only tunnel planning between the 1th level nodes and ULS network tunnel planning diagram is listed here, as shown in Table 1 and Figure 3.

Remark 4. By studying the above impressive example, the ideas and approaches proposed by us are verified to be correct and effective. The established model and the designed hybrid intelligent algorithm provide a new way to solve the optimization problem in uncertain network system.

5.3.   Comparisons with the traditional methods

To illustrate the superiority of the proposed method, we adopt a previous optimization method to solve this problem. Moreover, we analyze the results and compare the new approach with the previous approach.

According to ^[29], we employ the dynamic programming model of the ULS to obtain its construction schedule and dynamic evolution process. Let the tunnel be constructed at each stage and the specific model is as follows:

where $k \in (1, 2, \cdot \cdot \cdot, m)$ is the stage variable, ${d_k}$ the length of the kth tunnel, ${L_k}$ is the total length of previous k tunnels allowed to be constructed in the ULS network at the beginning of the kth stage and ${L_0} = 0$, ${x_k} \in \left\{ {0, 1} \right\}$ indicates whether the kth tunnel is built or not, and ${f_k}({L_k})$ represents the maximum value of which the total length of being allowed construction routes is less than ${L_k}$.

We adopt the simulated annealing algorithm to solve the above model. By programming with MATLAB, the table of dynamic planning for the tunnels and the ULS network tunnel planning diagram are shown as follows:

By analyzing the results of dynamical network tunnel planning and uncertain network system planning, we found that though the result of the previous approach is acceptable, some 1th level nodes with vast volume are not connected with each other. Moreover, some 2th level nodes are close to each other, but the freight volume is small, and there is no need to build tunnels between these nodes. This planning scheme cannot meet the needs of logistics and transportation to the greatest extent. As we consider the uncertainty of tunnel construction, the tunnel planning of ULS proposed by us is more reasonable and effective.

Remark 5. The Comparison of two methods illustrates the improvement and superiority of the proposed method.

Remark 6. In this paper, we adopt the hybrid intelligent algorithm to solve the optimization model in an uncertain network system. It needs to simulate the uncertain function first, and then use the Floyd algorithm to solve the model. The algorithm steps are not simple enough, and the simulation of uncertain function is random. In the future, we will devote ourselves to designing the heuristic algorithm to directly solve the uncertain programming model.

6.   Conclusions

There are vast uncertain factors in the network system; therefore, it is necessary for us to consider the uncertainty in the network system when studying network optimization problems. Based on uncertainty theory, uncertain programming, network optimization theory and hybrid intelligent algorithm, we investigate the optimization problem of an uncertain network system. First, we propose the general definition of an uncertain network system based on the uncertainty of network attributes and network structures. Second, by the form of an adjacency matrix, we employ the conditional uncertain measure matrix to identify the uncertain network system, which provides a new idea for the storage form of the uncertain network system in computer. Third, we establish the optimization model of the shortest path problem in an uncertain network system, and we design a hybrid intelligent algorithm to solve the optimization model. Finally, by studying an example and comparing it with other results, the ideas and approaches proposed in this paper are verified to be correct and effective. The established model and designed intelligent algorithm provide a new way to solve the optimization problem in an uncertain network system.

In the future, we will focus on further combining the uncertainty theory with the uncertain network system and developing the uncertain optimization model with different decision criteria such as expected value planning and opportunity constraint planning. Furthermore, we will extend our idea to the maximum flow problem, matching problem and minimum cost flow problem in uncertain network system. For the algorithm of the optimization model in an uncertain network system, the hybrid intelligent algorithm is adopted in this paper. In the future, we will devote ourselves to designing the heuristic algorithm to directly solve the uncertain programming model.

Acknowledgments

This work is supported by the school level scientific research project of Neijiang Normal University (2021YB19) and the applied basic research project of Sichuan Province (2021JY0108).

Conflict of interest

We declare that we have no conflicts of interest.