# Evaluation of Transportation Network Reliability under Emergency Based on Reserve Capacity

Authors: Xiongfei Zhang; Qi Zhong; Qin Luo
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

There are differences between the requirements for traffic network for traffic demand in daily and emergency situations. In order to evaluate how the network designed for daily needs can meet the surging demand for emergency evacuation, the concept of emergency reliability and corresponding evaluation method is proposed. This paper constructs a bilevel programming model to describe the proposed problem. The upper level problem takes the maximum reserve capacity multiplier as the optimization objective and considers the influence of reversible lane measures taken under emergency conditions. The lower level model adopts the combined traffic distribution/assignment model with capacity limits, to describe evacuees’ path and shelter choice behavior under emergency conditions and take into account the traits of crowded traffic. An iterative optimization method is proposed to solve the upper level model, and the lower level model is transformed into a UE assignment problem with capacity limits over a network of multiple origins and single destination, by adding a dummy node and several dummy links in the network. Then a dynamic penalty function algorithm is used to solve the problem. In the end, numerical studies and results are provided to demonstrate the rationality of the proposed model and feasibility of the proposed solution algorithms.


---

## Body

## 1. Introduction

In recent decades, the frequent occurrence of emergencies around the world has caused certain casualties and property losses, posing a great challenge to public security. Especially when these emergencies occur in densely populated urban areas, they are undoubtedly becoming a burden to the already crowded urban traffic. This premise puts forward higher requirements for traffic network under emergency.Apparently, different from the daily demand of the traffic network, the traffic demand under emergency conditions has an evident feature of unidirection and will surge within a short time. As a result, the existing capacity of road infrastructures is usually not able to meet the demand of evacuation.To investigate the maximum emergency evacuation demand that can be satisfied by the network designed for daily needs, this paper analyzes the traffic demand under emergency conditions and takes the emergency reliability of traffic network as the research target.Meanwhile, so as to take full advantage of the finite road resources, ease the traffic pressure which exceeds the load of the road network, increase the evacuation capacity of the road network, and improve the evacuation efficiency, traffic managers will take certain emergency traffic management measures, such as lane reversal. Hence, when studying the traffic network emergency reliability, we should not only consider the particularity of emergency traffic demand, but also consider the impact of these measures on the network service capacity at the same time. As a result, the network under this situation can be deemed as a variable one with capacity constraints, which is more in line with the traits of traffic supply and demand in an emergency.The remainder of this paper is organized as follows: Section2 is the literature review. Section 3 is the problem statement. Section 4 establishes the mathematical model and Section 5 proposes the solution algorithm. Section 6 is the case study. Section 7 summarizes the conclusions.


## 2. Literature Review

Traffic reliability research began in the 1980s. Over the past decade, transportation reliability has been a new avenue for advancing transportation research in terms of both theories and practical applications, and has attracted tremendous effort over the past few years [1]. Chen first introduced capacity reliability as a new network performance index [2]. In general, it is defined as one of the important indexes to measure traffic network quality and evaluate network operation state. The higher the reliability of the road network, the more stable the overall operation of the road network, indicating that the structure of the road network is reasonable, with strong anti-interference ability. Existing reliability studies of road networks at home and abroad mainly include the following three categories: connectivity reliability, travel time reliability, and capacity reliability.Chang [3] analyzed with different paths failure strategy quantificationally by measuring the betweenness centrality of the paths so as to study the reliability of highway and transportation network. Li [4] proposed a method to calculate connectivity reliability of shortest path in the network model of complex system. Based on the concept of network connectivity reliability, Harun [5] discussed the assessment of road maintenance and network capacity expansion planning, revealed the relationship between network capacity expansion and connectivity reliability.Wael [6] investigated the impact of roadworks undertaken on a given road link over wider parts of the network and assessed network travel time reliability by setting up a network assignment model. Sabyasachee [7] proposed a method based on empirically observed travel time data, to measure and determine the value of travel time reliability, estimate changes in it, and incorporate reliability in the transportation planning process. Vincenza [8] proposed a methodology for estimating travel time reliability of an extended road network, through the calibration of empirical relations and the finding’s representation on GIS maps with a dynamic simulation model. Taking into account the influence of travel time variability on the congestion profile, Roxana [9] addressed the valuation of travel time reliability in the presence of endogenous congestion and the role of scheduling preferences.Researches in capacity reliability mainly concern about the max-flow of the network in early stage, especially in transportation network. Capacity reliability is defined as the largest multiplier applied to a given existing (or basic) OD demand matrix that can be allocated to a network without violating the link capacities [10]. Chen [2] extended the capacity reliability analysis by providing a comprehensive methodology, which combines reliability and uncertainty analysis, network equilibrium models, and sensitivity analysis of equilibrium network flow, to assess the performance of a degradable road network. To evaluate capacity reliability, Kuang [11] built up a bilevel programming model based on travel time reliability, concerning OD traffic demand multiplier, and investigated the interaction between two kinds of reliability. Lee [12] proposed a capacity reliability algorithm with Monte Carlo simulation in communication network based on the shortest delay which can indicate the delay’s transient variation caused by flow fluctuation. Qin [13] considered quantity of emergency resources, reserve capacity, and number of locations and built an optimization model for emergency resource layout considering service reliability, in which the objective function is to minimize the system cost and various constraints are considered.The reliability of road network under extreme conditions is very important. In the case of not considering the road damage, how much margin a network has to accommodate emergency traffic demand is an important question that needs to be considered in traffic network design. Based on capacity reliability, this paper evaluates traffic network reliability under emergency conditions from planning perspective.


## 3. Problem Statements

This section first analyzes the characteristics of evacuation traffic flow, then summarizes emergency traffic management measures under emergency conditions, and finally leads to the establishment of emergency reliability concept.


### 3.1. Traffic Flow Characteristics under Emergency Conditions

Different from the traffic state under daily conditions, the traffic state under emergency evacuation has the characteristics of suddenness, high risk, contingency, and so on. In general, emergency evacuation traffic has the following characteristics.(1) Large and Centralized Demand.From the perspective of space, the origin node of emergency evacuation traffic demand is concentrated in the influenced area. And from the perspective of time, traffic demand for emergency evacuation is basically concentrated in a short period of time before and after the disaster, and people need to be evacuated to a safe area in a short time. This leads to the uneven spatial and temporal distribution of traffic flow directly [14]. In the case of emergencies, the peak of travel demand is several times higher than the peak of daily travel demand, which brings great difficulties to the traffic management of emergency evacuation.(2) Characteristics of Crowded Traffic Flow.Due to the large and centralized traffic demand, a large number of crowded points and congested sections will inevitably appear in the traffic network. The traffic flow on the road is basically saturated or oversaturated, and the evacuation traffic flow is basically in the following state, so it is difficult to find an acceptable gap for overtaking [15]. Therefore, emergency evacuation traffic network is a network with congestion influence.(3) High Reliability Requirement.Sudden disasters threaten people’s life and property safety, so emergency evacuees have higher requirements on the reliability of whether they can be quickly evacuated to a safe area. The reliability requirements are as follows: network connectivity reliability, road capacity reliability, travel time reliability, etc.(4) Uneven Flow of Both Directions.In the process of evacuation, the traffic flow from the affected area to other refuge areas is usually large, resulting in oversaturation and serious traffic congestion. However, the traffic flow into the evacuation zone is small, and most lanes are idle.


### 3.2. Emergency Traffic Management strategies

Depending on traffic flow characteristics under emergency conditions, there are several emergency traffic management measures that are commonly used in practice. The purpose is to improve evacuation efficiency and reduce casualties and property losses.(1) Staged Evacuation Strategy.Staged evacuation strategy is widely used in emergency situations when different parts of the target network may suffer different levels of severity over different time windows. By evacuating those populations in the network via an optimized sequence, the staged evacuation strategy can best utilize available roadway capacity, optimally distribute the total demand over the evacuation time horizon, and thus minimize the network congestion level [16, 17].(2) Lane Reversal.In order to alleviate the one-way traffic demand in emergency evacuation which is far beyond the capacity of the road network, the direction of one or more lanes of the road can be reversed to increase the capacity of evacuation direction [15].(3) Crossing Elimination Strategy.The delay of evacuation vehicles mainly occurs at intersections, which is caused by the conflict and interweaving of evacuation flows from different directions. The interference of evacuation traffic flow can be reduced by eliminating or reducing the confluence point and conflict point of intersections or changing the conflict point into confluence point, which can improve the maximum traffic flow of evacuation network significantly.The most widely used emergency traffic control strategy is lane reversal.


### 3.3. Establishment of Emergency Reliability Concept

