# Dynamic Network Planning of Underground Logistics System on Uncertainty Graph

Authors: YiHua Zhong; ShiMing Luo; Min Bao; XiaoDie Lv
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

When designing the underground logistics system, it is necessary to consider the uncertainty of logistics nodes, high cost, and high risk. This paper employed the theories of uncertain graph and dynamic programming to solve the network planning problem of underground logistics system. Firstly, we proposed the concepts of uncertainty measure matrix and vertices structure uncertainty graph by using uncertainty measure and uncertainty graph. Secondly, vertices structure uncertainty graph of the underground logistics system was constructed based on our proposed vertices structure uncertainty graph and the uncertainty of logistics nodes. Thirdly, the dynamic programming model of the underground logistics system was established, and its solution algorithm was also designed by improving simulated annealing. Finally, the correctness and feasibility of the method was validated by using a numerical example of the underground logistics system in Xianlin district, Nanjing City in China.


---

## Body

## 1. Introduction

Problems in transportation and logistics had been tackled well since computers and operational research (OR) became available [1]. However, a new challenge to transportation and logistics is the huge pollution and economic impact of transportation on the environment and logistic costs of companies. The underground logistics system (ULS) is the system of underground freight transportation and supply in inner city and among cities. It can reduce urban pollution by using electric energy to achieve transportation of low-carbon environmental protection. Moreover, it can also effectively reduce the cost and traffic pressure on the ground road to alleviate urban traffic congestion. At present, many countries in the world considered developing urban underground logistics system as a new way of alleviating traffic dilemma. Modern underground logistics system has been studied for nearly 30 years. The United States, Britain, Holland, and Japan just only carried out some of the engineering practices for the underground logistics system [2, 3], but there is still not any successful case as an example of studying [4]. Therefore, the international research for ULS is a relatively new expanding field.The applications of the early ULS are various. American scholars proposed the freight transports by using underground pipeline or tube transport, which were driven by electricity to transport municipal refuse and coal. The Japanese scholars set up an underground mail system between the Tokyo station and the central post office. Holland scholars used the ULS to connect the Aalsmeer flower market, the Schiphol airport, and the Hoofddorp railway transfer station. By using the ULS, timeliness goods such as flowers may be transported in time [5]. But, nowadays the ULS is obviously different from the early transportation system in influence factors of their construction: the city scale and traffic network congestion [6]. The current studies on the ULS mainly focus on three aspects: feasibility analysis, risk assessment, and network planning of logistics system.Based on the OLS-ASH project (which is used to illustrate the designing of such a highly automated freight transportation system), Pielage proposed and analyzed the underground freight transport system and its feasibility as well as its specific design steps with the transportation system in Holland [3]. Hane et al. took Tokyo as an example to analyze the influence degree of the cost-benefit of constructing ULS on the original logistics system [7]. In 2004, Qian first presented a new ULS system and studied the traffic congestion of Beijing in China [8]. Chen et al. used macroenvironment to analyze the applicability of the ULS in China’s traffic environment and determined the internal and external factors affecting the system. Moreover, the relevant recommendations about risk assessment of building ULS were proposed based on the situation analysis framework [9]. van der Heijden et al. simulated and analyzed the operating characteristics of the underground logistics network structure and the constructing cost and efficiency among different regions [10].The researches on the node layout and network optimization of the ULS are the hottest research. Johan analyzed and compared the characteristics of different network structures of the ULS, such as punctiform network, linear network, and reticular network [11]. Based on a definite graph whose vertices and edges are predetermined, Zhu et al. established the node location model of 0-1 linear programming to find the best logistics node [12]. Considering the characteristics of urban environment and logistics nodes, Erkayman et al. proposed the fuzzy TOPSIS (technique for order preference by similarity to an ideal solution) method of planning the logistics center [13]. From the point of view of transportation, construction, economy, technology, and sustainable development, Turskis and Zavadskas presented the ARAS-F (fuzzy additive ratio assessment) method to select the logistics center [14]. According to the stage characteristics of integration process on logistics facilities in Beijing, Tianjin, and Hebei, Guo and Zhuang proposed the cloud model to evaluate complex systems [15]. Yan and Qin adopted the bilevel programming model to select the location of the underground logistics nodes, including the upper-level planning model from the perspective of decision-makers and the lower-level planning model from the perspective of customers [16]. Based on plant growth simulation algorithm, Li optimized the network route of ULS in large cities [17]. Binsbergen and Johan studied the optimization method of the route layout in urban underground logistics network [18]. By applying multimodule network analytic hierarchy process (AHP) based on point, linear, and surface, Mu set up a model of set covering to study and analyze the problem of road planning of the ULS [19].An important premise of the above studies on the ULS is that logistics nodes are predetermined. However, whether a logistics node of an ULS exists or not in real life depends on a number of factors such as total freight volume, transportation cost, traffic congestion index, construction cost, and traffic interruption. Because data and information of expert estimating and judging above those factors have not only fuzziness but also randomness or imprecision in studying the ULS, the above studies only solved the planning of the ULS with determinate logistics nodes. Obviously, it is not very appropriate to formulate the existence of logistics nodes and the edges connecting logistics nodes only by fuzzy theory or random theory. Uncertainty theory proposed in 2007 and refined in 2010 by Liu [20, 21] is a new tool to handle expert data with fuzziness or randomness or imprecision. In 2013, Gao and Gao first introduced uncertainty theory into graph models and proposed a concept of uncertain graph, in which the existence possibility (reliability) of each edge is described by uncertain measures [22]. It is well known that the ULS has the characteristic of high cost and high risk as well as difficulty improving. Moreover, the impact of logistics nodes on the whole system is different. From the view of ULS top-level design, the following problems should be focused: the time order and the evolution process about route construction of its optimal network. Therefore, a technical process for dynamic network planning of the ULS with vertices structure uncertainty graph may be obtained by applying dynamic network programming [23, 24] and extending uncertainty graph proposed by Gao and Gao [22, 23, 25].In this paper, firstly, the uncertainty graph of logistics nodes will be constructed according to the definition of vertices structure uncertainty graph and the key degree of each logistics node proposed by us. Secondly, the time order of evolution process and dynamic programming model of ULS will be established based on the uncertainty graph of logistics nodes formulated by us. This uncertainty graph of logistics nodes includes the measure size of each logistics node, the measure size of each tunnel, and each network route. Thirdly, the simulated annealing algorithm will be designed to solve this dynamic network optimization model to obtain the evolution process of an ULS construction project. Finally, the optimal construction time order and dynamic evolution process of an ULS will be programmed with an ULS construction project in Xianlin district, Nanjing city, China, by using the method and algorithm proposed in the paper.The remainder of this paper is organized as follows: in Section2, uncertainty measures and uncertainty graphs are introduced and formulated. It includes uncertainty measures and the relative definitions of vertices structure uncertainty graph. In Section 3 the vertices structure uncertainty graph based on an uncertainty of logistics nodes is constructed. Section 4 establishes a dynamic programming model of ULS network construction. In Section 5, an algorithm to solve dynamic programming of the ULS based on the simulated annealing algorithm is designed. In Section 6, a numerical case is studied to demonstrate the correctness of concepts and methods proposed in this paper. Section 7 concludes this paper with a brief summary.


