# Bilevel Optimization for the Hazmat Transportation Problem with Lane Reservation

Authors: Shengzhong Zhang; Qianqian Hui; Xue Bai; Rongting Sun
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

In this study, we investigate a bilevel optimization model for the hazmat transportation problem with lane reservation. The problem lies in selecting lanes to be reserved in the network and planning paths for hazmat transportation tasks. The trade-off among transportation cost, risk, and impact on the normal traffic is considered. By using the traffic flow theory, we quantify the impact on the normal traffic and modify the traditional risk measurement model. The problem is formulated as a multiobjective bilevel programming model involving the selection of reserved lanes for government and planning paths for hazmat carriers. Two hybrid metaheuristic algorithms based on the particle swarm optimization algorithm and the genetic algorithm, respectively, are proposed to solve the bilevel model. Their performance on small-scale instances is compared with exact solutions based on the enumeration method. Finally, the computational results on large-scale instances are compared and sensitivity analysis on the key parameters is presented. The results indicate the following: (1) Both algorithms are effective methods for solving this problem, and the method based on the particle swarm optimization algorithm requires a shorter computation time, whereas the method based on the genetic algorithm shows more advantages in optimality. (2) The bilevel model can effectively reduce the total risk of the hazmat transportation while considering the interests of hazmat carriers and ordinary travellers. (3) The utilization rate of reserved lanes increases with an increasing number of tasks. Nevertheless, once the proportion of hazmat vehicles becomes excessive, the advantage of reducing the risk of the reserved lanes gradually decreases.


---

## Body

## 1. Introduction

Owing to the rapid development of the chemical industry, the transportation demand for hazmat keeps increasing [1]. Road transportation occupies an important position in the transportation of hazmat and shows a rapid development trend. However, in recent years, many road traffic accidents involving hazmat have brought catastrophic losses to human beings and the environment [2]. There is an average of 36 serious social-impact accidents involving road transportation of hazmat in China annually [3].To reduce the accident risk, the lane reservation strategy has been employed in hazmat transportation [4–7]. The lane reservation can effectively reduce the risk of hazmat transportation, but it will inevitably affect the driving efficiency and time cost of ordinary vehicles [4]. Thus, it is important to measure the risk and the impact on the normal traffic accurately. Further, the probability of traffic accidents varies with traffic flow [8] and traffic state (e.g., the proportion of hazmat vehicles and the use of lanes) [9]. Also, the impact due to the lane reservation can be improved based on the traffic flow [10]. Therefore, motivated by this dynamic characteristic, this work is an expansion of previous Lane Reservation for Hazmat considering the impact of traffic flow.Existing researches formulated this problem into a multiobjective model, which ignored the hierarchical and master-slave relationship of decision-making between the government and hazmat carriers [11]. Further studies from the perspective of bilevel optimization are still necessary. Indeed, the lane reservation problem can be regarded as a special form of road network design based on the existing infrastructure. This paper is the modelling integration of hazmat transportation problem and network design problem from policy integration perspective. That can be interpreted as an expansion of the policy integration proposed by [12] considering the exclusive right-of-way of hazmat vehicles. Additionally, there is still dearth of efficient heuristic algorithms for large-scale problems [6].Based on these gaps, this study focuses on a bilevel optimization model for the hazmat transportation problem with consideration of the lane reservation strategy. The contributions are as follows: (1) We propose a bilevel programming model for hazmat transportation problem via lane reservation. (2) Based on the traffic flow density, vehicle speed, and other specific traffic information, we improve the quantification of the transportation risk and the impact on the normal traffic, which makes the model more practical. (3) Two hybrid metaheuristic algorithms are proposed and compared with the accurate algorithm based on enumeration method to verify the validity of the model and algorithm. (4) The effects of the number of hazmat transportation tasks and the proportion of hazmat vehicles are analyzed to provide some management insights.The rest of the paper is organized as follows. A literature review from two aspects, the hazmat transportation and lane reservation problem, is presented in Section2. The problem description and formulation are described in Section 3. Two heuristic algorithms are proposed in Section 4. In Section 5, computational experiments are conducted to demonstrate the effectiveness of model and algorithms. Finally, Section 6 presents conclusions and potential directions for future research.


## 2. Literature Review

### 2.1. Hazmat Transportation

The hazmat transportation problem is concerned with finding routes with minimum cost and minimum risk [13]. Our problem is considered as a transportation network design problem. Its mathematical programming formulation generally relates to regulatory policies on shipments with hazmat, aiming at minimizing the total network risk [12].The most important way is to restrict hazmat vehicles to travel on certain sections. Kara and Verter [14] first proposed the problem of designing a network by imposing curfews. Then He et al. [11] investigated the hazmat transportation problem with traffic restriction addressing also the concept of risk equity and provided a heuristic algorithm to always find a stable solution. Taslimi et al. [15] established a bilevel network design model considering the response time of accidents and risk equality. Esfandeh et al. [16] extended the network design problem to account for time-dependent road closure.Additionally, other traffic management policies have been integrated with network design problem. Marcotte et al. [17] proposed the toll policies to guide hazmat vehicles to route according to their economic and time preferences, thereby deterring hazmat vehicles from using certain road segments. Esfandeh et al. [18] studied the dual toll solution for hazmat vehicles and ordinary vehicles to regulate hazmat transportation. Wang [19] introduced the speed limit strategy for hazmat transportation. López-Ramos et al. [12] presented an integrated model and specialized local search for the road network pricing and the design of hazmat vehicles.


### 2.2. Lane Reservation Problem

The lane reservation is to select the lanes and/or the time intervals to reserve for only special tasks to satisfy the condition of time or safety. It was initially applied to the strategic planning of transportation tasks for large-scale events [20]. Wu et al. [21] first studied the lane reservation problem in time-constrained transportation networks as a mathematical model and obtained near-optimal solutions. Fang et al. [22] investigated a capacitated lane reservation problem by considering the residual capacity of a lane and consequently developed an exact algorithm based on cut-and-solve approach. Fang et al. [23] extended an optimal lane reservation problem with a dynamic link travel time which is closer to a real traffic situation. The most outstanding application of lane reservation is the exclusive bus lanes design [24]. In recent years, it has been gradually applied to automated truck freight transportation [25].Several studies have been carried out on lane reservation for hazmat. Zhou et al. [4] first introduced the lane reservation strategy into hazmat transportation. A multiobjective model is developed to minimize the total transportation risk and the impact on the normal traffic. Then they proposed a ε-constraint and fuzzy logic-based optimization for this problem [5]. Chu et al. [6] investigated the time-dependent lane reservation for hazmat and solved it via a cut-and-solve-based ε-constraint method. Then a new cut-and-solve and cutting plane combined method is proposed to reduce the computational time [7].


## 2.1. Hazmat Transportation

The hazmat transportation problem is concerned with finding routes with minimum cost and minimum risk [13]. Our problem is considered as a transportation network design problem. Its mathematical programming formulation generally relates to regulatory policies on shipments with hazmat, aiming at minimizing the total network risk [12].The most important way is to restrict hazmat vehicles to travel on certain sections. Kara and Verter [14] first proposed the problem of designing a network by imposing curfews. Then He et al. [11] investigated the hazmat transportation problem with traffic restriction addressing also the concept of risk equity and provided a heuristic algorithm to always find a stable solution. Taslimi et al. [15] established a bilevel network design model considering the response time of accidents and risk equality. Esfandeh et al. [16] extended the network design problem to account for time-dependent road closure.Additionally, other traffic management policies have been integrated with network design problem. Marcotte et al. [17] proposed the toll policies to guide hazmat vehicles to route according to their economic and time preferences, thereby deterring hazmat vehicles from using certain road segments. Esfandeh et al. [18] studied the dual toll solution for hazmat vehicles and ordinary vehicles to regulate hazmat transportation. Wang [19] introduced the speed limit strategy for hazmat transportation. López-Ramos et al. [12] presented an integrated model and specialized local search for the road network pricing and the design of hazmat vehicles.


## 2.2. Lane Reservation Problem

