# Regional Logistics Network Design in Mitigating Truck Flow-Caused Congestion Problems

Authors: Mi Gan; Xinyuan Li; Fadong Zhang; Zhenggang He
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

Truck flow plays a vital role in urban traffic congestion and has a significant influence on cities. In this study, we develop a novel model for solving regional logistics network (RLN) design problems considering the traffic status of the background transportation network. The models determine not only the facility location, initial distribution planning, roadway construction, and expansion decisions but also offer an optimal solution to the logistics network service level and truck-type selections. We first analyze the relationship between the urban transportation network and the RLN design problem using real truck data and traffic flow status in a typical city. Then, we develop the uncover degree function (UDF), which reflects the service degree of the RLN and formulates based on an impedance function. Subsequently, the integrated logistics network design models are proposed. We model the RLN design problem as a minimal cost problem and design double-layer Lagrangian relaxation heuristics algorithms to solve the model problems. Through experiments with data from the six-node problem and Sioux-Falls network, the effectiveness of the models and algorithms is verified. This study contributes to the planning of regional logistics networks while mitigating traffic congestion caused by truck flow.


---

## Body

## 1. Introduction

Traffic congestion has become a critical social issue in several metropolis and cities worldwide. Recently, both government and academia have put increasing effort to ease traffic congestion. Some of the major cities in China have achieved success regarding traffic congestion reduction. Compared with 2016, the maximum traffic-congested index during peak hours reduced by 4.8% [1]. Such progress may be attributed to the specific demand management mechanism and control policy, public transport system optimization, and emerging individual travel modes, such as ride-sharing demand-responsive transport and shared bikes [2]. In other words, the reduction in traffic congestion is due to the optimization of individual/passenger travel. However, from the perspective of roadway freight transport, there is a rising impact of urban congestion and greenhouse gas emissions. Truck flow accounts for 30% of the traffic flow in China’s expressways [3]. In urban areas, truck proportion is also increasing due to the development of e-commerce and the regional economy. Consequently, researchers seek to discover new ways of achieving traffic congestion relief in the roadway freight transport system [4].It should be noted that the spatiotemporal imbalance between the demand and supply of individual trips is not easy to solve. However, it is possible to adjust the spatiotemporal distribution of trucks by RLN design, which refers rescheduling delivery plans, relocating logistics facilities, and optimizing regional logistics networks [5]. Several measures can be taken to relieve traffic congestion caused by trucks. Such measures include controlling roadway freights by adjusting the in-city distribution or delivery time windows to avoid trucks traveling during commute time, as well as locating the logistics centers far from the cities [6, 7] since the distribution of truck flow is determined by commercial demand, which is not easily reduced. Moreover, cargoes should be transported to the right destination at a proper time. Thus, after the demand and supply locations are determined, the choice of the travel time and routes are usually limited. In China, there are strict rules and policies on the vehicle type, travel time, and truck routes in the cities. Assuming that optimizing the logistics network design and planning could predetermine the potential truck flow and route, then the design and planning of the logistics network should be carried out and integrated with the existing traffic flow in the urban traffic network. In this context, finding a mechanism to solve the roadway traffic flow problems through the RLN design is a critical issue to be addressed, which is essential to mitigate traffic congestion in a given region and to reduce truck travel delay.Generally, the constraints of the RLN design problem is to satisfy the regional logistics demand in a given time period. Then, the objectives of RLN include determining the number and locations of facilities and producing the transport plan among the facilities, in which the regional transport status is barely considered. Figure1 displays a real logistics network of Chengdu, China, showing the background traffic status. It is clear that, for a fixed location of logistics centers, there is limited space for selecting the travel route of trucks, indicating that the truck flow will affect the original regional transport network and may intensify the regional traffic congestion. In other words, it is necessary to take the regional transport status into account in the RLN design problem.Figure 1
Real logistics network and background traffic status.To fill the gap of existed research on RLN, this paper develops a novel RLN design model to mitigating truck flow-caused congestion problems. We attempt to use the delivery time to link the background traffic flow status and logistics system, and the delivery time is directly related to the RLN service level. Therefore, this study also falls into a service decay problem category in RLND, in which the service capacity gradually declines with the increase in the distance or travel time between the logistics facilities and demand points. Then, we capture the service decay of each facility in RLN by formulating a service uncover degree function (UDF). In the UDF, the delivery time is measured by an improved Bureau of Public Roads (BPR) function (impedance function), which calculated the truck delivery time by considering the background traffic state. By setting demand shortage penalty costs, we model the RLN design problem as a minimal cost problem. In the proposed model, besides the classic decision problem in RLN (e.g., facility location and transport planning), the decision for the degree of service and the corresponding truck-type selection-loading are integrated into the model. Last but not the least, the Lagrangian relaxation algorithm is developed in the model, and typical examples and sensitivity analysis demonstrate the effectiveness of the model and the algorithm.The remainder of this study is structured as follows. After reviewing the literature in Section2, we describe the problem and develop a novel UDF in Section 3. Then, the network design model and double-layer Lagrangian relaxation heuristics algorithms for solving the described problem are presented in Section 4. Numerical experiments and key factors sensitivity are analyzed in Section 5. In Section 6, the discussion and conclusions of the study are presented.


## 2. Literature Review