Given a traffic network which is designed for daily traffic demand, in order to evaluate the extent how the network can meet the evacuation requirements under emergency conditions, the concept of emergency reliability is proposed here. In this study, the concept of network reserve capacity is used to evaluate emergency reliability of traffic network. Network reserve capacity refers to the maximum traffic demand multiplier that can be applied to the given existing (or basic) traffic OD matrix in the process of trip assignment when the road capacity constraints can be satisfied [9].In this paper, traffic demand multiplierμ is used to express emergency reliability of the traffic network. First, the given emergency evacuation demand is expanded μ times to obtain a new evacuation demand. Then it is assigned to the traffic network according to evacuees’ travel behavior. The impact of lane reversal implementation on road capacity is considered during trip assignment. Since the capacity of each road section has a certain upper limit, there exists a maximum multiplier μ.With the constant adjustment of traffic demand multiplierμ, the trip assignment will approach the network equilibrium state continuously, until the traffic flows allocated to certain road sections reach the upper limit of their capacity. At that time, the maximum value of traffic demand multiplier μ is obtained. The maximum value of μ reflects the extent of network reliability. If multiplier μ≥1, it indicates that the traffic network is reliable. And the larger the multiplier is, the better the traffic network works, and the more reliable the traffic network is. At the same time, it also means that the traffic network can accommodate greater extra traffic demand.In the process of trip assignment, it is assumed that the evacuation demand from each origin node is known, and the evacuation demand to each destination depends on the choice of evacuees. Each evacuation destination corresponds to a shelter. And the evacuation demand that each shelter can accommodate is limited. It is assumed that, in case of emergency evacuation, evacuees tend to choose the fastest routes and the nearest shelter in order to reach the safe area as soon as possible, considering the congestion on the routes and in the shelters.


## 3.1. Traffic Flow Characteristics under Emergency Conditions

Different from the traffic state under daily conditions, the traffic state under emergency evacuation has the characteristics of suddenness, high risk, contingency, and so on. In general, emergency evacuation traffic has the following characteristics.(1) Large and Centralized Demand.From the perspective of space, the origin node of emergency evacuation traffic demand is concentrated in the influenced area. And from the perspective of time, traffic demand for emergency evacuation is basically concentrated in a short period of time before and after the disaster, and people need to be evacuated to a safe area in a short time. This leads to the uneven spatial and temporal distribution of traffic flow directly [14]. In the case of emergencies, the peak of travel demand is several times higher than the peak of daily travel demand, which brings great difficulties to the traffic management of emergency evacuation.(2) Characteristics of Crowded Traffic Flow.Due to the large and centralized traffic demand, a large number of crowded points and congested sections will inevitably appear in the traffic network. The traffic flow on the road is basically saturated or oversaturated, and the evacuation traffic flow is basically in the following state, so it is difficult to find an acceptable gap for overtaking [15]. Therefore, emergency evacuation traffic network is a network with congestion influence.(3) High Reliability Requirement.Sudden disasters threaten people’s life and property safety, so emergency evacuees have higher requirements on the reliability of whether they can be quickly evacuated to a safe area. The reliability requirements are as follows: network connectivity reliability, road capacity reliability, travel time reliability, etc.(4) Uneven Flow of Both Directions.In the process of evacuation, the traffic flow from the affected area to other refuge areas is usually large, resulting in oversaturation and serious traffic congestion. However, the traffic flow into the evacuation zone is small, and most lanes are idle.


## 3.2. Emergency Traffic Management strategies

Depending on traffic flow characteristics under emergency conditions, there are several emergency traffic management measures that are commonly used in practice. The purpose is to improve evacuation efficiency and reduce casualties and property losses.(1) Staged Evacuation Strategy.Staged evacuation strategy is widely used in emergency situations when different parts of the target network may suffer different levels of severity over different time windows. By evacuating those populations in the network via an optimized sequence, the staged evacuation strategy can best utilize available roadway capacity, optimally distribute the total demand over the evacuation time horizon, and thus minimize the network congestion level [16, 17].(2) Lane Reversal.In order to alleviate the one-way traffic demand in emergency evacuation which is far beyond the capacity of the road network, the direction of one or more lanes of the road can be reversed to increase the capacity of evacuation direction [15].(3) Crossing Elimination Strategy.The delay of evacuation vehicles mainly occurs at intersections, which is caused by the conflict and interweaving of evacuation flows from different directions. The interference of evacuation traffic flow can be reduced by eliminating or reducing the confluence point and conflict point of intersections or changing the conflict point into confluence point, which can improve the maximum traffic flow of evacuation network significantly.The most widely used emergency traffic control strategy is lane reversal.


## 3.3. Establishment of Emergency Reliability Concept

Given a traffic network which is designed for daily traffic demand, in order to evaluate the extent how the network can meet the evacuation requirements under emergency conditions, the concept of emergency reliability is proposed here. In this study, the concept of network reserve capacity is used to evaluate emergency reliability of traffic network. Network reserve capacity refers to the maximum traffic demand multiplier that can be applied to the given existing (or basic) traffic OD matrix in the process of trip assignment when the road capacity constraints can be satisfied [9].In this paper, traffic demand multiplierμ is used to express emergency reliability of the traffic network. First, the given emergency evacuation demand is expanded μ times to obtain a new evacuation demand. Then it is assigned to the traffic network according to evacuees’ travel behavior. The impact of lane reversal implementation on road capacity is considered during trip assignment. Since the capacity of each road section has a certain upper limit, there exists a maximum multiplier μ.With the constant adjustment of traffic demand multiplierμ, the trip assignment will approach the network equilibrium state continuously, until the traffic flows allocated to certain road sections reach the upper limit of their capacity. At that time, the maximum value of traffic demand multiplier μ is obtained. The maximum value of μ reflects the extent of network reliability. If multiplier μ≥1, it indicates that the traffic network is reliable. And the larger the multiplier is, the better the traffic network works, and the more reliable the traffic network is. At the same time, it also means that the traffic network can accommodate greater extra traffic demand.In the process of trip assignment, it is assumed that the evacuation demand from each origin node is known, and the evacuation demand to each destination depends on the choice of evacuees. Each evacuation destination corresponds to a shelter. And the evacuation demand that each shelter can accommodate is limited. It is assumed that, in case of emergency evacuation, evacuees tend to choose the fastest routes and the nearest shelter in order to reach the safe area as soon as possible, considering the congestion on the routes and in the shelters.


## 4. Mathematical Formulation

In this section, the mathematical description for the problem of interest is formally proposed with a bilevel programming model to analyze the aforementioned multiplierμ quantitatively.


### 4.1. Upper Level Model

Given an existing traffic networkG(N,A), where N denotes the set of nodes and A denotes the set of existing links. a,a′∈A, represent for the two opposite links of the same road segment respectively. na and na′ denote the number of lanes on the corresponding links. Naa′ is the total number of lanes of the segment.The upper level model aims to maximum the variableμ while searching for a feasible lane distribution scheme under unbalanced distribution of two-way traffic flow. The formulation is as follows:(1a)maxμ(1b)s.t.na+na′=Naa′(1c)na,na′≥0In this model, the total number of lanes of a certain segment,Naa′, should be a constant on the basis of the existing traffic network. And the number of lanes of all the segments in each direction in the lane distribution scheme could not exceed the corresponding upper bounds, according to the constraint conditions.The upper level model influences the lower level model through two sets of variables. The variableμ changes the actual evacuating demand calculated in the lower level model, and the number of lanes on each link, na and na′, influences the capacity of each link and ultimately affects the capacity of the entire road network.


### 4.2. Lower Level Model

