# Application of Hierarchical Facility Location-Routing Problem with Optimization of an Underground Logistic System: A Case Study in China

Authors: Yingpeng Hu; Kaixi Zhang; Jing Yang; Yanghui Wu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Facility location problem (FLP) and vehicle routing problem (VRP) are two of the most challenging issues in logistics. This paper presents an exploration of the multinode facility location-routing problem with realistic conditions. The disposal centers, transfer stations, connected collection sites, and unconnected collection sites are built into a new hierarchical model which is solved by Generate Algorithm (GA). Model costs include node construction cost, pipeline construction cost, transport cost, and transfer cost. This paper considers that the transportation is a bidirectional flow not a single flow; each pairs node in the area needs transportation; the dynamic routing selection method is used to determine the routes of unconnected collection sites. FLP and VRP can be both solved in this model. To illustrate the applicability of the model, a case study is presented and the results are discussed. The model in this paper can reduce the cost of the traditional underground logistics system by 6%~8% in experiments.


---

## Body

## 1. Introduction

The convenience of online consumption has significantly prompted the development of the logistics industry, but the accompanying cost and time concerns had attracted great attention due to the traffic congestion in cities. Accordingly, the future logistics system will gradually shift to the underground, forming an underground logistics system (ULS) [1]. Developed countries such as the Netherlands, the United States, Japan, the United Kingdom, and Germany have initially built ULS. Figure 1 shows the Cargo Cap in Germany.Figure 1
Cargo Cap in Germany.Logistic companies wish to reduce the overall cost of locating facilities and delivering goods. Instead of solving problems independently and combining their solutions, it is naturally better for such companies to consider problems in an integrated way because decisions can be taken simultaneously benefiting the overall cost minimization. In this sense, the location-routing problem (LRP) can be perfectly suitable for the ULS.LRP is a combination of two NP-hard optimization problems [2, 3] which are facility location problem (FLP) [4] and vehicle routing problem (VRP) [5]. It is necessary to define, at a minimum cost, where to open facilities (depots, factories, warehouses, etc.) for serving customers’ demands in the FLP, while it is necessary to determine routes of an overall minimum cost, which depart from a single facility for serving customers’ demands in the VRP. Both objectives must be met, resulting in the overall minimum cost related to locating facilities and determining vehicle routes departing from these facilities to meet customers’ demands in the LRP.FLP has been widely researched. Aikens [6] proposed nine basic location models, including a simple location model, a capacity-limited location model, a demand-changing location model, and a dynamic location model, which were solved by using the Dantzig-Wolfe decomposition algorithm. The subgradient optimization method was used to accelerate the convergence of the above algorithms. Holmberg K [7] considered the location problem of nonlinear transportation costs and solves it by the branch and bound method. Steven J.E. and Russell D.M. [8] also established a location model that considered inventory factors and used heuristic algorithms to solve them. Basti and Sevkli [9] studied p-median FLP aiming to minimize the maximum distance between nodes and facilities. Wang F [10] has considered the robust FLP with penalties, aiming to serve only a specified fraction of the clients. Tran T H [11] introduced a large-scale neighborhood search procedure for solving the single-source capacitance FLP (SSCFLP).Many methods have also been proposed to solve VRP. Clarke and Wright [12] proposed the saving method by listing the savings between points and constructing the path of large to small according to the saving amount. It has the advantage of fast calculation speed, but there are uncombined points and the edge points are difficult to combine. The problem with the scanning method proposed by Gillett and Miller [13] has a good effect, but this is nonprogressive optimization. Vidal T [14] proposed unified hybrid genetic search metaheuristic relied on problem-independent unified local searches, genetic operators, and advanced diversity management methods. Extensive computational experiments demonstrated the remarkable performance of the method which matched or outperformed the current state-of-the-art problem-tailored algorithms. Lai M [15] presented a novel two-stage hybrid metaheuristic method of VRP. The first stage adopts improved ant colony optimization (IACO) to determine the minimum number of used vehicles. The second stage employs improved Tabu search to optimize the total travel cost, in which the initial solutions are obtained by IACO in the first stage.The studies mentioned above all address either FLP or VRP but not both. For an effective response to an emergency, the planning for these two disaster phases (location and routing) must be coordinated, thus producing an LRP that aims to determine the locations of the depots while simultaneously determining dispatch routes. Location-routing models have been studied by many researchers since the late 1980s. Early LRP was considered in deterministic environments [16–18]. Stochastic location-routing models were subsequently studied by scholars. Toro-Díaz [19] developed a mathematical model for the LRP of emergency medical services with the objective of minimizing the response time and maximizing coverage. Caunhye [20] proposed a two-stage location-routing model with random demands. They solved the model by converting it into a single-stage counterpart. Gao [21] introduced an ant colony algorithm to solve the LRP of dynamic environments consisting of random and cyclic traffic factors. In past years, several other studies on LRP at random environments have been developed, such as Chan [22], Zhu [23], and Marinakis [24].In this paper, we presented a four-level model (disposal center, transfer station, connected collection sites, and unconnected collection sites) to minimize the cost of the underground logistics system instead of the traditional three-level model (disposal center, transfer station, and collection sites). Meanwhile, the model we proposed can solve FLP and VRP both unlike the currently related research which can only solve them separately.The paper is further organized as follows. Section2 presents a brief review of some basic concepts, assumptions, and routing selection method. In Section 3, we formulate a multiobjective optimization model for the determinate phenomenon. Section 4 presented a compared model and the parameter of Generate Algorithm (GA). Section 5 provides experiments and results analysis. Finally, a brief conclusion and outlook for potentially future research are given in Section 6.