Logistics network design (LND) is popularly applied in research and practice. The forward or reverse LND, supply chain design, service network design, and regional logistics network design (RLND) are branches of LND. There are different sophisticated theories about the application of LND in system engineering, operational research, and logistics engineering. LND mainly refers to solutions to a series of optimization problems in a logistics network system for long-term strategic planning levels, such as facility location, capacity decision, distribution planning, and vendor selection [8]. LND can be applied in terms of research, which could be in the enterprise/private sector or government/public sector. In the private sector, firms may apply LND models and algorithms when developing a logistics network or supply chain network for new markets or replanning the network for an existing market. The objective is to optimize the total costs for facility location, distribution planning, and supply chain organization while satisfying several demands in the final customer market [9]. However, RLND is mainly applied in the public sector perspective, which optimizes the social logistics network by minimizing the logistics cost of the whole society to provide decision support for the regional logistics network (RLN) planning. Thus, it is more realistic to consider the traffic congestion in RLND because RLND helps to solve region logistics problems and similar transportation planning problems, which influences regional logistics and transportation infrastructures. In addition, a comprehensively new regional logistics network can lead to a stronger competition among industries and offer location advantages. Most of them pay attention to the joint optimization problem of road network design and distribution based on different location problems, which provide a solid theoretical background for RLND. In general, the RLN design problem is difficult to tackle due to the nondeterministic polynomial-time hardness (NP-hardness) properties. Notably, it is more complicated if we consider the background traffic flow. From the literature, the RLN design problem is almost a complete theoretical system; researchers are mainly focused on developing more practical models and more efficient algorithms. The most popular algorithms for solving RLND problems include the intelligent optimization algorithm, heuristic algorithm, and network flow algorithm [10–17]. Yet, few studies considered the background traffic flow state.Concerning fusion of the logistics system and background transport network, motivated by cost reduction in the company sector, some studies managed congestion problems in the product logistics network or the supply chain network. Bai et al. first introduced the BPR function in modeling the travel time and congestion costs in the location of refinery location decisions [18]. Konur and Geunes utilized a game model in providing an analytical characterization of the effects of traffic congestion costs on equilibrium distribution flows [19]. Jouzdani et al. applied fuzzy linear programming in modeling the dynamic travel time during traffic congestion and solved the dynamic dairy facility location and supply chain planning problems [20]. More recently, Mohammad et al. managed congestion in a biomass supply chain network through dynamic freight routing using multimodal facilities at different periods of a year [21]. However, unlike in these reviewed studies, the optimal model proposed in this study designs a regional logistics network, avoids increasing the level of regional traffic congestion, and promotes the service level of each facility simultaneously.For the literature studies on the service decay function of facility in the logistics network, there is a specific service coverage radius for logistics facilities that when the demand point is within this coverage radius, this demand point is assumed to be covered entirely. But, this is considered as not being wholly covered when it is outside the coverage radius [22–24]. The service level degree corresponds to the extent whether the demand nodes are covered. The most relevant studies to date are the gradual recession coverage model, stepwise coverage model, stochastic range decay coverage model, and minimum-maximum regression models. Generally, in such models, the logistics facility is given initial upper and lower bounds for the service distance. When the travel distance between the customer/demand point and the facility is within the lower bound distance, it appears that the demand point is completely covered; when the distance exceeds the upper bound, the demand point is not covered. For the demand points in the upper and lower bounds, a decay function is built to describe the demand point. The critical variable in the classic decay coverage function is the shortest distance between the demand point and the facility point. This function is essentially a distance-covering function between the demand point and the facility point, that is, the service capacity gradually declines with the increase in the distance between the facilities and demand points. However, in reality, the logistics demand is not only a simple spatial distance but also focuses on the delivery time and delivery volume of the facility through diverse modes of transportation. Concerning the logistics demand characteristics, the noncoverage function of logistics demand based on time and logistics delivery quantity is constructed, which has been proved to be applicable in facility location problems [25].(1)fijtij=0,iftij≤tjorqij≤0,qijtij−tjTj−tj,iftj<tij≤Tjandqij>0,M,iftij>Tjorqij>0.In equation (1), Tj and tj represent the upper bound and lower bound of the response time of the logistics network, respectively, which are required in the customer/demand point, qij is the service volume from the supply point to the demand point, and tij is the shortest delivery time from the facility to the corresponding node. The upper bound is the maximum delivery time limit of the customer/demand point. The lower bound is the customer/demand point that could be fulfilled by the corresponding facility rapidly; in other words, the facility can provide a high service level to the corresponding customer/demand point. When the service time is within the upper and lower bounds, the demand point can be served, but its degree of service has a corresponding recession. Yu et al. further applied this function in the network design models of fresh agricultural product supply chain and pointed out that this function is equivalent to the logistics service-quality evaluation function [26].Although the function can describe the relationship of the service level between the facility and the demand point better, the free-flow time to be replaced is selected for the point between the facility and the point of transport of goods, that is, the road traffic network is neglected in the cargo transport process. Nevertheless, this assumption is inconsistent with the actual situation. Correspondingly, when the service time exceeds the upper bound demand time, the noncoverage is a considerably large constant. When only the free-flow transportation time is taken into account, the value of the freightqij can meet the demand, that is, qij>qijtij−tj/Tj−tj. However, when the traffic flow is considered, the actual transportation time will increase, the inequality will not always hold, and the function needed to be redefined.To capture the delivery time better, in the next section, we will first develop an uncover degree function (UDF) by applying the service decay function and the BPR function.


## 3. Formulating the Service Uncover Degree Function