## 2. Uncertainty Measure and Uncertainty Graph

### 2.1. Uncertainty Measure

LetΓ be a nonempty set and ℒ be a σ− algebra over Γ. Each element Λ in ℒ is called an event. The set function M is called an uncertain measure if it satisfies the following three axioms [20, 21].Axiom 1 normality.
M
Γ
=
1.Axiom 2 self-duality.
M
Λ
+
M
Λ
c
=
1 for any event Λ.Axiom 3 subadditivity.
For every countable sequence of eventsΛii=1+∞, we have(1)M∪i=1∞Λi≤∑i=1∞MΛi.
The tripletΓ,L,M is called an uncertainty space. Uncertainty measure is interpreted as the personal belief degree (not frequency) of an uncertain event that may happen. Thus, uncertainty measure and belief degree are synonymous. Uncertainty measure depends on the personal knowledge concerning the event. It will change if the state of knowledge changes. In other words, it may be understood simply as a probability Pr in a random environment, or a credibility measure Cr in the fuzzy environment, or a trust value Tr in the rough environment.


### 2.2. Vertices Structure Uncertainty Graph

The definition of an uncertain graph was first proposed by Gao and Gao [22] in 2013. But their definition assumed that the vertices in the graph are predetermined. Therefore, their definition may be considered as only applying to a special uncertain graph whose edges are not predetermined and whose existence possibility (reliability) of each edge is described by uncertain measures. It is called as the edge structure uncertainty graph by us. By analogy of its definition and the idea of adjacent matrix representing graph, we present definitions of uncertainty measure matrix and vertices structure uncertainty graph as follows.Definition 1.
The graph with uncertain vertices structure uniquely corresponds to an uncertainty measure matrixΦ=ϕijn×n if and only if ϕij satisfies the following:(1)
Wheni=j, ϕii=Mvi=1 represents the uncertainty measure of vertex vi existence, which is simply denoted as ϕi(2)
Wheni≠j, ϕij=Mvivj=1 represents the uncertainty measure of the edge connecting vertex vi and vertex vjwherevi=1 indicates that vertex i exists, vi=0 indicates that vertex i does not exist, vivj=1 indicates that the edge connecting vertices i and j exists, and vivj=0 indicates that the edge connecting vertices i and j does not exist.
Based on the uncertainty measure matrix and the definition of the edge structure uncertainty graph, we propose a definition of the vertices structure uncertainty graph as follows.Definition 2.
The graph with uncertain vertices structure is a three triple which can be denoted asN=V,E,Φ. V is the vertex set, and E is the edge set. Φ is the uncertainty measure matrix corresponding to an uncertain graph. It is simply called as a vertices structure uncertainty graph, where V and E determine the structure of the uncertain graph, and the uncertainty measure matrix Φ shows measures of vertices existing and measures of edges existing to connect these uncertain vertices in the graph.
For more intuitively understanding the edge structure uncertainty graph and the vertices structure uncertainty graph, Figure1 gives a simple uncertain graph for vertices A, B, and C and edges AB, AC, and BC.
In Figure1(a), if vertex O exists in an uncertainty measure M, then edges OA, OB, and OC must exist with uncertainty measures. Assuming that the edges OA, OB, and OC exist with the uncertainty measures Ma,Mb,andMc, respectively, and 0≤Ma,Mb,Mc,M≤1, then the uncertainty measure matrix corresponding to this graph satisfies the following:(2)Φ=111Ma111Mb111McMaMbMcM.
In Figure1(b), if vertex O exists (that is, M=1), but edges OA, OB, and OC exist with uncertainty measures Ma,Mb,andMc, respectively, then the uncertainty measure matrix corresponding to this graph satisfies the following:(3)Φ=111Ma111Mb111McMaMbMc1.
If vertex O does not exist (that is,M=0), then edges OA, OB, and OC must not exist, and then the uncertainty measure matrix corresponding to this graph satisfies the following:(4)Φ=1110111011100000.
Comparing the above three uncertainty measure matrices (2)–(4), we observe that matrices (3) and (4) are the special cases of matrix (2). Thus, the concept of vertices structure uncertainty graph proposed by us extends the concepts of the existing graphs, which may depict the concepts such as graph, probability graph, fuzzy graph, and uncertain graph.Figure 1
Two uncertain graphs with uncertain structure. (a) The vertex O exists in a measure. (b) The vertex O must exist and OA, OB, and OC must exist with a measure.
(a)
(b)


## 2.1. Uncertainty Measure

LetΓ be a nonempty set and ℒ be a σ− algebra over Γ. Each element Λ in ℒ is called an event. The set function M is called an uncertain measure if it satisfies the following three axioms [20, 21].Axiom 1 normality.
M
Γ
=
1.Axiom 2 self-duality.
M
Λ
+
M
Λ
c
=
1 for any event Λ.Axiom 3 subadditivity.
For every countable sequence of eventsΛii=1+∞, we have(1)M∪i=1∞Λi≤∑i=1∞MΛi.
The tripletΓ,L,M is called an uncertainty space. Uncertainty measure is interpreted as the personal belief degree (not frequency) of an uncertain event that may happen. Thus, uncertainty measure and belief degree are synonymous. Uncertainty measure depends on the personal knowledge concerning the event. It will change if the state of knowledge changes. In other words, it may be understood simply as a probability Pr in a random environment, or a credibility measure Cr in the fuzzy environment, or a trust value Tr in the rough environment.


## 2.2. Vertices Structure Uncertainty Graph

