# Assessing Urban Road Network Capacity considering Parking Supply and Parking Pricing

Authors: Xiaowei Jiang; Muqing Du; Haisheng Liu
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

To enhance the assessment of the network capacity for a given urban road system, the effects of the parking management strategies at destination areas are supposed to be considered in the network capacity assessment model. This study provides an extended road network capacity model which takes into consideration both the parking supply and parking pricing at each traffic zone. The network capacity model is formulated as a bilevel programming problem, with the maximization of total trip generation in the upper level and the combined trip distribution and traffic assignment (CTDTA) problem in the lower level. To reasonably characterize the impacts of the parking pricing and parking delay due to the congestion effect, two classes of travel demand are involved in the CTDTA model. An efficient and practical algorithm is provided for the solution of the bilevel network capacity model. Numerical experiments show the advantages of the proposed model and also demonstrate the effect of the parking supply and parking pricing on the assessment results of the road network capacity.


---

## Body

## 1. Introduction

The rapid growth of motor vehicle travel demand leads to most cities suffering from traffic congestion and parking space shortage. The road network capacity assessment is helpful to reflect the capability of the urban road system for allocating the maximum travel demand by motorists. Hence, to properly assess the capacity of the urban road network has long been an important goal for transportation project planning and evaluation. In the literature, most research explores the transportation network capacity problem by only considering the constraints from the link capacities (e.g., [1, 2]). However, a few studies indicate that involving the impact of parking management strategies can help to obtain more practical and reasonable results for the urban road network [3, 4]. On the other hand, assessing the network capacity with the parking management will be meaningful to properly coordinate the parking resource and motor travel demand in the level of the road network. The network-wide origin-destination (O-D) demand could redistribute in space due to the implementation of the new parking management strategies. Thereby, to incorporate the parking supply and/or parking pricing into the transportation network capacity problem will be of theoretical and practical significance for the decision making in urban parking management.The concept of network capacity is defined as the maximum travel demand that can be allocated to the transportation network without violating the capacity of any individual component (e.g., link and intersection) [5]. The network capacity has been recognized as an important measure to assess the network-wide performance in the urban transportation system. This concept has been widely used in many applications, such as capacity reliability analysis [6], network design problem [7], capacity flexibility analysis [8], and capacity vulnerability analysis [9]. Early studies assessed road network capacity by considering the capacity constraint on each road segment [10]. The maximum capacity was estimated by assigning the total O-D demand gradually, in which every slice of the O-D demand is loaded with an equilibrium traffic assignment [11]. Following that, the traffic signal splits at intersections were incorporated into the network capacity problem. The concept of reserve capacity is proposed [1] and extended in the study of the signal-controlled network [12–14]. Since the reserve capacity model assumes the O-D demand distribution to be unchanged, which is not practical for the networks in the developing areas, variable O-D demand was involved in the network capacity assessment [2, 5, 15]. On the other hand, as the distribution of the total O-D travel demand (compared with that of the motor O-D demand) is relatively stable, the multimodal choice was extended based on the reserve capacity concept [16, 17], in which the total demand with a fixed O-D distribution splits into several variable O-D tables which are separately associated with the different travel modes. Besides, other studies explored the impact of market penetration of the advanced traveler information system (ATIS) on the road network capacity [18]. Only limited research can be found for the impact of the parking supply or parking pricing on the transportation network capacity [3, 4, 19].In the assessment of the urban road network capacity, the parking constraints are twofold: (1) the parking supply, which determines both the upper bound of the parking demand and the parking time due to the level of congestion in each trip destination; (2) the parking pricing, which decides the parking fee at each destination area. Note that the upper limit of the parking demand can be regarded as the parking capacity that limits the growth of the travel demand by motorists, which is the same as the role of the link capacity. The parking time and fee at destinations are supposed to affect some travelers' travel choices, which leads to the redistribution of the O-D travel demand network wide. According to the existing studies, Asakura and Kashiwadani [19] and Leng and Yan [4] only consider the effect of the parking capacity on the network-wide capacity, and thus, the change on O-D demand pattern was not considered. Although Tam and Lam [3] involved both parking capacity and parking charge at destinations, the entire O-D trip distribution was assumed to only depend on the travel cost (specifically the accessibility measures) between the O-D pair, i.e., the level of destination congestion was not considered. Nevertheless, the parking time due to the level of destination congestion has been studied in the context of parking choice problems [20–23]. The parking (search) time is often defined as an increased function in terms of the parking demand dividing the parking capacity at the destination area. Xie et al. [24] once employed the parking time function in their study on the network capacity. They assumed all travel demands are variable under the impact of the travel cost at destinations, which could be loss of generality because the commuting demand may not willing to change their destination even the destination cost is very high.In summary, the existing research on the road network capacity considering parking supply and parking pricing has the following inadequacies: (1) only some of the factors were involved in the network capacity assessment, so the effect of the urban parking management strategies cannot be evaluated comprehensively [19]; (2) incomplete to characterize the impact of destination congestion on the network-wide travel demand pattern [3], which may result in impractical O-D demand pattern for the maximum network capacity; (3) not consider the difference among the motor travelers and, thus, causes the underestimate [4] or overestimate [24] to the total network capacity. In this study, we will characterize both the parking supply and parking pricing and incorporate them into a combined trip distribution and traffic assignment (CTDTA) model [25] which involves two classes of motor travel demand, i.e., the fixed demand and the variable demand. We refer the fixed demand to be the commuting motorists which will hold a stable O-D pattern under the impact of destination parking cost and refer the variable demand to be the non-commuting motorists which show a variable demand pattern with respect to the level of congestion in both the road network and the destination areas. The new model is expected to better capture the effect of both parking supply and parking pricing on the urban road network. The application of the new model will be more practical and helpful for assessing the capacity of the given road network, especially for the demonstration of strategies in urban parking management.The remaining of this paper is organized as follows. The next section presents the new urban road network capacity model with parking supply and parking demand. Then, section3 provides an efficient solution algorithm for our proposed model formulated as bilevel programming. Numerical experiments are conducted in section 4 to demonstrate the feature of the new model and the effect of parking supply and parking demand on the network capacity assessment. Finally, conclusions are summarized in section 5.


## 2. The Extended Road Network Capacity Model

### 2.1. Model Assumptions

The following assumptions are made to facilitate the presentation of the essential ideas in this study:(a)
Two classes of travel demand by motorists are involved, i.e., the fixed demand and variable demand. The fixed demand is related to the daily travel demand that has predetermined origins and destinations, such as the commuting traffic. The pattern (trips and spatial distribution) of the fixed demand will be stable regardless of the change of the travel impedance or cost from the origin to destination. On the contrary, the destinations of the variable demand are exchangeable with respect to the crowdedness and costs at the destinations, and thus, such kind of demand (such as shopping and recreation) shows a flexible demand pattern.(b)
The travelers associated with the fixed demand can only change the paths to minimize the individual travel cost, which is characterized by the user equilibrium principle. The travelers associated with the variable demand can change both the paths and destinations to minimize the total travel cost, which will be characterized by the combined trip distribution and traffic assignment model.(c)
The parking demand is a ratio of the total destination demand at a destination area, and it is restrained by the space of the parking facilities.(d)
Travelers have sufficient network information to choose travel paths in a user equilibrium manner.(e)
Due to the static nature of the model, the traffic flow is assumed in a steady state, and the study period is assumed to be one hour, such as the morning peak hour.


### 2.2. Model Formulation

We consider a directed networkG=N,A, where N is the set of all nodes and A is the set of all directed links. Let I and J be the set of origins and the set of destinations, respectively. Let Rij be the set of paths between the O-D pair i,j,∀i∈I,j∈J. The traffic flow on link a∈A is denoted by va. The travel time on link a is an increasing function of the traffic flow through itself, i.e., ta=tava. The variable travel demand between the O-D pair i,j is denoted by qij, and the fixed demand is denoted by eij. Let frij and hrij represent the traffic flow on path r corresponding to the variable demand and fixed demand, respectively.Since both the level and distribution of the variable demand are changeable with respect to the traffic situation in the transport network, the utility between origins and destinations will be utilized to derive the flow pattern of the variable demand. Hence, we define the utility from origini to destination j by Uij, which consists of the generalized destination cost Mj and the minimum travel cost τij from i to j, i.e., Uij=−τij−Mj. Specifically, Mj is defined as an increasing function of the total travel demand, Dj, at the destination j. As the noncommuting travelers at each origin i may have certain randomness on the destination choice, we employ the logit choice model to produce the conditional probability that a traveler from origin i will choose destination j, which is given by(1)Pj|i=exp−θτij+Mj∑n∈Jexp−θτin+Mn,∀i∈I,where θ is the dispersion parameter that reflects the traveler’s sensitivity to the travel utility.In equation (1), the minimum travel cost τijis determined by the network-wide traffic flow pattern in the context of the congestion. Generally, it can be conducted from the network equilibrium models. In this study, we obtain it by using an equilibrium combined trip distribution and traffic assignment model which can cope with the mixture of the fixed and variable demand. Besides, the generalized destination cost Mj will be incorporated with the pricing and the searching time in the parking area. The details will be presented in the remainder of this section. Our network capacity model will be formulated in a bilevel framework, where the upper-level problem maximizes the throughput of the network and the lower-level problem regulates the travel choice behaviors of the network users (for both the variable and fixed demand).


#### 2.2.1. Parking Supply and Parking Pricing

Letqj be the total occupancy of parking j∈J under equilibrium, and let kj be the capacity of parking j. Note that parking occupancy qj is obtained by multiplying the total travel demand, Dj, at area j with the parking rate ρj, i.e.,(2)qj=ρj⋅Dj,∀j∈J,where the total travel demand at destination j will be given by Dj=∑i∈Iqij+eij.Furthermore, we assume the parking search time is a convex function of parking occupancyqj and parking capacity kj [26]. Thus, the parking search time function Sjqj can be formulated as(3)Sjqj=μjsj1−qj/kj,∀j∈J,where sj is the average searching time in destination area j when the parking occupancy is low, referred to as the low-occupancy searching time. μj is a constant denoting how drivers’ attitudes to parking occupancy information. If drivers are unaware of the searching time, set μj=0; if drivers are completely aware of searching time, set μj=1. Note that the searching time reaches infinity as parking occupancy qj approaches parking capacity kj. This indicates that drivers arriving at a full occupancy parking area will never find a parking space.Although the parking time function in equation (3) nicely captures the effect of parking demand versus parking supply, the calculation of this function can lead to infeasible solutions if the parking occupancy is equal or greater than the parking capacity. Alternatively, the BPR-type functions were often employed [21, 23] to avoid the discontinuous phenomenon when the parking demand is approaching the capacity. We recommend the following formulation in practice:(4)Sjqj=sj1+φqjkjω,∀j∈J,where φ and ω are calibration parameters. When qj⟶kj, the parking search time increases to the 1+φ times of the low-occupancy searching time sj.The hourly parking price at areaj is denoted by πj. Thus, the drivers who choose area j as a travel destination will pay πj dollars per hour. Therefore, the generalized destination cost, Mj, for travelers who choose area j as their destination, is given by(5)Mj=πj+η⋅Sjqj,where η is the value of time for travelers. Generally, the values of πj are various for different destination areas, which depends on the industrial structure, land use, and locations. To reflect the differences among the destination areas, a more detailed traffic zone division will be implemented in practice.From the aspect of parking supply constraint, the parking occupancy should not exceed the parking capacity in areai, that is,(6)qj≤kj,∀j∈J.


#### 2.2.2. Combined Trip Distribution and Traffic Assignment Model