To enhance the understanding of the interface of regional truck flows and regional transportation systems, we have applied the truck trajectory data of Chengdu city from August 2017 to October 2017. The left part of Figure2 shows the spatial distribution of weekly truck flows of Chengdu city. Remarkably, the trucks are clustered on a limited path-road in the city. No matter the weekday, the trucks mainly traveled by the third ring road and fourth ring expressway as well as some main trunk roads connecting the logistics centers of the city. The right part of Figure 2 shows the ranking of the most congested roads in Chengdu city in 2017. The fourth ring expressway is ranked number 1, and the third ring road is ranked 4. Therefore, a considerable number of trucks passed through the most congested roads.Figure 2
Background traffic flow of Chengdu city from August–October 2017.
(a)
(b)To modeling and capturing the service decay on travel time, first, we need to model the relationships between the background traffic flow, logistics freight flow, and travel time. Figure3 gives a typical OD pair and its corresponding real route. Since the BPR function is the most widely accepted traffic delay function for both China and the U.S., we use the BPR function as the time function to estimate the travel time of each OD pair in the RLN as follows:(2)tijxij=tij01+αxijcijβ,where xij is the traffic flow between OD pair i, j; tijxij is the actual road access time when the traffic flow is xij; tij0 is the free-flow time; cij is the road traffic volume; and α and β are constants that depend on the government regulation (e.g., according to the recommendation of the US Department of Transportation, the general road constant value can be set to α=0.15 and β=4. In China, the values are also applied).Figure 3
Relationship between the OD pair and the real route.Based on the above analysis, the uncover degree function of the logistics demand point under the condition of traffic delay is deduced as follows:(3)xij=bij+yij,where bij is the average value of the traffic flow on road ij when the corresponding logistics facilities are not constructed; yij is the traffic flow on road ij when the corresponding logistics facilities are constructed. Introducing the constant δ to express the conversion factor between the traffic flow and freight volume, we have the following expression:(4)yij=δqij.Then, we obtain the UDF of the problem as follows. Suppose a unit of traffic can transport 1/δ unit of goods, apply (2), (3), and (4) into function (1), and overwrite the noncover value where the upper bound time is overwritten to a sufficiently large value of M.(5)fjtijxij=0,iftij0≤tj,tij01+αbij+δqij/cijβ−tjTj−tj,iftj<tij0≤Tj,M,iftij0>Tj.To facilitate the observation, measuring the relationship of the UDF and distribution time in the logistics network, letqij=1. Considering that the road traffic has already achieved the capacity bottlenecks, then bij+δqij/cij=1. The upper and lower bounds of the distribution time of the demand nodes are set to 24 and 12 h, respectively. MATLAB R2010a was employed to plot the relationship between the travel time and uncover degree.As shown in Figure4, when tij≤tj, the demand point is regarded as having high coverage. The logistics network can respond to the logistics demand of the demand point quickly, and the noncoverage value can be taken as zero. When tj<tij≤Tj, the demand point is assumed to be under good coverage, and the uncover degree value is decayed by increasing the transport time. When tij≤Tj, then the demand point is not covered by any corresponding facilities, and the logistics network can hardly respond to logistics needs. This situation should be avoided in an actual logistics network design process. Therefore, we manually set a value sufficient to describe the uncover degree.Figure 4
Uncover degree over transport time.


## 4. Models and Algorithms

### 4.1. Models

The RLND model constructed in this study aims to minimize the design and operation costs of the logistics network to satisfy the regional logistics demand. As the gathering point of the regional logistics demand is usually the best candidate for the logistics facility location, it is assumed that the demand point in the logistics network is also the candidate site for site selection. For the treatment of road traffic flow, it is assumed that the road background traffic flow is the accurate data, which can be obtained through historical data.We now introduce the following symbols as shown in Table1 in this section:Table 1
Symbol description.
Symbol
Description (unit)
N
Set of nodes in the network
D
Set of demand points
S
Set of supply centers
L
¯
Set of existing roads will not be expanded
L
¯
¯
Set of existing roads will be expanded
d
j
Amount of demand pointj needed (unit: tons)
m
i
j
Transportation cost per unit of cargoes of road (i, j) (unit: RMB yuan)
o
i
Fixed cost of constructing facilities at nodei during the planning period (unit: RMB yuan)
e
i
j
Construction cost per unit of the road based on logistics volume (unit: RMB yuan)
v
i
j
Expansion cost per unit of the road based on traffic flow (unit: RMB yuan)
θ
i
Logistics turnover cost per unit for constructing the facility locationi (unit: RMB yuan)
c
i
j
Capability of the traffic flow on the roadi,j (unit: pcu/h)
p
j
Penalty cost for delivery time not between the upper and lower bounds. It is regarded as the loss of opportunity cost because of stock out when delivering commodities. Moreover, it should be designed for the cargoes in societal logistics, such as medical supplies for emergency. (unit: RMB yuan)
z
i
Decision variable is equal to 1 when the facility location is at nodei; otherwise, it is 0
q
i
j
Decision variable, which stands for the freight volume of the roadi,j during the planning period, described as the amount of cargo from facility i to demand point j (unit: t)
Q
i
Turnover during the planning period when facility pointi is also the candidate for facility location (unit: tons)
λ
i
j
λ
i
j
=
δ
q
i
j
+
b
i
j
−
c
i
j
0, decision variable, if δqij+bij−cij>0, then expand the road; otherwise, its value is 0The following equations are used in the mathematical models:(6)minzq,o,λ,Q,f=∑i∈S∑j∈Deijqij+∑i∈S∑j∈Dmijqij+∑i∈S∑j∈Dvijλij+∑i∈SQiθi+∑i∈Szioi+∑j∈Dfjtijxijqijpj,(7)s.t.dj=∑j∈Sqij,∀i∈S,∀j∈D,(8)Qi=∑j∈Dqij,∀i∈S,∀j∈D,(9)∑i=0IQizi≥∑j∈Ddj,(10)λij≤δqij+bij−cij,∀i∈S,∀j∈D,ij∈L¯,(11)cij≥bij+δqij,∀i∈S,∀j∈D,ij∈L¯¯,(12)fjtijxij≤qijtij0,∀i∈S,∀j∈D,(13)λij≥0,qij≥0,Qi≥0,fjtijxij≥0,(14)zi=1,0,∀i∈S,∀j∈D.The objective function aims to minimize the costs of road building, transportation, road expansion, facility turnover, fixed costs of facility location, and punishment costs of the demand point uncover degree based on the traffic flow. Constraints (7) and (8) provide a balance between the supply and demand of the network flow. Constraint (9) guarantees that the supply of the logistics network is not less than the total demand. Constraint (10) describes the relationship between the road expansion variables and road capacity. Constraint (10) shows that the edge set of the roadway to be built only needs expansion when the actual traffic flow exceeds the capacity. Constraint (11) states that the road capacity should not be less than the sum of the background traffic flow and the increasing freight traffic flow for the edge set of the roads with no need for expansion. Constraint (12) limits the demand point uncovered function. Constraints (13) and (14) guarantee that the variables are positive and range between 0 and 1.