The definition of an uncertain graph was first proposed by Gao and Gao [22] in 2013. But their definition assumed that the vertices in the graph are predetermined. Therefore, their definition may be considered as only applying to a special uncertain graph whose edges are not predetermined and whose existence possibility (reliability) of each edge is described by uncertain measures. It is called as the edge structure uncertainty graph by us. By analogy of its definition and the idea of adjacent matrix representing graph, we present definitions of uncertainty measure matrix and vertices structure uncertainty graph as follows.Definition 1.
The graph with uncertain vertices structure uniquely corresponds to an uncertainty measure matrixΦ=ϕijn×n if and only if ϕij satisfies the following:(1)
Wheni=j, ϕii=Mvi=1 represents the uncertainty measure of vertex vi existence, which is simply denoted as ϕi(2)
Wheni≠j, ϕij=Mvivj=1 represents the uncertainty measure of the edge connecting vertex vi and vertex vjwherevi=1 indicates that vertex i exists, vi=0 indicates that vertex i does not exist, vivj=1 indicates that the edge connecting vertices i and j exists, and vivj=0 indicates that the edge connecting vertices i and j does not exist.
Based on the uncertainty measure matrix and the definition of the edge structure uncertainty graph, we propose a definition of the vertices structure uncertainty graph as follows.Definition 2.
The graph with uncertain vertices structure is a three triple which can be denoted asN=V,E,Φ. V is the vertex set, and E is the edge set. Φ is the uncertainty measure matrix corresponding to an uncertain graph. It is simply called as a vertices structure uncertainty graph, where V and E determine the structure of the uncertain graph, and the uncertainty measure matrix Φ shows measures of vertices existing and measures of edges existing to connect these uncertain vertices in the graph.
For more intuitively understanding the edge structure uncertainty graph and the vertices structure uncertainty graph, Figure1 gives a simple uncertain graph for vertices A, B, and C and edges AB, AC, and BC.
In Figure1(a), if vertex O exists in an uncertainty measure M, then edges OA, OB, and OC must exist with uncertainty measures. Assuming that the edges OA, OB, and OC exist with the uncertainty measures Ma,Mb,andMc, respectively, and 0≤Ma,Mb,Mc,M≤1, then the uncertainty measure matrix corresponding to this graph satisfies the following:(2)Φ=111Ma111Mb111McMaMbMcM.
In Figure1(b), if vertex O exists (that is, M=1), but edges OA, OB, and OC exist with uncertainty measures Ma,Mb,andMc, respectively, then the uncertainty measure matrix corresponding to this graph satisfies the following:(3)Φ=111Ma111Mb111McMaMbMc1.
If vertex O does not exist (that is,M=0), then edges OA, OB, and OC must not exist, and then the uncertainty measure matrix corresponding to this graph satisfies the following:(4)Φ=1110111011100000.
Comparing the above three uncertainty measure matrices (2)–(4), we observe that matrices (3) and (4) are the special cases of matrix (2). Thus, the concept of vertices structure uncertainty graph proposed by us extends the concepts of the existing graphs, which may depict the concepts such as graph, probability graph, fuzzy graph, and uncertain graph.Figure 1
Two uncertain graphs with uncertain structure. (a) The vertex O exists in a measure. (b) The vertex O must exist and OA, OB, and OC must exist with a measure.
(a)
(b)


## 3. Vertices Structure Uncertainty Graph Based on the Uncertainty of Logistics Nodes

### 3.1. Uncertainty Measure on the Existence of Logistics Nodes

When designing an ULS, the construction of logistics nodes on an area usually adopts location planning to make a preliminary determination [11–18]. The ULS has the characteristics of high cost and high risk as well as difficult improving. Especially, the impact of each logistics node on the whole logistics system is different. Thus, it is necessary to analyze and compute the key degree of each logistics node in the dynamic programming of an ULS network.Let there ben alternative logistics nodes in an ULS. Based on the impact degree of no-constructing logistics node i on the whole logistics network, we present using the impact degree to depict the key degree of logistics node i. Let U0 be the cost index of all logistics nodes operating normally (no interruption) and Ui be the cost index of the ith logistics node interrupting. The cost here could be the total freight volume, transportation cost, traffic congestion index, or construction cost of the ULS network. Thus, the key degree Mi of the ith logistics node may be computed by using the following formula:(5)Mi=Ui−U0U0,where Mi=0 (Ui=U0, i∈1,2,…,n) means that the interruption of the ith logistics node has no effect on the whole network; that is, the ith logistics node is not important in the whole network. The bigger the Mi is, the more critical the ith logistics node is.From the point of view of graph theory, the key degree of each logistics node decides the possibility of the corresponding vertex (logistics node) existence in the ULS. That is, the uncertainty measure of vertex existence is different.The bigger the key degree is, the bigger the possibility of the vertex existence is, and vice versa. By standardization key degreeMi, the ith vertex uncertainty measure can be obtained according to the following formula:(6)ϕi=Mi−mini∈1,2,…,nMimaxi∈1,2,…,nMi−mini∈1,2,…,nMi×100%.


### 3.2. Uncertainty Measure of the Edge Connecting Two Logistics Nodes

In an ULS network, if a logistics node does not exist, then the edges connecting it must not exist. According to this phenomenon, the uncertainty of an edge (route) may be depicted by using the freight volume.Ifhij represents the freight volume of from logistics node i to logistics node j, then the uncertainty measure of the edge connecting vertices i and j may defined as follows:(7)ϕij=hij−mini,j∈1,2,⋯nhijmaxi,j∈1,2,…,nhij−mini,j∈1,2,…,nhij×100%.


### 3.3. Vertices Structure Uncertainty Graph

According to definition 2 and Sections3.1 and 3.2, an ULS network may model as an uncertainty graph N=V,E,Φ. In which, logistics node i is taken as vertex vi (i∈1,2,…,n) of the graph, where n is the total number of logistics nodes, and the vertex set is denoted as V=v1,v2,…,vn; the transportation road (or tunnel) between vertex vi and vertex vj is taken as an edge ek (k∈1,2,…,m) of the graph, where m is the total number of edges of the graph, and the edge set of the graph is denoted as E=e1,e2,…,em; uncertainty measure matrix Φ=ϕijn×n, when i=j, ϕii=ϕi, and it may be computed by using formula (6); when i≠j, ϕij may be computed by using formula (7). Thus, a schematic diagram on logistics nodes of vertices structure uncertainty graph is shown in Figure 2.Figure 2
Schematic diagram on logistics nodes of vertices structure uncertainty graph.In Figure2, numbers on vertices and edges represent uncertainty measures for logistics nodes and transportation roads (or tunnels) in the ULS, which can be calculated by using formulas (6) and (7), respectively. The number 1.0 at vertices B, E, and D means that the effects of logistics nodes B, E, and D on the cost index of ULS are the same. Moreover, their effects are the greatest among the effects of logistics nodes on the cost index of the ULS. Therefore, logistics nodes B, E, and D must exist in the vertices structure uncertainty graph of the ULS. The numbers 0.5 and 0.7 at nodes A and C mean that they are less important than nodes B, E, and D, and the possibilities of their existing in the vertices structure uncertainty graph of ULS are 0.5 and 0.7, respectively. The numbers 0.7, 0.2, and 0.3 on edges BA, AC, and BC mean that the possibilities of building transport roads (or tunnels) BA, AC, and BC between nodes B, A, and C are 0.7, 0.2, and 0.3, respectively; the number 1.0 on edges BE and DB means that transport roads (or tunnels) BE and DB must be built between nodes B, D, and E, while the number 0.4 on edge DE means that the possibility of building transport road (or tunnel) DE between nodes D and E is only 0.4.