The lower level model is a traveler behavior model describing route and shelter choices of evacuees in emergency situations. The total number of trips generated at origin nodes is given, and the capacity of a single lane and each shelter is also known. Evacuees will choose the shelter that they can arrive as soon as possible and choose the route by which they can reach the safe area in the shortest time, with the consideration of congestion influence on the routes and in the shelters under emergency circumstance. The number of evacuees reaching each shelter is finally decided by the lower level model. Therefore the lower level model is formulated as a joint UE distribution/assignment model with capacity constraints:(2a)minZx,μ,n=∑a∫0xataω,nadω(2b)s.t.∑kfkrs=qrs(2c)∑sqrs=μDr(2d)∑rqrs≤Ds¯(2e)xa≤Cana(2f)fkrs≥0(2g)qrs≥0The definitional constraints are as follows:(2h)xa=∑r∑s∑kfkrsδa,krswherexa: traffic flow on link a;ta: travel time on link a, where ta(•) is the impedance function which represents the relationship between link travel time and link traffic flow;Ca: capacity of link a, where Ca(na) represents the relationship between link capacity and the number of lanes on the link;Dr: total number of existing trips generated at origin node r;D¯s: capacity of destination s (in this paper, destination refers to shelter);qrs: trip rate between origin r and destination s;fkrs: flow on path k connecting origin r and destination s;δa,krs: binary variable, if link a is on path k between OD pair r and s, δa,krs=1, otherwise, δa,krs=0.In this model, (2a) is the objective function, which is the sum of the integrals of the link performance functions. This function does not have any intuitive economic or behavioral interpretation. It should be viewed strictly as a mathematical construct that is utilized to solve equilibrium problems. Equations (2b) and (2c) represent a set of flow conservation constraints. Equation (2b) states that the flow on all paths connecting each OD pair has to equal the OD trip rate, and (2c) indicates that the total number of trips from each origin node to all the destination nodes has to equal the amplified traffic demand with variable μ at each origin node. Equation (2d) indicates that the total number of trips end with a certain shelter is constrained by the capacity of the shelter. Equation (2e) states that the capacity of a link constrains the flow on it. Equations (2f) and (2g) are nonnegative conditions to ensure that the solution of the program will be physically meaningful.The objective function of program (2a)–(2h),Z(x,μ,n), is formulated in terms of link flows, traffic demand multiplier and number of lanes on each link, whereas the flow conservation constraints are formulated in terms of path flows. Equation (2h) expresses the incident relationships between link flow and path flow, which is determined by the network structure itself.


### 4.3. Equivalency Conditions of Lower Level Model

To demonstrate the equivalence conditions of lower level model established above, it has to be shown that any flow pattern that solves the mathematical program (2a)–(2h) also satisfies the equilibrium conditions. This equivalency is demonstrated in this section by proving that the first-order conditions for the minimization program are identical to the equilibrium conditions. These conditions can be derived by forming and analyzing the Lagrangian [15, 18, 19].The Lagrangian of the equivalent minimization problem with respect to all the equality and inequality constraints can be formulated as(3)Lf,q,μ,m,α,β=Zxf+∑rsμrsqrs-∑kfkrs+∑rmrDr-∑sqrs+∑sαs∑rqrs-Ds¯+∑aβa∑rs∑kfkrsδa,krs-Cawhere μrs, mr, αs, and βa are Lagrangian multipliers.According to Karush-Kuhn-Tucker (KKT) conditions, Lagrangian function (3) must satisfy the following conditions at its extreme points:(4a)∂L∂fkrsfkrs=0and∂L∂fkrs≥0(4b)∂L∂qrsqrs=0and∂L∂qrs≥0(4c)∂L∂αsαs=0and∂L∂αs≤0(4d)∂L∂βaβa=0and∂L∂βa≤0(4e)∂L∂μrs=0(4f)∂L∂mr=0One can solve the partial derivatives in expression (3) and substitute them into expressions (4a) to (4f), which yields(5a)c-krs-μrsfkrs=0(5b)c-krs-μrs≥0(5c)μrs-mr+αsqrs=0(5d)μrs-mr+αs≥0(5e)∑rqrs-Ds¯αs=0(5f)∑rqrs-Ds¯≤0(5g)xa-Caβa=0(5h)xa-Ca≤0(5i)qrs-∑kfkrs=0(5j)Dr-∑sqrs=0(5k)fkrs≥0(5l)qrs≥0where(5m)t-a=taxa+βa(5n)c-krs=∑rs∑at-axaδa,krsHere,t-a and c-krs both denote the generalized travel time, while αs denotes the penalty coefficient related to shelter capacity, and βa denotes queuing delay due to limited link capacity respectively.Equations (5a) and (5b) spell out the familiar user-equilibrium condition over the network. With (5k), it can be inferred that the flow on path connecting any origin and destination satisfies(1)
iffkrs>0, c-krs=μrs;(2)
iffkrs=0, c-krs≥μrs.That is to say, the paths connecting any O-D pair can be divided into two categories: those carrying flow, on which the generalized travel time equals the minimum O-D generalized travel time; and those not carrying flow, on which the generalized travel time is greater than (or equal to) the minimum O-D generalized travel time. This is satisfied with the first equilibrium principle of Wardrop.Similarly, with (5c), (5d), and (5l), the following conditions can be speculated:(1)
ifqrs>0, μrs+αs=mr;(2)
ifqrs=0, μrs+αs≥mr.That is to say, when shelters is chosen by evacuees from origin r, the generalized impedance from origin r to shelter s is the smallest one among the generalized impedances from origin r to all the shelters. Otherwise, if none of evacuees choose shelter s as a destination, it means the generalized impedance from origin r to shelter s is greater than (or equal to) the minimum generalized travel time from origin r to all the shelters. This is consistent with the assumption that all evacuees tend to choose the nearest shelter.From (5e) and (5f), it can be inferred that, for shelter s, its capacity penalty coefficient satisfies(1)
if∑rqrs=Ds¯, αs≥0;(2)
if∑rqrs<Ds¯, αs=0.The penalty coefficient of shelters depends on the amount of demand reaching this destination. It only exists when shelter s has reached its capacity. Penalty coefficient of shelter s is caused by congestion in the shelter, but the penalty coefficient will not increase indefinitely, as evacuees will change their destinations to avoid excessive delays.Similarly, from (5g) and (5h), it can be inferred that, for link a, its queuing delay satisfies the following:(1)
ifxa=Ca, βa≥0;(2)
ifxa<Ca, βa=0.That is, the queuing delay on linka depends on its traffic flow. It only exists when the link traffic volume achieves its capacity. Queue delay is caused by congestion on the link and it causes the traffic flow to be redistributed spatially so that the traffic flow of all links does not exceed their capacity.Equations (5i) and (5j) are the flow conservation constraints.By solving the lower programming model, the link flows and path flows (the result of path flows is not unique) that meet the above conditions can be obtained. But if the demand is too large and exceeds the capacity of the whole traffic network, the model will have no solution.


## 4.1. Upper Level Model

Given an existing traffic networkG(N,A), where N denotes the set of nodes and A denotes the set of existing links. a,a′∈A, represent for the two opposite links of the same road segment respectively. na and na′ denote the number of lanes on the corresponding links. Naa′ is the total number of lanes of the segment.The upper level model aims to maximum the variableμ while searching for a feasible lane distribution scheme under unbalanced distribution of two-way traffic flow. The formulation is as follows:(1a)maxμ(1b)s.t.na+na′=Naa′(1c)na,na′≥0In this model, the total number of lanes of a certain segment,Naa′, should be a constant on the basis of the existing traffic network. And the number of lanes of all the segments in each direction in the lane distribution scheme could not exceed the corresponding upper bounds, according to the constraint conditions.The upper level model influences the lower level model through two sets of variables. The variableμ changes the actual evacuating demand calculated in the lower level model, and the number of lanes on each link, na and na′, influences the capacity of each link and ultimately affects the capacity of the entire road network.


## 4.2. Lower Level Model

The lower level model is a traveler behavior model describing route and shelter choices of evacuees in emergency situations. The total number of trips generated at origin nodes is given, and the capacity of a single lane and each shelter is also known. Evacuees will choose the shelter that they can arrive as soon as possible and choose the route by which they can reach the safe area in the shortest time, with the consideration of congestion influence on the routes and in the shelters under emergency circumstance. The number of evacuees reaching each shelter is finally decided by the lower level model. Therefore the lower level model is formulated as a joint UE distribution/assignment model with capacity constraints:(2a)minZx,μ,n=∑a∫0xataω,nadω(2b)s.t.∑kfkrs=qrs(2c)∑sqrs=μDr(2d)∑rqrs≤Ds¯(2e)xa≤Cana(2f)fkrs≥0(2g)qrs≥0The definitional constraints are as follows:(2h)xa=∑r∑s∑kfkrsδa,krswherexa: traffic flow on link a;ta: travel time on link a, where ta(•) is the impedance function which represents the relationship between link travel time and link traffic flow;Ca: capacity of link a, where Ca(na) represents the relationship between link capacity and the number of lanes on the link;Dr: total number of existing trips generated at origin node r;D¯s: capacity of destination s (in this paper, destination refers to shelter);qrs: trip rate between origin r and destination s;fkrs: flow on path k connecting origin r and destination s;δa,krs: binary variable, if link a is on path k between OD pair r and s, δa,krs=1, otherwise, δa,krs=0.In this model, (2a) is the objective function, which is the sum of the integrals of the link performance functions. This function does not have any intuitive economic or behavioral interpretation. It should be viewed strictly as a mathematical construct that is utilized to solve equilibrium problems. Equations (2b) and (2c) represent a set of flow conservation constraints. Equation (2b) states that the flow on all paths connecting each OD pair has to equal the OD trip rate, and (2c) indicates that the total number of trips from each origin node to all the destination nodes has to equal the amplified traffic demand with variable μ at each origin node. Equation (2d) indicates that the total number of trips end with a certain shelter is constrained by the capacity of the shelter. Equation (2e) states that the capacity of a link constrains the flow on it. Equations (2f) and (2g) are nonnegative conditions to ensure that the solution of the program will be physically meaningful.The objective function of program (2a)–(2h),Z(x,μ,n), is formulated in terms of link flows, traffic demand multiplier and number of lanes on each link, whereas the flow conservation constraints are formulated in terms of path flows. Equation (2h) expresses the incident relationships between link flow and path flow, which is determined by the network structure itself.