The lane reservation is to select the lanes and/or the time intervals to reserve for only special tasks to satisfy the condition of time or safety. It was initially applied to the strategic planning of transportation tasks for large-scale events [20]. Wu et al. [21] first studied the lane reservation problem in time-constrained transportation networks as a mathematical model and obtained near-optimal solutions. Fang et al. [22] investigated a capacitated lane reservation problem by considering the residual capacity of a lane and consequently developed an exact algorithm based on cut-and-solve approach. Fang et al. [23] extended an optimal lane reservation problem with a dynamic link travel time which is closer to a real traffic situation. The most outstanding application of lane reservation is the exclusive bus lanes design [24]. In recent years, it has been gradually applied to automated truck freight transportation [25].Several studies have been carried out on lane reservation for hazmat. Zhou et al. [4] first introduced the lane reservation strategy into hazmat transportation. A multiobjective model is developed to minimize the total transportation risk and the impact on the normal traffic. Then they proposed a ε-constraint and fuzzy logic-based optimization for this problem [5]. Chu et al. [6] investigated the time-dependent lane reservation for hazmat and solved it via a cut-and-solve-based ε-constraint method. Then a new cut-and-solve and cutting plane combined method is proposed to reduce the computational time [7].


## 3. Mathematical Model

### 3.1. Problem Description

LetG=N,A be a hazmat transportation network, where N is the set of nodes and A is the set of arcs; arc i,j∈A denotes a road segment from node i to node j. Hazmat transportation tasks are described by sets of origins (O⊆N) and destinations (D⊆N).The government has a leading position concerning the hazmat transportation risk, whereas hazmat carriers attempt to minimize their cost. We design a bilevel hazmat lane reservation problem (BHLRP) as depicted in Figure1. The upper level (UP) means the government selects lanes to be reserved considering the interests of hazmat carriers and ordinary travellers. That is done to minimize the transportation risk and the impact on the normal traffic. The lower level (LP) is the optimal path with the lowest cost for each task.Figure 1
Conceptual structure of the bilevel hazmat lane reservation problem.


### 3.2. Assumption and Notation

To better define the problem, we present some assumptions and notations here.


#### 3.2.1. Assumptions

(1)
Each road section has at least two lanes so that at least one general lane is in use after lane reservation(2)
When a lane is reserved in the section, hazmat vehicles passing through a road must use the reserved lane(3)
Vehicles are traveling in each section at a constant speed(4)
Potential accidents involving hazmat independently occur, and the probability of hazmat accidents is affected by traffic flow density(5)
There are only two types of vehicles in the road network, namely, hazmat vehicles and ordinary vehiclesDecision variables:(1)zij=1,if there is a reserved lane on arci,j,0,otherwise.xijw=1,if taskwpasses arci,jand there is a reserved lane,0,otherwise.yijw=1if taskwpasses arci,jy˜ijwis the situation before lane reservation0otherwise.


### 3.3. Impact on Normal Traffic

With the development of intelligent transportation network, traffic situations such as speed and traffic density can be obtained by analyzing huge amounts of real traffic data. This provides a new way to further quantify the impact on the normal traffic. We improve this indicator based on the traffic flow by referring to [26].Before implementing the lane reservation strategy, vehicles are evenly distributed on each lane of arci,j and travel at the same speed of Vij. After lane reservation, the traffic d1−βfij/Mij−1 with travel speed V′¯ij seen in equation (2) is derived from the speed-density relationship of traffic flow theory. vm is the optimal speed with the maximum flow. Thus, the impact on the normal traffic in arc i,j, Cij, can be defined by equation (3).(2)V′¯ij=Vij+vmlogMij−1Mij1−β,(3)Cij=T¯ij−Tij=dijV′¯ij−dijVij.


### 3.4. Risk Assessment

The risk assessment model used in our previous work, which considers risk as the product of the probability of hazmat accident and its consequence, ignores the impact of traffic flow density on the probability of accidents.Taking traffic flow density into account, we improve the method to measure the risk of hazmat vehicles passing reserved lanes. Before lane reservation, hazmat vehicles travel on each lane of arci,j with traffic density of fij/Mij and accident probability of πij. After lane reservation, βfij hazmat vehicles travel on the reserved lane and the probability of hazmat accident can be defined as(4)Pij=πijβfijfij/Mij=βMijπij.


### 3.5. Mathematical Model

In this subsection, we formulate an integer linear bilevel programming model for BHLRP; that is, the objective functions and the constraints are linear. All three decision variables are binary. Moreover, this formulation is under the partial cooperation assumption [27], also called an optimistic BHLRP. This implies that the government assumes that hazmat vehicles’ choice is always the most favorable one when there are multiple costly equivalent alternative travel routes. The model is presented as follows.The UP of BHLRP:(5)Minimizef1=∑w∈W∑i,j∈AEijPijxijw+Eijπijyijw−xijw,(6)Minimizef2=∑i,j∈ACijzij,(7)s.t.∑w∈W∑i,j∈AEijπij−Pijxijw−α∑w∈W∑i,j∈AEijπijy˜ijw≥0,(8)zij∈0,1,∀i,j∈A.The LP of BHLRP:(9)Minimizef3=∑w∈W∑i,j∈AT¯ijxijw+Tijyijw−xijw,(10)s.t.f3=∑w∈W∑i,j∈AT¯ijxijw+Tijyijw−xijw∑j:i,j∈Ayijw−∑j:j,i∈Ayijw=1,∀i=ow,0,∀i≠ow,−1,∀i=dw,∀w∈W,∀i,j∈N,(11)xijw≤yijw,∀i,j∈A,∀w∈W,(12)xijw≤zij,∀i,j∈A,∀w∈W,(13)xijw,yijw∈0,1,∀i,j∈A,∀w∈W.Equations (5)–(8) indicate the UP of the model and equations (9)–(13) show the LP of the model. The objective function (5) is to minimize the transportation risk. The objective function (6) is formulated to minimize the impact on normal traffic caused by the lane reservation strategy. Constraint (7) ensures the total risk should be reduced by α after lane reservation. Constraint (8) shows the 0-1 restriction on the upper decision variable.The objective function (9) seeks to minimize the total time cost of hazmat transportation. Constraint (10) guarantees that hazmat tasks should be transported from origination nodes to destination nodes and the flow balance at each node. Constraint (11) means that a reserved lane i,j may be used for task w only when the task’s path passes the arc i,j. Constraint (12) ensures that a reserved lane i,j may be used by task w only when the lane is reserved. Constraint (13) represents 0-1 restriction on the lower decision variables.


## 3.1. Problem Description

LetG=N,A be a hazmat transportation network, where N is the set of nodes and A is the set of arcs; arc i,j∈A denotes a road segment from node i to node j. Hazmat transportation tasks are described by sets of origins (O⊆N) and destinations (D⊆N).The government has a leading position concerning the hazmat transportation risk, whereas hazmat carriers attempt to minimize their cost. We design a bilevel hazmat lane reservation problem (BHLRP) as depicted in Figure1. The upper level (UP) means the government selects lanes to be reserved considering the interests of hazmat carriers and ordinary travellers. That is done to minimize the transportation risk and the impact on the normal traffic. The lower level (LP) is the optimal path with the lowest cost for each task.Figure 1
Conceptual structure of the bilevel hazmat lane reservation problem.


## 3.2. Assumption and Notation

To better define the problem, we present some assumptions and notations here.


### 3.2.1. Assumptions

(1)
Each road section has at least two lanes so that at least one general lane is in use after lane reservation(2)
When a lane is reserved in the section, hazmat vehicles passing through a road must use the reserved lane(3)
Vehicles are traveling in each section at a constant speed(4)
Potential accidents involving hazmat independently occur, and the probability of hazmat accidents is affected by traffic flow density(5)
There are only two types of vehicles in the road network, namely, hazmat vehicles and ordinary vehiclesDecision variables:(1)zij=1,if there is a reserved lane on arci,j,0,otherwise.xijw=1,if taskwpasses arci,jand there is a reserved lane,0,otherwise.yijw=1if taskwpasses arci,jy˜ijwis the situation before lane reservation0otherwise.


## 3.2.1. Assumptions

(1)
Each road section has at least two lanes so that at least one general lane is in use after lane reservation(2)
When a lane is reserved in the section, hazmat vehicles passing through a road must use the reserved lane(3)
Vehicles are traveling in each section at a constant speed(4)
Potential accidents involving hazmat independently occur, and the probability of hazmat accidents is affected by traffic flow density(5)
There are only two types of vehicles in the road network, namely, hazmat vehicles and ordinary vehiclesDecision variables:(1)zij=1,if there is a reserved lane on arci,j,0,otherwise.xijw=1,if taskwpasses arci,jand there is a reserved lane,0,otherwise.yijw=1if taskwpasses arci,jy˜ijwis the situation before lane reservation0otherwise.