## 3.1. Uncertainty Measure on the Existence of Logistics Nodes

When designing an ULS, the construction of logistics nodes on an area usually adopts location planning to make a preliminary determination [11–18]. The ULS has the characteristics of high cost and high risk as well as difficult improving. Especially, the impact of each logistics node on the whole logistics system is different. Thus, it is necessary to analyze and compute the key degree of each logistics node in the dynamic programming of an ULS network.Let there ben alternative logistics nodes in an ULS. Based on the impact degree of no-constructing logistics node i on the whole logistics network, we present using the impact degree to depict the key degree of logistics node i. Let U0 be the cost index of all logistics nodes operating normally (no interruption) and Ui be the cost index of the ith logistics node interrupting. The cost here could be the total freight volume, transportation cost, traffic congestion index, or construction cost of the ULS network. Thus, the key degree Mi of the ith logistics node may be computed by using the following formula:(5)Mi=Ui−U0U0,where Mi=0 (Ui=U0, i∈1,2,…,n) means that the interruption of the ith logistics node has no effect on the whole network; that is, the ith logistics node is not important in the whole network. The bigger the Mi is, the more critical the ith logistics node is.From the point of view of graph theory, the key degree of each logistics node decides the possibility of the corresponding vertex (logistics node) existence in the ULS. That is, the uncertainty measure of vertex existence is different.The bigger the key degree is, the bigger the possibility of the vertex existence is, and vice versa. By standardization key degreeMi, the ith vertex uncertainty measure can be obtained according to the following formula:(6)ϕi=Mi−mini∈1,2,…,nMimaxi∈1,2,…,nMi−mini∈1,2,…,nMi×100%.


## 3.2. Uncertainty Measure of the Edge Connecting Two Logistics Nodes

In an ULS network, if a logistics node does not exist, then the edges connecting it must not exist. According to this phenomenon, the uncertainty of an edge (route) may be depicted by using the freight volume.Ifhij represents the freight volume of from logistics node i to logistics node j, then the uncertainty measure of the edge connecting vertices i and j may defined as follows:(7)ϕij=hij−mini,j∈1,2,⋯nhijmaxi,j∈1,2,…,nhij−mini,j∈1,2,…,nhij×100%.


## 3.3. Vertices Structure Uncertainty Graph

According to definition 2 and Sections3.1 and 3.2, an ULS network may model as an uncertainty graph N=V,E,Φ. In which, logistics node i is taken as vertex vi (i∈1,2,…,n) of the graph, where n is the total number of logistics nodes, and the vertex set is denoted as V=v1,v2,…,vn; the transportation road (or tunnel) between vertex vi and vertex vj is taken as an edge ek (k∈1,2,…,m) of the graph, where m is the total number of edges of the graph, and the edge set of the graph is denoted as E=e1,e2,…,em; uncertainty measure matrix Φ=ϕijn×n, when i=j, ϕii=ϕi, and it may be computed by using formula (6); when i≠j, ϕij may be computed by using formula (7). Thus, a schematic diagram on logistics nodes of vertices structure uncertainty graph is shown in Figure 2.Figure 2
Schematic diagram on logistics nodes of vertices structure uncertainty graph.In Figure2, numbers on vertices and edges represent uncertainty measures for logistics nodes and transportation roads (or tunnels) in the ULS, which can be calculated by using formulas (6) and (7), respectively. The number 1.0 at vertices B, E, and D means that the effects of logistics nodes B, E, and D on the cost index of ULS are the same. Moreover, their effects are the greatest among the effects of logistics nodes on the cost index of the ULS. Therefore, logistics nodes B, E, and D must exist in the vertices structure uncertainty graph of the ULS. The numbers 0.5 and 0.7 at nodes A and C mean that they are less important than nodes B, E, and D, and the possibilities of their existing in the vertices structure uncertainty graph of ULS are 0.5 and 0.7, respectively. The numbers 0.7, 0.2, and 0.3 on edges BA, AC, and BC mean that the possibilities of building transport roads (or tunnels) BA, AC, and BC between nodes B, A, and C are 0.7, 0.2, and 0.3, respectively; the number 1.0 on edges BE and DB means that transport roads (or tunnels) BE and DB must be built between nodes B, D, and E, while the number 0.4 on edge DE means that the possibility of building transport road (or tunnel) DE between nodes D and E is only 0.4.


## 4. Dynamic Programming Model of ULS Network Construction

In view of the above analysis in Section3, we may establish a dynamic programming model of the ULS network construction to obtain its schedule and dynamic evolution process. Let an ULS have n logistics nodes and m tunnels. Then, it may model as an uncertainty graph with n vertices and m edges based on the vertices structure uncertainty graph. During the process of construction, it usually needs to be completed in r years. If the total route length of the ULS is Dtotal, then the tunnel (route) length to be built in every year is Dwish=Dtotal/r. Therefore, construction process in a year may be analyzed as follows:(1)
Number the logistic nodes according to the decreasing order of their uncertainty measuresϕi,i=1,2,…,n(2)
Schedule the ULS network routes to be constructed in the order of1,2,…,m based on the vertices structure uncertainty graph; that is, the ULS network has m edges(3)
Establish dynamic programming model


### 4.1. Set Variables

Let a route be built at each stage. Then, we may set the following variables:k: stage variable k∈1,2,…,m.dk: the length of the kth route, as the distance of edge BC is 5 km in Figure 3.ck: the value of the kth route connecting vertices vi and vj; that is, the uncertain measure ϕij of edge ek existing, as an example ck=0.3 means the uncertain measure of edge BC existing in Figure 3.Sk+1: the total length of previous k routes (tunnels) allowed to be constructed in the ULS network at the beginning of the kth stage, where S1=0.xk: whether the kth route is built or not, where xk=0 means that it is not built and xk=1 means that it is built.Figure 3
A graphic description that graphically explains what different variables represent.
(a)
(b)


### 4.2. State Transfer Functions