In this section, the lower-level model of the network capacity problem will be formulated by considering the parking cost at destinations. Following the assumptions in Section2.1, we consider the travelers can choose the destinations and paths to minimize the travel cost accordingly. The combined trip distribution and traffic assignment (CTDTA) model [25] will be employed to capture travelers’ behavior. Specifically, both the fixed demand and variable demand are considered in the road network. The travelers with fixed demand will be free to choose their travel paths, while the travelers with variable demand will be free to choose either the paths or the destinations. Both types of travelers aim to minimize their own travel cost for the whole trip. Furthermore, the CTDTA model will be extended to involve the parking supply and parking pricing at destinations, which will impact the destination choice of the variable travel demand. Thus, the extended CTDTA model is given as follows:(7)minZLq,f,h=∑a∈A∫0vataxdx+1θ∑i∈I∑j∈Jqijlnqij−1+∑j∈Jqjπj+η∑j∈J∫0qjSjydy,(8)s.t.∑j∈Jqij=Oi,∀i∈I,(9)∑r∈Rijhrij=eij,∀i∈I,j∈J,(10)∑r∈Rijfrij=qij,∀i∈I,j∈J,(11)va=∑i∈I∑j∈J∑r∈Rijfrij+hrijδa,rij,∀a∈A,(12)frij≥0,∀r∈Rij,i∈I,j∈J,(13)hrij≥0,∀r∈Rij,i∈I,j∈J,(14)qij≥0,∀i∈I,j∈J,where δa,rij is the link/path incidence indicator, which equals to 1 if link a is on path r between the O-D pair i,j and 0 otherwise. In the objective function, the first term indicates the user equilibrium of all travelers. The second term indicates the destination choice behavior of the variable demand only. The third and the fourth terms indicate the parking charging and the parking searching time at the destination area, respectively. Equations (8)–(10) define the flow conservation of the variable and fixed demand. Equation (11) is the relationship between link flows and path flows. Equations (12)–(14) are nonnegative constraints. Besides, according to the first-order necessary condition, the O-D flows of the variable demand is produced by the following logit share model:(15)qij=Oi⋅exp−θτij+πj+SjDj∑n∈Jexp−θτin+πn+SnDn,∀i∈I,j∈J,where the parking cost function, SjDj, is defined in equation (4).


#### 2.2.3. Total Trip Maximization Model

The upper-level problem defines a maximum trip production model, where the limits of the individual link capacity and zonal parking supply are considered. Thus, the upper-level problem is given by(16)maxZUO˜=∑i∈IO˜i,(17)s.t.vaO˜≤Ca,∀a∈A,(18)ρj⋅∑i∈IqijO˜+eij≤kj,∀j∈J,(19)O˜i≥0,∀i∈I.where vaO˜ and qijO˜ are obtained by solving the lower-level model. The objective is to maximize the summation of the trip production of the variable demand, O˜i, from each origin. Equation (17) represents that the traffic flow on each link should not exceed its capacity. Equation (18) represents that the parking demand at each traffic zone should not be over its parking space.


## 2.1. Model Assumptions

The following assumptions are made to facilitate the presentation of the essential ideas in this study:(a)
Two classes of travel demand by motorists are involved, i.e., the fixed demand and variable demand. The fixed demand is related to the daily travel demand that has predetermined origins and destinations, such as the commuting traffic. The pattern (trips and spatial distribution) of the fixed demand will be stable regardless of the change of the travel impedance or cost from the origin to destination. On the contrary, the destinations of the variable demand are exchangeable with respect to the crowdedness and costs at the destinations, and thus, such kind of demand (such as shopping and recreation) shows a flexible demand pattern.(b)
The travelers associated with the fixed demand can only change the paths to minimize the individual travel cost, which is characterized by the user equilibrium principle. The travelers associated with the variable demand can change both the paths and destinations to minimize the total travel cost, which will be characterized by the combined trip distribution and traffic assignment model.(c)
The parking demand is a ratio of the total destination demand at a destination area, and it is restrained by the space of the parking facilities.(d)
Travelers have sufficient network information to choose travel paths in a user equilibrium manner.(e)
Due to the static nature of the model, the traffic flow is assumed in a steady state, and the study period is assumed to be one hour, such as the morning peak hour.


## 2.2. Model Formulation

We consider a directed networkG=N,A, where N is the set of all nodes and A is the set of all directed links. Let I and J be the set of origins and the set of destinations, respectively. Let Rij be the set of paths between the O-D pair i,j,∀i∈I,j∈J. The traffic flow on link a∈A is denoted by va. The travel time on link a is an increasing function of the traffic flow through itself, i.e., ta=tava. The variable travel demand between the O-D pair i,j is denoted by qij, and the fixed demand is denoted by eij. Let frij and hrij represent the traffic flow on path r corresponding to the variable demand and fixed demand, respectively.Since both the level and distribution of the variable demand are changeable with respect to the traffic situation in the transport network, the utility between origins and destinations will be utilized to derive the flow pattern of the variable demand. Hence, we define the utility from origini to destination j by Uij, which consists of the generalized destination cost Mj and the minimum travel cost τij from i to j, i.e., Uij=−τij−Mj. Specifically, Mj is defined as an increasing function of the total travel demand, Dj, at the destination j. As the noncommuting travelers at each origin i may have certain randomness on the destination choice, we employ the logit choice model to produce the conditional probability that a traveler from origin i will choose destination j, which is given by(1)Pj|i=exp−θτij+Mj∑n∈Jexp−θτin+Mn,∀i∈I,where θ is the dispersion parameter that reflects the traveler’s sensitivity to the travel utility.In equation (1), the minimum travel cost τijis determined by the network-wide traffic flow pattern in the context of the congestion. Generally, it can be conducted from the network equilibrium models. In this study, we obtain it by using an equilibrium combined trip distribution and traffic assignment model which can cope with the mixture of the fixed and variable demand. Besides, the generalized destination cost Mj will be incorporated with the pricing and the searching time in the parking area. The details will be presented in the remainder of this section. Our network capacity model will be formulated in a bilevel framework, where the upper-level problem maximizes the throughput of the network and the lower-level problem regulates the travel choice behaviors of the network users (for both the variable and fixed demand).


### 2.2.1. Parking Supply and Parking Pricing

Letqj be the total occupancy of parking j∈J under equilibrium, and let kj be the capacity of parking j. Note that parking occupancy qj is obtained by multiplying the total travel demand, Dj, at area j with the parking rate ρj, i.e.,(2)qj=ρj⋅Dj,∀j∈J,where the total travel demand at destination j will be given by Dj=∑i∈Iqij+eij.Furthermore, we assume the parking search time is a convex function of parking occupancyqj and parking capacity kj [26]. Thus, the parking search time function Sjqj can be formulated as(3)Sjqj=μjsj1−qj/kj,∀j∈J,where sj is the average searching time in destination area j when the parking occupancy is low, referred to as the low-occupancy searching time. μj is a constant denoting how drivers’ attitudes to parking occupancy information. If drivers are unaware of the searching time, set μj=0; if drivers are completely aware of searching time, set μj=1. Note that the searching time reaches infinity as parking occupancy qj approaches parking capacity kj. This indicates that drivers arriving at a full occupancy parking area will never find a parking space.Although the parking time function in equation (3) nicely captures the effect of parking demand versus parking supply, the calculation of this function can lead to infeasible solutions if the parking occupancy is equal or greater than the parking capacity. Alternatively, the BPR-type functions were often employed [21, 23] to avoid the discontinuous phenomenon when the parking demand is approaching the capacity. We recommend the following formulation in practice:(4)Sjqj=sj1+φqjkjω,∀j∈J,where φ and ω are calibration parameters. When qj⟶kj, the parking search time increases to the 1+φ times of the low-occupancy searching time sj.The hourly parking price at areaj is denoted by πj. Thus, the drivers who choose area j as a travel destination will pay πj dollars per hour. Therefore, the generalized destination cost, Mj, for travelers who choose area j as their destination, is given by(5)Mj=πj+η⋅Sjqj,where η is the value of time for travelers. Generally, the values of πj are various for different destination areas, which depends on the industrial structure, land use, and locations. To reflect the differences among the destination areas, a more detailed traffic zone division will be implemented in practice.From the aspect of parking supply constraint, the parking occupancy should not exceed the parking capacity in areai, that is,(6)qj≤kj,∀j∈J.


### 2.2.2. Combined Trip Distribution and Traffic Assignment Model

In this section, the lower-level model of the network capacity problem will be formulated by considering the parking cost at destinations. Following the assumptions in Section2.1, we consider the travelers can choose the destinations and paths to minimize the travel cost accordingly. The combined trip distribution and traffic assignment (CTDTA) model [25] will be employed to capture travelers’ behavior. Specifically, both the fixed demand and variable demand are considered in the road network. The travelers with fixed demand will be free to choose their travel paths, while the travelers with variable demand will be free to choose either the paths or the destinations. Both types of travelers aim to minimize their own travel cost for the whole trip. Furthermore, the CTDTA model will be extended to involve the parking supply and parking pricing at destinations, which will impact the destination choice of the variable travel demand. Thus, the extended CTDTA model is given as follows:(7)minZLq,f,h=∑a∈A∫0vataxdx+1θ∑i∈I∑j∈Jqijlnqij−1+∑j∈Jqjπj+η∑j∈J∫0qjSjydy,(8)s.t.∑j∈Jqij=Oi,∀i∈I,(9)∑r∈Rijhrij=eij,∀i∈I,j∈J,(10)∑r∈Rijfrij=qij,∀i∈I,j∈J,(11)va=∑i∈I∑j∈J∑r∈Rijfrij+hrijδa,rij,∀a∈A,(12)frij≥0,∀r∈Rij,i∈I,j∈J,(13)hrij≥0,∀r∈Rij,i∈I,j∈J,(14)qij≥0,∀i∈I,j∈J,where δa,rij is the link/path incidence indicator, which equals to 1 if link a is on path r between the O-D pair i,j and 0 otherwise. In the objective function, the first term indicates the user equilibrium of all travelers. The second term indicates the destination choice behavior of the variable demand only. The third and the fourth terms indicate the parking charging and the parking searching time at the destination area, respectively. Equations (8)–(10) define the flow conservation of the variable and fixed demand. Equation (11) is the relationship between link flows and path flows. Equations (12)–(14) are nonnegative constraints. Besides, according to the first-order necessary condition, the O-D flows of the variable demand is produced by the following logit share model:(15)qij=Oi⋅exp−θτij+πj+SjDj∑n∈Jexp−θτin+πn+SnDn,∀i∈I,j∈J,where the parking cost function, SjDj, is defined in equation (4).


### 2.2.3. Total Trip Maximization Model

The upper-level problem defines a maximum trip production model, where the limits of the individual link capacity and zonal parking supply are considered. Thus, the upper-level problem is given by(16)maxZUO˜=∑i∈IO˜i,(17)s.t.vaO˜≤Ca,∀a∈A,(18)ρj⋅∑i∈IqijO˜+eij≤kj,∀j∈J,(19)O˜i≥0,∀i∈I.where vaO˜ and qijO˜ are obtained by solving the lower-level model. The objective is to maximize the summation of the trip production of the variable demand, O˜i, from each origin. Equation (17) represents that the traffic flow on each link should not exceed its capacity. Equation (18) represents that the parking demand at each traffic zone should not be over its parking space.


## 2.2.1. Parking Supply and Parking Pricing

Letqj be the total occupancy of parking j∈J under equilibrium, and let kj be the capacity of parking j. Note that parking occupancy qj is obtained by multiplying the total travel demand, Dj, at area j with the parking rate ρj, i.e.,(2)qj=ρj⋅Dj,∀j∈J,where the total travel demand at destination j will be given by Dj=∑i∈Iqij+eij.Furthermore, we assume the parking search time is a convex function of parking occupancyqj and parking capacity kj [26]. Thus, the parking search time function Sjqj can be formulated as(3)Sjqj=μjsj1−qj/kj,∀j∈J,where sj is the average searching time in destination area j when the parking occupancy is low, referred to as the low-occupancy searching time. μj is a constant denoting how drivers’ attitudes to parking occupancy information. If drivers are unaware of the searching time, set μj=0; if drivers are completely aware of searching time, set μj=1. Note that the searching time reaches infinity as parking occupancy qj approaches parking capacity kj. This indicates that drivers arriving at a full occupancy parking area will never find a parking space.Although the parking time function in equation (3) nicely captures the effect of parking demand versus parking supply, the calculation of this function can lead to infeasible solutions if the parking occupancy is equal or greater than the parking capacity. Alternatively, the BPR-type functions were often employed [21, 23] to avoid the discontinuous phenomenon when the parking demand is approaching the capacity. We recommend the following formulation in practice:(4)Sjqj=sj1+φqjkjω,∀j∈J,where φ and ω are calibration parameters. When qj⟶kj, the parking search time increases to the 1+φ times of the low-occupancy searching time sj.The hourly parking price at areaj is denoted by πj. Thus, the drivers who choose area j as a travel destination will pay πj dollars per hour. Therefore, the generalized destination cost, Mj, for travelers who choose area j as their destination, is given by(5)Mj=πj+η⋅Sjqj,where η is the value of time for travelers. Generally, the values of πj are various for different destination areas, which depends on the industrial structure, land use, and locations. To reflect the differences among the destination areas, a more detailed traffic zone division will be implemented in practice.From the aspect of parking supply constraint, the parking occupancy should not exceed the parking capacity in areai, that is,(6)qj≤kj,∀j∈J.