## 2. Preliminaries

This section introduces some fundamental concepts, basic assumptions, and routing selection method.Based on the existing research, the traditional underground logistics system first divided nodes into three parts which are logistics park nodes (disposal centers), primary nodes (transfer stations), and secondary nodes (collection sites). The logistics park (disposal center) first accepts the goods from the other areas and then transports the goods to the primary nodes (transfer stations) through the underground logistics pipeline after simple selection. The goods are transported through the underground logistics pipeline from primary nodes to secondary nodes (collection sites) after selection and transported to the customer by the secondary nodes. After solving the FLP, some methods are used to calculate the routes [12–15].In this paper, we first divided nodes into four parts which are logistics park nodes (disposal centers), primary nodes (transfer stations), secondary nodes (connected collection sites), and tertiary nodes (unconnected collection sites). The first two nodes are the same as the traditional underground logistics system, but when goods are transported to secondary nodes (connected collection sites) through underground pipe, they will be transported to tertiary nodes (unconnected collection sites) through ground transport system. After that, the routing will be decided by dynamic path selection method in Section2.2.


### 2.1. Assumptions

The model assumptions in this paper:( 1 ) Each basic node can be transformed into a primary node, secondary node, or a tertiary node, and the amount of freight and distance between each node (the distance considered in this paper is a straight-line distance) are all known.( 2 ) Different primary or secondary nodes have different cargo throughput capacity limits, and those limits are known.( 3 ) There are no hierarchies of the transport pipelines and the capacity of the pipeline restrictions is known.( 4 ) The construction costs of the primary and secondary nodes are known. the construction cost of pipeline is related to the length of pipeline regardless of the influence of the terrain or the like.( 5 ) Transport price of the goods are different from the underground and ground.( 6 ) The freight volume of two nodes are only allocated to the same transportation pipeline.( 7 ) The primary nodes and secondary nodes can only serve tertiary nodes within a radius.( 8 ) Goods within the region can be transported through all nodes.( 9 ) Price of processing and transshipment of goods for nodes are the same and known.


### 2.2. Dynamic Routing Selection Method

In the traditional ULS, all nodes are connected to underground pipe which is not necessary. In this paper, we divided secondary nodes into two parts based on whether being connected to underground pipe or not. In this way, we can use the ground transport system and reduce the construction cost of the underground pipelines and nodes; even the ground transportation cost is higher than underground transportation cost because of the waiting cost etc. The logistics underground network in this paper is shown in Figure2.Figure 2
The nodes graph in this paper.In this paper, the route of a tertiary node is not certain because it can use ground transport system with no limit. Therefore, we are using a dynamic routing selection method to decide the route. The reference sample is shown in Figure3.Figure 3
Sample routing selection.As shown in Figure3, the logistics park node F has cargo to be transported to the tertiary node C. There are two routes selection options:( 1 ) Cargo can be transported from the logistics park F through the underground pipeline FA to the primary node A, then from underground logistics pipeline AB to the secondary node B, and finally by ground to the tertiary node C.( 2 ) Cargo can be transported from the logistics park F through the underground pipeline FD to the primary node D and then transported by ground to the tertiary node C.Now, we set the tertiary nodeC as a secondary node and the underground pipes BC and DC actually exist. Therefore, we can use dijkstra algorithm to determine the shortest way of FC; let us call it FDC; and then we can calculate the transport cost of underground routing FC and ground routing DC separately. The determined formula is shown in Section 3.


## 2.1. Assumptions

The model assumptions in this paper:( 1 ) Each basic node can be transformed into a primary node, secondary node, or a tertiary node, and the amount of freight and distance between each node (the distance considered in this paper is a straight-line distance) are all known.( 2 ) Different primary or secondary nodes have different cargo throughput capacity limits, and those limits are known.( 3 ) There are no hierarchies of the transport pipelines and the capacity of the pipeline restrictions is known.( 4 ) The construction costs of the primary and secondary nodes are known. the construction cost of pipeline is related to the length of pipeline regardless of the influence of the terrain or the like.( 5 ) Transport price of the goods are different from the underground and ground.( 6 ) The freight volume of two nodes are only allocated to the same transportation pipeline.( 7 ) The primary nodes and secondary nodes can only serve tertiary nodes within a radius.( 8 ) Goods within the region can be transported through all nodes.( 9 ) Price of processing and transshipment of goods for nodes are the same and known.