Because the total length of previousk − 1 routes (tunnels) allowed to be constructed before the kth stage is Sk, the length of the tunnel constructed in the kth stage is dk⋅xk, and the total length of previous k routes (tunnels) allowed to be constructed in the ULS network at the beginning of the kth stage Sk+1=Sk+dk⋅xk. Then, the state transfer equation of the total length of the tunnel allowed to be constructed is as follows:(8)Sk=Sk+1−dk⋅xk,k=1,2,…,m.A graphic description that graphically explains what different variables represent can be seen in Figure3. Figure 3(a) shows that the total length of a tunnel allowed to be constructed before the beginning of stage 1 is S1=0. The length of tunnel BD constructed in the first stage is 7, so the total length of previous 1 tunnel allowed to be constructed at the beginning of the first stage is S2=S1+d1⋅x1=0+7×1=7. Figure 3(b) shows that the length of a tunnel allowed to be constructed before the beginning of stage 2 is S2=7. The length of tunnel BE constructed in the second stage is 6, so the total length of previous 2 tunnels allowed to be constructed at the beginning of the second stage is S3=S2+d2⋅x2=7+6×1=13.


### 4.3. Fundamental Equation

Assuming thatfkSk+1 represents the maximum value that the total length of being allowed construction routes is less than Sk+1, only previous k routes are built by optimal strategy. Then, the sequential recursion relation is as follows:(9)fkSk+1=max0≤dkxk≤Sk+1ckxk+fk−1Sk+1−dkxk,k=1,2,…,m,f0S1=0.For more easy calculation, equation (9) is transformed into the following recursion relation formula:(10)fkSk+1=max0≤xk≤Sk+1/dekckxk+fk−1Sk+1−dkxk,k=1,2,…,m,f0S1=0.Through calculating by the recursion relation equation (10) in sequence, the optimal result of construction routes can be obtained.


## 4.1. Set Variables

Let a route be built at each stage. Then, we may set the following variables:k: stage variable k∈1,2,…,m.dk: the length of the kth route, as the distance of edge BC is 5 km in Figure 3.ck: the value of the kth route connecting vertices vi and vj; that is, the uncertain measure ϕij of edge ek existing, as an example ck=0.3 means the uncertain measure of edge BC existing in Figure 3.Sk+1: the total length of previous k routes (tunnels) allowed to be constructed in the ULS network at the beginning of the kth stage, where S1=0.xk: whether the kth route is built or not, where xk=0 means that it is not built and xk=1 means that it is built.Figure 3
A graphic description that graphically explains what different variables represent.
(a)
(b)


## 4.2. State Transfer Functions

Because the total length of previousk − 1 routes (tunnels) allowed to be constructed before the kth stage is Sk, the length of the tunnel constructed in the kth stage is dk⋅xk, and the total length of previous k routes (tunnels) allowed to be constructed in the ULS network at the beginning of the kth stage Sk+1=Sk+dk⋅xk. Then, the state transfer equation of the total length of the tunnel allowed to be constructed is as follows:(8)Sk=Sk+1−dk⋅xk,k=1,2,…,m.A graphic description that graphically explains what different variables represent can be seen in Figure3. Figure 3(a) shows that the total length of a tunnel allowed to be constructed before the beginning of stage 1 is S1=0. The length of tunnel BD constructed in the first stage is 7, so the total length of previous 1 tunnel allowed to be constructed at the beginning of the first stage is S2=S1+d1⋅x1=0+7×1=7. Figure 3(b) shows that the length of a tunnel allowed to be constructed before the beginning of stage 2 is S2=7. The length of tunnel BE constructed in the second stage is 6, so the total length of previous 2 tunnels allowed to be constructed at the beginning of the second stage is S3=S2+d2⋅x2=7+6×1=13.


## 4.3. Fundamental Equation

Assuming thatfkSk+1 represents the maximum value that the total length of being allowed construction routes is less than Sk+1, only previous k routes are built by optimal strategy. Then, the sequential recursion relation is as follows:(9)fkSk+1=max0≤dkxk≤Sk+1ckxk+fk−1Sk+1−dkxk,k=1,2,…,m,f0S1=0.For more easy calculation, equation (9) is transformed into the following recursion relation formula:(10)fkSk+1=max0≤xk≤Sk+1/dekckxk+fk−1Sk+1−dkxk,k=1,2,…,m,f0S1=0.Through calculating by the recursion relation equation (10) in sequence, the optimal result of construction routes can be obtained.


## 5. A Dynamic Programming Algorithm for ULS Construction Based on Simulated Annealing Algorithm

The idea of original simulated annealing (SA) algorithm comes from the physical annealing process [19, 26]. It is often used to solve the problem of combinatorial optimization. Obviously, the problem of ULS construction planning is a combinatorial optimization problem with uncertain measures based on Section 4. Therefore, we present an improving SA to solve the problem of ULS construction project.


### 5.1. The Idea of Improving SA Algorithm

The idea is first to compute the uncertainty measures on logistics nodes and transportation roads (tunnels) connecting logistics nodes to establish the network road of ULS with the vertices structure uncertainty graph and then to use solid annealing to simulate the combinatorial optimization problem [27, 28], which is as follows.Firstly, according to the cost index of each logistics node and the existing freight volume in logistics system, the uncertainty measures of logistics nodes and transportation roads (tunnels) between logistics nodes are computed. Based on these, the network road of the ULS with the vertices structure uncertainty graph is established.Then, in order to get the transportation road (tunnel) construction process, priority should be given to the establishment of key logistics nodes and key tunnels associated with key logistics nodes on the basis of the different degrees of impact of each node on the whole logistics system and the different demands of freight volume on each transportation road (tunnel).Secondly, when the critical degree of logistics nodes is the same, priority should be given to the construction of transportation roads (tunnels) with larger freight volume.Comparing it with the original simulated annealing algorithm, the differences lie in the process of judging the generation and acceptance of new solutions. Firstly, the uncertainty measures of vertices and edges are calculated, and the edges associated with the vertices having larger uncertainty measures are selected as candidate sets. Then, the uncertainty measures on the edges of candidate sets are judged. Secondly, in simulating internal energyE, the computation of E being taken as objective function value f, the value (freight volume) of the tunnels needs to be first calculated as the uncertain measures ϕij of the network roads of the ULS.


### 5.2. The Steps of Improving SA Algorithm