## 2.2.2. Combined Trip Distribution and Traffic Assignment Model

In this section, the lower-level model of the network capacity problem will be formulated by considering the parking cost at destinations. Following the assumptions in Section2.1, we consider the travelers can choose the destinations and paths to minimize the travel cost accordingly. The combined trip distribution and traffic assignment (CTDTA) model [25] will be employed to capture travelers’ behavior. Specifically, both the fixed demand and variable demand are considered in the road network. The travelers with fixed demand will be free to choose their travel paths, while the travelers with variable demand will be free to choose either the paths or the destinations. Both types of travelers aim to minimize their own travel cost for the whole trip. Furthermore, the CTDTA model will be extended to involve the parking supply and parking pricing at destinations, which will impact the destination choice of the variable travel demand. Thus, the extended CTDTA model is given as follows:(7)minZLq,f,h=∑a∈A∫0vataxdx+1θ∑i∈I∑j∈Jqijlnqij−1+∑j∈Jqjπj+η∑j∈J∫0qjSjydy,(8)s.t.∑j∈Jqij=Oi,∀i∈I,(9)∑r∈Rijhrij=eij,∀i∈I,j∈J,(10)∑r∈Rijfrij=qij,∀i∈I,j∈J,(11)va=∑i∈I∑j∈J∑r∈Rijfrij+hrijδa,rij,∀a∈A,(12)frij≥0,∀r∈Rij,i∈I,j∈J,(13)hrij≥0,∀r∈Rij,i∈I,j∈J,(14)qij≥0,∀i∈I,j∈J,where δa,rij is the link/path incidence indicator, which equals to 1 if link a is on path r between the O-D pair i,j and 0 otherwise. In the objective function, the first term indicates the user equilibrium of all travelers. The second term indicates the destination choice behavior of the variable demand only. The third and the fourth terms indicate the parking charging and the parking searching time at the destination area, respectively. Equations (8)–(10) define the flow conservation of the variable and fixed demand. Equation (11) is the relationship between link flows and path flows. Equations (12)–(14) are nonnegative constraints. Besides, according to the first-order necessary condition, the O-D flows of the variable demand is produced by the following logit share model:(15)qij=Oi⋅exp−θτij+πj+SjDj∑n∈Jexp−θτin+πn+SnDn,∀i∈I,j∈J,where the parking cost function, SjDj, is defined in equation (4).


## 2.2.3. Total Trip Maximization Model

The upper-level problem defines a maximum trip production model, where the limits of the individual link capacity and zonal parking supply are considered. Thus, the upper-level problem is given by(16)maxZUO˜=∑i∈IO˜i,(17)s.t.vaO˜≤Ca,∀a∈A,(18)ρj⋅∑i∈IqijO˜+eij≤kj,∀j∈J,(19)O˜i≥0,∀i∈I.where vaO˜ and qijO˜ are obtained by solving the lower-level model. The objective is to maximize the summation of the trip production of the variable demand, O˜i, from each origin. Equation (17) represents that the traffic flow on each link should not exceed its capacity. Equation (18) represents that the parking demand at each traffic zone should not be over its parking space.


## 3. Solution Algorithm

In the previous section, the network capacity model considering parking pricing and supply was formulated as a bilevel model. Moreover, the lower-level model integrates two classes of travel demand associated with different travel choice behaviors. The solution of the proposed network capacity model is not trivial. Therefore, in order to apply the proposed network capacity model in practical applications, we design an improved sensitivity analysis-based (SAB) algorithm that enables to solve the bilevel problem efficiently. The SAB algorithm was widely used for solving the bilevel programming model [27]. The sensitivity analysis is specific to the anlaytical senstivity analysis of the lower-level model, which is used to produce the derivatives of the upper-level decision variables with respect to the lower-level one. The derivatives will be used to explicitly reflect the relationship between the upper level and lower level and help to solve the bilevel model iteratively. In practice, the SAB algorithm usually performs a fast convergence which makes the algorithm terminate within a considerable time. Given the nonconvexity of the bilevel problem, the SAB algorithm will converge to a local optimal point. However, as shown by Yang et al. [2], for the bilevel model, if the upper-level objective function is a linear function of its decision variables, the SAB algorithm can, at least, find a noninferior optimal solution. Therefore, the SAB approach is capable to find a satisfying solution for the proposed network capacity problem in this study. The accuracy of the solution is sufficient to be used for transportation project forecasting or evaluation.


### 3.1. Path-Based Algorithm for Solving the Lower-Level Model

According to the typical process of the SAB algorithm [27], the lower-level model should be resolved in every iteration to obtain the equilibrium traffic flow pattern with respect to the current upper-level solution. Note that there are two classes of travel demand with different O-D distributions involved in the extended CTDTA model, while their path choice principles are the same. It is general to suppose that the path flows of both the fixed and the variable demand have the same proportion on each equilibrated path. Thus, we used the total path flow, Frij, as the main variable in the traffic assignment stage. The ratio of the fixed demand to the variable demand on each path is obtained by eij/qij. Moreover, in this section, we embed the gradient projection (GP) method [28] in Evans’ algorithm [29] for solving the extended CTDTA model, in which the O-D flow is updated in an additional stage by dealing with a one-dimension search problem. Hence, we define the path flow proportion, γijr, to denote the portion of the total demand between O-D i,j that is assigned to path r. This definition has the merit that the value of γijr does not need to be rescaled when the O-D demand is updated. In addition, the GP method is capable to quickly converge to sufficiently high accuracy. The GP method is classified as the path-based algorithm, which enables to quickly extract the set of all equilibrated paths from the path-based optimal solution. The path set will be used as a precondition to in the next stage for the analytical sensitivity analysis approach of the lower-level model.The implementation of modified Evans’ algorithm consists of two stages: the traffic assignment stage and the trip distribution stage. The former is implemented to equilibrate path flows while fixing the current O-D demand; the latter performed to update variable O-D demand while restraining the current path flow proportion. We carry out the traffic assignment stage as an inner loop with certain times, so as to accelerate the convergence of the whole algorithm. Besides, when producing a new (auxiliary) O-D flow, the parking search time is derived in advance based on the O-D flow pattern in the previous iteration, i.e.,Sjn:=Sjqjn−1.The solution procedure for the extended CTDTA model is presented as follows:Initialization: we setn:  = 0 and determine the initial link cost ta0 and parking time Sj0 by setting link flows va=0,∀a∈A and variable O-D demand qij=0,∀i∈I,j∈J, respectively. For each origin i∈I, (1)
find the minimum-cost paths starting from origini. For each minimum cost path r¯ to destination j∈J, we denote the minimum cost by τij0, and let Rij0:=Rij0∪r¯.(2)
compute the initial variable OD demands by(20)qij0=Oi⋅exp−θτij0+πj+Sj0∑n∈Jexp−θτin0+πn+Sn0,∀i∈I,j∈J.(21)ΔFr=cijr−τij∑a∈Ar,r¯∂ta/∂va,∀r∈Rij,r≠r¯,(22)γijrn=Frijeij+qijn,∀r∈Rij,i∈I,j∈J.Step 2: we update variable O-D flows, retaining the path flow proportions, given the path flow proportionsγijrn, link flows van, and path costs cijrn obtained in Step 1.Step 2.1: for each destinationj, we compute the parking search time Sjn⋅ based on the O-D demand eij and qijn−1.Step 2.2: for each O-D pair, we optimize the variable O-D demand:(1)
The set of auxiliary trip demandsq^ijn is found by the following logit share model:(23)q^ijn=Oi⋅exp−θτijn+πj+Sjn∑k∈Jexp−θτikn+πk+Skn,∀i∈I,j∈J.(24)max0≤λ≤1ZLλ=∑λ∫0vλ/ataxdx+1θ∑i∈I∑j∈Jqijλlnqijλ−1+∑j∈Jqjλ⋅πj+∑j∈J∫0qλ/jSjydy,(25)van+1≔vaλ∗,∀a∈A,qijn+1≔qijλ∗,∀i∈I,j∈J.(26)Frij=γijreij+qijn+1,∀r∈Rij,i∈I,j∈J.(3)
For each destinationj∈J associated with origin i, we assign both the fixed demand eij and the variable demand qij0 to the minimum cost path r¯ from i to j and, thereby, initialize the path flow Frij and path flow proportions γijr0=1, as well as the link flows va0.(4)
update the link costs.Main Loop. For n = 1 to number of main iterations (LMain):Step 1: we equilibrate path flows, retaining the variable demands, given the current variable O-D demandqijn and path flows Frij, obtained from the (n-1)th-iteration. For m = 1 to number of inner iterations (LInner):For each origini∈I, we generate the minimum path tree rooted from i. For each destination j∈J associated with origin i, we retrieve the minimum path r¯ with the minimum cost τij and equilibrate the path set Rij between the O-D pair i,j as follows:Step 1.1: column generation: updating the costs of paths,cijr,∀r∈Rij.Ifr¯∉Rij, let Rij:=Rij∪r¯; otherwise, label the minimum path in Rij as r¯.Step 1.2: shift flow from nonminimum paths to the minimum path:(1)
The path flow shift is computed as follows:whereAr,r¯ is the set of links that belong either to nonminimum path r or to minimum path r¯ but not to both of them.(2)
The path flows are updated and projected onto the feasible set:Nonminimum paths:Frij:=Frij−minΔFr,Frij,∀r∈Rij,r≠r¯Minimum path:Fr¯ij:=qij+eij−∑r∈Rij,r≠r¯FrijIfFrij=0, then eliminate this path r from the path set, that is, Rij:=Rij/r.(3)
The link flows {va}, the link costs {ta}, and the derivative costs {∂ta/∂va} are updated.Step 1.3: updating the path flow proportions:(2)
The auxiliary link flowsv^an are obtained with the given path flow proportions γijrn.(3)
Letvaλ=1−λvan+λv^an,∀a∈A; qijλ=1−λqijn+λq^ijn,∀i∈I,j∈J, and we solve the one-dimensional search problem defined as follows to obtain the optimal step size λ∗∈0,1:whereqjλ=ρjDjλ=∑j∈Jeij+qijλ.(4)
The link flows and the variable O-D demands are updated as follows:Step 2.3: updating the path flows:Step 2.4: the link costs {ta} and the derivative costs ∂ta/∂va are updated.Step 3: checking convergence: it is terminated if the convergence criterion is satisfied; otherwise, a new iteration of the main loop is started, and setn: = n + 1.


### 3.2. Sensitivity Analysis of the CTDTA Model