### 4.2. Algorithms

To solve this problem, the heuristic algorithm based on Lagrangian relaxation (HALR) is used to provide the upper and lower bounds for the original problem. Subsequently, the corresponding algorithm is developed to solve the NP-hardness problem in the model expressed from (6)–(14).Accounting for the characteristics of models (6)–(14), constraints (8) and (10) are used for relaxation. The simple Lagrange multiplier μij and nonnegative Lagrange multiplier μij′ are introduced, and the relaxation of the original problem is as follows:(15)minzq,o,λ,Q,f=∑i∈S∑j∈Deijqij+∑i∈S∑j∈Dmijqij+∑i∈S∑j∈Dvijλij+∑i∈SQiθi+∑i∈Szioi+∑j∈Dfjtijxijpj+∑i∈S∑j∈DμijQi−∑j∈Dqij+∑i∈S∑j∈Dμij′λij−δqij−bij+cij.For any sumμij and μij′, objective function (15) is a lower bound of the original problem. Furthermore, (15) is rewritten as a function based on the Lagrangian multiplier and decomposes into the following two subproblems.Subproblem 1: this subproblem refers to the general logistics network design. This problem can be solved using the developed heuristic algorithm.(16)min∑i∈S∑j∈Deij+mij−μij′δqij+∑i∈S∑j∈Dvij+μij′λij+∑i∈Sμij+Qiθi+∑j∈D−μijqij+∑i∈Szioi.Subproblem 2: it refers to the traffic flow assignment. This problem can also be solved by the developed heuristic algorithm.(17)min∑j∈Dfjtijxijpj+∑i∈S∑j∈D−μij′bij+∑i∈S∑j∈Dμij′cijsubject to7,9,and11–14.Based on the above analysis, the algorithm steps of the original problem are designed as follows:(1)
Initialize the input data according to the free flow of time between the nodes on the network. Remove the connection side of the situationtij0>Tj. For the connection edge tij0≤tj, take fjtijxij=0; for the connection edge tj<tij0≤Tj, take fjtijxij=qijtij01+αbij+δqij/cijβ−tj/Tj−tj.(2)
Construct the Lagrangian multiplierμij and μij′, and relax the original problem, as shown in (15). In addition, relax 0, 1 constraint (14).(3)
Letk be equal to 100 for a small-scale problem or 500 for a large-scale problem. Take ε as a small, nonnegative real number, run a subgradient search to solve subproblem model (16), and obtain an approximate optimal solution.(4)
Substituteqij∗ into objective function (17) and obtain the following expression: ∑i∈S∑j∈Dqij∗pj/Tj−tjtijxij−∑j∈Dtjpj/Tj−tj+∑i∈S∑j∈Dμij′cij−bij,whereμij′ is the transport time on the virtual edge, that is, tv=μij′, which can be solved using the Frank–Wolfe method.(5)
According to the zero flow without allotting, obtain a groupxa,xv and update the impedance of each road to find the direction of the next iteration. From the updated impedance of all the distributions, access additional flow ya,yv.(6)
Letxn+1a=xna+ηyna−xna, and xn+1v=xnv+ηynv−xnv.To determine the solution of the following equation,(18)∑ayna−xnataxna+λyna−xna=0,∑vynv−xnvtvxnv+ηynv−xnv=0,we obtain the upper-bound solution of the two subproblemsz¯1 and z¯2 by updating the iteration. Obtain z¯ when xn+1a−xna≤ξ and xn+1v−xnv≤ξ.(7)
Letϖn+1=2z¯−zμ,μ′/∑i∈S∑j∈DQi−∑j∈Dqij2+λij−δqij−bij+cij2. Recall that the number of iterations is 100 (small-scale problem) or 500 (large-scale problem). At z¯−zμ,μ′≤3%, the optimal solution is output, and the algorithm is terminated.


## 4.1. Models