On the basis of the above idea and the algorithm of original SA, the concrete steps of the improving SA algorithm are as follows:Step 1: compute the uncertainty measures on logistics nodes and transportation roads (tunnels) connecting logistics nodes of the ULS with the vertices structure uncertainty graph.Step 2: number the logistic nodes according to the decreasing order of their uncertainty measuresϕi,i=1,2,…,n.Step 3: schedule the ULS network routes to be constructed in the order ofk=1,2,…,m based on the decreasing order of their uncertainty measures ϕij of the existing edge ek.Step 4: determine the solution spaceS=x1,x2,…,xm∑k=1mdkxk<Dwish, where each feasible solution is represented by using a binary string.Step 5: determine the internal energyE. The internal energy E is depicted as the objective function value f—the value (freight volume) of the tunnels; i.e., E=fx1,x2,…,xm=∑k=1mckxk, ck=ϕij.Step 6: let the initial temperaturet and initial solution x=x0.Step 7: generate a new solutionxt. A route edge (tunnel) x is first selected randomly. If it is not in the ULS that has been constructed, then it will allow to be constructed as a new solution x=xt. Otherwise, the next tunnel of x is chosen randomly as the edge xt; that is, a new solution is generated by choosing xt in the neighborhood of x.Step 8: internal circulation.(1)
Calculate objective function valuesE corresponding to x and xt. If the objective function value of xt is less than that of x, then stop and let x=xt. Otherwise, if exp−Ext−Ex/t>ε, where ε∈0,1 is a random number, then stop and let x=xt.(2)
When the stop condition in (1) is not satisfied, then updatet and repeat (1).Step 9: external circulation.(1)
Cool down according to equations (11)–(13).(2)
If the stop condition of external circulation is not satisfied, then go to Step 5. Otherwise, stop the algorithm, where the value differenceΔf and the length difference Δd in the edge of planning to be built tunnel in the ULS are satisfied, respectively:(11)Δf=ci,constructing theith tunnel during the period,ci−cj,constructing theith tunnel and not constructing thejth tunnel in the period,cj−ci,constructing thejth tunnel and not constructing theith tunnel during the period,(12)Δd=di,constructing theith tunnel during the period,di−dj,constructing theith tunnel and not constructing thejth tunnel in the period,dj−di,constructing thejth tunnel and not constructing theith tunnel during the period,(13)p=0,ifd+Δd>Dwish,1,ifd+Δd≤Dwish,andΔf>0,expΔf/tk,otherwise,Δ
d is the mileage increment of the total length of constructing the tunnels in the current planning. When planning to construct the tunnels, it is not known whether the tunnel will be built or not. Therefore, the extended metropolis criterion rule is used to compute p:
wheretk is the temperature control parameter.


### 5.3. The Flow Diagram of Improving SA Algorithm

The flow diagram of the improving SA algorithms can be seen in Figure4.Figure 4
The flow diagram of the improving SA algorithm.


## 5.1. The Idea of Improving SA Algorithm

The idea is first to compute the uncertainty measures on logistics nodes and transportation roads (tunnels) connecting logistics nodes to establish the network road of ULS with the vertices structure uncertainty graph and then to use solid annealing to simulate the combinatorial optimization problem [27, 28], which is as follows.Firstly, according to the cost index of each logistics node and the existing freight volume in logistics system, the uncertainty measures of logistics nodes and transportation roads (tunnels) between logistics nodes are computed. Based on these, the network road of the ULS with the vertices structure uncertainty graph is established.Then, in order to get the transportation road (tunnel) construction process, priority should be given to the establishment of key logistics nodes and key tunnels associated with key logistics nodes on the basis of the different degrees of impact of each node on the whole logistics system and the different demands of freight volume on each transportation road (tunnel).Secondly, when the critical degree of logistics nodes is the same, priority should be given to the construction of transportation roads (tunnels) with larger freight volume.Comparing it with the original simulated annealing algorithm, the differences lie in the process of judging the generation and acceptance of new solutions. Firstly, the uncertainty measures of vertices and edges are calculated, and the edges associated with the vertices having larger uncertainty measures are selected as candidate sets. Then, the uncertainty measures on the edges of candidate sets are judged. Secondly, in simulating internal energyE, the computation of E being taken as objective function value f, the value (freight volume) of the tunnels needs to be first calculated as the uncertain measures ϕij of the network roads of the ULS.


## 5.2. The Steps of Improving SA Algorithm

On the basis of the above idea and the algorithm of original SA, the concrete steps of the improving SA algorithm are as follows:Step 1: compute the uncertainty measures on logistics nodes and transportation roads (tunnels) connecting logistics nodes of the ULS with the vertices structure uncertainty graph.Step 2: number the logistic nodes according to the decreasing order of their uncertainty measuresϕi,i=1,2,…,n.Step 3: schedule the ULS network routes to be constructed in the order ofk=1,2,…,m based on the decreasing order of their uncertainty measures ϕij of the existing edge ek.Step 4: determine the solution spaceS=x1,x2,…,xm∑k=1mdkxk<Dwish, where each feasible solution is represented by using a binary string.Step 5: determine the internal energyE. The internal energy E is depicted as the objective function value f—the value (freight volume) of the tunnels; i.e., E=fx1,x2,…,xm=∑k=1mckxk, ck=ϕij.Step 6: let the initial temperaturet and initial solution x=x0.Step 7: generate a new solutionxt. A route edge (tunnel) x is first selected randomly. If it is not in the ULS that has been constructed, then it will allow to be constructed as a new solution x=xt. Otherwise, the next tunnel of x is chosen randomly as the edge xt; that is, a new solution is generated by choosing xt in the neighborhood of x.Step 8: internal circulation.(1)
Calculate objective function valuesE corresponding to x and xt. If the objective function value of xt is less than that of x, then stop and let x=xt. Otherwise, if exp−Ext−Ex/t>ε, where ε∈0,1 is a random number, then stop and let x=xt.(2)
When the stop condition in (1) is not satisfied, then updatet and repeat (1).Step 9: external circulation.(1)
Cool down according to equations (11)–(13).(2)
If the stop condition of external circulation is not satisfied, then go to Step 5. Otherwise, stop the algorithm, where the value differenceΔf and the length difference Δd in the edge of planning to be built tunnel in the ULS are satisfied, respectively:(11)Δf=ci,constructing theith tunnel during the period,ci−cj,constructing theith tunnel and not constructing thejth tunnel in the period,cj−ci,constructing thejth tunnel and not constructing theith tunnel during the period,(12)Δd=di,constructing theith tunnel during the period,di−dj,constructing theith tunnel and not constructing thejth tunnel in the period,dj−di,constructing thejth tunnel and not constructing theith tunnel during the period,(13)p=0,ifd+Δd>Dwish,1,ifd+Δd≤Dwish,andΔf>0,expΔf/tk,otherwise,Δ
d is the mileage increment of the total length of constructing the tunnels in the current planning. When planning to construct the tunnels, it is not known whether the tunnel will be built or not. Therefore, the extended metropolis criterion rule is used to compute p:
wheretk is the temperature control parameter.


## 5.3. The Flow Diagram of Improving SA Algorithm

The flow diagram of the improving SA algorithms can be seen in Figure4.Figure 4
The flow diagram of the improving SA algorithm.


## 6. Case Study

### 6.1. Problem