In every iteration, the SAB algorithm evaluates the derivatives of the lower-level decision variables with respect to the upper-level ones (i.e.,∇O˜v and ∇O˜q) based on the current solution to the lower-level model. The derivatives will be used to approximate the bilevel model as a linear programming problem which is easier to tackle. For the original CTDTA model, the approach for deriving derivatives can follow the restriction sensitivity analysis approach for the combined model in Du et al. [30]. The restriction approach reduces the original problem involving all path variables into a restricted one that only consists of those independent equilibrated paths, so the problem of nonuniqueness of the path flows can be handled. Also, using the sensitivity results of the independent paths in the restricted problem, the derivatives of the link flow in the original one will be restored. The necessary results of the analytical sensitivity analysis of the extended CTDTA model are presented in the following.To simplify the calculation of the sensitivity analysis approach, the extended CTDTA model in equations (7)–(14) will be reformulated as follows (by including the perturbation ε):(27)minZL′f,h,ε=∑a∈A∫0vatax,εdx+1θ∑i∈I∑j∈J∑r∈Rijfrijln∑r∈Rijfrij−1+∑j∈Jqjπj+η∑j∈J∫0qjSjy,εdy,(28)s.t.∑j∈J∑r∈Rijfrij=Oiε,∀i∈I,(29)∑r∈Rijhrij=eijε,∀i∈I,j∈J,(30)va=∑i∈I∑j∈J∑r∈Rijfrij+hrijδa,rij,∀a∈A,(31)frij≥0,∀r∈Rij,i∈I,j∈J,(32)hrij≥0,∀r∈Rij,i∈I,j∈J.In the equations given above, the decision variables are reduced to the path flowsf and h only. After that, by substituting equation (30) into the upper limit of the integral in the first term of the objective function, we can obtain the following Lagrange function of the abovementioned problem.(33)Lf,h,λ,μ,ε=∑a∈A∫0∑i∈I∑j∈J∑r∈Rijfrij+hrijδa,rijtax,εdx+1θ∑i∈I∑j∈J∑r∈Rijfrijln∑r∈Rijfrij−1+∑j∈Jqjπj+η∑j∈J∫0qjSjy,εdy+λiOiε−∑j∈J∑r∈Rijfrij+μijeijε−∑r∈Rijhrij,where λ=λi and μ=μij are the Lagrange multipliers associated with the conservation constraints (28) and (29). Then, the Kuhn–Tucker condition can be conducted as follows (set ε=0):(34)cf∗,h∗,0+1θΛfTlnΛff∗+ΛfTΨTρ+ηS⋅,0−ΛfTΦTλ=0,cf∗,h∗,0+ΛhTΨTρ+ηS⋅,0−ΛhTμ=0,ΦΛff∗−O0=0,Λhh∗−e0=0,ufTf∗=0,uhTh∗=0,uf≥0,uh≥0,f∗≥0,h∗≥0.By only retaining the used paths whose flows are positive, the abovementioned equation system will be reduced to(35)cf∗,h∗,0+1θΛfTlnΛff0∗+ΛfTΨTρ+ηS⋅,0−ΛfTΦTλ=0,cf∗,h∗,0+ΛhTΨTρ+ηS⋅,0−ΛhTμ=0,ΦΛff0∗−O0=0,Λhh0∗−e0=0.Furthermore, letf0∗,h0∗ be partitioned as fB,fNBT,hB,hNBT. fB and hB are the basic variables of path flows associated with the variable and fixed demand, respectively; fNB and hNB are the corresponding nonbasic variables. Note that fB and hB are the flows on the independent equilibrated paths according to the restriction sensitivity analysis approach. Then, we can restrict the equation system by holding the nonbasic variable to be fNB,hNB=0. Thereby, the Jacobian matrix Jxwith respect to the solution variables x=fB,hB,λ,μ, and the Jacobian matrix JO˜ with respect to the production of the variable demand from origins can be derived as(36)Jx=∇f2L∇f,hL−ΛfTΦTλ0∇h,fL∇h2L0−ΛhTΦΛf0000Λh00,JO˜=00−I0T,where(37)∇f2L=ΔfT∇vtv,0Δf+10ΛfTdiag1frijΛf+ΛfTΨTη∇qS⋅ΨΛf,∇h,fL=ΔhT∇vtv,εΔf+ΛhTΨTη∇qS⋅ΨΛf,∇h2L=ΔhT∇vtv,εΔh+ΛhTΨTη∇qS⋅ΨΛh,∇f,hL=ΔfT∇vtv,εΔh+ΛfTΨTη∇qS⋅ΨΛh.Note thatdiag1/frij is a diagonal matrix with 1/frij as the diagonal element. Here, the perturbation ε corresponds to the original production O˜ in this problem. Δfand Δh are the link/path incidence matrix corresponding to independent equilibrated path flow fB and hB, respectively. Λfand Λh are the O-D/path incidence matrix corresponding to fB and hB, separately. Φ is the origin/O-D incidence matrix. Ψ is the destination/O-D incidence matrix. The superscript ‘T’ represents the transposed matrix. ‘I’ denotes the identity matrix. The link cost function, t⋅, is strongly monotonically defined in v, which guarantees the uniqueness of the equilibrium solution.Therefore, in the restricted problem, the derivatives of the model solutions with respect to the input parameters are produced by the following equation:(38)∇O˜x=Jx−1−JO˜,where Jx is an invertible Jacobian matrix. According to the restriction approach, the derivative, ∇O˜xε, is first conducted in the restricted problem, and then, ∇O˜v, which is defined in the original problem, will be obtained by(39)∇O˜v=Δf∇O˜fB+Δf∇O˜hB.Equation (39) indicates that the variations on the link flows can be just represented by the changes in the basic path flows, which is the rationale of the restriction sensitivity analysis approach. In addition, ∇O˜q is also obtained by(40)∇O˜q=Λf∇O˜fB+Λf∇O˜hB.In addition, the inverse of matrixJx in equation (38) is required to be worked out. To avoid the disadvantages of deriving the whole inverse matrix directly, it is usually to solve the corresponding linear equations as an alternative. Hence, equation (38) is rewritten as(41)Jx⋅∇O˜x=−JO˜.The abovementioned system of linear equations can be solved efficiently by using the exiting solvers, such as the Cplex or Matlab built-in functions. Besides, the well-known block inversion formula can be used to incorporate with iterative solution techniques for the system of linear equations [31], ensuring that no matrix needs to be inverted with large dimension.


### 3.3. An Adaptive Step-Size Method for SAB Algorithm

The analytical sensitivity expressions derived in the previous section are essential to uncover the implicit relationships between lower-level decision variables, (v, q), and upper-level variables, O˜. With the derivatives, the bilevel model is approximated as a single-level model using first-order Taylor’s expansion at a solution point, i.e., O˜∗=f−1v∗,q∗. Let vO˜∗ and qO˜∗ denote the solutions to the lower-level model at O˜∗,respectively. The implicit relationships can be represented by using the Taylor expansion:(42)vO˜≈vO˜∗+∇O˜v⋅O˜−O˜∗,qO˜≈qO˜∗+∇O˜q⋅O˜−O˜∗,where the derivatives ∇O˜v and ∇O˜q are obtained from the sensitivity analysis of the CTDTA model. Therefore, the original bilevel problem will be approximated as(43)Max∑j∈JO˜js.t.∇O˜vρΨ⋅∇O˜q⋅O˜≤Ck−ρΨ⋅e−v∗ρΨ⋅q∗+∇O˜vρΨ⋅∇O˜q⋅O˜∗O˜≥0.LetO^n denote the solution of the abovementioned linear programming problem. Since the auxiliary solution O^n does not always satisfy the feasibility of the original problem, so the solution is updated using the convex combination of the solution in the last iteration, O˜n (i.e., the start point in this iteration), and the auxiliary solution, O^n, which is given by(44)O˜n+1≔O˜n+minζmaxO^n−O˜n,1⋅O^n−O˜n,where ζmax∈0,1 is a predetermined maximum step size that prevents the updated solution from moving too long. O^n−O˜n is the descent direction. The value of ζmax could be flexible. An adaptive scheme for ζmax will be suggested in the large-scale problem for providing a step size sequence that ensures the convergence.


## 3.1. Path-Based Algorithm for Solving the Lower-Level Model

According to the typical process of the SAB algorithm [27], the lower-level model should be resolved in every iteration to obtain the equilibrium traffic flow pattern with respect to the current upper-level solution. Note that there are two classes of travel demand with different O-D distributions involved in the extended CTDTA model, while their path choice principles are the same. It is general to suppose that the path flows of both the fixed and the variable demand have the same proportion on each equilibrated path. Thus, we used the total path flow, Frij, as the main variable in the traffic assignment stage. The ratio of the fixed demand to the variable demand on each path is obtained by eij/qij. Moreover, in this section, we embed the gradient projection (GP) method [28] in Evans’ algorithm [29] for solving the extended CTDTA model, in which the O-D flow is updated in an additional stage by dealing with a one-dimension search problem. Hence, we define the path flow proportion, γijr, to denote the portion of the total demand between O-D i,j that is assigned to path r. This definition has the merit that the value of γijr does not need to be rescaled when the O-D demand is updated. In addition, the GP method is capable to quickly converge to sufficiently high accuracy. The GP method is classified as the path-based algorithm, which enables to quickly extract the set of all equilibrated paths from the path-based optimal solution. The path set will be used as a precondition to in the next stage for the analytical sensitivity analysis approach of the lower-level model.The implementation of modified Evans’ algorithm consists of two stages: the traffic assignment stage and the trip distribution stage. The former is implemented to equilibrate path flows while fixing the current O-D demand; the latter performed to update variable O-D demand while restraining the current path flow proportion. We carry out the traffic assignment stage as an inner loop with certain times, so as to accelerate the convergence of the whole algorithm. Besides, when producing a new (auxiliary) O-D flow, the parking search time is derived in advance based on the O-D flow pattern in the previous iteration, i.e.,Sjn:=Sjqjn−1.The solution procedure for the extended CTDTA model is presented as follows:Initialization: we setn:  = 0 and determine the initial link cost ta0 and parking time Sj0 by setting link flows va=0,∀a∈A and variable O-D demand qij=0,∀i∈I,j∈J, respectively. For each origin i∈I, (1)
find the minimum-cost paths starting from origini. For each minimum cost path r¯ to destination j∈J, we denote the minimum cost by τij0, and let Rij0:=Rij0∪r¯.(2)
compute the initial variable OD demands by(20)qij0=Oi⋅exp−θτij0+πj+Sj0∑n∈Jexp−θτin0+πn+Sn0,∀i∈I,j∈J.(21)ΔFr=cijr−τij∑a∈Ar,r¯∂ta/∂va,∀r∈Rij,r≠r¯,(22)γijrn=Frijeij+qijn,∀r∈Rij,i∈I,j∈J.Step 2: we update variable O-D flows, retaining the path flow proportions, given the path flow proportionsγijrn, link flows van, and path costs cijrn obtained in Step 1.Step 2.1: for each destinationj, we compute the parking search time Sjn⋅ based on the O-D demand eij and qijn−1.Step 2.2: for each O-D pair, we optimize the variable O-D demand:(1)
The set of auxiliary trip demandsq^ijn is found by the following logit share model:(23)q^ijn=Oi⋅exp−θτijn+πj+Sjn∑k∈Jexp−θτikn+πk+Skn,∀i∈I,j∈J.(24)max0≤λ≤1ZLλ=∑λ∫0vλ/ataxdx+1θ∑i∈I∑j∈Jqijλlnqijλ−1+∑j∈Jqjλ⋅πj+∑j∈J∫0qλ/jSjydy,(25)van+1≔vaλ∗,∀a∈A,qijn+1≔qijλ∗,∀i∈I,j∈J.(26)Frij=γijreij+qijn+1,∀r∈Rij,i∈I,j∈J.(3)
For each destinationj∈J associated with origin i, we assign both the fixed demand eij and the variable demand qij0 to the minimum cost path r¯ from i to j and, thereby, initialize the path flow Frij and path flow proportions γijr0=1, as well as the link flows va0.(4)
update the link costs.Main Loop. For n = 1 to number of main iterations (LMain):Step 1: we equilibrate path flows, retaining the variable demands, given the current variable O-D demandqijn and path flows Frij, obtained from the (n-1)th-iteration. For m = 1 to number of inner iterations (LInner):For each origini∈I, we generate the minimum path tree rooted from i. For each destination j∈J associated with origin i, we retrieve the minimum path r¯ with the minimum cost τij and equilibrate the path set Rij between the O-D pair i,j as follows:Step 1.1: column generation: updating the costs of paths,cijr,∀r∈Rij.Ifr¯∉Rij, let Rij:=Rij∪r¯; otherwise, label the minimum path in Rij as r¯.Step 1.2: shift flow from nonminimum paths to the minimum path:(1)
The path flow shift is computed as follows:whereAr,r¯ is the set of links that belong either to nonminimum path r or to minimum path r¯ but not to both of them.(2)
The path flows are updated and projected onto the feasible set:Nonminimum paths:Frij:=Frij−minΔFr,Frij,∀r∈Rij,r≠r¯Minimum path:Fr¯ij:=qij+eij−∑r∈Rij,r≠r¯FrijIfFrij=0, then eliminate this path r from the path set, that is, Rij:=Rij/r.(3)
The link flows {va}, the link costs {ta}, and the derivative costs {∂ta/∂va} are updated.Step 1.3: updating the path flow proportions:(2)
The auxiliary link flowsv^an are obtained with the given path flow proportions γijrn.(3)
Letvaλ=1−λvan+λv^an,∀a∈A; qijλ=1−λqijn+λq^ijn,∀i∈I,j∈J, and we solve the one-dimensional search problem defined as follows to obtain the optimal step size λ∗∈0,1:whereqjλ=ρjDjλ=∑j∈Jeij+qijλ.(4)
The link flows and the variable O-D demands are updated as follows:Step 2.3: updating the path flows:Step 2.4: the link costs {ta} and the derivative costs ∂ta/∂va are updated.Step 3: checking convergence: it is terminated if the convergence criterion is satisfied; otherwise, a new iteration of the main loop is started, and setn: = n + 1.