## 3.3. Impact on Normal Traffic

With the development of intelligent transportation network, traffic situations such as speed and traffic density can be obtained by analyzing huge amounts of real traffic data. This provides a new way to further quantify the impact on the normal traffic. We improve this indicator based on the traffic flow by referring to [26].Before implementing the lane reservation strategy, vehicles are evenly distributed on each lane of arci,j and travel at the same speed of Vij. After lane reservation, the traffic d1−βfij/Mij−1 with travel speed V′¯ij seen in equation (2) is derived from the speed-density relationship of traffic flow theory. vm is the optimal speed with the maximum flow. Thus, the impact on the normal traffic in arc i,j, Cij, can be defined by equation (3).(2)V′¯ij=Vij+vmlogMij−1Mij1−β,(3)Cij=T¯ij−Tij=dijV′¯ij−dijVij.


## 3.4. Risk Assessment

The risk assessment model used in our previous work, which considers risk as the product of the probability of hazmat accident and its consequence, ignores the impact of traffic flow density on the probability of accidents.Taking traffic flow density into account, we improve the method to measure the risk of hazmat vehicles passing reserved lanes. Before lane reservation, hazmat vehicles travel on each lane of arci,j with traffic density of fij/Mij and accident probability of πij. After lane reservation, βfij hazmat vehicles travel on the reserved lane and the probability of hazmat accident can be defined as(4)Pij=πijβfijfij/Mij=βMijπij.


## 3.5. Mathematical Model

In this subsection, we formulate an integer linear bilevel programming model for BHLRP; that is, the objective functions and the constraints are linear. All three decision variables are binary. Moreover, this formulation is under the partial cooperation assumption [27], also called an optimistic BHLRP. This implies that the government assumes that hazmat vehicles’ choice is always the most favorable one when there are multiple costly equivalent alternative travel routes. The model is presented as follows.The UP of BHLRP:(5)Minimizef1=∑w∈W∑i,j∈AEijPijxijw+Eijπijyijw−xijw,(6)Minimizef2=∑i,j∈ACijzij,(7)s.t.∑w∈W∑i,j∈AEijπij−Pijxijw−α∑w∈W∑i,j∈AEijπijy˜ijw≥0,(8)zij∈0,1,∀i,j∈A.The LP of BHLRP:(9)Minimizef3=∑w∈W∑i,j∈AT¯ijxijw+Tijyijw−xijw,(10)s.t.f3=∑w∈W∑i,j∈AT¯ijxijw+Tijyijw−xijw∑j:i,j∈Ayijw−∑j:j,i∈Ayijw=1,∀i=ow,0,∀i≠ow,−1,∀i=dw,∀w∈W,∀i,j∈N,(11)xijw≤yijw,∀i,j∈A,∀w∈W,(12)xijw≤zij,∀i,j∈A,∀w∈W,(13)xijw,yijw∈0,1,∀i,j∈A,∀w∈W.Equations (5)–(8) indicate the UP of the model and equations (9)–(13) show the LP of the model. The objective function (5) is to minimize the transportation risk. The objective function (6) is formulated to minimize the impact on normal traffic caused by the lane reservation strategy. Constraint (7) ensures the total risk should be reduced by α after lane reservation. Constraint (8) shows the 0-1 restriction on the upper decision variable.The objective function (9) seeks to minimize the total time cost of hazmat transportation. Constraint (10) guarantees that hazmat tasks should be transported from origination nodes to destination nodes and the flow balance at each node. Constraint (11) means that a reserved lane i,j may be used for task w only when the task’s path passes the arc i,j. Constraint (12) ensures that a reserved lane i,j may be used by task w only when the lane is reserved. Constraint (13) represents 0-1 restriction on the lower decision variables.


## 4. Solution Algorithm

This paper formulates a bilevel optimization model for BHLRP. In addition to the complexity of the routing problem, it is understood that the bilevel model is NP-hard [28]. Several exact methods depend on some characteristics of the solution space, such as the vertex enumeration [29] and the KKT method [11, 14]. These can only solve partial bilevel programming problems [30]. Furthermore, the heuristic algorithm, such as the particle swarm optimization (PSO) [31, 32] and the genetic algorithm (GA) [33, 34], is applied to solving bilevel problems because of its better global search capability and its lower dependence on the form of the objective function.In the bilevel model, we will consider the lane reservation and routing problems simultaneously. The UP has decision priority and can predict the response of the LP to each decision. The LP is a multisource shortest path problem that obeys the shortest path allocation principle. Therefore, we propose a three-stage solution to resolve this problem, presented in Table1. According to the route of tasks, a 0-1 matrix (z0) is introduced in step 1 to represent candidate sections to be reserved. Because there is a task passing through arc i,j, that is, ∑w∈Wyijw≥1, it is a candidate road section with a reserved lane (zij0=1).Table 1
Systematic description of the resolving approach of BHLRP.
Decision typeDecision variablesDecision-makerOutputsStep 1Routingy˜ijwLPThe set of candidate segments to be reservedStep 2LocationzijUPThe layout of reserved lanesStep 3Routingxijw, yijwLPThe shortest path for tasks after lane reservationTo obtain an approximate optimal solution in a reasonable time, based on the three-stage solution, we design two hybrid heuristic algorithms named EX-PSO-EX and EX-GA-EX, combining PSO and GA with the shortest path algorithm, respectively, to solve BHLRP. To verify the effectiveness of the proposed algorithms, there is a benchmark algorithm combining explicit complete enumeration with the shortest path algorithm, named EX-EX-EX. This method is only suitable for solving small-scale examples. The optimal solution obtained by it can be compared to the approximate optimal solution obtained by heuristic algorithms to evaluate their performance. Table2 illustrates the general structure of the three approaches.Table 2
Proposed approaches for solving the BHLRP based on a three-stage strategy.
(1) EX-PSO-EX(2) EX-GA-EX(3) EX-EX-EXStep 1Exact solutionExact solutionExact solutionStep 2Particle swarm optimization algorithmGenetic algorithmExplicit complete enumerationStep 3Exact solutionExact solutionExact solution


### 4.1. Solution Code

In BHLRP, the decision variable of UPzij is binary; thus, a type of layout of reserved lanes z can be represented as a binary matrix of two dimension sn×n. The position i,j equals 1 if there is a reserved lane on arc i,j and 0 otherwise. Figure 2(a) describes a solution to the lane reservation in a 10-node network. As seen in this reservation plan, arcs (4, 5), (4, 6), (6, 4), (7, 8), (8, 9), and (8, 10) are reserved.Figure 2
Solution representation for BHLRP. (a) An example of a network reserved lanes plan matrix with 10 nodes. (b) An example of a routing plan matrix for a task with 10 nodes.
(a)(b)The decision variable of LPyijw is notated as a 0-1 matrix of three dimensions n×n×w. Each page denotes the path of task w. The position i,j,w equals 1 if task w passes arc i,j but 0 otherwise. The path of a task from node 10 to node 4 is displayed in Figure 2(b). The path is 10-8-6-4. The decision variable of LP xijw, obtained by the dot product of yijw and zij, is also expressed in a 0-1 matrix of three dimensions n×n×w.


### 4.2. Fitness Calculation

First, objective functions (6), (6), and the left part of constraint (7) are marked as f1z,f2z, and hz, respectively. As the dimensions of f1z, and f2z are not uniform, after maximum-minimum normalization, we record their linear weighted sum as the new objective function. Then hz is dealt with via the penalty function. Hence, the fitness function can be expressed as(14)fitnessz=λf1z+1−λf2z+Mmax0,hz2,where M is a sufficiently large positive number to indicate the penalty factor.


### 4.3. EX-PSO-EX