The RLND model constructed in this study aims to minimize the design and operation costs of the logistics network to satisfy the regional logistics demand. As the gathering point of the regional logistics demand is usually the best candidate for the logistics facility location, it is assumed that the demand point in the logistics network is also the candidate site for site selection. For the treatment of road traffic flow, it is assumed that the road background traffic flow is the accurate data, which can be obtained through historical data.We now introduce the following symbols as shown in Table1 in this section:Table 1
Symbol description.
Symbol
Description (unit)
N
Set of nodes in the network
D
Set of demand points
S
Set of supply centers
L
¯
Set of existing roads will not be expanded
L
¯
¯
Set of existing roads will be expanded
d
j
Amount of demand pointj needed (unit: tons)
m
i
j
Transportation cost per unit of cargoes of road (i, j) (unit: RMB yuan)
o
i
Fixed cost of constructing facilities at nodei during the planning period (unit: RMB yuan)
e
i
j
Construction cost per unit of the road based on logistics volume (unit: RMB yuan)
v
i
j
Expansion cost per unit of the road based on traffic flow (unit: RMB yuan)
θ
i
Logistics turnover cost per unit for constructing the facility locationi (unit: RMB yuan)
c
i
j
Capability of the traffic flow on the roadi,j (unit: pcu/h)
p
j
Penalty cost for delivery time not between the upper and lower bounds. It is regarded as the loss of opportunity cost because of stock out when delivering commodities. Moreover, it should be designed for the cargoes in societal logistics, such as medical supplies for emergency. (unit: RMB yuan)
z
i
Decision variable is equal to 1 when the facility location is at nodei; otherwise, it is 0
q
i
j
Decision variable, which stands for the freight volume of the roadi,j during the planning period, described as the amount of cargo from facility i to demand point j (unit: t)
Q
i
Turnover during the planning period when facility pointi is also the candidate for facility location (unit: tons)
λ
i
j
λ
i
j
=
δ
q
i
j
+
b
i
j
−
c
i
j
0, decision variable, if δqij+bij−cij>0, then expand the road; otherwise, its value is 0The following equations are used in the mathematical models:(6)minzq,o,λ,Q,f=∑i∈S∑j∈Deijqij+∑i∈S∑j∈Dmijqij+∑i∈S∑j∈Dvijλij+∑i∈SQiθi+∑i∈Szioi+∑j∈Dfjtijxijqijpj,(7)s.t.dj=∑j∈Sqij,∀i∈S,∀j∈D,(8)Qi=∑j∈Dqij,∀i∈S,∀j∈D,(9)∑i=0IQizi≥∑j∈Ddj,(10)λij≤δqij+bij−cij,∀i∈S,∀j∈D,ij∈L¯,(11)cij≥bij+δqij,∀i∈S,∀j∈D,ij∈L¯¯,(12)fjtijxij≤qijtij0,∀i∈S,∀j∈D,(13)λij≥0,qij≥0,Qi≥0,fjtijxij≥0,(14)zi=1,0,∀i∈S,∀j∈D.The objective function aims to minimize the costs of road building, transportation, road expansion, facility turnover, fixed costs of facility location, and punishment costs of the demand point uncover degree based on the traffic flow. Constraints (7) and (8) provide a balance between the supply and demand of the network flow. Constraint (9) guarantees that the supply of the logistics network is not less than the total demand. Constraint (10) describes the relationship between the road expansion variables and road capacity. Constraint (10) shows that the edge set of the roadway to be built only needs expansion when the actual traffic flow exceeds the capacity. Constraint (11) states that the road capacity should not be less than the sum of the background traffic flow and the increasing freight traffic flow for the edge set of the roads with no need for expansion. Constraint (12) limits the demand point uncovered function. Constraints (13) and (14) guarantee that the variables are positive and range between 0 and 1.


## 4.2. Algorithms

To solve this problem, the heuristic algorithm based on Lagrangian relaxation (HALR) is used to provide the upper and lower bounds for the original problem. Subsequently, the corresponding algorithm is developed to solve the NP-hardness problem in the model expressed from (6)–(14).Accounting for the characteristics of models (6)–(14), constraints (8) and (10) are used for relaxation. The simple Lagrange multiplier μij and nonnegative Lagrange multiplier μij′ are introduced, and the relaxation of the original problem is as follows:(15)minzq,o,λ,Q,f=∑i∈S∑j∈Deijqij+∑i∈S∑j∈Dmijqij+∑i∈S∑j∈Dvijλij+∑i∈SQiθi+∑i∈Szioi+∑j∈Dfjtijxijpj+∑i∈S∑j∈DμijQi−∑j∈Dqij+∑i∈S∑j∈Dμij′λij−δqij−bij+cij.For any sumμij and μij′, objective function (15) is a lower bound of the original problem. Furthermore, (15) is rewritten as a function based on the Lagrangian multiplier and decomposes into the following two subproblems.Subproblem 1: this subproblem refers to the general logistics network design. This problem can be solved using the developed heuristic algorithm.(16)min∑i∈S∑j∈Deij+mij−μij′δqij+∑i∈S∑j∈Dvij+μij′λij+∑i∈Sμij+Qiθi+∑j∈D−μijqij+∑i∈Szioi.Subproblem 2: it refers to the traffic flow assignment. This problem can also be solved by the developed heuristic algorithm.(17)min∑j∈Dfjtijxijpj+∑i∈S∑j∈D−μij′bij+∑i∈S∑j∈Dμij′cijsubject to7,9,and11–14.Based on the above analysis, the algorithm steps of the original problem are designed as follows:(1)
Initialize the input data according to the free flow of time between the nodes on the network. Remove the connection side of the situationtij0>Tj. For the connection edge tij0≤tj, take fjtijxij=0; for the connection edge tj<tij0≤Tj, take fjtijxij=qijtij01+αbij+δqij/cijβ−tj/Tj−tj.(2)
Construct the Lagrangian multiplierμij and μij′, and relax the original problem, as shown in (15). In addition, relax 0, 1 constraint (14).(3)
Letk be equal to 100 for a small-scale problem or 500 for a large-scale problem. Take ε as a small, nonnegative real number, run a subgradient search to solve subproblem model (16), and obtain an approximate optimal solution.(4)
Substituteqij∗ into objective function (17) and obtain the following expression: ∑i∈S∑j∈Dqij∗pj/Tj−tjtijxij−∑j∈Dtjpj/Tj−tj+∑i∈S∑j∈Dμij′cij−bij,whereμij′ is the transport time on the virtual edge, that is, tv=μij′, which can be solved using the Frank–Wolfe method.(5)
According to the zero flow without allotting, obtain a groupxa,xv and update the impedance of each road to find the direction of the next iteration. From the updated impedance of all the distributions, access additional flow ya,yv.(6)
Letxn+1a=xna+ηyna−xna, and xn+1v=xnv+ηynv−xnv.To determine the solution of the following equation,(18)∑ayna−xnataxna+λyna−xna=0,∑vynv−xnvtvxnv+ηynv−xnv=0,we obtain the upper-bound solution of the two subproblemsz¯1 and z¯2 by updating the iteration. Obtain z¯ when xn+1a−xna≤ξ and xn+1v−xnv≤ξ.(7)
Letϖn+1=2z¯−zμ,μ′/∑i∈S∑j∈DQi−∑j∈Dqij2+λij−δqij−bij+cij2. Recall that the number of iterations is 100 (small-scale problem) or 500 (large-scale problem). At z¯−zμ,μ′≤3%, the optimal solution is output, and the algorithm is terminated.