## 3.2. Sensitivity Analysis of the CTDTA Model

In every iteration, the SAB algorithm evaluates the derivatives of the lower-level decision variables with respect to the upper-level ones (i.e.,∇O˜v and ∇O˜q) based on the current solution to the lower-level model. The derivatives will be used to approximate the bilevel model as a linear programming problem which is easier to tackle. For the original CTDTA model, the approach for deriving derivatives can follow the restriction sensitivity analysis approach for the combined model in Du et al. [30]. The restriction approach reduces the original problem involving all path variables into a restricted one that only consists of those independent equilibrated paths, so the problem of nonuniqueness of the path flows can be handled. Also, using the sensitivity results of the independent paths in the restricted problem, the derivatives of the link flow in the original one will be restored. The necessary results of the analytical sensitivity analysis of the extended CTDTA model are presented in the following.To simplify the calculation of the sensitivity analysis approach, the extended CTDTA model in equations (7)–(14) will be reformulated as follows (by including the perturbation ε):(27)minZL′f,h,ε=∑a∈A∫0vatax,εdx+1θ∑i∈I∑j∈J∑r∈Rijfrijln∑r∈Rijfrij−1+∑j∈Jqjπj+η∑j∈J∫0qjSjy,εdy,(28)s.t.∑j∈J∑r∈Rijfrij=Oiε,∀i∈I,(29)∑r∈Rijhrij=eijε,∀i∈I,j∈J,(30)va=∑i∈I∑j∈J∑r∈Rijfrij+hrijδa,rij,∀a∈A,(31)frij≥0,∀r∈Rij,i∈I,j∈J,(32)hrij≥0,∀r∈Rij,i∈I,j∈J.In the equations given above, the decision variables are reduced to the path flowsf and h only. After that, by substituting equation (30) into the upper limit of the integral in the first term of the objective function, we can obtain the following Lagrange function of the abovementioned problem.(33)Lf,h,λ,μ,ε=∑a∈A∫0∑i∈I∑j∈J∑r∈Rijfrij+hrijδa,rijtax,εdx+1θ∑i∈I∑j∈J∑r∈Rijfrijln∑r∈Rijfrij−1+∑j∈Jqjπj+η∑j∈J∫0qjSjy,εdy+λiOiε−∑j∈J∑r∈Rijfrij+μijeijε−∑r∈Rijhrij,where λ=λi and μ=μij are the Lagrange multipliers associated with the conservation constraints (28) and (29). Then, the Kuhn–Tucker condition can be conducted as follows (set ε=0):(34)cf∗,h∗,0+1θΛfTlnΛff∗+ΛfTΨTρ+ηS⋅,0−ΛfTΦTλ=0,cf∗,h∗,0+ΛhTΨTρ+ηS⋅,0−ΛhTμ=0,ΦΛff∗−O0=0,Λhh∗−e0=0,ufTf∗=0,uhTh∗=0,uf≥0,uh≥0,f∗≥0,h∗≥0.By only retaining the used paths whose flows are positive, the abovementioned equation system will be reduced to(35)cf∗,h∗,0+1θΛfTlnΛff0∗+ΛfTΨTρ+ηS⋅,0−ΛfTΦTλ=0,cf∗,h∗,0+ΛhTΨTρ+ηS⋅,0−ΛhTμ=0,ΦΛff0∗−O0=0,Λhh0∗−e0=0.Furthermore, letf0∗,h0∗ be partitioned as fB,fNBT,hB,hNBT. fB and hB are the basic variables of path flows associated with the variable and fixed demand, respectively; fNB and hNB are the corresponding nonbasic variables. Note that fB and hB are the flows on the independent equilibrated paths according to the restriction sensitivity analysis approach. Then, we can restrict the equation system by holding the nonbasic variable to be fNB,hNB=0. Thereby, the Jacobian matrix Jxwith respect to the solution variables x=fB,hB,λ,μ, and the Jacobian matrix JO˜ with respect to the production of the variable demand from origins can be derived as(36)Jx=∇f2L∇f,hL−ΛfTΦTλ0∇h,fL∇h2L0−ΛhTΦΛf0000Λh00,JO˜=00−I0T,where(37)∇f2L=ΔfT∇vtv,0Δf+10ΛfTdiag1frijΛf+ΛfTΨTη∇qS⋅ΨΛf,∇h,fL=ΔhT∇vtv,εΔf+ΛhTΨTη∇qS⋅ΨΛf,∇h2L=ΔhT∇vtv,εΔh+ΛhTΨTη∇qS⋅ΨΛh,∇f,hL=ΔfT∇vtv,εΔh+ΛfTΨTη∇qS⋅ΨΛh.Note thatdiag1/frij is a diagonal matrix with 1/frij as the diagonal element. Here, the perturbation ε corresponds to the original production O˜ in this problem. Δfand Δh are the link/path incidence matrix corresponding to independent equilibrated path flow fB and hB, respectively. Λfand Λh are the O-D/path incidence matrix corresponding to fB and hB, separately. Φ is the origin/O-D incidence matrix. Ψ is the destination/O-D incidence matrix. The superscript ‘T’ represents the transposed matrix. ‘I’ denotes the identity matrix. The link cost function, t⋅, is strongly monotonically defined in v, which guarantees the uniqueness of the equilibrium solution.Therefore, in the restricted problem, the derivatives of the model solutions with respect to the input parameters are produced by the following equation:(38)∇O˜x=Jx−1−JO˜,where Jx is an invertible Jacobian matrix. According to the restriction approach, the derivative, ∇O˜xε, is first conducted in the restricted problem, and then, ∇O˜v, which is defined in the original problem, will be obtained by(39)∇O˜v=Δf∇O˜fB+Δf∇O˜hB.Equation (39) indicates that the variations on the link flows can be just represented by the changes in the basic path flows, which is the rationale of the restriction sensitivity analysis approach. In addition, ∇O˜q is also obtained by(40)∇O˜q=Λf∇O˜fB+Λf∇O˜hB.In addition, the inverse of matrixJx in equation (38) is required to be worked out. To avoid the disadvantages of deriving the whole inverse matrix directly, it is usually to solve the corresponding linear equations as an alternative. Hence, equation (38) is rewritten as(41)Jx⋅∇O˜x=−JO˜.The abovementioned system of linear equations can be solved efficiently by using the exiting solvers, such as the Cplex or Matlab built-in functions. Besides, the well-known block inversion formula can be used to incorporate with iterative solution techniques for the system of linear equations [31], ensuring that no matrix needs to be inverted with large dimension.


## 3.3. An Adaptive Step-Size Method for SAB Algorithm

The analytical sensitivity expressions derived in the previous section are essential to uncover the implicit relationships between lower-level decision variables, (v, q), and upper-level variables, O˜. With the derivatives, the bilevel model is approximated as a single-level model using first-order Taylor’s expansion at a solution point, i.e., O˜∗=f−1v∗,q∗. Let vO˜∗ and qO˜∗ denote the solutions to the lower-level model at O˜∗,respectively. The implicit relationships can be represented by using the Taylor expansion:(42)vO˜≈vO˜∗+∇O˜v⋅O˜−O˜∗,qO˜≈qO˜∗+∇O˜q⋅O˜−O˜∗,where the derivatives ∇O˜v and ∇O˜q are obtained from the sensitivity analysis of the CTDTA model. Therefore, the original bilevel problem will be approximated as(43)Max∑j∈JO˜js.t.∇O˜vρΨ⋅∇O˜q⋅O˜≤Ck−ρΨ⋅e−v∗ρΨ⋅q∗+∇O˜vρΨ⋅∇O˜q⋅O˜∗O˜≥0.LetO^n denote the solution of the abovementioned linear programming problem. Since the auxiliary solution O^n does not always satisfy the feasibility of the original problem, so the solution is updated using the convex combination of the solution in the last iteration, O˜n (i.e., the start point in this iteration), and the auxiliary solution, O^n, which is given by(44)O˜n+1≔O˜n+minζmaxO^n−O˜n,1⋅O^n−O˜n,where ζmax∈0,1 is a predetermined maximum step size that prevents the updated solution from moving too long. O^n−O˜n is the descent direction. The value of ζmax could be flexible. An adaptive scheme for ζmax will be suggested in the large-scale problem for providing a step size sequence that ensures the convergence.


## 4. Numerical Experiments

Numerical experiments are conducted in this section. In the first example, we employ a small network, composed of 7 links and 6 nodes to demonstrate the proposed network capacity model and, then, analyze the effect of parking pricing and parking supply on the network capacity of the road system. The example network is shown in Figure1. There are 4 O-D pairs from the origin nodes 1 and 2 to the destination nodes 3 and 4. The BPR function is used as the link performance function, given by tava=ta01+0.15va/Ca4. The characteristics of all links in the network are listed in Table 1. Table 2 gives the fixed demand in the network. The parameters related parking strategies at destinations are listed in Table 3. Besides, the value of time η is set to 1.0, and the dispersion parameter θ for destination choice is set to 0.5.Figure 1
An example network.Table 1
Link characteristics of the example network in Figure1.
Links1234567ta0105124454Ca1001208080505050Table 2
Fixed travel demand in the network.
34O¯i13020502402060D¯j7040Total demand = 110Table 3
The parameters of parking strategy at destinations.
DestinationsLow-occupancy searching timesjγωParking pricingπjParking capacitykjParking rateρj32.01.02.04.01000.7543.01.02.05.0800.75


### 4.1. Results of the New Model