## 4.3. Equivalency Conditions of Lower Level Model

To demonstrate the equivalence conditions of lower level model established above, it has to be shown that any flow pattern that solves the mathematical program (2a)–(2h) also satisfies the equilibrium conditions. This equivalency is demonstrated in this section by proving that the first-order conditions for the minimization program are identical to the equilibrium conditions. These conditions can be derived by forming and analyzing the Lagrangian [15, 18, 19].The Lagrangian of the equivalent minimization problem with respect to all the equality and inequality constraints can be formulated as(3)Lf,q,μ,m,α,β=Zxf+∑rsμrsqrs-∑kfkrs+∑rmrDr-∑sqrs+∑sαs∑rqrs-Ds¯+∑aβa∑rs∑kfkrsδa,krs-Cawhere μrs, mr, αs, and βa are Lagrangian multipliers.According to Karush-Kuhn-Tucker (KKT) conditions, Lagrangian function (3) must satisfy the following conditions at its extreme points:(4a)∂L∂fkrsfkrs=0and∂L∂fkrs≥0(4b)∂L∂qrsqrs=0and∂L∂qrs≥0(4c)∂L∂αsαs=0and∂L∂αs≤0(4d)∂L∂βaβa=0and∂L∂βa≤0(4e)∂L∂μrs=0(4f)∂L∂mr=0One can solve the partial derivatives in expression (3) and substitute them into expressions (4a) to (4f), which yields(5a)c-krs-μrsfkrs=0(5b)c-krs-μrs≥0(5c)μrs-mr+αsqrs=0(5d)μrs-mr+αs≥0(5e)∑rqrs-Ds¯αs=0(5f)∑rqrs-Ds¯≤0(5g)xa-Caβa=0(5h)xa-Ca≤0(5i)qrs-∑kfkrs=0(5j)Dr-∑sqrs=0(5k)fkrs≥0(5l)qrs≥0where(5m)t-a=taxa+βa(5n)c-krs=∑rs∑at-axaδa,krsHere,t-a and c-krs both denote the generalized travel time, while αs denotes the penalty coefficient related to shelter capacity, and βa denotes queuing delay due to limited link capacity respectively.Equations (5a) and (5b) spell out the familiar user-equilibrium condition over the network. With (5k), it can be inferred that the flow on path connecting any origin and destination satisfies(1)
iffkrs>0, c-krs=μrs;(2)
iffkrs=0, c-krs≥μrs.That is to say, the paths connecting any O-D pair can be divided into two categories: those carrying flow, on which the generalized travel time equals the minimum O-D generalized travel time; and those not carrying flow, on which the generalized travel time is greater than (or equal to) the minimum O-D generalized travel time. This is satisfied with the first equilibrium principle of Wardrop.Similarly, with (5c), (5d), and (5l), the following conditions can be speculated:(1)
ifqrs>0, μrs+αs=mr;(2)
ifqrs=0, μrs+αs≥mr.That is to say, when shelters is chosen by evacuees from origin r, the generalized impedance from origin r to shelter s is the smallest one among the generalized impedances from origin r to all the shelters. Otherwise, if none of evacuees choose shelter s as a destination, it means the generalized impedance from origin r to shelter s is greater than (or equal to) the minimum generalized travel time from origin r to all the shelters. This is consistent with the assumption that all evacuees tend to choose the nearest shelter.From (5e) and (5f), it can be inferred that, for shelter s, its capacity penalty coefficient satisfies(1)
if∑rqrs=Ds¯, αs≥0;(2)
if∑rqrs<Ds¯, αs=0.The penalty coefficient of shelters depends on the amount of demand reaching this destination. It only exists when shelter s has reached its capacity. Penalty coefficient of shelter s is caused by congestion in the shelter, but the penalty coefficient will not increase indefinitely, as evacuees will change their destinations to avoid excessive delays.Similarly, from (5g) and (5h), it can be inferred that, for link a, its queuing delay satisfies the following:(1)
ifxa=Ca, βa≥0;(2)
ifxa<Ca, βa=0.That is, the queuing delay on linka depends on its traffic flow. It only exists when the link traffic volume achieves its capacity. Queue delay is caused by congestion on the link and it causes the traffic flow to be redistributed spatially so that the traffic flow of all links does not exceed their capacity.Equations (5i) and (5j) are the flow conservation constraints.By solving the lower programming model, the link flows and path flows (the result of path flows is not unique) that meet the above conditions can be obtained. But if the demand is too large and exceeds the capacity of the whole traffic network, the model will have no solution.


## 5. Solution Algorithm

This section aims to design an algorithm to effectively solve the proposed bilevel model. Since bilevel programming is a NP-hard problem, which is difficult to solve by traditional optimization algorithms or analytical methods, the usual solving methods are based on heuristic algorithms. Therefore, in this paper, iterative optimization algorithm is adopted in the upper model. Besides, the addition of constraint conditions in the lower model changes the original Descartes form of UE model, which results in the fact that the lower model cannot be solved by traditional F-W method. Commonly used methods include penalty function method and Lagrange multiplier method. In this paper, the lower model is transformed and then solved by dynamic penalty function algorithm proposed by Zhang [19]. Step-by-step procedures of two algorithms are also given below, respectively.


### 5.1. Solution Algorithm for Upper Level Model

The specific steps of the iterative optimization algorithm are shown in Algorithm1.Algorithm 1:Iterative optimization algorithm.
Step 1: Initialization. Setμ0=1, k=1. Initialize parameters including step size σ (σ>0), population size m, maximum number of iterations max and mutation probabilityp. Step 2: Generate initial lane distribution schemes. Generatem lane distribution schemes randomly, including the original lane distribution scheme. All the schemes are represented byu={u1,u2,⋯,um}, which is the change in the number of lanes in each pair of sections. Step 3: Find the feasible lane distribution schemes. For each lane distribution scheme: (3.1) Calculate the number of lanes on each linka, na, and its capacity Ca; (3.2) Run the lower programming model according to demandμkDr; (3.3) If any solution exists, store the corresponding lane distribution scheme into the set of historical feasible schemesP. Turn to Step 5. Step 4: Renew the schemes. If all schemes can’t find a feasible solution in the lower level model, they should be renewed according to following procedure: (4.1) Renew the update count of lane schemes,n, and if n>max, turn to Step 6; (4.2) If there are more thanm schemes in set P, randomly pick m schemes and do mutation processing by using local search algorithm, then obtainm new schemes. (4.3) If there are less thanm schemes in set P, suppose it is w, do mutation processing by using local searching algorithm to all of these schemes. Besides, generatem-w schemes at random. (4.4) Turn to Step 3. Step 5:Let μk+1=μk+σ, k=k+1, and turn to Step 3. Step 6: Termination. Letμ=μk-σ. The algorithm ends.The process of local searching algorithm in Algorithm1 is as follows. Lane schemes are generally generated in a monotonous way, such as random generating method, which can easily get trapped in local optimality. In order to obtain better newly generated schemes, this paper starts from historically feasible lane distribution schemes in set P and searches their neighborhoods to get new schemes based on the characteristics of specific problems.For each road section, judge the flow distribution results of a certain historical feasible scheme; ifta/Ca≥ta′/Ca′, ua increases by 1 with probability p while ensuring that it does not exceed its upper limit; otherwise, ua decreases by 1 with probability p while ensuring it does not exceed its lower limit. This is the principle of generating a new lane distribution scheme.


### 5.2. Solution Algorithm for Lower Level Model