## 5. Computational Study

### 5.1. Experimental Design

To observe the impact of traffic flow delay on the logistics network design problem and to compare the experimental results, two classical logistics network design problems are adopted to be experimented with the model and the algorithm.As shown in Figures5(a) and 5(b), the network structures are represented as the classical six-point problem considering the road expansion and Sioux-Falls network problem. Where the site selection cost and unit operating cost are marked beside the node, the unit transport cost of the transport line is marked on the line. The traffic flow status of the six-node network is presented in the table part of Figure 5(a). For the Sioux-Falls network, the free-flow travel time of each path and the background traffic flow are displayed at the right gray-scale maps in Figure 5(b). In the six-point problem, the dotted line indicates the road to be constructed, whereas the solid line signifies the existing road to be expanded. In the Sioux-Falls network, the road construction is complete, and only the expansion problem of the road between the nodes is considered. Only the roads with a current capacity of 2000–4000 pcu/h will be expanded. Assuming that the upper and lower limits of logistics network response time are 24 and 12 h, respectively; the logistics network penalties to be considered include the product unit cost taking 40 yuan/unit. The unit construction cost of the road is 20 yuan, and the expansion cost based on traffic flow is 0.133 yuan/pcu (estimated at a payback period of 30 years). The values of the constants in the function are α=0.15 and β=4, while the value of δ is 0.1.Figure 5
Classic problems. (a) Six-point problem. (b) Sioux-Falls network.
(a)
(b)Table 2
Computational result performance analysis.
Problem
Six-node problem
Sioux-Falls network
Network scale
6/6/9
24/24/76
Number of facilities
2
10
Number of roadway constructions
1
0
Number of roadway expansions
0
15
Number of iterations of HALR
100
500
Running time of HALR (seconds)
15.6
172.1
Gap of HALR (%)
0.2
1.8
Running time of GA (seconds)
50.7
883
Gap of GA (%)
0.0
0.0


### 5.2. Calculation Results and Analysis

(1)
The computational result displayed in Table2 is analyzed by encoding the HALR algorithm and applying a Genetic Algorithm (GA) toolbox with MATLAB R2010(a) on a personal computer launched Intel Core (TM) i7, 1.80 GHz, and 4 GB RAM. The results show the approximate optimal solution and the difference in value between its upper and lower bounds.
For a small-scale six-point problem and a large-scale Sioux-Falls network problem, both the model and the algorithm can determine the approximate optimal solution within an adequate time. The upper and lower bounds are within the acceptable range. For the small-scale problem, the optimal solution with higher precision can be obtained, whereas there is some redundancy between the upper and lower bounds for the large-scale problem.
Concerning the computational performance comparison of genetic algorithms (GA) and the algorithms we proposed in Section4 (HALR), the results show although the GA could achieve more accurate results, the computational time is much longer.
(2)
To further demonstrate the practicability of the proposed model and the algorithm, experiments are designed for the Sioux-Falls network problem to solve the traffic network design problem without considering the road traffic flow, i.e., subproblem 1. Moreover, comparative analyses are made on the total cost, location, road construction, road expansion, and traffic congestion, respectively. Taking the road traffic flow saturation to reflect the traffic congestion andϕ=∑i,jδqij+bij/cij, that is, the ratio of road traffic volume and road capacity in the network, the ratio between the traffic flow and capacity reached 0.927. Therefore, only the roads with newly constructed logistics network facilities and the edge set ϕ≥0.927 are calculated as the critical congested roads. We select the numbers of these edges and the value maxϕ in the network to represent the degree of network traffic congestion. A higher number of congested sides and a closer value of maxϕ to 1 result in a more saturated road traffic. Excessive traffic volume quickly leads to traffic congestion.As presented in Table3, the traffic network design problem without considering the traffic flow neglects the road background traffic flow, and the road design capacity directly replaces the road capacity. Eliminating the congestion penalty cost without regard to the transport time, the total cost and the number of facilities are reduced by 8.6% and 20%, respectively. However, the total network transport time is increased by 35%, and the number of congested roads is increased by 157%. The maximum road saturation is close to 1, which leads to the original network traffic congestion. However, when considering the background traffic status and service level for the RLND problem, the optimal results of our model could meet the distribution time constraints in the regional logistics network. In addition, the model can balance the distribution truck flow in a more saturated traffic network. However, these are achieved with a slight sacrifice of the construction and operation cost saving. Furthermore, the optimal facility location and distribution plan will not cause traffic overload to realize the sustainable development of the logistics network.Table 3
Comparison of logistics network design solutions.
Our model
General RLN
Comparison value (%)
Total cost
174825.81
159727.63
8.6
Number of facilities
10
8
20
Number of constructed roadways
0
0
0
Number of expansion roadways
6
0
100
Total transport time
137.5
186.5
−35
Number of roadways where traffic is heavier
7
18
−157
Max
ϕ
0.931
0.978
−5


### 5.3. Sensitivity Analysis