The ULS dynamic network programming method proposed in this paper is used to plan the optimal schedule of network route construction in Xianlin district, Nanjing city, based on the underground logistics system (ULS) mentioned in question F of the 14th “Huawei cup” China Postgraduate Mathematic Contest in Modelling in 2017. The network construction project of underground logistics system requires constructing 45 logistics nodes (the numbers 1–13 are the 1st level nodes; the numbers 14–45 are the 2nd level nodes) and 81 tunnels (the total length is 290 km) during the 8th year. Figure5 shows position distribution of logistics nodes at all levels; Table 1 gives the related data of the nodes and tunnels on the ULS.Figure 5
Position distribution of logistics nodes at all levels in Xianlin district.Table 1
The related data of logistics nodes.
Number
X position
Y position
Inflow
Outflow
1
148037.4
149443.9
1544.086
1528.184
2
145146.8
151489.6
11698.71
11064.55
3
140416.6
152146.1
14112.56
14103.54
4
149366.9
153648.1
9541.856
9226.744
5
144403.3
155930
10114.65
12104.62
6
137889.7
157781.7
8299.6
8540.79
7
141629.7
160163.7
6707.157
5996.62
8
148375.7
159294.3
7146.025
6914.614
9
150413.2
159364.7
10813.93
9715.012
10
155477.4
162651.1
6601.267
5761.77
11
158487.3
164413.4
6442.007
5625.619
12
169251.1
165333.2
153.939
252.769
13
163428
166293.4
6622.373
6225.333
14
141732.2
149908
2826.742
2689.738
15
145062.7
150092.6
2546.253
2431.514
16
139998.8
150082.7
2334.953
2429.127
17
149198.5
149918.9
2129.194
2057.143
18
143976.3
151159.2
1634.509
1524.001
19
144302.1
152239.5
964.361
865.667
20
140808.2
152432.5
3241.555
3426.522
21
139366.7
151652.6
2525.864
2662.456
22
142733.4
153099.6
2782.18
2505.738
23
147188.8
152823.2
4208.429
4041.365
24
140309.2
153473.8
2993.329
2710.818
25
144691
154317
2317.39
2754.09
26
147771.4
156163
2351.513
2176.283
27
149951.9
157738.3
4753.68
4090.284
28
137348.1
155938.5
4021.458
3672.704
29
136656.2
157553.6
1751.44
1809.175
30
139713.8
158198.1
2784.112
2434.092
31
142527.8
158313
3553.178
2896.085
32
135607.1
159148.9
1088.694
1851.249
33
144348.9
159828.8
987.691
966.32
34
139356.9
160405.2
2285.787
2269.248
35
145961.8
157814.7
1255.392
1330.97
36
147221.1
157904.4
3301.446
2454.303
37
150211.9
158547.6
4969.057
4677.888
38
146987.7
159418.2
4904.498
4855.147
39
149877.2
161091
859.515
884.769
40
154830.1
160255.1
4260.346
3322.93
41
153147
160216.5
2080.225
1882.86
42
164429.9
163490
2661.528
1977.437
43
158431.3
162322.4
2955.537
2692.746
44
165296
166307.5
967.672
1021.723
45
157354.7
166956.7
2378.161
1880.603


### 6.2. The Uncertainty Graph on Logistics Nodes

Using the method of formulating the vertices structure uncertainty graph based on the uncertainty of logistics nodes in Section3, the network road of the ULS with the vertices structure uncertainty graph is as shown in Figure 6.Figure 6
The network road of ULS.


### 6.3. The Construction Schedule and Dynamic Evolution Process of ULS Network Route

Based on the methods in Sections4 and 5, let parameters of the improving SA algorithm be as follows: cutoff temperature TF = 0.000001, annealing factor a = 0.9, initial temperature T = 100, and iterations res = 8100. By using the improving SA, we obtained the total number of tunnels to plan to be built and the corresponding serial numbers of tunnels, the actual total length network to plan to be completed, and the total freight volume in each year during 8 years, which can be seen in Table 2. Table 2 shows that the total length to be established in every year is roughly the same. The tunnel with bigger uncertainty measure of logistics nodes existing is always constructed in priority. That is, the relevant logistics nodes and tunnels with larger total freight volume are constructed in priority during the previous two years.Table 2
The relevant data tables for the tunnel construction in each year.
Total flow of freight transport
Total length of tunnels
Total number of tunnels
The number of constructed tunnels
First year
302.476
39.468
19
2, 5, 6, 25, 27, 29, 32, 35, 54, 60, 61, 64, 65, 68, 69, 71, 73, 75, 44
Second year
288.073
36.332
10
7, 13, 17, 22, 23, 38, 40, 47, 50, 81
Third year
110.929
36.550
10
1, 9, 11, 14, 20, 21, 24, 31, 37, 43
Fourth year
115.789
36.371
10
3, 4, 12, 15, 26, 30, 33, 36, 41, 45
Fifth year
121.275
36.829
9
8, 10, 19, 49, 52, 56, 53, 57, 59
Sixth year
127.338
35.346
7
16, 28, 42, 46, 77, 79, 80
Seventh year
133.705
36.967
9
18, 34, 39, 48, 51, 62, 63, 66, 67
Eighth year
144.786
32.137
7
55, 58, 70, 72, 74, 76, 78
Total
1344.371
290
81In addition, Figure7 gives the evolution process of the whole underground logistics network construction in this district. That is, it gives a schedule chart of tunnel construction that is actually built each year in 8 years.Figure 7
The evolution process of ULS construction. (a) First year. (b) Second year. (c) Third year. (d) Fourth year. (e) Fifth year. (f) Sixth year. (g) Seventh year. (h) Eighth year.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)It can be seen from Figure7 that the network built in every year is a block except the first year. It is because that the freight volume of each logistics node is also relatively large around the logistics node with large freight volume. Although the construction network in the first year seems to be scattered, it was found that most of the tunnels built in the first year are connected with the key logistics nodes. Because the key degree (the freight volume) is relatively large at the key logistics nodes, the key nodes should be given priority in the top layer design.


## 6.1. Problem