As for the lower level model, the topology of the origin network is firstly transferred. Augment the original network with a dummy node, denoteds′, and connect all the destination nodes (i.e., shelters) to node s′, deriving several dummy links. The total number of dummy links is the product of the number of shelters. Assume that free flow travel time on each dummy link is 0, and capacity of each dummy link equals the capacity of the corresponding shelter.This simple modification of the network topology can transform the combined distribution/assignment problem with constraint of traffic capacity into an equivalent UE problem with constraint of traffic capacity. Based on the modification, a dynamic penalty function algorithm is used to solve the problem.The basic idea of the dynamic penalty function algorithm is to transform equivalent UE problem with constraint into traditional UE problem by adding penalty function. In UE problem with constraint, the generalized travel timeC-krs at equilibrium is composed of travel time calculated by impedance function and queuing delay denote by Lagrangian multipliers βa. However, the Lagrangian multipliers cannot be calculated directly, thus a penalty function p(xa,λa)=λaf(xa/Ca) is used to replace it. Here, λa is penalty function coefficient related to link a. Let y denotes the ratio of xa to Ca so as to simplify the instruction. The following form of function f(y) is adopted:(6)fy=ρ21-yy<1-ρy-12ρ+1y≥1-ρwhere ρ can be a very small constant between 0 and 1.Functionf(y) has the following characteristics:(1)
monotone, continuous, and derivable;(2)
wheny=1, f(y)=1 and p(xa,λa)=λa; when y>1, f(y) is very big; when y<1, f(y) is very small.During the problem solving process, bothλa and f(xa/Ca) will be constantly updated according to the new link traffic flow obtained from each iteration, so that the penalty function p(xa,λa) will finally approach Lagrange multiplier βa. Update rule for λa is as follows:(7)λan=λan-1fxanCaDue to the poor convergence performance of the traditional Frank-Wolfe method for solving UE model, the linear decomposition algorithm proposed by Aashitiani and Magnanti [20, 21] is used here to solve UE problem. Based on the path flow, the linear decomposition algorithm starts from the nonlinear complementarity problem (NCP) of UE problem and transforms it into a series of linear complementarity problems.The specific steps of the dynamic penalty function algorithm for the lower level model are shown in Algorithm2.Algorithm 2:Dynamic penalty function algorithm.
Step 1: Initialization. (1.1) Setn=1, initialize parameters including penalty function parameters ρ, penalty function coefficients λa0 and convergence criteriaε1 and ε2; (1.2) Set valid paths of each O-D pairKwrs=⌀. Step 2: Calculate initial solution f (2.1) Calculate the generalized travel timet-a according to the initial link flow {xa=0,∀a}, and find the shortest path between each OD pair; (2.2) Apply all-or-nothing assignment to get the initial path flowf. Step 3: For each OD pair rs: (3.1) Update the set of valid pathsKwrs and calculate the generalized travel time t-a, obtain the shortest path krs and its travel timeurs between each OD pair rs. If the convergence criterion Eq. (∗) is not satisfied, then Kwrs=Kwrs∪{krs}; m i n k ∈ K w r s c - k r s ( f ) - u r s u r s ≤ ε 1 (∗) (3.2) Linearize the NCP problem composed of effective paths at{fkrs,∀k∈Kwrs} and solve it by improved Lemke algorithm [22] to get new {fkrs,urs}; (3.3) If the convergence criterion Eq. (∗∗) is not satisfied, return to (3.2). m a x k ∈ K w r s , f k > 0 c - k r s ( f ) - u r s m a x k ∈ K w r s , f k > 0 c - k r s ( f ) ≤ ε 1 (∗∗) Step 4:Update the link flow xn=x(f) and penalty function parameter λn. Step 5: Termination criterion. If the convergence criterion Eq. (∗∗∗) is satisfied, xn is the answer. Otherwise, let n=n+1 and turn to Step 3. | x n - x n - 1 | x n - 1 ≤ ε 2 (∗∗∗)


## 5.1. Solution Algorithm for Upper Level Model

The specific steps of the iterative optimization algorithm are shown in Algorithm1.Algorithm 1:Iterative optimization algorithm.
Step 1: Initialization. Setμ0=1, k=1. Initialize parameters including step size σ (σ>0), population size m, maximum number of iterations max and mutation probabilityp. Step 2: Generate initial lane distribution schemes. Generatem lane distribution schemes randomly, including the original lane distribution scheme. All the schemes are represented byu={u1,u2,⋯,um}, which is the change in the number of lanes in each pair of sections. Step 3: Find the feasible lane distribution schemes. For each lane distribution scheme: (3.1) Calculate the number of lanes on each linka, na, and its capacity Ca; (3.2) Run the lower programming model according to demandμkDr; (3.3) If any solution exists, store the corresponding lane distribution scheme into the set of historical feasible schemesP. Turn to Step 5. Step 4: Renew the schemes. If all schemes can’t find a feasible solution in the lower level model, they should be renewed according to following procedure: (4.1) Renew the update count of lane schemes,n, and if n>max, turn to Step 6; (4.2) If there are more thanm schemes in set P, randomly pick m schemes and do mutation processing by using local search algorithm, then obtainm new schemes. (4.3) If there are less thanm schemes in set P, suppose it is w, do mutation processing by using local searching algorithm to all of these schemes. Besides, generatem-w schemes at random. (4.4) Turn to Step 3. Step 5:Let μk+1=μk+σ, k=k+1, and turn to Step 3. Step 6: Termination. Letμ=μk-σ. The algorithm ends.The process of local searching algorithm in Algorithm1 is as follows. Lane schemes are generally generated in a monotonous way, such as random generating method, which can easily get trapped in local optimality. In order to obtain better newly generated schemes, this paper starts from historically feasible lane distribution schemes in set P and searches their neighborhoods to get new schemes based on the characteristics of specific problems.For each road section, judge the flow distribution results of a certain historical feasible scheme; ifta/Ca≥ta′/Ca′, ua increases by 1 with probability p while ensuring that it does not exceed its upper limit; otherwise, ua decreases by 1 with probability p while ensuring it does not exceed its lower limit. This is the principle of generating a new lane distribution scheme.


## 5.2. Solution Algorithm for Lower Level Model

As for the lower level model, the topology of the origin network is firstly transferred. Augment the original network with a dummy node, denoteds′, and connect all the destination nodes (i.e., shelters) to node s′, deriving several dummy links. The total number of dummy links is the product of the number of shelters. Assume that free flow travel time on each dummy link is 0, and capacity of each dummy link equals the capacity of the corresponding shelter.This simple modification of the network topology can transform the combined distribution/assignment problem with constraint of traffic capacity into an equivalent UE problem with constraint of traffic capacity. Based on the modification, a dynamic penalty function algorithm is used to solve the problem.The basic idea of the dynamic penalty function algorithm is to transform equivalent UE problem with constraint into traditional UE problem by adding penalty function. In UE problem with constraint, the generalized travel timeC-krs at equilibrium is composed of travel time calculated by impedance function and queuing delay denote by Lagrangian multipliers βa. However, the Lagrangian multipliers cannot be calculated directly, thus a penalty function p(xa,λa)=λaf(xa/Ca) is used to replace it. Here, λa is penalty function coefficient related to link a. Let y denotes the ratio of xa to Ca so as to simplify the instruction. The following form of function f(y) is adopted:(6)fy=ρ21-yy<1-ρy-12ρ+1y≥1-ρwhere ρ can be a very small constant between 0 and 1.Functionf(y) has the following characteristics:(1)
monotone, continuous, and derivable;(2)
wheny=1, f(y)=1 and p(xa,λa)=λa; when y>1, f(y) is very big; when y<1, f(y) is very small.During the problem solving process, bothλa and f(xa/Ca) will be constantly updated according to the new link traffic flow obtained from each iteration, so that the penalty function p(xa,λa) will finally approach Lagrange multiplier βa. Update rule for λa is as follows:(7)λan=λan-1fxanCaDue to the poor convergence performance of the traditional Frank-Wolfe method for solving UE model, the linear decomposition algorithm proposed by Aashitiani and Magnanti [20, 21] is used here to solve UE problem. Based on the path flow, the linear decomposition algorithm starts from the nonlinear complementarity problem (NCP) of UE problem and transforms it into a series of linear complementarity problems.The specific steps of the dynamic penalty function algorithm for the lower level model are shown in Algorithm2.Algorithm 2:Dynamic penalty function algorithm.
Step 1: Initialization. (1.1) Setn=1, initialize parameters including penalty function parameters ρ, penalty function coefficients λa0 and convergence criteriaε1 and ε2; (1.2) Set valid paths of each O-D pairKwrs=⌀. Step 2: Calculate initial solution f (2.1) Calculate the generalized travel timet-a according to the initial link flow {xa=0,∀a}, and find the shortest path between each OD pair; (2.2) Apply all-or-nothing assignment to get the initial path flowf. Step 3: For each OD pair rs: (3.1) Update the set of valid pathsKwrs and calculate the generalized travel time t-a, obtain the shortest path krs and its travel timeurs between each OD pair rs. If the convergence criterion Eq. (∗) is not satisfied, then Kwrs=Kwrs∪{krs}; m i n k ∈ K w r s c - k r s ( f ) - u r s u r s ≤ ε 1 (∗) (3.2) Linearize the NCP problem composed of effective paths at{fkrs,∀k∈Kwrs} and solve it by improved Lemke algorithm [22] to get new {fkrs,urs}; (3.3) If the convergence criterion Eq. (∗∗) is not satisfied, return to (3.2). m a x k ∈ K w r s , f k > 0 c - k r s ( f ) - u r s m a x k ∈ K w r s , f k > 0 c - k r s ( f ) ≤ ε 1 (∗∗) Step 4:Update the link flow xn=x(f) and penalty function parameter λn. Step 5: Termination criterion. If the convergence criterion Eq. (∗∗∗) is satisfied, xn is the answer. Otherwise, let n=n+1 and turn to Step 3. | x n - x n - 1 | x n - 1 ≤ ε 2 (∗∗∗)