## 2.2. Dynamic Routing Selection Method

In the traditional ULS, all nodes are connected to underground pipe which is not necessary. In this paper, we divided secondary nodes into two parts based on whether being connected to underground pipe or not. In this way, we can use the ground transport system and reduce the construction cost of the underground pipelines and nodes; even the ground transportation cost is higher than underground transportation cost because of the waiting cost etc. The logistics underground network in this paper is shown in Figure2.Figure 2
The nodes graph in this paper.In this paper, the route of a tertiary node is not certain because it can use ground transport system with no limit. Therefore, we are using a dynamic routing selection method to decide the route. The reference sample is shown in Figure3.Figure 3
Sample routing selection.As shown in Figure3, the logistics park node F has cargo to be transported to the tertiary node C. There are two routes selection options:( 1 ) Cargo can be transported from the logistics park F through the underground pipeline FA to the primary node A, then from underground logistics pipeline AB to the secondary node B, and finally by ground to the tertiary node C.( 2 ) Cargo can be transported from the logistics park F through the underground pipeline FD to the primary node D and then transported by ground to the tertiary node C.Now, we set the tertiary nodeC as a secondary node and the underground pipes BC and DC actually exist. Therefore, we can use dijkstra algorithm to determine the shortest way of FC; let us call it FDC; and then we can calculate the transport cost of underground routing FC and ground routing DC separately. The determined formula is shown in Section 3.


## 3. Problem Description

In this paper, the goals of our problem are(1) to determine the subset of nodes and (2) to plan the routes from logistics park to other nodes.


### 3.1. Notations and Definitions

Let us first introduce the notations and decision variables that will be used to model the problem.Indices i = 1,2 , ⋯ , m: Logistics park i = m + 1 , ⋯ , m + n: Basic nodes.Parameters a 1: Daily depreciation cost for a single primary node a 2: Daily depreciation cost for a single secondary node a 3: Daily depreciation cost per kilometer pipeline a 4: Underground transport cost per ton per kilometer a 5: Ground transport cost per ton per kilometer a 6: Cost of transit services per ton of cargo transshipment r: The serving range u: The capacity limits of the pipe v 1: The throughput capacity limits of the primary node v 2: The throughput capacity limits of the secondary node.Decision Variables and Decision Vectors Q = 1 , ⋯ , m , m + 1 , ⋯ , m + n: All nodes set Q 1: Nodes set of primary nodes Q 2: Nodes set of secondary nodes Q 12: Nodes set of primary and secondary nodes Q 23: Nodes set of secondary and tertiary nodes Q 3: Nodes set of tertiary nodes X: Path existence matrix x i j: 1 if the pipe between i and j exists, 0 otherwise, i,j∈Q S: Distance matrix H: Freight volume matrix D: Available distance existence matrix d i s t ( s i j ): The shortest path from i to j through S w 1: Node construction cost w 2: Pipeline construction cost w 3: Transportation cost w 4: Transfer cost.


### 3.2. Multiobjective Location-Routing Model

The objective function of this model is the total cost function which includes the node construction cost, the pipeline construction cost, the transport cost of the region, and transfer cost.


#### 3.2.1. Objective 1: Node Construction Cost

According to the path existence matrixX, if a certain node j is connected to a logistics park i, that is, ∑ixij≠0, i∈{1,⋯,m},j∈{m+1.⋯,m+n}, we can get Q1 and Q23.(1)Q1=j∣∑i=1mxij≠0,j∈m+1,⋯,m+nQ23=j∣∑i=1mxij=0,j∈m+1,⋯,m+n.It can be known that a tertiary node is not connected to any other nodes; that is, if ∑ixij≠0, i∈Q,j∈Q23, then the node j is a tertiary node, so we can get Q3 and Q2. (2)Q3=j∣∑ixij≠0,i∈Q,j∈Q23(3)Q2=Q23∖Q3After the numbers of Q1, Q2, and Q3 are all known, we can calculate the node construction cost using card(Q) which means the number of elements of set Q; that is,(4)w1=a1∗cardQ1+a2∗cardQ2.


#### 3.2.2. Objective 2: Pipeline Construction Cost

According to the available distance existence matrixD(D=X∗S) whose element dij(dij=sij∗xij) represents the straight-line distance from i to j, we can calculate the pipeline construction cost; that is, (5)w2=a3∗∑i=1m+n∑j=1m+ndij.


#### 3.2.3. Objective 3: Transport Cost