The ULS dynamic network programming method proposed in this paper is used to plan the optimal schedule of network route construction in Xianlin district, Nanjing city, based on the underground logistics system (ULS) mentioned in question F of the 14th “Huawei cup” China Postgraduate Mathematic Contest in Modelling in 2017. The network construction project of underground logistics system requires constructing 45 logistics nodes (the numbers 1–13 are the 1st level nodes; the numbers 14–45 are the 2nd level nodes) and 81 tunnels (the total length is 290 km) during the 8th year. Figure5 shows position distribution of logistics nodes at all levels; Table 1 gives the related data of the nodes and tunnels on the ULS.Figure 5
Position distribution of logistics nodes at all levels in Xianlin district.Table 1
The related data of logistics nodes.
Number
X position
Y position
Inflow
Outflow
1
148037.4
149443.9
1544.086
1528.184
2
145146.8
151489.6
11698.71
11064.55
3
140416.6
152146.1
14112.56
14103.54
4
149366.9
153648.1
9541.856
9226.744
5
144403.3
155930
10114.65
12104.62
6
137889.7
157781.7
8299.6
8540.79
7
141629.7
160163.7
6707.157
5996.62
8
148375.7
159294.3
7146.025
6914.614
9
150413.2
159364.7
10813.93
9715.012
10
155477.4
162651.1
6601.267
5761.77
11
158487.3
164413.4
6442.007
5625.619
12
169251.1
165333.2
153.939
252.769
13
163428
166293.4
6622.373
6225.333
14
141732.2
149908
2826.742
2689.738
15
145062.7
150092.6
2546.253
2431.514
16
139998.8
150082.7
2334.953
2429.127
17
149198.5
149918.9
2129.194
2057.143
18
143976.3
151159.2
1634.509
1524.001
19
144302.1
152239.5
964.361
865.667
20
140808.2
152432.5
3241.555
3426.522
21
139366.7
151652.6
2525.864
2662.456
22
142733.4
153099.6
2782.18
2505.738
23
147188.8
152823.2
4208.429
4041.365
24
140309.2
153473.8
2993.329
2710.818
25
144691
154317
2317.39
2754.09
26
147771.4
156163
2351.513
2176.283
27
149951.9
157738.3
4753.68
4090.284
28
137348.1
155938.5
4021.458
3672.704
29
136656.2
157553.6
1751.44
1809.175
30
139713.8
158198.1
2784.112
2434.092
31
142527.8
158313
3553.178
2896.085
32
135607.1
159148.9
1088.694
1851.249
33
144348.9
159828.8
987.691
966.32
34
139356.9
160405.2
2285.787
2269.248
35
145961.8
157814.7
1255.392
1330.97
36
147221.1
157904.4
3301.446
2454.303
37
150211.9
158547.6
4969.057
4677.888
38
146987.7
159418.2
4904.498
4855.147
39
149877.2
161091
859.515
884.769
40
154830.1
160255.1
4260.346
3322.93
41
153147
160216.5
2080.225
1882.86
42
164429.9
163490
2661.528
1977.437
43
158431.3
162322.4
2955.537
2692.746
44
165296
166307.5
967.672
1021.723
45
157354.7
166956.7
2378.161
1880.603


## 6.2. The Uncertainty Graph on Logistics Nodes

Using the method of formulating the vertices structure uncertainty graph based on the uncertainty of logistics nodes in Section3, the network road of the ULS with the vertices structure uncertainty graph is as shown in Figure 6.Figure 6
The network road of ULS.


## 6.3. The Construction Schedule and Dynamic Evolution Process of ULS Network Route

Based on the methods in Sections4 and 5, let parameters of the improving SA algorithm be as follows: cutoff temperature TF = 0.000001, annealing factor a = 0.9, initial temperature T = 100, and iterations res = 8100. By using the improving SA, we obtained the total number of tunnels to plan to be built and the corresponding serial numbers of tunnels, the actual total length network to plan to be completed, and the total freight volume in each year during 8 years, which can be seen in Table 2. Table 2 shows that the total length to be established in every year is roughly the same. The tunnel with bigger uncertainty measure of logistics nodes existing is always constructed in priority. That is, the relevant logistics nodes and tunnels with larger total freight volume are constructed in priority during the previous two years.Table 2
The relevant data tables for the tunnel construction in each year.
Total flow of freight transport
Total length of tunnels
Total number of tunnels
The number of constructed tunnels
First year
302.476
39.468
19
2, 5, 6, 25, 27, 29, 32, 35, 54, 60, 61, 64, 65, 68, 69, 71, 73, 75, 44
Second year
288.073
36.332
10
7, 13, 17, 22, 23, 38, 40, 47, 50, 81
Third year
110.929
36.550
10
1, 9, 11, 14, 20, 21, 24, 31, 37, 43
Fourth year
115.789
36.371
10
3, 4, 12, 15, 26, 30, 33, 36, 41, 45
Fifth year
121.275
36.829
9
8, 10, 19, 49, 52, 56, 53, 57, 59
Sixth year
127.338
35.346
7
16, 28, 42, 46, 77, 79, 80
Seventh year
133.705
36.967
9
18, 34, 39, 48, 51, 62, 63, 66, 67
Eighth year
144.786
32.137
7
55, 58, 70, 72, 74, 76, 78
Total
1344.371
290
81In addition, Figure7 gives the evolution process of the whole underground logistics network construction in this district. That is, it gives a schedule chart of tunnel construction that is actually built each year in 8 years.Figure 7
The evolution process of ULS construction. (a) First year. (b) Second year. (c) Third year. (d) Fourth year. (e) Fifth year. (f) Sixth year. (g) Seventh year. (h) Eighth year.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)It can be seen from Figure7 that the network built in every year is a block except the first year. It is because that the freight volume of each logistics node is also relatively large around the logistics node with large freight volume. Although the construction network in the first year seems to be scattered, it was found that most of the tunnels built in the first year are connected with the key logistics nodes. Because the key degree (the freight volume) is relatively large at the key logistics nodes, the key nodes should be given priority in the top layer design.


## 7. Conclusion

For the ULS being a new type of efficient transportation system, the route construction planning of the ULS network is essentially a key step of constructing ULS. Because the dynamic network planning of the ULS is a complex problem, we used comprehensively the graph theory, optimization theory, uncertain programming, dynamic optimization model, and simulated annealing algorithm to study it. After the relevant information of ground freight traffic is available, firstly, the influence degree of a logistics node interruption on the whole logistics network is used to depict the key degree of the logistics node, and it formulates the uncertainty measure of the logistics node. For the bigger the freight volume is, the bigger the possibility of the edge existence is; thus, the freight volume is used to express the uncertainty measure of edge connecting two logistics nodes. Secondly, a vertices structure uncertainty graph is formulated. Finally, a dynamic programming model of the ULS network construction is made, and an improving simulated annealing algorithm is designed to solve dynamic network optimization and the schedule problem of the ULS construction. The optimal time process of the network route construction in Xianlin district, Nanjing, China, shows that the ideas and methods proposed in this paper are correct and feasible. The established programming model and the design algorithm are effective and reliable for solving the network optimization of the ULS.About the route construction planning of the ULS network, we only study its dynamic network programming of the ULS with uncertain logistics nodes. It has still many problems worth studying, such as uncertain programming model of its route based on expected-value model, chance-constrained programming, and dependent-chance programming; network layout based on linear graph, ring graph, and grid graph; and its programming problem of considering more comprehensive uncertainty factor.



---

*Source: 1979275-2019-10-23.xml*