## 6. Numerical Experiments

In this section, the above proposed model and algorithm will be tested and evaluated in an experimental network. First the topology of network and relevant information is given, then the analyzation of the results.


### 6.1. Topology of Network

Take the test network in the Figure1 as the example, which has 9 nodes and 24 directed links. Here node 1 and node 4 are the origin points of evacuation, and node 3, 6, and 9 are shelters. Information of link properties in the network, including link free flow travel time and link capacities, is listed in Table 1. Information of evacuation demand of each origin point is listed in Table 2, and Table 3 gives the information of the capacity of shelters.Table 1
Information of link properties.
Link no. Starting node Ending node Number of lanes Free-flow travel time (min) Capacity(pcu/h) 1 1 2 3 1.5 900 2 2 1 3 1 900 3 2 3 3 0.8 900 4 3 2 3 0.8 900 5 1 4 2 1 600 6 4 1 2 0.8 600 7 2 5 4 1.25 1200 8 5 2 4 1 1200 9 3 6 3 1.25 900 10 6 3 3 2 900 11 4 5 4 1.5 1200 12 5 4 4 1.25 1200 13 5 6 4 0.75 1200 14 6 5 4 0.6 1200 15 4 7 3 0.8 900 16 7 4 3 0.9 900 17 5 8 4 1.25 1200 18 8 5 4 1.2 1200 19 6 9 3 1.1 900 20 9 6 3 1 900 21 7 8 3 0.95 900 22 8 7 3 0.9 900 23 8 9 3 1.2 900 24 9 8 3 1.3 900Table 2
Information of evacuation demand.
No. Origin node Demand (pcu/h) 1 1 1500 2 4 1200Table 3
Information of shelter capacity.
No. Destination node Capacity (pcu/h) 1 3 1000 2 6 800 3 9 1200Figure 1
Topology of tested network.Modify the original network by adding a dummy node 10 and connect it with three shelters by three dummy links. The topology of modified network is shown in Figure2. As mentioned above, free flow travel time of each dummy link is always 0, and capacity of each dummy link equals to the capacity of the corresponding shelter. On the basis of the modification above, the problem of interest is transformed into UE assignment problem of a multiorigin and single-destination network with link capacity constraints.Figure 2
Topology of modified network.


### 6.2. Result Analysis

(1) Result Analysis of the Lower Model. The trip assignment results are analyzed when μ=1 without changing the number of lanes in each link. In the experiment, values of each parameter are as follows: ρ=0.01, ε1=ε2=0.001, the initial penalty function coefficient λa0=0.1t0, where t0 denotes the average of free flow travel time on all links. The BPR formula is employed as impedance function and two parameters in the function are set as 0.15 and 4, respectively.(a) From the Perspective of Route Choice.Tables 4 and 5 show the path details of OD pair 1-10 and 4-10 at equilibrium. From the perspective of route choice, for OD pair 1-10, three paths are chosen by evacuees, and the generalized travel time for these three paths is all equal to 4.8443min, which is the minimum generalized travel time of this OD pair. The generalized travel time of unselected paths including path 4, 5, and 6 is 6.1449, 6.0435, and 6.9712min, respectively, all larger than 4.8443min. Similarly, for OD pair 4-10, three paths are chosen by evacuees, and the generalized travel time for these three paths is all equal to 3.6940min. The generalized travel time of unselected paths including path 4, 5, and 6 is 4.5875, 5.6443, and 6.0504min, respectively.Table 4
Path details of OD pair 1-10 at equilibrium.
Path No. Path flow(pcu/h) Composition of path(link no.) Travel time(min) Queuing delay(min) Generalized travel time(min) 1 900 1,3,25 2.645 2.1993 4.8443 2 557.6044 5,15,21,23,27 4.2837 0.5606 4.8443 3 42.3956 5,11,13,26 3.7375 1.1068 4.8443 4 0 5,11,7,3,25 5.0450 1.0999 6.1449 5 0 1,7,13,26 3.8375 2.2060 6.0435 6 0 5,15,21,17,13,9,25 6.4106 0.5606 6.9712Table 5
Path details of OD pair 4-10 at equilibrium.
Path No. Path flow(pcu/h) Composition of path(link no.) Travel time(min) Queuing delay(min) Generalized travel time(min) 1 757.6044 11,13,26 2.5875 1.1065 3.6940 2 42.3956 15,21,23,27 3.1337 0.5603 3.6940 3 400 11,13,19,27 3.6939 0.0001 3.6940 4 0 11,13,10,25 4.5875 0 4.5875 5 0 6,1,3,25 3.4450 2.1993 5.6443 6 0 15,21,23,19,9,25 5.4901 0.5603 6.0504Although the path flow results of traffic assignment in crowded traffic networks with queuing delays are not necessarily unique, the result satisfies that generalized travel time of all the selected paths is equal, which meets the conditions of UE equilibrium.(b) From the Perspective of Shelter Choice.According to the path flow results, the demand from origins to all the shelter can be referred, shown in Table 6. For origin node 1, the number of evacuees choosing shelter 3, 6, and 9 is 900, 42.3956, and 557.6044, respectively. And the generalized travel time from node 1 to all the shelters is equal to 4.8443. For origin node 4, the number of evacuees choosing shelter 6 and 9 is 757.6044 and 442.3956, respectively. No one chooses shelter 3 because its generalized travel time is 3.8375, a little larger than other shelters.Table 6
Detailed information for OD pairs.
No. Origin node Destination node Demand(pcu/h) Minimum generalized travel time(min) 1 1 3 900 4.8443 2 1 6 42.3956 4.8443 3 1 9 557.6044 4.8443 4 4 3 0 3.8375 5 4 6 757.6044 3.6940 6 4 9 442.3956 3.6940That means for a certain origin, generalized travel time of all the selected shelters is equal, and generalized travel time of shelters which are not chosen is larger than the chosen shelters.Table7 shows the final shelter demands. The number of evacuees choosing the three shelters is 900, 800, and 1000, respectively. And among them, only shelter 6 reaches its capacity, and the queuing delay is 1.1064 min. The other two shelters are not saturated and the queuing delays are both 0. This is consistent with the previous conclusion that the queuing delay associated with shelters only exists when the shelter has reached its capacity.Table 7
Detail information for shelter choice.
No. Destination node Capacity(pcu/h) Demand(pcu/h) Queuing Delay(min) 1 3 1000 900 0 2 6 800 800 1.1064 3 9 1200 1000 0All the experimental results are consistent with the above analysis of first-order conditions of the Lagrangian function.(2) Results Analysis of Bilevel Model.In order to illustrate the rationality of the model and the effectiveness of the algorithm proposed in this paper, three different demand scenarios and two different shelter capacity scenarios (shown in Table 8) are constructed, and four cases of combination of different scenarios are generated (shown in Table 9).Table 8
Information of different demand and shelter capacity scenarios.
Demand scenarios Shelter capacity scenarios Origin node Demand (pcu/h)  Destination node Capacity (pcu/h) D1 1 1500 S1 3 1000 4 1200  6 800 D2 1 700  9 1200 4 2000 S2 3 3000 D3 4 700  6 800 7 2000  9 3000Table 9
Information of combination of different scenarios.
No. Demand scenario Shelter capacity scenario Case 1 D1 S1 Case 2 D1 S2 Case 3 D2 S2 Case 4 D3 S2In the solving algorithm, set step sizeσ=0.01, population size as m=10, maximum iteration count max=50, and mutation probability p=0.8.(a) Results Analysis of Different Cases.In case 1, the maximum multiplier μ that the solution algorithm can obtain is 1.11. The corresponding feasible lane distribution scheme and link flow are shown in Table 10. Only links 5, 15, and 19 are saturated, but there is still plenty of potential room for the capacity of these links. Table 11 shows the corresponding shelter demands. Three shelters are chosen by 997, 800, and 1200 evacuees, respectively. All the shelters are almost saturated. It turns out that the emergency reliability of the entire road network in the case here is limited to the shelter capacity.Table 10
Feasible lane distribution scheme and link flow in Case 1 whenμ=1.11.
Link No. Number of lanes Capacity Link flow(pcu/h) 1 5 1500 1065 2 1 300 0 3 4 1200 1000 4 2 600 0 5 2 600 600 6 2 600 0 7 6 1200 65 8 2 600 0 9 5 1500 0 10 1 300 0 11 5 1500 1332 12 3 900 0 13 7 2100 1100 14 1 300 0 15 2 600 600 16 4 1200 0 17 4 1200 297 18 4 1200 0 19 1 300 300 20 5 1500 0 21 3 900 600 22 3 900 0 23 3 900 897 24 3 900 0Table 11
Detailed information for shelter choice in Case 1 whenμ=1.11.
No. Destination node Capacity (pcu/h) Demand (pcu/h) 1 3 1000 997 2 6 800 800 3 9 1200 1200In case 2, by increasing the shelter capacity, the maximum multiplierμ coms up to 2.00. The corresponding results at optimal are shown in Tables 12 and 13. Although shelter 6 is saturated, but there is still plenty of room in shelter 3 and 9, to accommodate additional evacuation demands. Some typical links are saturated including links 1, 3, 5, 11, and 15. Meanwhile, the opposite links of link 1, 3, and 5 have no remaining capacity, which means the capacity of these three links cannot be enlarged by applying reversal lane strategy. In other words, the emergency reliability of the entire road network is limited.Table 12
Feasible lane distribution scheme and link flow in Case 2 whenμ=2.00.
Link No. Number of lanes Capacity Link flow(pcu/h) 1 6 1800 1800 2 0 0 0 3 6 1800 1800 4 0 0 0 5 4 1200 1200 6 0 0 0 7 4 1200 0 8 4 1200 0 9 1 300 0 10 5 1500 0 11 7 2100 2100 12 1 300 0 13 8 2400 2100 14 0 0 0 15 5 1500 1500 16 1 300 0 17 0 0 0 18 8 2400 0 19 5 1500 1300 20 1 300 0 21 6 1800 1500 22 0 0 0 23 6 1800 1500 24 0 0 0Table 13
Detailed information for shelter choice in Case 2 whenμ=2.00.
No. Destination node Capacity (pcu/h) Demand (pcu/h) 1 3 3000 1800 2 6 800 800 3 9 3000 2800In conclusion, the emergency reliability of the entire road network can be limited by both shelter capacity and road capacity. Although improving road capacity is a good way to improve network emergency reliability, sometimes, increasing the shelter capacity, there would also be a significant increase in the network emergency reliability.(b) Performance Evaluation of the Proposed Algorithm.Case 3 and 4 are obtained by adjusting the pattern of evacuation demand. Both cases can be solved effectively by the proposed algorithm.By analyzing the solution results of all the above cases and combining the enumeration method, the true optimal value of multiplierμ in different cases can be obtained. The true optimal can also be checked by the network topology under feasible lane distribution schemes. The results are shown in Table 14. It can be seen that, in different cases, the optimal multiplier calculated by the proposed algorithm is almost equal to its true optimal value, and the slight difference in some cases is caused by the step size. Therefore, the algorithm proposed in this paper is proved to be of high accuracy.Table 14
Comparison between calculated optimal solution and true optimal solution.
Calculated optimal Computation time True optimal Case 1 1.11 125 1.111111 Case 2 2.00 1125 2 Case 3 2.22 1340 2.222222 Case 4 1.80 940 1.8The computation time of the proposed algorithm is mainly consumed in solving the lower level joint UE distribution/assignment problem. Therefore, in this paper, the times of solving the lower assignment problem are used to evaluate the solving efficiency of the proposed algorithm. Each case runs 10 times, and the average times to solve the lower assignment problem are listed in Table14. It can be seen that the calculation times are acceptable in those numerical experiments. In addition, the research results of this paper are applicable to evaluate the existing road network at the level of management planning, and the solving efficiency of the model can meet the actual needs.