The transport cost consists of two parts: one is the transport cost of the node connected to the underground pipeline, and the other is the transport cost of the tertiary nodes.According to the node distance matrixD, we can determine the shortest distance and the transport order for nodes except Q3 through dijkstra algorithm. We can calculate the first part of the transportation cost as w30; that is, (6)w30=a4∗∑i∑jhij∙distdij,i∈Q∖Q3,j∈Q∖Q3.According to Section 2.2, for each node i of Q3, we set the routes whose distance between i and other nodes from Q12 is less than the existing serving range. That is, for each i from Q3, we have node distance matrix Liji.(7)liji=sij,sij≤r,i∈Q3,j∈Q12dij,dij≠0inf,dij=0According to the node distance matrixLiji, we can determine the shortest distance and transport order for the node i which is from Q3 through dijkstra algorithm. We set that order as i→f1ij→f2ij→⋯→ftij→j, so the underground transport distance is ∑i=1t-1Sfiijfi+1ij+Sftijj and the ground transport distance is Sif1ij, so we can calculate the second part w31; that is,(8)w31=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+Sftijj+a5∗Sif1ij,i∈Q3,j∈Q12.The routing may not be the same because the freight volumeshij and hji are not the same. The method we proposed is a dynamic routing selection method, so it is necessary to calculate the transport cost of nodes from Q12 to nodes of Q3. That means that we have another order j→f1ij→f2ij→⋯→ftij→i, and we can calculate the third part w32; that is,(9)w32=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+Sjf1ij+a5∗Sftiji,i∈Q3,j∈Q12.We have calculated the transport cost of nodes fromQ12 to Q12, Q12 to Q3, Q3 to Q12, and then we need to calculate the transport cost of nodes from Q3 to Q3.For the nodei from Q3 transport to another nodej which is from Q3, using the dynamic routing selection method; the order should be i→f1ij→f2ij→⋯→ftij→j, and we can calculate the last part; that is, (10)w33=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+a5∗Sftijj+Sif1ij,i∈Q3,j∈Q3 so the total transport cost can be calculated as (11)w3=w30+w31+w32+w33.


#### 3.2.4. Objective 4: Transfer Cost

According to Section3.2.3, we have determined all the routing order, so we can get the number of nodes of each routing as pij, so the transfer cost can be calculated; that is, (12)w4=a6∗∑i∑jhij∗pij-1,i,j∈Qso the objective function of this model is (13)min⁡w=w1+w2+w3+w4.


### 3.3. Constraints

( 1 ) The tertiary nodes must be within the service scope of a primary or secondary node; that is,(14)mini⁡sij≤r,i∈Q3,j∈Q∖Q3.( 2 ) The tertiary nodes are not connected to the underground pipelines; that is,(15)xij=0,i∈Q3,j∈Q.( 3 ) All secondary nodes belong to a primary node and form a set with the primary node. The secondary nodes in the set can only be connected to nodes in the set and are not connected to other similar sets of nodes; that is,(16)∑jxij=1,i∈Q2,j∈Q1(17)∑k∑jxij=0,k∈Q1,i∈j∣∑jxkj=1,j∈Q2∖i.(4) The cargo flow should be smaller than the pipe capacity limit u; that is, (18)xij∗hij≤u.(5) The total amount of goods of a secondary node’s own goods and the tertiary nodes served shall not exceed the node’s throughput capacity limit v1,v2,(19)∑jhij≤v1,i∈Q1,j∈j∣minj⁡sij≤r,j∈i,Q3∑jhij≤v2,i∈Q2,j∈j∣minj⁡sij≤r,j∈i,Q3


## 3.1. Notations and Definitions

Let us first introduce the notations and decision variables that will be used to model the problem.Indices i = 1,2 , ⋯ , m: Logistics park i = m + 1 , ⋯ , m + n: Basic nodes.Parameters a 1: Daily depreciation cost for a single primary node a 2: Daily depreciation cost for a single secondary node a 3: Daily depreciation cost per kilometer pipeline a 4: Underground transport cost per ton per kilometer a 5: Ground transport cost per ton per kilometer a 6: Cost of transit services per ton of cargo transshipment r: The serving range u: The capacity limits of the pipe v 1: The throughput capacity limits of the primary node v 2: The throughput capacity limits of the secondary node.Decision Variables and Decision Vectors Q = 1 , ⋯ , m , m + 1 , ⋯ , m + n: All nodes set Q 1: Nodes set of primary nodes Q 2: Nodes set of secondary nodes Q 12: Nodes set of primary and secondary nodes Q 23: Nodes set of secondary and tertiary nodes Q 3: Nodes set of tertiary nodes X: Path existence matrix x i j: 1 if the pipe between i and j exists, 0 otherwise, i,j∈Q S: Distance matrix H: Freight volume matrix D: Available distance existence matrix d i s t ( s i j ): The shortest path from i to j through S w 1: Node construction cost w 2: Pipeline construction cost w 3: Transportation cost w 4: Transfer cost.


## 3.2. Multiobjective Location-Routing Model