To clarify the interface of the facility numbers and uncover degree (UD), as well as the effect of conversion factor variation of traffic flow and freight volume on network design decisions, we carried out sensitivity analysis using the data of the Sioux-Falls network. The results are plotted by MATLAB R2010(a) based on the calculated data.Figure6 shows the relationship between the UD and the number of facilities in the logistics network. The UD decreases with the increase in the number of facilities for a particular range. However, when the number of facilities reaches 20, the logistics network demand is completely covered; thus, UD is 0. When the number of facilities is within the range of (5, 20), UD decreases with the increase in the number of facilities. When the number is 5 or less, UD reaches its peak as the demand of the network cannot be satisfied.Figure 6
The UD variation by facility location numbers.Figure7 displays the effect of the conversion factor of traffic flow and freight volume on UD. The curve shows a gradually increasing trend. There are three UD stable areas, which are (0.03, 0.06), (0.12, 0.17), and (0.23, 0.26), respectively, and the UD does not change in terms of area. Recall that and δ=yij/qij, where yij is the truck flow and qij is the freight volume. Thus, the freight load by truck = 1/δ, in tons. It is noted that a smaller traffic flow yields better results for the same volume freight, which signifies that a smaller δ is more desirable. The relationship with UD reveals that we could choose an optimal truck-type selection-loading to minimize the total costs and the UD. In the UD stable area, minimal δ is an optimal solution for truck-operating company to select the right truck type. As the three stable areas correspond to the freight load of (16.7, 33.3), (5.9, 8.3), and (3.8, 4.3), it is optimal to choose the truck type with the load capacity of 33.3 tons for UD=280 (similarly, 8.3 tons for UD=520 and 4.3 tons for UD=990).Figure 7
Variation of demand uncover degree by parameterδ.Figure8 shows how the conversion factor of traffic flow and freight volume impact on the numbers of facility nodes. There are also three stable areas in the rising curve, which are (0.01, 0.025), (0.06, 0.13), and (0.16, 0.22). Typically, the number of facilities increases with the increase in δ, but the stable areas are within the ideal range, such as (0.06, 0.13). A higher freight load volume can be reached without increasing the facility cost by choosing the minimal δ=0.06. In other words, selecting the truck type with the load capacity of 16.7 tons is the optimal solution for the trucks with load capacities ranging from 7.7 to 16.7 tons.Figure 8
Variation of facility location nodes by parameterδ.For overall optimality, the range of values ofδ (0.12, 0.13) and (0.16, 0.17) is the overlapped stable area for both UD and the number of facilities, which indicates that the trucks with loading capacity of 6.3 tons (corresponding to δ=0.16) and 8.3 tons (corresponding to δ=0.12) could be the optimal truck types for an RLN considering the traffic congestion.


## 5.1. Experimental Design

To observe the impact of traffic flow delay on the logistics network design problem and to compare the experimental results, two classical logistics network design problems are adopted to be experimented with the model and the algorithm.As shown in Figures5(a) and 5(b), the network structures are represented as the classical six-point problem considering the road expansion and Sioux-Falls network problem. Where the site selection cost and unit operating cost are marked beside the node, the unit transport cost of the transport line is marked on the line. The traffic flow status of the six-node network is presented in the table part of Figure 5(a). For the Sioux-Falls network, the free-flow travel time of each path and the background traffic flow are displayed at the right gray-scale maps in Figure 5(b). In the six-point problem, the dotted line indicates the road to be constructed, whereas the solid line signifies the existing road to be expanded. In the Sioux-Falls network, the road construction is complete, and only the expansion problem of the road between the nodes is considered. Only the roads with a current capacity of 2000–4000 pcu/h will be expanded. Assuming that the upper and lower limits of logistics network response time are 24 and 12 h, respectively; the logistics network penalties to be considered include the product unit cost taking 40 yuan/unit. The unit construction cost of the road is 20 yuan, and the expansion cost based on traffic flow is 0.133 yuan/pcu (estimated at a payback period of 30 years). The values of the constants in the function are α=0.15 and β=4, while the value of δ is 0.1.Figure 5
Classic problems. (a) Six-point problem. (b) Sioux-Falls network.
(a)
(b)Table 2
Computational result performance analysis.
Problem
Six-node problem
Sioux-Falls network
Network scale
6/6/9
24/24/76
Number of facilities
2
10
Number of roadway constructions
1
0
Number of roadway expansions
0
15
Number of iterations of HALR
100
500
Running time of HALR (seconds)
15.6
172.1
Gap of HALR (%)
0.2
1.8
Running time of GA (seconds)
50.7
883
Gap of GA (%)
0.0
0.0


## 5.2. Calculation Results and Analysis

(1)
The computational result displayed in Table2 is analyzed by encoding the HALR algorithm and applying a Genetic Algorithm (GA) toolbox with MATLAB R2010(a) on a personal computer launched Intel Core (TM) i7, 1.80 GHz, and 4 GB RAM. The results show the approximate optimal solution and the difference in value between its upper and lower bounds.
For a small-scale six-point problem and a large-scale Sioux-Falls network problem, both the model and the algorithm can determine the approximate optimal solution within an adequate time. The upper and lower bounds are within the acceptable range. For the small-scale problem, the optimal solution with higher precision can be obtained, whereas there is some redundancy between the upper and lower bounds for the large-scale problem.
Concerning the computational performance comparison of genetic algorithms (GA) and the algorithms we proposed in Section4 (HALR), the results show although the GA could achieve more accurate results, the computational time is much longer.
(2)
To further demonstrate the practicability of the proposed model and the algorithm, experiments are designed for the Sioux-Falls network problem to solve the traffic network design problem without considering the road traffic flow, i.e., subproblem 1. Moreover, comparative analyses are made on the total cost, location, road construction, road expansion, and traffic congestion, respectively. Taking the road traffic flow saturation to reflect the traffic congestion andϕ=∑i,jδqij+bij/cij, that is, the ratio of road traffic volume and road capacity in the network, the ratio between the traffic flow and capacity reached 0.927. Therefore, only the roads with newly constructed logistics network facilities and the edge set ϕ≥0.927 are calculated as the critical congested roads. We select the numbers of these edges and the value maxϕ in the network to represent the degree of network traffic congestion. A higher number of congested sides and a closer value of maxϕ to 1 result in a more saturated road traffic. Excessive traffic volume quickly leads to traffic congestion.As presented in Table3, the traffic network design problem without considering the traffic flow neglects the road background traffic flow, and the road design capacity directly replaces the road capacity. Eliminating the congestion penalty cost without regard to the transport time, the total cost and the number of facilities are reduced by 8.6% and 20%, respectively. However, the total network transport time is increased by 35%, and the number of congested roads is increased by 157%. The maximum road saturation is close to 1, which leads to the original network traffic congestion. However, when considering the background traffic status and service level for the RLND problem, the optimal results of our model could meet the distribution time constraints in the regional logistics network. In addition, the model can balance the distribution truck flow in a more saturated traffic network. However, these are achieved with a slight sacrifice of the construction and operation cost saving. Furthermore, the optimal facility location and distribution plan will not cause traffic overload to realize the sustainable development of the logistics network.Table 3
Comparison of logistics network design solutions.
Our model
General RLN
Comparison value (%)
Total cost
174825.81
159727.63
8.6
Number of facilities
10
8
20
Number of constructed roadways
0
0
0
Number of expansion roadways
6
0
100
Total transport time
137.5
186.5
−35
Number of roadways where traffic is heavier
7
18
−157
Max
ϕ
0.931
0.978
−5