In the EX-PSO-EX algorithm, a Sigmoid function is introduced to deal with the velocity of particles when determining the reserved lanes via PSO. Thus, we can ensure the position value of each particle is 0 or 1. Further, the position updated formula is improved as follows:(15)zij=1,if rand≤sVandzij0=1,0,else.The Sigmoid functionsV=1/1+exp−V implies that the probability of value in the next step is 1 by mapping particle velocity V to 0,1 interval. Moreover, zij=1 ensures that the particles update only at the position of candidate sections to be reserved. It ensures the updated particles are still relatively optimal feasible solutions.Additionally, adaptive weight and asynchronous learning factors are used to balance the global search ability and local improvement ability of the PSO algorithm. The updated formulas of the weight and the learning factor are shown in (16) and (17), respectively.(16)ω=ωMin+ωMax−ωMin∗f−fminfavg−fmin,f≤favg,ωMax,f>favg.LetωMax and ωMin, respectively, represent the maximum and minimum values of ω. f is the current fitness value of the particle. Moreover, favg and fmin indicate the average fitness value and the minimum fitness value of all current particles, respectively.(17)cr=tcrf−criMaxIter,r=1,2,where cri and crf are the initial and final values of the iteration of cr, respectively, t is the current number of iterations, and MaxIter denotes the maximum number of iterations. We refer to literature [35] to obtain their values: c1i=c2f=0.5, c1f=c2i=2.5, ωMax=0.9, and ωMin=0.2. Figure 3 shows the pseudocode to solve BHLRP by using the EX-PSO-EX method.Figure 3
Pseudocode of EX-PSO-EX for BHLRP.


### 4.4. EX-GA-EX

By using GA to determine lanes to be reserved in step 2, we propose the second hybrid metaheuristic method, EX-GA-EX. The pseudocode is shown in Figure4. In EX-PSO-EX, binary coding is adopted to code each chromosome into a matrix of n×n, representing a solution for lane reservation.Figure 4
Pseudocode of EX-GA-EX for BHLRP.To search for the solution space effectively, we consider the genetic operators, namely, the ranking selection operator, uniform cross-block operator, and uniform mutation operator, as illustrated in Figure5. To ensure the offspring after crossing and mutation are still a relatively better feasible solution, both the intersection block and mutation location are generated in the candidate segments of lane reservation.Figure 5
Illustration of operators. (a) Crossover operators (crossover points are (1, 3) and (4, 4)). (b) Mutation operators.
(a)(b)


### 4.5. Benchmark Algorithm: EX-EX-EX

In the EX-EX-EX method, we enumerate the solutions of the lane reservation in step 2 completely based on the candidate segments obtained in step 1. To some extent, it minimizes the enumeration space and enumeration quantity. The pseudocode of EX-EX-EX is given in Figure6.Figure 6
Pseudocode of EX-EX-EX for BHLRP.


## 4.1. Solution Code

In BHLRP, the decision variable of UPzij is binary; thus, a type of layout of reserved lanes z can be represented as a binary matrix of two dimension sn×n. The position i,j equals 1 if there is a reserved lane on arc i,j and 0 otherwise. Figure 2(a) describes a solution to the lane reservation in a 10-node network. As seen in this reservation plan, arcs (4, 5), (4, 6), (6, 4), (7, 8), (8, 9), and (8, 10) are reserved.Figure 2
Solution representation for BHLRP. (a) An example of a network reserved lanes plan matrix with 10 nodes. (b) An example of a routing plan matrix for a task with 10 nodes.
(a)(b)The decision variable of LPyijw is notated as a 0-1 matrix of three dimensions n×n×w. Each page denotes the path of task w. The position i,j,w equals 1 if task w passes arc i,j but 0 otherwise. The path of a task from node 10 to node 4 is displayed in Figure 2(b). The path is 10-8-6-4. The decision variable of LP xijw, obtained by the dot product of yijw and zij, is also expressed in a 0-1 matrix of three dimensions n×n×w.


## 4.2. Fitness Calculation

First, objective functions (6), (6), and the left part of constraint (7) are marked as f1z,f2z, and hz, respectively. As the dimensions of f1z, and f2z are not uniform, after maximum-minimum normalization, we record their linear weighted sum as the new objective function. Then hz is dealt with via the penalty function. Hence, the fitness function can be expressed as(14)fitnessz=λf1z+1−λf2z+Mmax0,hz2,where M is a sufficiently large positive number to indicate the penalty factor.


## 4.3. EX-PSO-EX

In the EX-PSO-EX algorithm, a Sigmoid function is introduced to deal with the velocity of particles when determining the reserved lanes via PSO. Thus, we can ensure the position value of each particle is 0 or 1. Further, the position updated formula is improved as follows:(15)zij=1,if rand≤sVandzij0=1,0,else.The Sigmoid functionsV=1/1+exp−V implies that the probability of value in the next step is 1 by mapping particle velocity V to 0,1 interval. Moreover, zij=1 ensures that the particles update only at the position of candidate sections to be reserved. It ensures the updated particles are still relatively optimal feasible solutions.Additionally, adaptive weight and asynchronous learning factors are used to balance the global search ability and local improvement ability of the PSO algorithm. The updated formulas of the weight and the learning factor are shown in (16) and (17), respectively.(16)ω=ωMin+ωMax−ωMin∗f−fminfavg−fmin,f≤favg,ωMax,f>favg.LetωMax and ωMin, respectively, represent the maximum and minimum values of ω. f is the current fitness value of the particle. Moreover, favg and fmin indicate the average fitness value and the minimum fitness value of all current particles, respectively.(17)cr=tcrf−criMaxIter,r=1,2,where cri and crf are the initial and final values of the iteration of cr, respectively, t is the current number of iterations, and MaxIter denotes the maximum number of iterations. We refer to literature [35] to obtain their values: c1i=c2f=0.5, c1f=c2i=2.5, ωMax=0.9, and ωMin=0.2. Figure 3 shows the pseudocode to solve BHLRP by using the EX-PSO-EX method.Figure 3
Pseudocode of EX-PSO-EX for BHLRP.


## 4.4. EX-GA-EX

By using GA to determine lanes to be reserved in step 2, we propose the second hybrid metaheuristic method, EX-GA-EX. The pseudocode is shown in Figure4. In EX-PSO-EX, binary coding is adopted to code each chromosome into a matrix of n×n, representing a solution for lane reservation.Figure 4
Pseudocode of EX-GA-EX for BHLRP.To search for the solution space effectively, we consider the genetic operators, namely, the ranking selection operator, uniform cross-block operator, and uniform mutation operator, as illustrated in Figure5. To ensure the offspring after crossing and mutation are still a relatively better feasible solution, both the intersection block and mutation location are generated in the candidate segments of lane reservation.Figure 5
Illustration of operators. (a) Crossover operators (crossover points are (1, 3) and (4, 4)). (b) Mutation operators.
(a)(b)


## 4.5. Benchmark Algorithm: EX-EX-EX

In the EX-EX-EX method, we enumerate the solutions of the lane reservation in step 2 completely based on the candidate segments obtained in step 1. To some extent, it minimizes the enumeration space and enumeration quantity. The pseudocode of EX-EX-EX is given in Figure6.Figure 6
Pseudocode of EX-EX-EX for BHLRP.


## 5. Computational Results

In this section, computational results are presented to verify the effectiveness of the above model and algorithms and to assess the impact of the key factors. All the proposed hybrid algorithms are encoded with MATLAB 2018 software and all experiments are performed on a server with 3.00 GHz speed and 8 GB RAM.Based on random network topology generator [36], the road network is randomly generated. This approach is presented in Table 3. Then 60 instances of different scales are created ranging from 8 to 100 nodes and from 5 to 30 tasks and different proportions of hazmat vehicles of 0.1-0.2. To ensure the best performance of PSO and GA, combining with the Taguchi Method [29], the parameters for different scale examples are calculated through a large amount of presolving, as shown in Tables 4 and 5.Table 3
Generating the instance problems for the proposed model.
ParametersValueNRandomly and uniformly generated in the plane [0, 100] × [0, 100]ORandomly and uniformly generated fromNDRandomly and uniformly generated fromNdijxi−xj2+yi−y21/2i,jGenerated by a probability function,pi,j=βexp−dij−5/α∗100,0<α,0≤1cijGenerated byU0,1MijGenerated byU2,5VijGenerated byN50,10EijGenerated byU1000,18000πijGenerated bydij∗U8−7,20−7Table 4
Parameters used in EX-PSO-EX.
Factorsn < 2020 ≤n ≤ 4040 <n ≤ 100noP304050MaxIter506070Table 5
Parameters used in EX-GA-EX.
Factorsn < 2020 ≤n ≤ 4040 <n ≤ 100Pop size203040MaxIter203050Crossover rate (PC)0.80.80.9Mutation rate (Pm)0.10.10.2