The objective function of this model is the total cost function which includes the node construction cost, the pipeline construction cost, the transport cost of the region, and transfer cost.


### 3.2.1. Objective 1: Node Construction Cost

According to the path existence matrixX, if a certain node j is connected to a logistics park i, that is, ∑ixij≠0, i∈{1,⋯,m},j∈{m+1.⋯,m+n}, we can get Q1 and Q23.(1)Q1=j∣∑i=1mxij≠0,j∈m+1,⋯,m+nQ23=j∣∑i=1mxij=0,j∈m+1,⋯,m+n.It can be known that a tertiary node is not connected to any other nodes; that is, if ∑ixij≠0, i∈Q,j∈Q23, then the node j is a tertiary node, so we can get Q3 and Q2. (2)Q3=j∣∑ixij≠0,i∈Q,j∈Q23(3)Q2=Q23∖Q3After the numbers of Q1, Q2, and Q3 are all known, we can calculate the node construction cost using card(Q) which means the number of elements of set Q; that is,(4)w1=a1∗cardQ1+a2∗cardQ2.


### 3.2.2. Objective 2: Pipeline Construction Cost

According to the available distance existence matrixD(D=X∗S) whose element dij(dij=sij∗xij) represents the straight-line distance from i to j, we can calculate the pipeline construction cost; that is, (5)w2=a3∗∑i=1m+n∑j=1m+ndij.


### 3.2.3. Objective 3: Transport Cost

The transport cost consists of two parts: one is the transport cost of the node connected to the underground pipeline, and the other is the transport cost of the tertiary nodes.According to the node distance matrixD, we can determine the shortest distance and the transport order for nodes except Q3 through dijkstra algorithm. We can calculate the first part of the transportation cost as w30; that is, (6)w30=a4∗∑i∑jhij∙distdij,i∈Q∖Q3,j∈Q∖Q3.According to Section 2.2, for each node i of Q3, we set the routes whose distance between i and other nodes from Q12 is less than the existing serving range. That is, for each i from Q3, we have node distance matrix Liji.(7)liji=sij,sij≤r,i∈Q3,j∈Q12dij,dij≠0inf,dij=0According to the node distance matrixLiji, we can determine the shortest distance and transport order for the node i which is from Q3 through dijkstra algorithm. We set that order as i→f1ij→f2ij→⋯→ftij→j, so the underground transport distance is ∑i=1t-1Sfiijfi+1ij+Sftijj and the ground transport distance is Sif1ij, so we can calculate the second part w31; that is,(8)w31=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+Sftijj+a5∗Sif1ij,i∈Q3,j∈Q12.The routing may not be the same because the freight volumeshij and hji are not the same. The method we proposed is a dynamic routing selection method, so it is necessary to calculate the transport cost of nodes from Q12 to nodes of Q3. That means that we have another order j→f1ij→f2ij→⋯→ftij→i, and we can calculate the third part w32; that is,(9)w32=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+Sjf1ij+a5∗Sftiji,i∈Q3,j∈Q12.We have calculated the transport cost of nodes fromQ12 to Q12, Q12 to Q3, Q3 to Q12, and then we need to calculate the transport cost of nodes from Q3 to Q3.For the nodei from Q3 transport to another nodej which is from Q3, using the dynamic routing selection method; the order should be i→f1ij→f2ij→⋯→ftij→j, and we can calculate the last part; that is, (10)w33=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+a5∗Sftijj+Sif1ij,i∈Q3,j∈Q3 so the total transport cost can be calculated as (11)w3=w30+w31+w32+w33.


### 3.2.4. Objective 4: Transfer Cost

According to Section3.2.3, we have determined all the routing order, so we can get the number of nodes of each routing as pij, so the transfer cost can be calculated; that is, (12)w4=a6∗∑i∑jhij∗pij-1,i,j∈Qso the objective function of this model is (13)min⁡w=w1+w2+w3+w4.


## 3.2.1. Objective 1: Node Construction Cost

According to the path existence matrixX, if a certain node j is connected to a logistics park i, that is, ∑ixij≠0, i∈{1,⋯,m},j∈{m+1.⋯,m+n}, we can get Q1 and Q23.(1)Q1=j∣∑i=1mxij≠0,j∈m+1,⋯,m+nQ23=j∣∑i=1mxij=0,j∈m+1,⋯,m+n.It can be known that a tertiary node is not connected to any other nodes; that is, if ∑ixij≠0, i∈Q,j∈Q23, then the node j is a tertiary node, so we can get Q3 and Q2. (2)Q3=j∣∑ixij≠0,i∈Q,j∈Q23(3)Q2=Q23∖Q3After the numbers of Q1, Q2, and Q3 are all known, we can calculate the node construction cost using card(Q) which means the number of elements of set Q; that is,(4)w1=a1∗cardQ1+a2∗cardQ2.