## 5.3. Sensitivity Analysis

To clarify the interface of the facility numbers and uncover degree (UD), as well as the effect of conversion factor variation of traffic flow and freight volume on network design decisions, we carried out sensitivity analysis using the data of the Sioux-Falls network. The results are plotted by MATLAB R2010(a) based on the calculated data.Figure6 shows the relationship between the UD and the number of facilities in the logistics network. The UD decreases with the increase in the number of facilities for a particular range. However, when the number of facilities reaches 20, the logistics network demand is completely covered; thus, UD is 0. When the number of facilities is within the range of (5, 20), UD decreases with the increase in the number of facilities. When the number is 5 or less, UD reaches its peak as the demand of the network cannot be satisfied.Figure 6
The UD variation by facility location numbers.Figure7 displays the effect of the conversion factor of traffic flow and freight volume on UD. The curve shows a gradually increasing trend. There are three UD stable areas, which are (0.03, 0.06), (0.12, 0.17), and (0.23, 0.26), respectively, and the UD does not change in terms of area. Recall that and δ=yij/qij, where yij is the truck flow and qij is the freight volume. Thus, the freight load by truck = 1/δ, in tons. It is noted that a smaller traffic flow yields better results for the same volume freight, which signifies that a smaller δ is more desirable. The relationship with UD reveals that we could choose an optimal truck-type selection-loading to minimize the total costs and the UD. In the UD stable area, minimal δ is an optimal solution for truck-operating company to select the right truck type. As the three stable areas correspond to the freight load of (16.7, 33.3), (5.9, 8.3), and (3.8, 4.3), it is optimal to choose the truck type with the load capacity of 33.3 tons for UD=280 (similarly, 8.3 tons for UD=520 and 4.3 tons for UD=990).Figure 7
Variation of demand uncover degree by parameterδ.Figure8 shows how the conversion factor of traffic flow and freight volume impact on the numbers of facility nodes. There are also three stable areas in the rising curve, which are (0.01, 0.025), (0.06, 0.13), and (0.16, 0.22). Typically, the number of facilities increases with the increase in δ, but the stable areas are within the ideal range, such as (0.06, 0.13). A higher freight load volume can be reached without increasing the facility cost by choosing the minimal δ=0.06. In other words, selecting the truck type with the load capacity of 16.7 tons is the optimal solution for the trucks with load capacities ranging from 7.7 to 16.7 tons.Figure 8
Variation of facility location nodes by parameterδ.For overall optimality, the range of values ofδ (0.12, 0.13) and (0.16, 0.17) is the overlapped stable area for both UD and the number of facilities, which indicates that the trucks with loading capacity of 6.3 tons (corresponding to δ=0.16) and 8.3 tons (corresponding to δ=0.12) could be the optimal truck types for an RLN considering the traffic congestion.


## 6. Conclusion

In this study, the effect of traffic flow on the regional logistics network design is analyzed. Based on the study of partial coverage function and traffic flow-delay BPR function, the function of uncovering logistics facilities (UDF) is constructed through an analysis of real-travel time between the pair of facilities and customer/demand points. Using this function, an integrated optimization model of the regional logistics network is developed. The two-layer Lagrangian relaxation heuristic algorithm is applied in solving the design problem of the logistics network: six-point problem and Sioux-Falls network problem. The performance analysis demonstrates the validity of the model and the algorithm for two-scale problems. The results of the sensitivity analysis also show the relationship between the demand point coverage and the number of locations in the logistics network. The results also describe the relationship between the demand point coverage and the number of facility locations with the traffic volume and the fluctuation of the traffic-flow conversion factor. The model can guide the practical planning and design of truck-type selection and loading scheme in a regional logistics network. The simplified model can also direct the logistics company in specifying the real-time distribution plan, minimize logistics costs, ensure timely delivery, and reduce congestion when the distribution vehicle travels in the background transportation network. In addition, the traffic network pressure on the regional transport network can be reduced owing to the proper choice of truck travel time.From the managerial view, this study shows the following:(1)
The proposed models and algorithms could support the decision maker in planning a logistics network with a little increase in the total cost, together with a higher service level based on service time and without causing traffic congestion.(2)
The proposed model can replicate the effect of traffic congestion on the design of logistics network to some extent.(3)
Considering the effect of traffic congestion, the total transportation time, path flow/capacity ratio in the logistics network design, and the number of congested routes in the regional logistics network can be optimized.(4)
Generally, the uncover degree of customer/demand points increases with the conversion factor of traffic flow and freight volumeδ. However, there are some stable areas to uncover degree that have some specific ranges of δ. The uncover degree is stable when the value of δ is increased.(5)
Similarly, the number of facility locations increases with conversion factor of traffic flow and freight volumeδ. However, some stable areas for the number of facilities have specific ranges of δ. The number of facilities that needs to be constructed is stable when increasing the value of δ.Future studies should focus on estimating the real-travel time by truck trajectory data. Additionally, a data-driven model for solving the regional logistics network design problem should be formulated.



---

*Source: 5197025-2020-04-29.xml*