### 5.1. Comparison of Algorithm Performance

After generating 60 random instances, instances in small scale (n<20) were solved based on the EX-EX-EX approach. Then the EX-PSO-EX and EX-GA-EX approaches were applied to solve all instances. Each instance is solved with different algorithms 15 times and their averages are recorded.The results for small-scale instances are listed in Table6. Columns 2–4 contain the sizes of the instances. The next column shows the number of candidate sections to be reserved (nc). Columns 6-7 show the upper objective function value (fu) of the optimal solution (fu∗) and CPU time obtained by EX-EX-EX. Columns 8–19 show the average value of fu (Average Solution), the percentage deviation of the solution’s mean with respect to fu∗ (Avg), the minimum of fu (Best Solution), the percentage deviation of the solution’s minimum with respect to fu∗ (Best), the standard deviation of fu (Standard Deviation), and the CPU time obtained by EX-PSO-EX and EX-GA-EX, respectively.Table 6
Computational comparison of small scale between EX-EX-EX and EX-PSO-EX and EX-GA-EX withα = 0.1, β = 0.1, and λ = 0.7 (sets 1–15).
Set|N||A|WncEX-EX-EXEX-PSO-EXEX-GA-EXfu∗CPU time (sec)fuCPU time (Sec)fuCPU time (sec)Average SolutionAvgBest SolutionBestStandard DeviationAverage SolutionAvgBest SolutionBestStandard Deviation1816570.3630.2600.3640.0040.3630.0000.0060.2670.3630.0000.3630.0000.0000.74928185100.2112.9330.2120.0050.2110.0000.0040.2690.2110.0000.2110.0000.0000.75138205100.2082.9320.2080.0030.2080.0000.0010.2800.2080.0000.2080.0000.0000.7564822570.3010.2580.3010.0000.3010.0000.0000.2720.3010.0000.3010.0000.0000.7685824570.2370.2620.2370.0000.2370.0000.0000.2780.2370.0000.2370.0000.0000.762610305100.1743.0910.1770.0140.1740.0000.0070.8680.1740.0000.1740.0000.0000.795710325110.2176.8340.2180.0020.2170.0000.0020.5410.2170.0000.2170.0000.0000.804810345100.2453.1290.2450.0000.2450.0000.0000.5570.2450.0000.2450.0000.0000.80791036590.1261.4150.1260.0000.1260.0000.0000.5580.1260.0000.1260.0000.0000.8171010385110.3446.9400.3510.0220.3440.0000.0060.5510.3440.0020.3440.0000.0030.81211157010130.25167.8400.2590.0300.2510.0000.0061.0680.2510.0000.2510.0000.0001.56612157210140.270138.5240.2850.0560.2700.0000.0121.0660.2700.0000.2700.0000.0001.59813157410150.253299.2400.2560.0100.2530.0000.0021.0680.2530.0000.2530.0000.0001.59414157610160.177645.7550.1880.0440.1770.0000.0111.0750.1770.0000.1770.0000.0001.59815157810170.3151381.5170.3230.0250.3160.0030.0041.0670.3170.0040.3150.0000.0031.585Note that the CPU time required by EX-EX-EX is not only affected byN, A, and W but also directly related to nc, exhibiting exponential growth in small-scale examples. Set 15 with only 15 nodes, 78 sections, and 17 candidate sections has been running for up to 1381.517 s. However, with EX-PSO-EX and EX-GA-EX, all sets in Table 6 can obtain their effective approximate optimal solution with CPU time of less than 2 s, which is much lower than EX-EX-EX. Although EX-GA-EX takes a while longer than EX-PSO-EX in most of the examples, the optimal solution of 13 examples is found in each of the 15 runs in Table 6. From the other 6 indicators, such as Average Solution and Avg, the performance of EX-GA-EX is better than that of EX-PSO-EX.To further test the performance of EX-PSO-EX and EX-GA-EX, we use them to solve 15 larger examples. The CPU time to solve them with EX-EX-EX is more than 3600 s. Their Average Solution, Best Solution, Standard Deviation, and the CPU time of each instance are shown in Table7. Additionally, Figure 7 shows the time for solving the 3 methods proposed. Furthermore, the Standard Deviations of sets 1–30 obtained by EX-PSO-EX and EX-GA-EX are illustrated in Figure 8.Table 7
Computational comparison of medium scale and large scale between EX-PSO-EX and EX-GA-EX withW=20, α = 0.1, β = 0.1, and λ = 0.7 (sets 16–30).
Set|N||A|EX-PSO-EXEX-GA-EXfuCPU time (sec)fuCPU time (sec)Average SolutionBest SolutionStandard DeviationAverage SolutionBest SolutionStandard Deviation16201260.2460.2260.0122.6870.2070.2060.0024.12317302860.2820.2650.0113.9070.2360.2340.0025.89118405260.3010.2860.0087.2100.2700.2680.0039.34319456340.2940.2730.0109.0340.2400.2290.00914.83520507820.2210.1990.01110.7160.1860.1820.00218.00521559360.3260.2980.01411.9640.2780.2670.00717.348226011140.3050.2830.01114.0800.2630.2570.00423.276236512980.3080.2820.01015.8000.2540.2460.00623.730247014980.2730.2560.00818.0950.2400.2360.00326.656257517160.2700.2450.01220.7530.2270.2200.00636.752268019540.3010.2790.01424.9100.2480.2320.00947.277278521520.3080.2830.01230.8850.2640.2590.00560.051289024040.2870.2730.01034.5000.2440.2370.00468.128299527100.3290.3110.01038.9000.2940.2870.00575.8283010029480.2840.2710.00742.4840.2440.2360.00585.214Figure 7
Comparison of CPU time in EX-EX-EX, EX-PSO-EX, and EX-GA-EX (sets 1–30).Figure 8
Comparison of standard deviation of the value of the objective function in EX-PSO-EX and EX-GA-EX (sets 1–30).In terms of average CPU time, it takes 85.214 s to solve set 30 with EX-GA-EX, while EX-GA-EX consumes about half the time taken by EX-PSO-EX. However, the performance of EX-GA-EX in the optimal and average solution quality is better. The maximum standard deviation is only 0.014. The results show that, even in larger instances, the performance of EX-PSO-EX and EX-GA-EX is robust, which can be used as an effective method to solve the problem of lane selection for BHLRP.


### 5.2. Sensitivity Analysis