## 6.1. Topology of Network

Take the test network in the Figure1 as the example, which has 9 nodes and 24 directed links. Here node 1 and node 4 are the origin points of evacuation, and node 3, 6, and 9 are shelters. Information of link properties in the network, including link free flow travel time and link capacities, is listed in Table 1. Information of evacuation demand of each origin point is listed in Table 2, and Table 3 gives the information of the capacity of shelters.Table 1
Information of link properties.
Link no. Starting node Ending node Number of lanes Free-flow travel time (min) Capacity(pcu/h) 1 1 2 3 1.5 900 2 2 1 3 1 900 3 2 3 3 0.8 900 4 3 2 3 0.8 900 5 1 4 2 1 600 6 4 1 2 0.8 600 7 2 5 4 1.25 1200 8 5 2 4 1 1200 9 3 6 3 1.25 900 10 6 3 3 2 900 11 4 5 4 1.5 1200 12 5 4 4 1.25 1200 13 5 6 4 0.75 1200 14 6 5 4 0.6 1200 15 4 7 3 0.8 900 16 7 4 3 0.9 900 17 5 8 4 1.25 1200 18 8 5 4 1.2 1200 19 6 9 3 1.1 900 20 9 6 3 1 900 21 7 8 3 0.95 900 22 8 7 3 0.9 900 23 8 9 3 1.2 900 24 9 8 3 1.3 900Table 2
Information of evacuation demand.
No. Origin node Demand (pcu/h) 1 1 1500 2 4 1200Table 3
Information of shelter capacity.
No. Destination node Capacity (pcu/h) 1 3 1000 2 6 800 3 9 1200Figure 1
Topology of tested network.Modify the original network by adding a dummy node 10 and connect it with three shelters by three dummy links. The topology of modified network is shown in Figure2. As mentioned above, free flow travel time of each dummy link is always 0, and capacity of each dummy link equals to the capacity of the corresponding shelter. On the basis of the modification above, the problem of interest is transformed into UE assignment problem of a multiorigin and single-destination network with link capacity constraints.Figure 2
Topology of modified network.


## 6.2. Result Analysis