## 3.2.2. Objective 2: Pipeline Construction Cost

According to the available distance existence matrixD(D=X∗S) whose element dij(dij=sij∗xij) represents the straight-line distance from i to j, we can calculate the pipeline construction cost; that is, (5)w2=a3∗∑i=1m+n∑j=1m+ndij.


## 3.2.3. Objective 3: Transport Cost

The transport cost consists of two parts: one is the transport cost of the node connected to the underground pipeline, and the other is the transport cost of the tertiary nodes.According to the node distance matrixD, we can determine the shortest distance and the transport order for nodes except Q3 through dijkstra algorithm. We can calculate the first part of the transportation cost as w30; that is, (6)w30=a4∗∑i∑jhij∙distdij,i∈Q∖Q3,j∈Q∖Q3.According to Section 2.2, for each node i of Q3, we set the routes whose distance between i and other nodes from Q12 is less than the existing serving range. That is, for each i from Q3, we have node distance matrix Liji.(7)liji=sij,sij≤r,i∈Q3,j∈Q12dij,dij≠0inf,dij=0According to the node distance matrixLiji, we can determine the shortest distance and transport order for the node i which is from Q3 through dijkstra algorithm. We set that order as i→f1ij→f2ij→⋯→ftij→j, so the underground transport distance is ∑i=1t-1Sfiijfi+1ij+Sftijj and the ground transport distance is Sif1ij, so we can calculate the second part w31; that is,(8)w31=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+Sftijj+a5∗Sif1ij,i∈Q3,j∈Q12.The routing may not be the same because the freight volumeshij and hji are not the same. The method we proposed is a dynamic routing selection method, so it is necessary to calculate the transport cost of nodes from Q12 to nodes of Q3. That means that we have another order j→f1ij→f2ij→⋯→ftij→i, and we can calculate the third part w32; that is,(9)w32=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+Sjf1ij+a5∗Sftiji,i∈Q3,j∈Q12.We have calculated the transport cost of nodes fromQ12 to Q12, Q12 to Q3, Q3 to Q12, and then we need to calculate the transport cost of nodes from Q3 to Q3.For the nodei from Q3 transport to another nodej which is from Q3, using the dynamic routing selection method; the order should be i→f1ij→f2ij→⋯→ftij→j, and we can calculate the last part; that is, (10)w33=∑i∑jhij∗a4∗∑i=1t-1Sfiijfi+1ij+a5∗Sftijj+Sif1ij,i∈Q3,j∈Q3 so the total transport cost can be calculated as (11)w3=w30+w31+w32+w33.


## 3.2.4. Objective 4: Transfer Cost

According to Section3.2.3, we have determined all the routing order, so we can get the number of nodes of each routing as pij, so the transfer cost can be calculated; that is, (12)w4=a6∗∑i∑jhij∗pij-1,i,j∈Qso the objective function of this model is (13)min⁡w=w1+w2+w3+w4.


## 3.3. Constraints

( 1 ) The tertiary nodes must be within the service scope of a primary or secondary node; that is,(14)mini⁡sij≤r,i∈Q3,j∈Q∖Q3.( 2 ) The tertiary nodes are not connected to the underground pipelines; that is,(15)xij=0,i∈Q3,j∈Q.( 3 ) All secondary nodes belong to a primary node and form a set with the primary node. The secondary nodes in the set can only be connected to nodes in the set and are not connected to other similar sets of nodes; that is,(16)∑jxij=1,i∈Q2,j∈Q1(17)∑k∑jxij=0,k∈Q1,i∈j∣∑jxkj=1,j∈Q2∖i.(4) The cargo flow should be smaller than the pipe capacity limit u; that is, (18)xij∗hij≤u.(5) The total amount of goods of a secondary node’s own goods and the tertiary nodes served shall not exceed the node’s throughput capacity limit v1,v2,(19)∑jhij≤v1,i∈Q1,j∈j∣minj⁡sij≤r,j∈i,Q3∑jhij≤v2,i∈Q2,j∈j∣minj⁡sij≤r,j∈i,Q3


## 4. Layout Optimization Based on GA

The model established in this paper belongs to the complex space search problem with multiobjective and multiconstraint conditions. The conventional solution method has poor timeliness and large calculation volume. This paper adoptsGA with migration operation in the heuristic algorithm [25] to solve this kind problem.


### 4.1. Comparison Model

To verify the validity of this model, we use the model in the literature of YI Mei [26] to conduct a controlled trial. YI Mei uses a traditional optimization model to classify all nodes into primary nodes and secondary nodes. When building the objective function, it not only considers the amount of freight between the logistics park and all nodes, but also considers the amount of freight between nodes.Since YI Mei’s model assumes that the position of primary and secondary nodes are known, we modified YI Mei’s model. First, we usedGA to generate the location of the primary nodes and secondary nodes, and each solution can get an optimal network and the minimum cost through the YI Mei model; then we use the minimum cost as a fitness function to choose the best network and the lowest cost of the issue. The modified model is referred to as a comparison model. For convenience, we call the model of this paper “model F” and the comparison model “model T”.