To make a trade-off between the effect of risk reduction and the impact on the normal traffic, it is necessary to further evaluate the effectiveness of lane reservation solutions with different numbers of tasks and hazmat vehicle ratios. Two scenarios are set up and each scenario tests several instance sets.Considering the good performance of EX-GA-EX in different scales, we use it to solve each set 15 times and record and use the average value obtained. The evaluation results are shown in Tables8–11 and Figures 9-10.Table 8
Result of experiments with variedW, when α = 0.1, β = 0.1, and λ = 0.7.
Set|N||A|WNumber of reserved lanesRiskΔRiskRelative change in risk (%)Effectfu3120126571.5001.81554.7450.5170.2613210112.0953.93565.2551.1740.2583315172.9195.21564.1151.8750.2341620215.1546.90557.2601.6170.2073425226.40510.52062.1561.9470.2183530287.12910.77460.1782.3890.2823630286582.0751.87154.7450.3310.3133710102.3902.60765.2550.5340.2253815163.0343.91064.1151.3050.2401720225.2526.42457.2601.4340.2363925247.71310.19762.1562.1560.25840303310.95913.34160.1782.2210.2454140526571.6241.63350.1290.3620.2954210133.0043.44353.4070.9520.3154315193.0044.18058.1821.3290.2621820234.9378.21362.4581.9250.2704425315.8027.99457.9462.0450.2864530357.2509.48956.6902.3010.259Table 9
Result of experiments with varied |W|, whenα = 0.1, β = 0.1, and λ = 0.7.
|N||A|ΔRisk/effectW = 5W = 10W = 15W = 20W = 25W = 30201263.5143.3532.7824.2695.4034.509302865.6524.8852.9964.4814.7286.007405264.5083.6173.1464.2683.9104.123Average ratio4.5583.9522.9744.3394.6804.880Table 10
Result of experiments with variedβ, when W = 20, α = 0.1, and λ = 0.7.
Set|N||A|βNumber of reserved lanesRiskΔRiskΔRisk/number of reserved lanesEffectfu16201260.1215.1466.9130.3291.6320.208460.12215.9926.0660.2921.4300.268470.14216.8015.2570.2531.2640.328480.16217.6074.4510.2131.1190.389490.18218.6673.3910.1630.8010.459500.2199.4952.5630.1380.6280.51917302860.1225.2486.4290.2901.4210.234510.12235.8905.7870.2521.4000.237520.14236.6425.0350.2181.3720.239530.16247.1314.5460.1921.3410.243540.18247.8523.8240.1591.3420.244550.2208.6513.0250.1541.1580.24718405260.1234.8938.2570.3571.9410.269560.12225.5857.5650.3371.7620.267570.14216.4486.7020.3151.5820.280580.16227.1545.9960.2761.5090.294590.18227.8275.3230.2431.3550.296600.2208.5044.6460.2381.1980.298Table 11
Result of experiments with variedβ, when W = 20, α = 0.1, and λ = 0.7.
|N||A|ΔRisk/effectβ = 0.1β = 0.12β = 0.14β = 0.16β = 0.18β = 0.2201264.2364.2414.1603.9774.2334.080302864.5254.1323.9593.1552.8492.613405264.2554.2954.2353.9733.9283.877Average ratio4.5254.2234.1183.7023.6703.523Figure 9
The trend of the average ratio asW increases.Figure 10
The trend of the average ratio asβ increases.


#### 5.2.1. Effect of the Number of Tasks (W)

The number of tasks reflects the size of the examples. Table8 shows average computational results of the scenario where W varies from 5 to 30 in three networks, 20 × 126, 30 × 286, and 40 × 526. The results include the number of reserved lanes, the risk, the decreased risk compared to the risk before lane reservation (Risk), the relative change in risk, the impact on normal traffic (Effect), and fu. Firstly, after lane reservation, the value of fu is much smaller than 1, the value of fu before lane reservation, and the relative reduction of the risk exceeds 50%. This indicates that the effect of lane reservation in reducing the risk of hazmat transportation is very significant. Secondly, with the increase in W, reserved lanes need to be set up on more sections. At this time, the risk, Risk, and Effect show an obvious increasing trend; however, the effect of reserved lanes to reduce the risk is increasingly obvious. The increase in risk is mainly due to the increase in the total risk with the increase in W. It is not difficult to imagine that if there are no reserved lanes, then total risk will increase more; the increase in Risk and Effect is due to the increase in the number of road sections with reserved roads.To evaluate the effectiveness of reserved lanes with varied |W|, Table9 shows the ratio of Risk and Effect (Risk/Effect) under three different networks and their average ratio. Figure 9 shows the trend of the average ratio. The results show that, with the increase in W, there is a trend of increasing after decreasing. When W is small, the decrease shows that reducing the same risk will have a greater impact on the normal traffic. This is mainly because fewer sections can be shared between tasks so that additional reserved lanes need to be set up to meet the risk reduction needs. Then the number of affected sections will increase. When W increases to 15 or more, Risk/Effect rises instead. It is not possible to set up new reserved lanes. There will be more of same road sections between tasks; that is, the utilization rate will be improved. Therefore, the utilization rate of reserved lanes is very important to ensure the effectiveness of the lane reservation.


#### 5.2.2. Effect of the Proportion of Hazmat Vehicles (β)

The proportion of hazmat vehiclesβ will affect the traffic flow density on these two kinds of lanes after lane reservation. It will have an impact on the risk and the normal traffic. To evaluate the effectiveness of reserved lanes with varied β, Table 10 shows the average computational results of the scenario where β varies from 0.1 to 0.2 in three networks, 20 × 126, 30 × 286, and 40 × 526. With the increase in β, fu and the risk increase, while Risk and the reduced risk per lane (Risk/Number of reserved lanes) decrease, which reflects the decline in the effect of reserved lanes on risk reduction. The main reason is that more hazmat vehicles can travel on reserved lanes. The traffic flow density on reserved lanes will increase relatively. It will increase the probability of accident to some extent. Reduction of Effect can be attributed to the fact that fewer ordinary vehicles travel at a slower speed. Additionally, the traffic flow density on GP lanes decreases, which will reduce the impact on the traffic time on GP lanes.The result shows that the number of reserved lanes does not necessarily increase with the proportion of hazmat vehicles. This indicates that more sections are affected. Thus, the time for ordinary vehicles to travel through these lanes will be longer. Additionally, ifβ is increased to a certain extent, the advantage of reserved lanes to reduce risk will be no longer obvious. This also reflects the validity of the model to a certain extent.Table11 shows Risk/Effect under three different networks with varied β and the average ratio. Figure 10 shows the trend of the average ratio. With the increase in β, Risk/Effect decreases from 4.525 to 3.523. Although the utilization of reserved lanes will improve, the optimization effect becomes decreasingly significant. When the proportion is sufficiently large to have a negative impact on the free flow on reserved lanes, the advantage of lane reservation to risk reduction will gradually decrease. Especially in some road sections where β≥1/Mij, the traffic flow density on the reserved lane after lane reservation will be greater than that on each lane before lane reservation. This may signify that it may not be sufficient to set up only one reserved lane in these sections.


## 5.1. Comparison of Algorithm Performance