(1) Result Analysis of the Lower Model. The trip assignment results are analyzed when μ=1 without changing the number of lanes in each link. In the experiment, values of each parameter are as follows: ρ=0.01, ε1=ε2=0.001, the initial penalty function coefficient λa0=0.1t0, where t0 denotes the average of free flow travel time on all links. The BPR formula is employed as impedance function and two parameters in the function are set as 0.15 and 4, respectively.(a) From the Perspective of Route Choice.Tables 4 and 5 show the path details of OD pair 1-10 and 4-10 at equilibrium. From the perspective of route choice, for OD pair 1-10, three paths are chosen by evacuees, and the generalized travel time for these three paths is all equal to 4.8443min, which is the minimum generalized travel time of this OD pair. The generalized travel time of unselected paths including path 4, 5, and 6 is 6.1449, 6.0435, and 6.9712min, respectively, all larger than 4.8443min. Similarly, for OD pair 4-10, three paths are chosen by evacuees, and the generalized travel time for these three paths is all equal to 3.6940min. The generalized travel time of unselected paths including path 4, 5, and 6 is 4.5875, 5.6443, and 6.0504min, respectively.Table 4
Path details of OD pair 1-10 at equilibrium.
Path No. Path flow(pcu/h) Composition of path(link no.) Travel time(min) Queuing delay(min) Generalized travel time(min) 1 900 1,3,25 2.645 2.1993 4.8443 2 557.6044 5,15,21,23,27 4.2837 0.5606 4.8443 3 42.3956 5,11,13,26 3.7375 1.1068 4.8443 4 0 5,11,7,3,25 5.0450 1.0999 6.1449 5 0 1,7,13,26 3.8375 2.2060 6.0435 6 0 5,15,21,17,13,9,25 6.4106 0.5606 6.9712Table 5
Path details of OD pair 4-10 at equilibrium.
Path No. Path flow(pcu/h) Composition of path(link no.) Travel time(min) Queuing delay(min) Generalized travel time(min) 1 757.6044 11,13,26 2.5875 1.1065 3.6940 2 42.3956 15,21,23,27 3.1337 0.5603 3.6940 3 400 11,13,19,27 3.6939 0.0001 3.6940 4 0 11,13,10,25 4.5875 0 4.5875 5 0 6,1,3,25 3.4450 2.1993 5.6443 6 0 15,21,23,19,9,25 5.4901 0.5603 6.0504Although the path flow results of traffic assignment in crowded traffic networks with queuing delays are not necessarily unique, the result satisfies that generalized travel time of all the selected paths is equal, which meets the conditions of UE equilibrium.(b) From the Perspective of Shelter Choice.According to the path flow results, the demand from origins to all the shelter can be referred, shown in Table 6. For origin node 1, the number of evacuees choosing shelter 3, 6, and 9 is 900, 42.3956, and 557.6044, respectively. And the generalized travel time from node 1 to all the shelters is equal to 4.8443. For origin node 4, the number of evacuees choosing shelter 6 and 9 is 757.6044 and 442.3956, respectively. No one chooses shelter 3 because its generalized travel time is 3.8375, a little larger than other shelters.Table 6
Detailed information for OD pairs.
No. Origin node Destination node Demand(pcu/h) Minimum generalized travel time(min) 1 1 3 900 4.8443 2 1 6 42.3956 4.8443 3 1 9 557.6044 4.8443 4 4 3 0 3.8375 5 4 6 757.6044 3.6940 6 4 9 442.3956 3.6940That means for a certain origin, generalized travel time of all the selected shelters is equal, and generalized travel time of shelters which are not chosen is larger than the chosen shelters.Table7 shows the final shelter demands. The number of evacuees choosing the three shelters is 900, 800, and 1000, respectively. And among them, only shelter 6 reaches its capacity, and the queuing delay is 1.1064 min. The other two shelters are not saturated and the queuing delays are both 0. This is consistent with the previous conclusion that the queuing delay associated with shelters only exists when the shelter has reached its capacity.Table 7
Detail information for shelter choice.
No. Destination node Capacity(pcu/h) Demand(pcu/h) Queuing Delay(min) 1 3 1000 900 0 2 6 800 800 1.1064 3 9 1200 1000 0All the experimental results are consistent with the above analysis of first-order conditions of the Lagrangian function.(2) Results Analysis of Bilevel Model.In order to illustrate the rationality of the model and the effectiveness of the algorithm proposed in this paper, three different demand scenarios and two different shelter capacity scenarios (shown in Table 8) are constructed, and four cases of combination of different scenarios are generated (shown in Table 9).Table 8
Information of different demand and shelter capacity scenarios.
Demand scenarios Shelter capacity scenarios Origin node Demand (pcu/h)  Destination node Capacity (pcu/h) D1 1 1500 S1 3 1000 4 1200  6 800 D2 1 700  9 1200 4 2000 S2 3 3000 D3 4 700  6 800 7 2000  9 3000Table 9
Information of combination of different scenarios.
No. Demand scenario Shelter capacity scenario Case 1 D1 S1 Case 2 D1 S2 Case 3 D2 S2 Case 4 D3 S2In the solving algorithm, set step sizeσ=0.01, population size as m=10, maximum iteration count max=50, and mutation probability p=0.8.(a) Results Analysis of Different Cases.In case 1, the maximum multiplier μ that the solution algorithm can obtain is 1.11. The corresponding feasible lane distribution scheme and link flow are shown in Table 10. Only links 5, 15, and 19 are saturated, but there is still plenty of potential room for the capacity of these links. Table 11 shows the corresponding shelter demands. Three shelters are chosen by 997, 800, and 1200 evacuees, respectively. All the shelters are almost saturated. It turns out that the emergency reliability of the entire road network in the case here is limited to the shelter capacity.Table 10
Feasible lane distribution scheme and link flow in Case 1 whenμ=1.11.
Link No. Number of lanes Capacity Link flow(pcu/h) 1 5 1500 1065 2 1 300 0 3 4 1200 1000 4 2 600 0 5 2 600 600 6 2 600 0 7 6 1200 65 8 2 600 0 9 5 1500 0 10 1 300 0 11 5 1500 1332 12 3 900 0 13 7 2100 1100 14 1 300 0 15 2 600 600 16 4 1200 0 17 4 1200 297 18 4 1200 0 19 1 300 300 20 5 1500 0 21 3 900 600 22 3 900 0 23 3 900 897 24 3 900 0Table 11
Detailed information for shelter choice in Case 1 whenμ=1.11.
No. Destination node Capacity (pcu/h) Demand (pcu/h) 1 3 1000 997 2 6 800 800 3 9 1200 1200In case 2, by increasing the shelter capacity, the maximum multiplierμ coms up to 2.00. The corresponding results at optimal are shown in Tables 12 and 13. Although shelter 6 is saturated, but there is still plenty of room in shelter 3 and 9, to accommodate additional evacuation demands. Some typical links are saturated including links 1, 3, 5, 11, and 15. Meanwhile, the opposite links of link 1, 3, and 5 have no remaining capacity, which means the capacity of these three links cannot be enlarged by applying reversal lane strategy. In other words, the emergency reliability of the entire road network is limited.Table 12
Feasible lane distribution scheme and link flow in Case 2 whenμ=2.00.
Link No. Number of lanes Capacity Link flow(pcu/h) 1 6 1800 1800 2 0 0 0 3 6 1800 1800 4 0 0 0 5 4 1200 1200 6 0 0 0 7 4 1200 0 8 4 1200 0 9 1 300 0 10 5 1500 0 11 7 2100 2100 12 1 300 0 13 8 2400 2100 14 0 0 0 15 5 1500 1500 16 1 300 0 17 0 0 0 18 8 2400 0 19 5 1500 1300 20 1 300 0 21 6 1800 1500 22 0 0 0 23 6 1800 1500 24 0 0 0Table 13
Detailed information for shelter choice in Case 2 whenμ=2.00.
No. Destination node Capacity (pcu/h) Demand (pcu/h) 1 3 3000 1800 2 6 800 800 3 9 3000 2800In conclusion, the emergency reliability of the entire road network can be limited by both shelter capacity and road capacity. Although improving road capacity is a good way to improve network emergency reliability, sometimes, increasing the shelter capacity, there would also be a significant increase in the network emergency reliability.(b) Performance Evaluation of the Proposed Algorithm.Case 3 and 4 are obtained by adjusting the pattern of evacuation demand. Both cases can be solved effectively by the proposed algorithm.By analyzing the solution results of all the above cases and combining the enumeration method, the true optimal value of multiplierμ in different cases can be obtained. The true optimal can also be checked by the network topology under feasible lane distribution schemes. The results are shown in Table 14. It can be seen that, in different cases, the optimal multiplier calculated by the proposed algorithm is almost equal to its true optimal value, and the slight difference in some cases is caused by the step size. Therefore, the algorithm proposed in this paper is proved to be of high accuracy.Table 14
Comparison between calculated optimal solution and true optimal solution.
Calculated optimal Computation time True optimal Case 1 1.11 125 1.111111 Case 2 2.00 1125 2 Case 3 2.22 1340 2.222222 Case 4 1.80 940 1.8The computation time of the proposed algorithm is mainly consumed in solving the lower level joint UE distribution/assignment problem. Therefore, in this paper, the times of solving the lower assignment problem are used to evaluate the solving efficiency of the proposed algorithm. Each case runs 10 times, and the average times to solve the lower assignment problem are listed in Table14. It can be seen that the calculation times are acceptable in those numerical experiments. In addition, the research results of this paper are applicable to evaluate the existing road network at the level of management planning, and the solving efficiency of the model can meet the actual needs.


## 7. Conclusions

Reliability is an important feature of transportation network. In order to evaluate the reliability of road network under emergency evacuation, a bilevel programming model is proposed in this paper. The concept of reserve capacity is adopted, and the influence of reversible lane measures taken under emergency conditions, as well as the capacity limits of links and shelters, are considered. An iterative optimization method is proposed to solve the upper level model, and the lower level model is transformed and then solved by a dynamic penalty function algorithm. Finally, the numerical example demonstrates the rationality of the proposed model and feasibility of the proposed solution algorithms.The proposed lower level model can effectively reflect the route choice and shelter choice behavior of evacuees under emergency condition. Evacuees may choose to evacuate to another shelter if the shelter with smaller travel time is full. Besides, when the shortest path has reached its maximum capacity, evacuees are forced to choose other subprime paths. The assignment result accords with UE equilibrium.Although the reserve capacity of the network can be improved by reversible lane measures, but both link capacity and shelter capacity could be the restriction of emergency reliability of the entire road network. In addition, the efficiency of the proposed algorithms is also verified in the case study.The model proposed here is a little complicated and many practical problems have been simplified. In further study, the proposed model can be not difficult to contain congestion and delays at intersections. Additionally, uncertainty factors should be considered, including demand uncertainty, disaster location uncertainty, link capacity uncertainty, and so on.



---

*Source: 1370159-2019-03-07.xml*