To show the advantages of the proposed model, the result of the proposed model is compared with the other network capacity models in the literature [3, 4, 19, 24]. The experiments are carried out on the example in Figure 1. As the models in the literature on this topic were conducted for different problems under various backgrounds, it is inappropriate to compare the results of these models directly. Therefore, we conclude three situations from the literature: (1) without variable O-D demand (i.e., the reserve capacity model in this paper); (2) without variable destination cost; (3) without fixed O-D demand.For the situation without the variable O-D demand, the reserve network capacity model [1] is modified by adding the parking supply constraint. The O-D flows are assumed to grow following a fixed O-D distribution, and the effect of traffic congestion and parking pricing at destination areas is not involved. The reserve capacity is the most classical concept that has been widely applied for the assessment of transportation network capacity. Such concept was used in Asakura and Kashiwadani [19] and Leng and Yan [4]. The results of the reserve capacity model and the proposed model are reported in Tables 4 and 5, respectively.Table 4
Results of the reserve network capacity model.
O-DDemand typesDestination demandLinksLink flowV/C ratioFixed demandAdditional demandDestinationTotal trip attractionParking demand1–3307.50387.5065.6137.500.3751–4205.00450.0037.5275.000.6252–34010.00325.000.3122–4205.00425.000.312Total11027.50550.001.000650.001.000725.000.500Network capacity137.50 (demand multiplier = 1.25)Table 5
Results of the proposed road network capacity model.
O-DDemand typesDestination demandLinksLink flowV/C ratioFixed demandAdditional demandDestinationTotal trip attractionParking demand1–33053.333133.33100.0183.330.8331–4206.91465.1348.85226.910.3362–34010.00338.210.4782–42018.21450.001.000Total11088.46576.910.641650.001.000726.910.538Network capacity198.46From the results in Tables4 and 5, the network capacity is to be 137.5 by the reserve capacity model, while it is evaluated to be 222.35 by the proposed model. In both models, flows on link 5 and link 6 reach the capacity, and the links are the bottlenecks limiting the growth of the total travel demand in the network. Besides, in the results of the reserve capacity model, no parking facility is saturated; however, in the results of the proposed model, the parking capacity at destination 3 is fully used. The network capacity from the reserve capacity model is evidently lower than that from the proposed model. It means the reserve capacity tends to produce too conservative results [8], since it assumes an unchangeable travel demand pattern. The network-wide travel demand will be restricted to continue to grow if the flow on any individual link meets its capacity. By contrast, the proposed model with the CTDTA model as the lower level produces a changeable O-D demand pattern, which is more practical. Thus, a portion of travel demand can adjust their travel destination according to the parking cost and available space at the destination area. In this example, the limits to the total demand come from the capacities on link 5 and link 6, the parking capacity at destination 3, and the restraint from the O-D travel cost (soft constraint). Note that the variable travel demand does not change the O-D distribution in a completely free manner. The O-D travel distribution should follow the logit share model in equation (15), by which the destinations with lower disutility will be assigned more travel demand for any origin area, and vice versa.For the situation without variable destination cost, the O-D flows are assumed to grow with a variable O-D distribution, while the effect of traffic congestion at destinations is not considered. Tam and Lam [3] employed this behavior pattern for the maximum car ownership problem. For the situation without the fixed O-D demand, all motorists are considered to change their trip destination under the influence of traffic congestion (both from O-D travel cost and destination cost) and parking management strategy. Tam and Lam [3] and Xie et al. [24] used this assumption.Figure2 further compares the maximum demand patterns of different network capacity models. The abovementioned three situations are labeled as “Reserve Capacity,” “Without Destination Cost,” and “Without Fixed Demand.” The O-D demand patterns of the models are significantly different. Specifically, the differences are mainly on the demands between O-D (1–3) and O-D (2–4). The maximum demand pattern from the “Reserve Capacity” model is rather conservative, as it clearly follows the fixed O-D demand (as a prescribed O-D demand) existed in the network. Although O-D (1–3) and O-D (2–4) can be allocated more travel demand, limited by the capacity on link 5 and link 6 (the vital links for O-D (2–3)), the total demand cannot increase further. On the other hand, without considering the effect of destination congestions (i.e., the parking search time increases as the destination demand), the network capacity is overestimated in the situation “Without Destination Cost”. Note that the travel demands between O-D (1–4) and O-D (2–4) are higher than those from the results of the proposed model. This reflects that, without variable destination cost, the congestion effect at destination 4 cannot be captured. Travelers will choose destination 4 even though the congestion in this area is at a high level (i.e., the parking search time could be very long), which is unrealistic in real-life. Moreover, the situation “Without Fixed Demand” assumes an extreme demand pattern of maximum flow, in which the travel demand between O-D (2–4) is much higher while the demand of O-D (1–4) is lower compared with the other models. Such a demand pattern means the commuters between O-D (1–4) should be asked to give up their trips to increase the demand between the other O-D pairs, which is also not realistic for the urban transportation system.Figure 2
O-D demand pattern of maximum flow from different network capacity models.In Figure2, the proposed model produces a moderate result for network capacity assessment. Compared to the “Reserve Capacity” model, the potential of the network capacity by our model will be further developed between O-D (1–3) and O-D (2–4) after link 5 and link 6 reach their capacities. The total demand will keep growing until the parking capacity at destination 3 is violated. Besides, note that the demand between O-D (1–4) does not increase much. Because the travel cost between O-D (1–4) is significantly larger than that between O-D (1–3), most variable travel demands from origin 1 would like to choose node 3 as the destination for noncommuting activities. As the demand between O-D (1–3) cannot increase (limited by parking capacity), the demand for O-D (1–4) will not grow either. We find such restraint is caused by the travel cost difference among O-D pairs, which is referred to be the soft constraint as mentioned before. In conclusion, the proposed model can capture a more comprehensive situation compared with the models in the literature and, thus, is capable to better assess the road network capacity problem.


### 4.2. The Effect of considering Parking Supply and Parking Pricing

Based on the proposed network capacity model incorporated with parking strategies, we analyze the effect of parking supply and parking pricing on the network-wide capacity in this section. For this purpose, we configure 6 scenarios listed in Table6. The base scenario is the same as the example in Section 4.1. Scenarios 1 to 3 are associated with the changes in parking supply strategies. Scenarios 4 to 6 are corresponding to the adjustment of the parking pricing strategies at the destination areas.Table 6
Descriptions of scenarios.
ScenariosDescription0Base scenario1Only expand parking capacity at destination 32Only expand parking capacity at destination 43Expand parking capacity at both destinations4Increase parking pricing at one destination only5Increase parking pricing at both destinations in the same proportion6Increase parking pricing at both destinations by the same amount


#### 4.2.1. Effect of Parking Supply

With the same parking pricing strategy, the effect of the parking supply on the network-wide capacity is analyzed. For Scenario 1 to 3, the settings of the parking capacities and the results of the network capacity model are reported in Table7.In Scenario 1, only the parking capacity at destination 3 is expanded (from 100 to 1000). Compared with the base scenario, the total network capacity is increased from 198.46 to 221.87. One of the binding (or active) constraints changes from the destination 3 to link 1. This indicates that the total capacity in the base scenario is limited by the parking capacity at destination 3. Expanding the parking supply at such destination areas can effectively enhance the network-wide capacity.In Scenario 2, only the parking capacity at destination 4 is expanded (from 80 to 1000). However, the total network capacity is not increased (it could appear as unobvious changes in practice). It is because that the parking supply at the destination constraint is still active. Expanding the capacities on the other destinations will have a small effect on the network-wide capacity.In Scenario 3, both the parking capacities at destination 4 and destination 5 are increased to 1000. It results in the same total network capacity as Scenario 1. This means if the network-wide capacity should be enhanced, it only needs to deal with the destinations whose capacity constraints are binding to the maximum total demand. The investment on the nonbinding parking supplies will have a marginal contribution to the total network capacity. Note that all of the binding constraints change to link capacities if the parking capacities are enlarged sufficiently. There is no need to expand parking capacities too much. On the other hand, ignoring the parking supply capacity might overestimate the capacity of the transportation network.Table 7
Results of network capacity under different parking capacities.
Parking capacityk3,k4Base scenario: (100, 80)Scenario 1: (1000, 80)Scenario 2: (100, 1000)Scenario 3: (1000, 1000)DestinationsParking demandTotal trip attractionParking demandTotal trip attractionParking demandTotal trip attractionParking demandTotal trip attraction3100.00133.33112.50150.00100.00133.33112.50150.00448.8565.1353.9071.8748.8565.1353.9071.87Network capacity198.46221.87198.46221.87Binding constraints∗Capacities on link 5 and link 6∗∗Parking capacity at destination 3Capacity on link 1Parking capacity at destination 3Capacity on link 1∗The capacity limits of the maximum network throughput. ∗∗The capacity constraints on link 5 and link 6 are active in all scenarios.


#### 4.2.2. Effect of Parking Pricing

By holding the parking supply the same as the base scenario, the effect of the parking supply on the network-wide capacity can be investigated. The settings of parking capacities, as well as the model results, through Scenario 4 to 6 are reported in Table8.In Scenario 4, we only raise the parking pricing at destination 3 (from 4.0 to 8.0). However, the total network capacity is enhanced significantly (increasing to 240.0). Both destinations are saturated so the total travel demand cannot increase anymore. Specifically, the parking costs (consists of parking pricing and parking search time) for destination 3 and destination 4 are changed from 8.00 to 9.12 to 12.00 and 11.00, respectively. This results in the growth in the proportion of the travelers who choose node 4 as their destination. Hence, the demand to destination 4 can further grow, until the parking demand reaches the capacity.In Scenario 4, we raise the parking pricing to 200% for both destinations. The total network capacity is decreased slightly. The change of the parking pricing leads to the redistribution of the O-D demand pattern. According to the parking cost, a large proportion of travelers (for variable demand only) tend to choose destination 3. Therefore, the demand for destination 4 will not reach that level as the base scenario due to the soft constraint on O-D (1–4) and O-D (2–4).In Scenario 6, we increase the parking pricing with the same amount (by 4.0). Based on our model, the network capacity is unchanged despite the parking costs change a lot. In practice, one may regard such adjustment of the parking pricing has little impact on the network-wide capacity.Table 8
Results of network capacity under different parking pricing strategies.
Parking pricingπ3,π4Base scenario: (4.0, 5.0)Scenario 4: <(8.0, 5.0)Scenario 5: (8.0, 10.0)Scenario 6: (8.0, 9.0)DestinationsParking demandParking costParking demandParking costParking demandParking costParking demandParking cost3100.008.00100.0012.00100.0012.00100.0012.00448.859.1280.0011.0042.9813.8748.8513.12Network capacity198.46240.00190.65198.46In summary, adjusting the parking pricing strategy for selected destination areas will have an obvious influence on the network capacity of the transportation system. However, increase the parking pricing at all destinations together may result in a small effect for enhancing network capacity. Note that the O-D pattern (or spatial distribution) is the key to obtain a high network capacity. Figure3 shows the maximal O-D demand pattern for Scenario 4 and Scenario 6. The travel demand increases significantly on O-D (1–4) and O-D (2–4). It indicates that Scenario 4 results in a more proper O-D pattern to match the given network with higher utilization, and thus, a better effect is obtained on the network capacity compared with Scenario 6 (as well as Scenario 5).Figure 3
O-D demand pattern of maximum flow for Scenario 4 and Scenario 6.


### 4.3. Case Study in the Sioux-Falls Network