After generating 60 random instances, instances in small scale (n<20) were solved based on the EX-EX-EX approach. Then the EX-PSO-EX and EX-GA-EX approaches were applied to solve all instances. Each instance is solved with different algorithms 15 times and their averages are recorded.The results for small-scale instances are listed in Table6. Columns 2–4 contain the sizes of the instances. The next column shows the number of candidate sections to be reserved (nc). Columns 6-7 show the upper objective function value (fu) of the optimal solution (fu∗) and CPU time obtained by EX-EX-EX. Columns 8–19 show the average value of fu (Average Solution), the percentage deviation of the solution’s mean with respect to fu∗ (Avg), the minimum of fu (Best Solution), the percentage deviation of the solution’s minimum with respect to fu∗ (Best), the standard deviation of fu (Standard Deviation), and the CPU time obtained by EX-PSO-EX and EX-GA-EX, respectively.Table 6
Computational comparison of small scale between EX-EX-EX and EX-PSO-EX and EX-GA-EX withα = 0.1, β = 0.1, and λ = 0.7 (sets 1–15).
Set|N||A|WncEX-EX-EXEX-PSO-EXEX-GA-EXfu∗CPU time (sec)fuCPU time (Sec)fuCPU time (sec)Average SolutionAvgBest SolutionBestStandard DeviationAverage SolutionAvgBest SolutionBestStandard Deviation1816570.3630.2600.3640.0040.3630.0000.0060.2670.3630.0000.3630.0000.0000.74928185100.2112.9330.2120.0050.2110.0000.0040.2690.2110.0000.2110.0000.0000.75138205100.2082.9320.2080.0030.2080.0000.0010.2800.2080.0000.2080.0000.0000.7564822570.3010.2580.3010.0000.3010.0000.0000.2720.3010.0000.3010.0000.0000.7685824570.2370.2620.2370.0000.2370.0000.0000.2780.2370.0000.2370.0000.0000.762610305100.1743.0910.1770.0140.1740.0000.0070.8680.1740.0000.1740.0000.0000.795710325110.2176.8340.2180.0020.2170.0000.0020.5410.2170.0000.2170.0000.0000.804810345100.2453.1290.2450.0000.2450.0000.0000.5570.2450.0000.2450.0000.0000.80791036590.1261.4150.1260.0000.1260.0000.0000.5580.1260.0000.1260.0000.0000.8171010385110.3446.9400.3510.0220.3440.0000.0060.5510.3440.0020.3440.0000.0030.81211157010130.25167.8400.2590.0300.2510.0000.0061.0680.2510.0000.2510.0000.0001.56612157210140.270138.5240.2850.0560.2700.0000.0121.0660.2700.0000.2700.0000.0001.59813157410150.253299.2400.2560.0100.2530.0000.0021.0680.2530.0000.2530.0000.0001.59414157610160.177645.7550.1880.0440.1770.0000.0111.0750.1770.0000.1770.0000.0001.59815157810170.3151381.5170.3230.0250.3160.0030.0041.0670.3170.0040.3150.0000.0031.585Note that the CPU time required by EX-EX-EX is not only affected byN, A, and W but also directly related to nc, exhibiting exponential growth in small-scale examples. Set 15 with only 15 nodes, 78 sections, and 17 candidate sections has been running for up to 1381.517 s. However, with EX-PSO-EX and EX-GA-EX, all sets in Table 6 can obtain their effective approximate optimal solution with CPU time of less than 2 s, which is much lower than EX-EX-EX. Although EX-GA-EX takes a while longer than EX-PSO-EX in most of the examples, the optimal solution of 13 examples is found in each of the 15 runs in Table 6. From the other 6 indicators, such as Average Solution and Avg, the performance of EX-GA-EX is better than that of EX-PSO-EX.To further test the performance of EX-PSO-EX and EX-GA-EX, we use them to solve 15 larger examples. The CPU time to solve them with EX-EX-EX is more than 3600 s. Their Average Solution, Best Solution, Standard Deviation, and the CPU time of each instance are shown in Table7. Additionally, Figure 7 shows the time for solving the 3 methods proposed. Furthermore, the Standard Deviations of sets 1–30 obtained by EX-PSO-EX and EX-GA-EX are illustrated in Figure 8.Table 7
Computational comparison of medium scale and large scale between EX-PSO-EX and EX-GA-EX withW=20, α = 0.1, β = 0.1, and λ = 0.7 (sets 16–30).
Set|N||A|EX-PSO-EXEX-GA-EXfuCPU time (sec)fuCPU time (sec)Average SolutionBest SolutionStandard DeviationAverage SolutionBest SolutionStandard Deviation16201260.2460.2260.0122.6870.2070.2060.0024.12317302860.2820.2650.0113.9070.2360.2340.0025.89118405260.3010.2860.0087.2100.2700.2680.0039.34319456340.2940.2730.0109.0340.2400.2290.00914.83520507820.2210.1990.01110.7160.1860.1820.00218.00521559360.3260.2980.01411.9640.2780.2670.00717.348226011140.3050.2830.01114.0800.2630.2570.00423.276236512980.3080.2820.01015.8000.2540.2460.00623.730247014980.2730.2560.00818.0950.2400.2360.00326.656257517160.2700.2450.01220.7530.2270.2200.00636.752268019540.3010.2790.01424.9100.2480.2320.00947.277278521520.3080.2830.01230.8850.2640.2590.00560.051289024040.2870.2730.01034.5000.2440.2370.00468.128299527100.3290.3110.01038.9000.2940.2870.00575.8283010029480.2840.2710.00742.4840.2440.2360.00585.214Figure 7
Comparison of CPU time in EX-EX-EX, EX-PSO-EX, and EX-GA-EX (sets 1–30).Figure 8
Comparison of standard deviation of the value of the objective function in EX-PSO-EX and EX-GA-EX (sets 1–30).In terms of average CPU time, it takes 85.214 s to solve set 30 with EX-GA-EX, while EX-GA-EX consumes about half the time taken by EX-PSO-EX. However, the performance of EX-GA-EX in the optimal and average solution quality is better. The maximum standard deviation is only 0.014. The results show that, even in larger instances, the performance of EX-PSO-EX and EX-GA-EX is robust, which can be used as an effective method to solve the problem of lane selection for BHLRP.


## 5.2. Sensitivity Analysis

To make a trade-off between the effect of risk reduction and the impact on the normal traffic, it is necessary to further evaluate the effectiveness of lane reservation solutions with different numbers of tasks and hazmat vehicle ratios. Two scenarios are set up and each scenario tests several instance sets.Considering the good performance of EX-GA-EX in different scales, we use it to solve each set 15 times and record and use the average value obtained. The evaluation results are shown in Tables8–11 and Figures 9-10.Table 8
Result of experiments with variedW, when α = 0.1, β = 0.1, and λ = 0.7.
Set|N||A|WNumber of reserved lanesRiskΔRiskRelative change in risk (%)Effectfu3120126571.5001.81554.7450.5170.2613210112.0953.93565.2551.1740.2583315172.9195.21564.1151.8750.2341620215.1546.90557.2601.6170.2073425226.40510.52062.1561.9470.2183530287.12910.77460.1782.3890.2823630286582.0751.87154.7450.3310.3133710102.3902.60765.2550.5340.2253815163.0343.91064.1151.3050.2401720225.2526.42457.2601.4340.2363925247.71310.19762.1562.1560.25840303310.95913.34160.1782.2210.2454140526571.6241.63350.1290.3620.2954210133.0043.44353.4070.9520.3154315193.0044.18058.1821.3290.2621820234.9378.21362.4581.9250.2704425315.8027.99457.9462.0450.2864530357.2509.48956.6902.3010.259Table 9
Result of experiments with varied |W|, whenα = 0.1, β = 0.1, and λ = 0.7.
|N||A|ΔRisk/effectW = 5W = 10W = 15W = 20W = 25W = 30201263.5143.3532.7824.2695.4034.509302865.6524.8852.9964.4814.7286.007405264.5083.6173.1464.2683.9104.123Average ratio4.5583.9522.9744.3394.6804.880Table 10
Result of experiments with variedβ, when W = 20, α = 0.1, and λ = 0.7.
Set|N||A|βNumber of reserved lanesRiskΔRiskΔRisk/number of reserved lanesEffectfu16201260.1215.1466.9130.3291.6320.208460.12215.9926.0660.2921.4300.268470.14216.8015.2570.2531.2640.328480.16217.6074.4510.2131.1190.389490.18218.6673.3910.1630.8010.459500.2199.4952.5630.1380.6280.51917302860.1225.2486.4290.2901.4210.234510.12235.8905.7870.2521.4000.237520.14236.6425.0350.2181.3720.239530.16247.1314.5460.1921.3410.243540.18247.8523.8240.1591.3420.244550.2208.6513.0250.1541.1580.24718405260.1234.8938.2570.3571.9410.269560.12225.5857.5650.3371.7620.267570.14216.4486.7020.3151.5820.280580.16227.1545.9960.2761.5090.294590.18227.8275.3230.2431.3550.296600.2208.5044.6460.2381.1980.298Table 11
Result of experiments with variedβ, when W = 20, α = 0.1, and λ = 0.7.
|N||A|ΔRisk/effectβ = 0.1β = 0.12β = 0.14β = 0.16β = 0.18β = 0.2201264.2364.2414.1603.9774.2334.080302864.5254.1323.9593.1552.8492.613405264.2554.2954.2353.9733.9283.877Average ratio4.5254.2234.1183.7023.6703.523Figure 9
The trend of the average ratio asW increases.Figure 10
The trend of the average ratio asβ increases.


### 5.2.1. Effect of the Number of Tasks (W)

The number of tasks reflects the size of the examples. Table8 shows average computational results of the scenario where W varies from 5 to 30 in three networks, 20 × 126, 30 × 286, and 40 × 526. The results include the number of reserved lanes, the risk, the decreased risk compared to the risk before lane reservation (Risk), the relative change in risk, the impact on normal traffic (Effect), and fu. Firstly, after lane reservation, the value of fu is much smaller than 1, the value of fu before lane reservation, and the relative reduction of the risk exceeds 50%. This indicates that the effect of lane reservation in reducing the risk of hazmat transportation is very significant. Secondly, with the increase in W, reserved lanes need to be set up on more sections. At this time, the risk, Risk, and Effect show an obvious increasing trend; however, the effect of reserved lanes to reduce the risk is increasingly obvious. The increase in risk is mainly due to the increase in the total risk with the increase in W. It is not difficult to imagine that if there are no reserved lanes, then total risk will increase more; the increase in Risk and Effect is due to the increase in the number of road sections with reserved roads.To evaluate the effectiveness of reserved lanes with varied |W|, Table9 shows the ratio of Risk and Effect (Risk/Effect) under three different networks and their average ratio. Figure 9 shows the trend of the average ratio. The results show that, with the increase in W, there is a trend of increasing after decreasing. When W is small, the decrease shows that reducing the same risk will have a greater impact on the normal traffic. This is mainly because fewer sections can be shared between tasks so that additional reserved lanes need to be set up to meet the risk reduction needs. Then the number of affected sections will increase. When W increases to 15 or more, Risk/Effect rises instead. It is not possible to set up new reserved lanes. There will be more of same road sections between tasks; that is, the utilization rate will be improved. Therefore, the utilization rate of reserved lanes is very important to ensure the effectiveness of the lane reservation.