### 4.2. Selecting the Number of Solution Variables

A binary encoding GA is applied for the specific problem of this paper. The solution to the genetic algorithm is a row vector form. The value of each component indicates whether there is an underground pipe connection between corresponding nodes or not. Assume that there aren basic nodes and m logistics parks. Because the logistics parks are not connected with each other and the nodes are not connected by themselves, the pipeline connection corresponding to all components in the solution vector can be converted into an upper triangular matrix with all diagonal elements 0; the solution vector length is mn+n(n-1)/2, and the presence matrix is a (n+m)(n+m) square matrix. Assuming there are 2 logistics parks and 3 basic nodes, the solution vector length is 9 and the ordering is represented as x1,x2,⋯,x8,x9. A 5∗5 presence matrix can be generated from the above variables, as shown in Figure 4.Figure 4
Solution vector and node connection conversion diagram.The first three solutionsx1,x2,x3 are converted to x13,x14,x15, which represent the relationship between the path from the 1st logistics park to those three nodes; the solutions x4,x5,x6 are converted to x23,x24,x25, representing the relationship between the path from the 2nd logistics park to those three nodes; and the solutions x7,x8 are converted to x34,x35, representing the path existence between the 3rd basic node and the other two basic nodes. The solution x9 is converted to x45, which represents the existence of a path from the basic node 4 to the basic node 5.According to the above conversion relationships, the path existence relationship between nodes can be pushed out from the final solution.


### 4.3. Parameters Setting of GA

The parameters of the GA are shown in Table1.Table 1
Parameter settings in the GA.
Number of variables m n + n ( n - 1 ) / 2 Population type Double vector Bounds 0,1 Population size 300 Scaling function Rank Selection function Stochastic uniform Elite count 20 Crossover fraction 0.8 Mutation function Constraint dependent Migration direction Forward Migration fraction 0.2 Migration interval 20 Constraint parameters Augmented Lagrangian Initial penalty 10 Penalty factor 100


## 4.1. Comparison Model

To verify the validity of this model, we use the model in the literature of YI Mei [26] to conduct a controlled trial. YI Mei uses a traditional optimization model to classify all nodes into primary nodes and secondary nodes. When building the objective function, it not only considers the amount of freight between the logistics park and all nodes, but also considers the amount of freight between nodes.Since YI Mei’s model assumes that the position of primary and secondary nodes are known, we modified YI Mei’s model. First, we usedGA to generate the location of the primary nodes and secondary nodes, and each solution can get an optimal network and the minimum cost through the YI Mei model; then we use the minimum cost as a fitness function to choose the best network and the lowest cost of the issue. The modified model is referred to as a comparison model. For convenience, we call the model of this paper “model F” and the comparison model “model T”.


## 4.2. Selecting the Number of Solution Variables

A binary encoding GA is applied for the specific problem of this paper. The solution to the genetic algorithm is a row vector form. The value of each component indicates whether there is an underground pipe connection between corresponding nodes or not. Assume that there aren basic nodes and m logistics parks. Because the logistics parks are not connected with each other and the nodes are not connected by themselves, the pipeline connection corresponding to all components in the solution vector can be converted into an upper triangular matrix with all diagonal elements 0; the solution vector length is mn+n(n-1)/2, and the presence matrix is a (n+m)(n+m) square matrix. Assuming there are 2 logistics parks and 3 basic nodes, the solution vector length is 9 and the ordering is represented as x1,x2,⋯,x8,x9. A 5∗5 presence matrix can be generated from the above variables, as shown in Figure 4.Figure 4
Solution vector and node connection conversion diagram.The first three solutionsx1,x2,x3 are converted to x13,x14,x15, which represent the relationship between the path from the 1st logistics park to those three nodes; the solutions x4,x5,x6 are converted to x23,x24,x25, representing the relationship between the path from the 2nd logistics park to those three nodes; and the solutions x7,x8 are converted to x34,x35, representing the path existence between the 3rd basic node and the other two basic nodes. The solution x9 is converted to x45, which represents the existence of a path from the basic node 4 to the basic node 5.According to the above conversion relationships, the path existence relationship between nodes can be pushed out from the final solution.


## 4.3. Parameters Setting of GA

The parameters of the GA are shown in Table1.Table 1
Parameter settings in the GA.
Number of variables m n + n ( n - 1 ) / 2 Population type Double vector Bounds 0,1 Population size 300 Scaling function Rank Selection function Stochastic uniform Elite count 20 Crossover fraction 0.8 Mutation function Constraint dependent Migration direction Forward Migration fraction 0.2 Migration interval 20 Constraint parameters Augmented Lagrangian Initial penalty 10 Penalty factor 100


## 5. Experiment and Result Analysis