In this section, we numerically test the network capacity model with parking management strategies using the Sioux-Falls network (https://github.com/bstabler/TransportationNetworks). The Sioux-Falls network is a highway network with 24 nodes, 76 links, and 528 O-D pairs. All 24 nodes are origin/destination nodes. In order to test the network capacity model, we assumed the fixed travel demand does not exceed the network capacity. Therefore, the demand of all O-D pairs is rescaled as 1/5 of the original data.We considered three different parking management strategies in the Sioux-Falls network: (1) unlimited parking space and unified parking pricing for all destinations; (2) limited parking space and unified parking pricing at the destinations; and (3) limited parking space and adjusted parking pricing at the destinations. For the unlimited parking space situation, all destination areas are assumed to have infinite parking capacity, so there is no parking capacity constraint. For the limited parking space situation, we considered each destination is assigned with limited parking capacity. The capacity constraints are chosen according to the fixed demand in the network. Specifically, destination 10 (with the most trip attraction of the fixed demand) is assigned with 20,000 unit parking capacity; destinations 11, 15, 16, 17, 20, and 22 are assigned with 12,000 unit parking capacity; and the capacity of the other destinations is set to 10,000. For the adjusted parking pricing situation, the parking fee at selected destinations (destinations 3, 4, 10, 12, 16, 17, 20, and 22) is raised from 5 to 7 (Dollars).The network capacities are assessed by using the proposed model associated with the abovementioned three parking management strategies. The link flow patterns of the maximum flow are shown in Figures4–6, from which the link utilization patterns are illustrated. The width of a link represents its capacity. If a link is fully utilized (when link capacity is reached), it will be marked in red; otherwise, it will be in green. The summarized results of the network capacity assessment are presented in Table 9. Figure 7 illustrates the parking demand at each destination area corresponding to the three parking management strategies.Figure 4
Link utilization pattern of maximum flow with an unlimited parking space.Figure 5
Link utilization pattern of maximum flow with a limited parking space.Figure 6
Link utilization pattern of maximum flow with limited parking space and adjusted parking pricing strategy.Table 9
Summarized results under different parking management strategies in Sioux-Falls.
Parking management strategiesNetwork capacityBinding capacity constraintsLink #Destination #Unlimited parking space and unified parking pricing347,221.5 pcu/h2, 4, 6, 9, 12, 16, 17, 19, 25, 29, 32, 34, 36, 39, 42, 46, 49, 52, 58, 61, 65, 69, 73, 75 (24 links)NoneLimited parking space and unified parking pricing289,707.4 pcu/h4, 9, 16, 19, 39, 42, 49, 65, 66, 69, 73, 75, 76 (13 links)3, 4, 10, 12, 16, 17, 22 (7 destinations)Limited parking space and adjusted parking pricing306,230.4 pcu/h4, 12, 17, 19, 34, 39, 42, 46, 49, 61, 66, 69, 73, 76 (14 links)1, 2, 5, 8, 10, 15, 16 (7 destinations)Figure 7
Maximum parking demand under different parking management strategies.According to the numerical results in Table9, the network capacity could be significantly overestimated when the capacity constraints of the parking supply are ignored. In the case of an unlimited parking space, as the parking capacity is not considered, the total travel demand is derived by only regarding the restraint of the link capacity. The trip attraction at some destinations may go unreasonably high. After involving the effect of the parking capacity, the network-wide capacity has been reduced much. As Figure 5 demonstrates, the number of saturated links (colored in red) decreases, compared to Figure 4, which indicates that the overall utilization of the network goes down. On the other hand, there are many links with low utilization (colored in green). These results can be regarded as the realistic capacity of this network, by considering the effect of the parking supply. Furthermore, if the traffic managers want to enhance the network-wide capacity with the limited road and parking supply resources, the adjusted parking pricing strategies will be recommended. By raising the parking fee at the selected destinations whose parking spaces have been in a saturated situation, the network capacity will be increased further. This effect is consistent with the experimental results in section 4.2.1. Figure 6 shows that the network utilization will be increased compared to Figure 5, as the portion of the green links is reduced. Therefore, adjusting parking pricing at the destination will be an effective strategy to promote the road network capacity.


## 4.1. Results of the New Model

To show the advantages of the proposed model, the result of the proposed model is compared with the other network capacity models in the literature [3, 4, 19, 24]. The experiments are carried out on the example in Figure 1. As the models in the literature on this topic were conducted for different problems under various backgrounds, it is inappropriate to compare the results of these models directly. Therefore, we conclude three situations from the literature: (1) without variable O-D demand (i.e., the reserve capacity model in this paper); (2) without variable destination cost; (3) without fixed O-D demand.For the situation without the variable O-D demand, the reserve network capacity model [1] is modified by adding the parking supply constraint. The O-D flows are assumed to grow following a fixed O-D distribution, and the effect of traffic congestion and parking pricing at destination areas is not involved. The reserve capacity is the most classical concept that has been widely applied for the assessment of transportation network capacity. Such concept was used in Asakura and Kashiwadani [19] and Leng and Yan [4]. The results of the reserve capacity model and the proposed model are reported in Tables 4 and 5, respectively.Table 4
Results of the reserve network capacity model.
O-DDemand typesDestination demandLinksLink flowV/C ratioFixed demandAdditional demandDestinationTotal trip attractionParking demand1–3307.50387.5065.6137.500.3751–4205.00450.0037.5275.000.6252–34010.00325.000.3122–4205.00425.000.312Total11027.50550.001.000650.001.000725.000.500Network capacity137.50 (demand multiplier = 1.25)Table 5
Results of the proposed road network capacity model.
O-DDemand typesDestination demandLinksLink flowV/C ratioFixed demandAdditional demandDestinationTotal trip attractionParking demand1–33053.333133.33100.0183.330.8331–4206.91465.1348.85226.910.3362–34010.00338.210.4782–42018.21450.001.000Total11088.46576.910.641650.001.000726.910.538Network capacity198.46From the results in Tables4 and 5, the network capacity is to be 137.5 by the reserve capacity model, while it is evaluated to be 222.35 by the proposed model. In both models, flows on link 5 and link 6 reach the capacity, and the links are the bottlenecks limiting the growth of the total travel demand in the network. Besides, in the results of the reserve capacity model, no parking facility is saturated; however, in the results of the proposed model, the parking capacity at destination 3 is fully used. The network capacity from the reserve capacity model is evidently lower than that from the proposed model. It means the reserve capacity tends to produce too conservative results [8], since it assumes an unchangeable travel demand pattern. The network-wide travel demand will be restricted to continue to grow if the flow on any individual link meets its capacity. By contrast, the proposed model with the CTDTA model as the lower level produces a changeable O-D demand pattern, which is more practical. Thus, a portion of travel demand can adjust their travel destination according to the parking cost and available space at the destination area. In this example, the limits to the total demand come from the capacities on link 5 and link 6, the parking capacity at destination 3, and the restraint from the O-D travel cost (soft constraint). Note that the variable travel demand does not change the O-D distribution in a completely free manner. The O-D travel distribution should follow the logit share model in equation (15), by which the destinations with lower disutility will be assigned more travel demand for any origin area, and vice versa.For the situation without variable destination cost, the O-D flows are assumed to grow with a variable O-D distribution, while the effect of traffic congestion at destinations is not considered. Tam and Lam [3] employed this behavior pattern for the maximum car ownership problem. For the situation without the fixed O-D demand, all motorists are considered to change their trip destination under the influence of traffic congestion (both from O-D travel cost and destination cost) and parking management strategy. Tam and Lam [3] and Xie et al. [24] used this assumption.Figure2 further compares the maximum demand patterns of different network capacity models. The abovementioned three situations are labeled as “Reserve Capacity,” “Without Destination Cost,” and “Without Fixed Demand.” The O-D demand patterns of the models are significantly different. Specifically, the differences are mainly on the demands between O-D (1–3) and O-D (2–4). The maximum demand pattern from the “Reserve Capacity” model is rather conservative, as it clearly follows the fixed O-D demand (as a prescribed O-D demand) existed in the network. Although O-D (1–3) and O-D (2–4) can be allocated more travel demand, limited by the capacity on link 5 and link 6 (the vital links for O-D (2–3)), the total demand cannot increase further. On the other hand, without considering the effect of destination congestions (i.e., the parking search time increases as the destination demand), the network capacity is overestimated in the situation “Without Destination Cost”. Note that the travel demands between O-D (1–4) and O-D (2–4) are higher than those from the results of the proposed model. This reflects that, without variable destination cost, the congestion effect at destination 4 cannot be captured. Travelers will choose destination 4 even though the congestion in this area is at a high level (i.e., the parking search time could be very long), which is unrealistic in real-life. Moreover, the situation “Without Fixed Demand” assumes an extreme demand pattern of maximum flow, in which the travel demand between O-D (2–4) is much higher while the demand of O-D (1–4) is lower compared with the other models. Such a demand pattern means the commuters between O-D (1–4) should be asked to give up their trips to increase the demand between the other O-D pairs, which is also not realistic for the urban transportation system.Figure 2
O-D demand pattern of maximum flow from different network capacity models.In Figure2, the proposed model produces a moderate result for network capacity assessment. Compared to the “Reserve Capacity” model, the potential of the network capacity by our model will be further developed between O-D (1–3) and O-D (2–4) after link 5 and link 6 reach their capacities. The total demand will keep growing until the parking capacity at destination 3 is violated. Besides, note that the demand between O-D (1–4) does not increase much. Because the travel cost between O-D (1–4) is significantly larger than that between O-D (1–3), most variable travel demands from origin 1 would like to choose node 3 as the destination for noncommuting activities. As the demand between O-D (1–3) cannot increase (limited by parking capacity), the demand for O-D (1–4) will not grow either. We find such restraint is caused by the travel cost difference among O-D pairs, which is referred to be the soft constraint as mentioned before. In conclusion, the proposed model can capture a more comprehensive situation compared with the models in the literature and, thus, is capable to better assess the road network capacity problem.


## 4.2. The Effect of considering Parking Supply and Parking Pricing

Based on the proposed network capacity model incorporated with parking strategies, we analyze the effect of parking supply and parking pricing on the network-wide capacity in this section. For this purpose, we configure 6 scenarios listed in Table6. The base scenario is the same as the example in Section 4.1. Scenarios 1 to 3 are associated with the changes in parking supply strategies. Scenarios 4 to 6 are corresponding to the adjustment of the parking pricing strategies at the destination areas.Table 6
Descriptions of scenarios.
ScenariosDescription0Base scenario1Only expand parking capacity at destination 32Only expand parking capacity at destination 43Expand parking capacity at both destinations4Increase parking pricing at one destination only5Increase parking pricing at both destinations in the same proportion6Increase parking pricing at both destinations by the same amount


### 4.2.1. Effect of Parking Supply

With the same parking pricing strategy, the effect of the parking supply on the network-wide capacity is analyzed. For Scenario 1 to 3, the settings of the parking capacities and the results of the network capacity model are reported in Table7.In Scenario 1, only the parking capacity at destination 3 is expanded (from 100 to 1000). Compared with the base scenario, the total network capacity is increased from 198.46 to 221.87. One of the binding (or active) constraints changes from the destination 3 to link 1. This indicates that the total capacity in the base scenario is limited by the parking capacity at destination 3. Expanding the parking supply at such destination areas can effectively enhance the network-wide capacity.In Scenario 2, only the parking capacity at destination 4 is expanded (from 80 to 1000). However, the total network capacity is not increased (it could appear as unobvious changes in practice). It is because that the parking supply at the destination constraint is still active. Expanding the capacities on the other destinations will have a small effect on the network-wide capacity.In Scenario 3, both the parking capacities at destination 4 and destination 5 are increased to 1000. It results in the same total network capacity as Scenario 1. This means if the network-wide capacity should be enhanced, it only needs to deal with the destinations whose capacity constraints are binding to the maximum total demand. The investment on the nonbinding parking supplies will have a marginal contribution to the total network capacity. Note that all of the binding constraints change to link capacities if the parking capacities are enlarged sufficiently. There is no need to expand parking capacities too much. On the other hand, ignoring the parking supply capacity might overestimate the capacity of the transportation network.Table 7
Results of network capacity under different parking capacities.
Parking capacityk3,k4Base scenario: (100, 80)Scenario 1: (1000, 80)Scenario 2: (100, 1000)Scenario 3: (1000, 1000)DestinationsParking demandTotal trip attractionParking demandTotal trip attractionParking demandTotal trip attractionParking demandTotal trip attraction3100.00133.33112.50150.00100.00133.33112.50150.00448.8565.1353.9071.8748.8565.1353.9071.87Network capacity198.46221.87198.46221.87Binding constraints∗Capacities on link 5 and link 6∗∗Parking capacity at destination 3Capacity on link 1Parking capacity at destination 3Capacity on link 1∗The capacity limits of the maximum network throughput. ∗∗The capacity constraints on link 5 and link 6 are active in all scenarios.


### 4.2.2. Effect of Parking Pricing

By holding the parking supply the same as the base scenario, the effect of the parking supply on the network-wide capacity can be investigated. The settings of parking capacities, as well as the model results, through Scenario 4 to 6 are reported in Table8.In Scenario 4, we only raise the parking pricing at destination 3 (from 4.0 to 8.0). However, the total network capacity is enhanced significantly (increasing to 240.0). Both destinations are saturated so the total travel demand cannot increase anymore. Specifically, the parking costs (consists of parking pricing and parking search time) for destination 3 and destination 4 are changed from 8.00 to 9.12 to 12.00 and 11.00, respectively. This results in the growth in the proportion of the travelers who choose node 4 as their destination. Hence, the demand to destination 4 can further grow, until the parking demand reaches the capacity.In Scenario 4, we raise the parking pricing to 200% for both destinations. The total network capacity is decreased slightly. The change of the parking pricing leads to the redistribution of the O-D demand pattern. According to the parking cost, a large proportion of travelers (for variable demand only) tend to choose destination 3. Therefore, the demand for destination 4 will not reach that level as the base scenario due to the soft constraint on O-D (1–4) and O-D (2–4).In Scenario 6, we increase the parking pricing with the same amount (by 4.0). Based on our model, the network capacity is unchanged despite the parking costs change a lot. In practice, one may regard such adjustment of the parking pricing has little impact on the network-wide capacity.Table 8
Results of network capacity under different parking pricing strategies.
Parking pricingπ3,π4Base scenario: (4.0, 5.0)Scenario 4: <(8.0, 5.0)Scenario 5: (8.0, 10.0)Scenario 6: (8.0, 9.0)DestinationsParking demandParking costParking demandParking costParking demandParking costParking demandParking cost3100.008.00100.0012.00100.0012.00100.0012.00448.859.1280.0011.0042.9813.8748.8513.12Network capacity198.46240.00190.65198.46In summary, adjusting the parking pricing strategy for selected destination areas will have an obvious influence on the network capacity of the transportation system. However, increase the parking pricing at all destinations together may result in a small effect for enhancing network capacity. Note that the O-D pattern (or spatial distribution) is the key to obtain a high network capacity. Figure3 shows the maximal O-D demand pattern for Scenario 4 and Scenario 6. The travel demand increases significantly on O-D (1–4) and O-D (2–4). It indicates that Scenario 4 results in a more proper O-D pattern to match the given network with higher utilization, and thus, a better effect is obtained on the network capacity compared with Scenario 6 (as well as Scenario 5).Figure 3
O-D demand pattern of maximum flow for Scenario 4 and Scenario 6.


## 4.2.1. Effect of Parking Supply

With the same parking pricing strategy, the effect of the parking supply on the network-wide capacity is analyzed. For Scenario 1 to 3, the settings of the parking capacities and the results of the network capacity model are reported in Table7.In Scenario 1, only the parking capacity at destination 3 is expanded (from 100 to 1000). Compared with the base scenario, the total network capacity is increased from 198.46 to 221.87. One of the binding (or active) constraints changes from the destination 3 to link 1. This indicates that the total capacity in the base scenario is limited by the parking capacity at destination 3. Expanding the parking supply at such destination areas can effectively enhance the network-wide capacity.In Scenario 2, only the parking capacity at destination 4 is expanded (from 80 to 1000). However, the total network capacity is not increased (it could appear as unobvious changes in practice). It is because that the parking supply at the destination constraint is still active. Expanding the capacities on the other destinations will have a small effect on the network-wide capacity.In Scenario 3, both the parking capacities at destination 4 and destination 5 are increased to 1000. It results in the same total network capacity as Scenario 1. This means if the network-wide capacity should be enhanced, it only needs to deal with the destinations whose capacity constraints are binding to the maximum total demand. The investment on the nonbinding parking supplies will have a marginal contribution to the total network capacity. Note that all of the binding constraints change to link capacities if the parking capacities are enlarged sufficiently. There is no need to expand parking capacities too much. On the other hand, ignoring the parking supply capacity might overestimate the capacity of the transportation network.Table 7
Results of network capacity under different parking capacities.
Parking capacityk3,k4Base scenario: (100, 80)Scenario 1: (1000, 80)Scenario 2: (100, 1000)Scenario 3: (1000, 1000)DestinationsParking demandTotal trip attractionParking demandTotal trip attractionParking demandTotal trip attractionParking demandTotal trip attraction3100.00133.33112.50150.00100.00133.33112.50150.00448.8565.1353.9071.8748.8565.1353.9071.87Network capacity198.46221.87198.46221.87Binding constraints∗Capacities on link 5 and link 6∗∗Parking capacity at destination 3Capacity on link 1Parking capacity at destination 3Capacity on link 1∗The capacity limits of the maximum network throughput. ∗∗The capacity constraints on link 5 and link 6 are active in all scenarios.


## 4.2.2. Effect of Parking Pricing

By holding the parking supply the same as the base scenario, the effect of the parking supply on the network-wide capacity can be investigated. The settings of parking capacities, as well as the model results, through Scenario 4 to 6 are reported in Table8.In Scenario 4, we only raise the parking pricing at destination 3 (from 4.0 to 8.0). However, the total network capacity is enhanced significantly (increasing to 240.0). Both destinations are saturated so the total travel demand cannot increase anymore. Specifically, the parking costs (consists of parking pricing and parking search time) for destination 3 and destination 4 are changed from 8.00 to 9.12 to 12.00 and 11.00, respectively. This results in the growth in the proportion of the travelers who choose node 4 as their destination. Hence, the demand to destination 4 can further grow, until the parking demand reaches the capacity.In Scenario 4, we raise the parking pricing to 200% for both destinations. The total network capacity is decreased slightly. The change of the parking pricing leads to the redistribution of the O-D demand pattern. According to the parking cost, a large proportion of travelers (for variable demand only) tend to choose destination 3. Therefore, the demand for destination 4 will not reach that level as the base scenario due to the soft constraint on O-D (1–4) and O-D (2–4).In Scenario 6, we increase the parking pricing with the same amount (by 4.0). Based on our model, the network capacity is unchanged despite the parking costs change a lot. In practice, one may regard such adjustment of the parking pricing has little impact on the network-wide capacity.Table 8
Results of network capacity under different parking pricing strategies.
Parking pricingπ3,π4Base scenario: (4.0, 5.0)Scenario 4: <(8.0, 5.0)Scenario 5: (8.0, 10.0)Scenario 6: (8.0, 9.0)DestinationsParking demandParking costParking demandParking costParking demandParking costParking demandParking cost3100.008.00100.0012.00100.0012.00100.0012.00448.859.1280.0011.0042.9813.8748.8513.12Network capacity198.46240.00190.65198.46In summary, adjusting the parking pricing strategy for selected destination areas will have an obvious influence on the network capacity of the transportation system. However, increase the parking pricing at all destinations together may result in a small effect for enhancing network capacity. Note that the O-D pattern (or spatial distribution) is the key to obtain a high network capacity. Figure3 shows the maximal O-D demand pattern for Scenario 4 and Scenario 6. The travel demand increases significantly on O-D (1–4) and O-D (2–4). It indicates that Scenario 4 results in a more proper O-D pattern to match the given network with higher utilization, and thus, a better effect is obtained on the network capacity compared with Scenario 6 (as well as Scenario 5).Figure 3
O-D demand pattern of maximum flow for Scenario 4 and Scenario 6.


## 4.3. Case Study in the Sioux-Falls Network

In this section, we numerically test the network capacity model with parking management strategies using the Sioux-Falls network (https://github.com/bstabler/TransportationNetworks). The Sioux-Falls network is a highway network with 24 nodes, 76 links, and 528 O-D pairs. All 24 nodes are origin/destination nodes. In order to test the network capacity model, we assumed the fixed travel demand does not exceed the network capacity. Therefore, the demand of all O-D pairs is rescaled as 1/5 of the original data.We considered three different parking management strategies in the Sioux-Falls network: (1) unlimited parking space and unified parking pricing for all destinations; (2) limited parking space and unified parking pricing at the destinations; and (3) limited parking space and adjusted parking pricing at the destinations. For the unlimited parking space situation, all destination areas are assumed to have infinite parking capacity, so there is no parking capacity constraint. For the limited parking space situation, we considered each destination is assigned with limited parking capacity. The capacity constraints are chosen according to the fixed demand in the network. Specifically, destination 10 (with the most trip attraction of the fixed demand) is assigned with 20,000 unit parking capacity; destinations 11, 15, 16, 17, 20, and 22 are assigned with 12,000 unit parking capacity; and the capacity of the other destinations is set to 10,000. For the adjusted parking pricing situation, the parking fee at selected destinations (destinations 3, 4, 10, 12, 16, 17, 20, and 22) is raised from 5 to 7 (Dollars).The network capacities are assessed by using the proposed model associated with the abovementioned three parking management strategies. The link flow patterns of the maximum flow are shown in Figures4–6, from which the link utilization patterns are illustrated. The width of a link represents its capacity. If a link is fully utilized (when link capacity is reached), it will be marked in red; otherwise, it will be in green. The summarized results of the network capacity assessment are presented in Table 9. Figure 7 illustrates the parking demand at each destination area corresponding to the three parking management strategies.Figure 4
Link utilization pattern of maximum flow with an unlimited parking space.Figure 5
Link utilization pattern of maximum flow with a limited parking space.Figure 6
Link utilization pattern of maximum flow with limited parking space and adjusted parking pricing strategy.Table 9
Summarized results under different parking management strategies in Sioux-Falls.
Parking management strategiesNetwork capacityBinding capacity constraintsLink #Destination #Unlimited parking space and unified parking pricing347,221.5 pcu/h2, 4, 6, 9, 12, 16, 17, 19, 25, 29, 32, 34, 36, 39, 42, 46, 49, 52, 58, 61, 65, 69, 73, 75 (24 links)NoneLimited parking space and unified parking pricing289,707.4 pcu/h4, 9, 16, 19, 39, 42, 49, 65, 66, 69, 73, 75, 76 (13 links)3, 4, 10, 12, 16, 17, 22 (7 destinations)Limited parking space and adjusted parking pricing306,230.4 pcu/h4, 12, 17, 19, 34, 39, 42, 46, 49, 61, 66, 69, 73, 76 (14 links)1, 2, 5, 8, 10, 15, 16 (7 destinations)Figure 7
Maximum parking demand under different parking management strategies.According to the numerical results in Table9, the network capacity could be significantly overestimated when the capacity constraints of the parking supply are ignored. In the case of an unlimited parking space, as the parking capacity is not considered, the total travel demand is derived by only regarding the restraint of the link capacity. The trip attraction at some destinations may go unreasonably high. After involving the effect of the parking capacity, the network-wide capacity has been reduced much. As Figure 5 demonstrates, the number of saturated links (colored in red) decreases, compared to Figure 4, which indicates that the overall utilization of the network goes down. On the other hand, there are many links with low utilization (colored in green). These results can be regarded as the realistic capacity of this network, by considering the effect of the parking supply. Furthermore, if the traffic managers want to enhance the network-wide capacity with the limited road and parking supply resources, the adjusted parking pricing strategies will be recommended. By raising the parking fee at the selected destinations whose parking spaces have been in a saturated situation, the network capacity will be increased further. This effect is consistent with the experimental results in section 4.2.1. Figure 6 shows that the network utilization will be increased compared to Figure 5, as the portion of the green links is reduced. Therefore, adjusting parking pricing at the destination will be an effective strategy to promote the road network capacity.


## 5. Conclusions

This study proposed an extended road network capacity model based on the transportation network capacity model in [2]. In the extended model with a bilevel programming formulation, the constraint and impact of parking supply and parking pricing at each traffic zone (corresponding to the travel destination) are involved to enhance the assessment of the road network capacity for obtaining a more reasonable result. The parking supply is embodied as the capacity constraint in the upper level and is employed in the parking search time function for the CTDTA model in the lower level. The parking pricing is integrated into the objective function of the lower-level model. For solving the capacity model efficiently, we provided a sensitivity analysis based (SAB) solution algorithm, in which the lower-level CTDTA model is solved by a path-based solution algorithm. From the numerical examples, we showed that the proposed network capacity model is capable to capture the effect of parking strategies on the O-D travel demand pattern, which improves the reasonability of the network capacity assessment result. The experiments also demonstrated that the parking supply is significant to restrain the network-wide capacity. To expand the network-wide capacity, it is efficient to deal with the destinations whose parking capacity is binding to the maximum travel demand. Also, implementing different parking pricing adjustments at destination areas will be more effective by raising the parking pricing at all destinations with a unified standard. Future works will apply our proposed model to real case studies. Also, it will be of interest to find the optimal parking management scheme for expanding the capacity of the given transportation network to the maximum level.



---

*Source: 8820680-2020-10-29.xml*