### 5.2.2. Effect of the Proportion of Hazmat Vehicles (β)

The proportion of hazmat vehiclesβ will affect the traffic flow density on these two kinds of lanes after lane reservation. It will have an impact on the risk and the normal traffic. To evaluate the effectiveness of reserved lanes with varied β, Table 10 shows the average computational results of the scenario where β varies from 0.1 to 0.2 in three networks, 20 × 126, 30 × 286, and 40 × 526. With the increase in β, fu and the risk increase, while Risk and the reduced risk per lane (Risk/Number of reserved lanes) decrease, which reflects the decline in the effect of reserved lanes on risk reduction. The main reason is that more hazmat vehicles can travel on reserved lanes. The traffic flow density on reserved lanes will increase relatively. It will increase the probability of accident to some extent. Reduction of Effect can be attributed to the fact that fewer ordinary vehicles travel at a slower speed. Additionally, the traffic flow density on GP lanes decreases, which will reduce the impact on the traffic time on GP lanes.The result shows that the number of reserved lanes does not necessarily increase with the proportion of hazmat vehicles. This indicates that more sections are affected. Thus, the time for ordinary vehicles to travel through these lanes will be longer. Additionally, ifβ is increased to a certain extent, the advantage of reserved lanes to reduce risk will be no longer obvious. This also reflects the validity of the model to a certain extent.Table11 shows Risk/Effect under three different networks with varied β and the average ratio. Figure 10 shows the trend of the average ratio. With the increase in β, Risk/Effect decreases from 4.525 to 3.523. Although the utilization of reserved lanes will improve, the optimization effect becomes decreasingly significant. When the proportion is sufficiently large to have a negative impact on the free flow on reserved lanes, the advantage of lane reservation to risk reduction will gradually decrease. Especially in some road sections where β≥1/Mij, the traffic flow density on the reserved lane after lane reservation will be greater than that on each lane before lane reservation. This may signify that it may not be sufficient to set up only one reserved lane in these sections.


## 5.2.1. Effect of the Number of Tasks (W)

The number of tasks reflects the size of the examples. Table8 shows average computational results of the scenario where W varies from 5 to 30 in three networks, 20 × 126, 30 × 286, and 40 × 526. The results include the number of reserved lanes, the risk, the decreased risk compared to the risk before lane reservation (Risk), the relative change in risk, the impact on normal traffic (Effect), and fu. Firstly, after lane reservation, the value of fu is much smaller than 1, the value of fu before lane reservation, and the relative reduction of the risk exceeds 50%. This indicates that the effect of lane reservation in reducing the risk of hazmat transportation is very significant. Secondly, with the increase in W, reserved lanes need to be set up on more sections. At this time, the risk, Risk, and Effect show an obvious increasing trend; however, the effect of reserved lanes to reduce the risk is increasingly obvious. The increase in risk is mainly due to the increase in the total risk with the increase in W. It is not difficult to imagine that if there are no reserved lanes, then total risk will increase more; the increase in Risk and Effect is due to the increase in the number of road sections with reserved roads.To evaluate the effectiveness of reserved lanes with varied |W|, Table9 shows the ratio of Risk and Effect (Risk/Effect) under three different networks and their average ratio. Figure 9 shows the trend of the average ratio. The results show that, with the increase in W, there is a trend of increasing after decreasing. When W is small, the decrease shows that reducing the same risk will have a greater impact on the normal traffic. This is mainly because fewer sections can be shared between tasks so that additional reserved lanes need to be set up to meet the risk reduction needs. Then the number of affected sections will increase. When W increases to 15 or more, Risk/Effect rises instead. It is not possible to set up new reserved lanes. There will be more of same road sections between tasks; that is, the utilization rate will be improved. Therefore, the utilization rate of reserved lanes is very important to ensure the effectiveness of the lane reservation.


## 5.2.2. Effect of the Proportion of Hazmat Vehicles (β)

The proportion of hazmat vehiclesβ will affect the traffic flow density on these two kinds of lanes after lane reservation. It will have an impact on the risk and the normal traffic. To evaluate the effectiveness of reserved lanes with varied β, Table 10 shows the average computational results of the scenario where β varies from 0.1 to 0.2 in three networks, 20 × 126, 30 × 286, and 40 × 526. With the increase in β, fu and the risk increase, while Risk and the reduced risk per lane (Risk/Number of reserved lanes) decrease, which reflects the decline in the effect of reserved lanes on risk reduction. The main reason is that more hazmat vehicles can travel on reserved lanes. The traffic flow density on reserved lanes will increase relatively. It will increase the probability of accident to some extent. Reduction of Effect can be attributed to the fact that fewer ordinary vehicles travel at a slower speed. Additionally, the traffic flow density on GP lanes decreases, which will reduce the impact on the traffic time on GP lanes.The result shows that the number of reserved lanes does not necessarily increase with the proportion of hazmat vehicles. This indicates that more sections are affected. Thus, the time for ordinary vehicles to travel through these lanes will be longer. Additionally, ifβ is increased to a certain extent, the advantage of reserved lanes to reduce risk will be no longer obvious. This also reflects the validity of the model to a certain extent.Table11 shows Risk/Effect under three different networks with varied β and the average ratio. Figure 10 shows the trend of the average ratio. With the increase in β, Risk/Effect decreases from 4.525 to 3.523. Although the utilization of reserved lanes will improve, the optimization effect becomes decreasingly significant. When the proportion is sufficiently large to have a negative impact on the free flow on reserved lanes, the advantage of lane reservation to risk reduction will gradually decrease. Especially in some road sections where β≥1/Mij, the traffic flow density on the reserved lane after lane reservation will be greater than that on each lane before lane reservation. This may signify that it may not be sufficient to set up only one reserved lane in these sections.


## 6. Conclusion

In this study, the problem of hazmat transportation with lane reservation is studied. A bilevel multiobjective model is established for the problem. The measure of the risk and the impact on the normal traffic is improved by incorporating specific traffic information, such as traffic flow. Subsequently we design two hybrid metaheuristic algorithms and an exact algorithm to solve the model. To validate the model and algorithms, 60 examples are created and the sensitivity analysis of two key factors (the number of transportation tasks and the proportion of hazmat vehicles) is conducted. The main conclusions are as follows:(1)
The bilevel optimization model for the hazmat transportation problem with the lane reservation can significantly reduce the risk of the hazmat transportation while considering the interests of hazmat enterprises and ordinary travellers.(2)
The proposed hybrid metaheuristic algorithms can obtain effective approximate optimal solutions while greatly reducing the solution time. EX-PSO-EX is superior to EX-GA-EX in CPU time. EX-GA-EX has more advantages in the average and optimal solution quality of the approximate optimal solution.(3)
The utilization of reserved lanes will affect the effectiveness of risk reduction. To a certain extent, the increase in transportation tasks will improve the utilization of reserved lanes. When the proportion of hazmat vehicles is enough to have a negative impact on the free flow on the reserved lane, the advantage of reducing the risk of the reserved lane will gradually decrease.(4)
In sections where hazmat vehicles are particularly dense,β≥1/Mij, it may not be enough to set up only one reserved lane. The government should consider the road network structure, the vehicle composition ratio, and other relevant traffic data when selecting reserved lanes to further weigh the effect of risk reduction and the impact on normal traffic.The model we propose does not consider the impact of time-varying conditions and other uncertainties on transportation risk, neither does it consider the impact of social vehicles on hazmat vehicles. Therefore, making the model closer to the actual situation is a further research direction. Another future work may be to consider the integration of lane reservation and other regulation policies. Additionally, in order to effectively reduce the risk and improve the utilization of existing transportation infrastructure of urban areas, a dynamic lane reservation for hazmat transportation may be a more applicable choice based on the actual traffic state and the regulation of traffic state information.



---

*Source: 2530154-2020-07-08.xml*