The experimental data used in this paper are the data on the 2017 China Graduate Mathematical Contest Modeling Problem F [27]. The logistics data are from Jiangsu Province, China. The competition titles require the construction of an underground logistics network with the lowest total cost.For better comparing the merits of the models, we randomly select two sets of data from the original data. The first set of data has 2 logistics parks and 20 sets of basic nodes, and the second set of data has 2 logistics parks and 30 sets of basic nodes. The relevant costs of nodes and pipeline construction and other parameters are shown in Table2.Table 2
Underground pipeline related expenses.
a 1 4.11 thousand RMB/each node/day a 2 2.74 thousand RMB/each node/day a 3 10.96 thousand RMB/kilometer a 4 1 RMB/ton/kilometer a 5 2 RMB/ton/kilometer a 6 1 RMB/ton/time u 10 ton v 1 4000 ton v 2 3000 ton r 3 kilometersAccording to the parameters and experimental data, this paper obtains the iterative result graphs and the best individuals for the two models under the corresponding data, as shown in Figure5.Figure 5
Iterative process of GA of two models.From Figure5, we can see that, whether it is a group of 20 basic nodes or 30 basic nodes, the GA can show stable convergence of two different models. Moreover, the total cost of pipe network construction obtained by Model F is less than the total cost of the Model T. With the increase in basic data points, the cost reduction rate is greater. For example, with the 20 basic nodes, the total cost of the Model F is approximately 2.56424 (million RMB/day), while the total cost of the Model T is about 2.73251 (million RMB/day), which is a decrease of 6.16%. Compared to the basic nodes reaching 30 groups, the total cost of Model F is about 3.38837 (million RMB/day), while the total cost of Model T is approximately 3.7159 (million RMB/day), which is a decrease of 8.81%.Table3 compares the numbers of the primary, secondary, and tertiary nodes that need to be constructed under the two models. It can be seen that under the Model F, it can be found through the comparison of the number of nodes that, whether in 20 data points or 30 data points, the results obtained by the Model F can greatly reduce the number of nodes to be built in practical applications.Table 3
Node composition of two algorithms.
20 nodes 30 nodes model T F T F  Primary nodes 5 5 6 6  Secondary nodes 15 9 24 14  Tertiary nodes 0 6 0 14Qualitative Analysis. In the first case, the Model F needs to build 14 nodes in total, and the Model T needs to build 20. In the second case, the Model F needs to build a total of 20 nodes, and the Model T needs to build 30 Nodes which greatly reduce the node’s construction costs. Table 4 is a detailed comparison of the total construction cost and the cost of each part of different algorithms. The pipeline construction cost and transport cost of Model F are less than the pipeline construction cost and transport cost of Model T.Table 4
Costs of two models (thousand RMB/day).
20 basic nodes 30 basic nodes Models T F T F  Node build cost 61.6 452.0 90.4 63.0  Pipeline build cost 2165.7 2020.4 2858.7 2705.3  Transport cost 470.6 426.9 710.8 578.0  Transit cost 34.7 28.9 56.0 42.1  Total cost 2732.5 2546.2 3715.9 3388.4Quantitative Analysis. According to the best individual obtained by the GA, specific costs can be obtained as shown in Table 4. From the table, when the node data are 20, the cost of Model F is less than the cost of Model T. This shows that Model F is obviously better than Model T and is implemented.The best individuals of GA are shown in Figure6. According to Figure 6, the final underground logistics networks pipeline diagram can be obtained.Figure 6
Best individual genetic algorithm in two different models.Figure6 indicates all the best individuals corresponding to the solution obtained under two different models of optimization results. According to Section 4.2, these best individuals stand for the corresponding two nodes that need to be connected to an underground pipe. The optimal solution obtained by the genetic algorithm can be converted into a path existence matrix. According to this model, the data on the entire underground logistics network can be obtained. All the best network pipeline diagrams obtained under different models are shown in Figure 7. Model T needs underground pipelines to connect all nodes, but under the Model F, some nodes do not need to connect to underground pipelines under the premise of meeting the distribution scope and can only meet the distribution requirements through the traditional ground logistics transportation.Figure 7
Pipeline diagrams of two models under different sets of data.In Figure7, the color of the connection between the nodes is given randomly and has no special meaning.


## 6. Conclusion

In this paper, we studied the multidepot facilities location-routing problem with realistic conditions to build an underground logistics system. This paper considered that the transportation is a bidirectional flow not a single flow, each pairs node in the area needs transport, using the dynamic routing selection method to determine the routing of unconnected collection sites. Due to the computational complexity of the model, a genetic algorithm was designed to solve the proposed model. The efficiency of the proposed model was illustrated with experiments. Compared with previous work, the main contribution of our paper is to propose a new four-level hierarchical model which simultaneously considered the FLP and VRP both.



---

*Source: 7235048-2018-09-26.xml*