# Optimal Design of Transportation Networks with Automated Vehicle Links and Congestion Pricing

Authors: Yipeng Ye; Hua Wang
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

We propose a bi-level network design model comprising automated vehicle (AV) links and congestion pricing to improve traffic congestion. As upper-level road planners strive to minimize total travel-time costs by optimizing both the network design and the congestion pricing, lower-level travelers make choices about their routes to minimize their individual travel costs. Our proposed model integrates a network design and congestion pricing to improve traffic congestion and we use a relaxation-based method to solve the model. We conducted a series of numerical tests to analyze the proposed model and solution method. Our results indicate that network design is more effective than congestion pricing when the AV market penetration is high and the opposite is true when AV penetration is low. More importantly, we find that a network design of automated vehicle links with congestion pricing is superior to a single network design or congestion pricing, especially when both AVs and conventional vehicles have a relatively large market penetration.


---

## Body

## 1. Introduction

Urban transportation plays an important role in economic activity throughout the world. However, road congestion has become a serious problem in many metropolitan cities and has led to various problems, including economic inefficiency, traffic accidents, pollution, and excessive energy consumption. Network design and congestion pricing are classic and effective instruments for solving traffic congestion and have been studied for decades. Some studies have proposed network design strategies [1, 2]. Also, some comprehensive reviews have summarized the results of studies of the transportation network design problem (NDP) [3, 4]. Other studies worldwide have proposed and tested practical congestion pricing [5–7].Automated vehicles (AV) have attracted increasing attention in recent years and they are expected to improve the future safety levels and traffic congestion of existing urban transportation systems through improvements in traffic safety, road capacity, travel time, energy consumption, and pollution levels. Two of the anticipated advantages (relative to human-driver vehicle control) are increased road network capacity and the freeing up of driver-occupant time to engage in leisure activities or economically productive (nondriving) tasks [8]. Jiang [9] studied optimal signal design for mixed equilibrium networks with autonomous and regular vehicles. With the rapid increase of car ownership, the problem of traffic emission and lack of land for parking becomes a serious issue [10], and AV can substantially reduce traffic emission and save land for parking. AVs can also help traffic safety. Zhu and Ukkusuri [11] indicated that connected vehicle technology would potentially reduce 81% of all-vehicle target crashes, 83% of all light-vehicle target crashes, and 72% of all heavy-truck target crashes annually. Tientrakool et al. [12] and Chen et al. [13] stated that the capacity of AV links may approximately triple due to the benefits resulting from vehicle-to-vehicle communication. It follows that congestion pricing may become unnecessary when conventional vehicles (CV) are completely phased out. Despite these exciting developments regarding AVs, CVs cannot be phased out immediately and will continue to be widely used for many years. As such, it is necessary to consider the NDP and congestion pricing during this transitional period characterized by heterogeneous AV and CV travel modes.Among the transportation NDP and congestion pricing studies addressing AV and CV modes, few focus on the simultaneous optimization of the transportation system NDP and congestion pricing. An NDP with congestion pricing can be viewed as a Stackelberg game between the road planner and travelers, in which the road planner acts as the leader and travelers are the followers. In this paper, we investigate transportation networks involving both AV and CV modes and present an optimal and simultaneous network design and congestion pricing for these networks. We assume that some links in the network belong to the candidate link set and all links in this set can be converted to AV links or remain as regular links. AV links would allow only AVs to operate on them and their capacities could triple, as reported in Tientrakool et al. [12] and Chen et al. [13]. Regular links in the candidate link set allow both AVs and CVs to operate on them. To induce traffic flow and promote AV market penetration, the road planner can implement congestion pricing for CVs on the regular links in the candidate link set. Once the AV links are established and congestion pricing is deployed, we assume that AVs and CVs will follow the Wardrop equilibrium principle with respect to route choice to minimize their individual travel costs and yield a multiclass user equilibrium (UE). The results of this study show that the proposed NDP with congestion pricing can be an effective method for minimizing total travel time cost in a network comprising both AV and CV modes. More importantly, we find that NDP with congestion pricing outperforms a single NDP or congestion pricing, especially when both AVs and CVs have fairly large market penetrations. This means that the NDP with congestion pricing is an effective approach for alleviating traffic congestion in the transitional period characterized by heterogeneous AV and CV travel modes.


### 1.1. Literature Review

Although AVs are expected to greatly improve the safety and efficiency of transportation networks, proper management instruments must be applied in the transitional period during which there are heterogeneous AV and CV travel modes. Both the NDP and the congestion pricing are considered to be effective instruments for alleviating traffic congestion and they are typically employed to maximize network performance (e.g., minimize total travel-time cost, maximize social welfare) while travelers’ route choices are taken into account. The literature includes several comprehensive reviews of NDP, including those by Yang and H. Bell [4] and Farahani et al. [3]. Congestion pricing has also been extensively studied by both road managers and researchers and has long been considered to be an effective method for managing traffic demand and increasing tax revenue. Zhang and Yang [14] developed a method of simultaneously determining optimal locations and toll levels of cordon-based congestion pricing. Zhang et al. [15] studied the cooperation and competition congestion pricing policy among multiple regions. We refer interested readers to Yang and Huang [16] for details regarding developments in road pricing research. In this section, we briefly summarize recent studies related to our work, including AV research, joint road transportation management, and traffic optimization methods.(  1) Research on AVs. Many studies have highlighted the potential social benefits of AVs. Le Vine et al. [8] identified two benefits of road vehicle automation: (I) increased road capacity and (II) the freeing up the drivers’ in-car time for a wide range of economically valuable activities. Chen et al. [13] indicated that there are potential benefits of AVs to increase traffic safety, driver productivity, road capacity, and travel speed. Ji et al. [17] pointed out that connected AVs can be easily operated due to the application of information technology in AVs.Although existing AV developments and emerging innovations in AV technology indicate the huge potential for improving traffic safety and congestion, applications of AV technologies are as yet limited. In general, AV technologies are being developed to sense and make assessments about the environment in which the AV is traveling (e.g., other travelers, road signs, and traffic flow density) and to initiate the appropriate actions in response. However, these assessments fully depend on the proper functioning of the sensory devices, which remain in the research-and-development phase with numerous ongoing experiments [18]. Some studies have sought to improve AV performance via technical innovation. Häne et al. [19] developed an obstacle detection system for self-driving cars, using monocular cameras and wheel odometry. Aparicio et al. [20] aimed to improve the effectiveness of safety systems for active vulnerable road users (VRUs) that are currently on the market by expanding the scope of scenarios addressed by these systems and improving the overall system performance.Although currently immature AV technologies are being rapidly developed, it will be many years before AVs are widely adopted. As such, a long-term period of mixed AV and CV traffic flow is inevitable. Some researchers have suggested the expansion of dedicated AV areas to improve overall system traffic performance. For example, several studies have suggested the conversion of some traffic lanes into dedicated AV lanes to alleviate traffic congestion and improve traveler safety, since existing managed lanes are already equipped with communication systems [21]. Chen et al. [13] proposed the application of a time-dependent AV-lane design model on a general network for both AVs and CVs. Godsmark and Kakkar [22] proposed that AV areas can be designed to maximize the benefits realized from AVs, as well as to promote AV adoption. In addition, Chen et al. [23] proposed a mathematical framework for designing an optimal AV zone to achieve these goals.(  2) Joint Managements for Road Transportation. There has been an abundance of literatures published on the NDP and congestion pricing over the past half century. Readers can refer to Yang and H. Bell [4], Farahani et al. [3], and Yang and Huang [16] for comprehensive reviews and detailed discussions regarding the NDP and congestion pricing. Researchers also studied other kinds of joint implementation, such as joint management of road tolls and road credits. Jiang et al. [24] investigated simultaneous optimization of road tolls and tradable road credits in public-private mixed traffic networks. Wang and Zhang [7] examined the joint implementation of tradable credit and road pricing in public-private partnership networks considering UE-CN mixed equilibrium behaviors. In this section, we review recent studies related to the joint management of road transportation.Considering the development of network modelling to simultaneously determine network design strategy and road pricing, Koh et al. [25] studied joint optimal pricing and road capacity investment problems ranging from policy to technology perspectives. Zhang and van Wee [26] proposed a simultaneous toll-location and toll-level optimization model to maximize the network reserve capacity, which differs substantially from previous studies that aimed to minimize total travel time or maximize total social welfare. Wang et al. [27] proposed a bi-level programming model comprising a joint optimal-link-based tradable-credit-charging scheme and road capacity improvement. Their study results indicated that the synergistic effect of link-based credit charging and road capacity improvement enhanced urban transportation network performance. Xu et al. [28] proposed a discrete network design model with a road pricing scheme for minimizing total travel time under budgetary constraints. This optimal road capacity improvement and toll-level scheme considered the available budget levels and toll revenues.(  3) Traffic Optimization Methods. In recent years, a number of studies have focused on the development of algorithms for NDP and road pricing, including sensitivity-analysis-based [9, 29], cutting constraint [30], linearization [31, 32], and relaxation [27, 33] algorithms. Some metaheuristic algorithms have also been applied to solve these kinds of problems. For example, Meng et al. [5] proposed the hybrid genetic algorithm- (GA-) cost averaging (CA) method to solve the optimal-distance-based toll design problem for cordon-based congestion pricing schemes. Sun et al. [34] used a particle swarm optimization algorithm to design reliability-based traffic networks with advanced traveler information systems.


### 1.2. Positioning and Objective

Some researchers have considered the use of infrastructure adaption planning for AVs to reduce traffic congestion and improve traveler safety [21, 22, 35]. However, these works offered no integrated methods for solving traffic congestion. With this paper, we fill this gap by proposing a simultaneous optimization model of the NDP and congestion pricing for transportation networks with mixed AV and CV flow.Although network design and congestion pricing have long been subjects of study, to the best of our knowledge, no studies have offered a specialized solution method for a discrete NDP with continuous pricing. In this paper, we propose a relaxation-based method for solving this kind of problem.Specifically, our objectives in this paper are twofold. First, we propose a bi-level network design model of AV links and congestion pricing for improving traffic congestion, while considering traveler behavior with respect to route choice. Secondly, we propose a relaxation-based method for solving the above model, which can also be applied to solve a discrete NDP with continuous pricing.


### 1.3. Challenges, Our Solution Method, and Contributions

To achieve the above objectives, we have formulated an NDP with congestion pricing using bi-level programming, while also considering traveler behavior regarding route choice. Not surprisingly, this model is computationally challenging. The first difficulty is that the bi-level model is a NP-hard problem, even if it involves bi-level linear programming [36]. The second difficulty is that the variables in the upper level of the bi-level programming contain integer (network design variables) and continuous (pricing variables) aspects, which some previously developed bi-level programming algorithms for the NDP and pricing (e.g., Wang et al. [33], Wang et al. [27]) are unable to solve.To tackle these computational challenges, we decomposed the bi-level programming process into a number of subproblems. The subproblems for determining the upper bounds can be solved by the relaxation algorithm proposed by Wang et al. [27]. The subproblems for determining the lower bounds can be solved by the outer-approximation algorithm proposed by Wang et al. [33]. As the number of iterations increases, the gap between the lower and upper bounds decreases sharply and finally converges to zero.Contributions. This paper makes the following contributions:(1)
We propose a bi-level programming to formulate the NDP with congestion pricing for transportation networks with mixed AV and CV traffic flow. To the best of our knowledge, this is the first model that incorporates both network design and congestion pricing for this kind of network.(2)
We propose a relaxation-based method for solving the model, which can also be applied to solve a discrete NDP with continuous pricing.Managerial Insights.This paper also contributes to the following managerial insights:(1)
If we compare congestion pricing with network design, we find that congestion pricing is effective when AV market penetration is low and network design is effective when AV penetration is high. As such, road planners must apply different strategies to network with different AV market penetrations.(2)
Network design becomes more effective as the origin–destination (OD) demand is increasing, so it follows that AV promotion and AV link design may be the solution for alleviating traffic congestion when traffic demand continually increases.(3)
In the transitional period characterized by heterogeneous AV and CV travel modes, the NDP with congestion pricing strongly outperforms either network design or congestion pricing when both AVs and CVs have fairly large market penetrations. This finding indicates that the NDP with congestion pricing represents an effective management method for the transitional period when both AVs and CVs are operating.This paper is organized as follows. In Section2, we list the symbols used and propose our bi-level model for transportation systems in which both AV and CV modes are being used. In Section 3, we propose the use of the relaxation-based method for solving the bi-level model. In Section 4, we describe the numerical tests we conducted to analyze the proposed model and solution method. In Section 5, we conclude this paper with a brief summary and suggestions for future work.


## 1.1. Literature Review

Although AVs are expected to greatly improve the safety and efficiency of transportation networks, proper management instruments must be applied in the transitional period during which there are heterogeneous AV and CV travel modes. Both the NDP and the congestion pricing are considered to be effective instruments for alleviating traffic congestion and they are typically employed to maximize network performance (e.g., minimize total travel-time cost, maximize social welfare) while travelers’ route choices are taken into account. The literature includes several comprehensive reviews of NDP, including those by Yang and H. Bell [4] and Farahani et al. [3]. Congestion pricing has also been extensively studied by both road managers and researchers and has long been considered to be an effective method for managing traffic demand and increasing tax revenue. Zhang and Yang [14] developed a method of simultaneously determining optimal locations and toll levels of cordon-based congestion pricing. Zhang et al. [15] studied the cooperation and competition congestion pricing policy among multiple regions. We refer interested readers to Yang and Huang [16] for details regarding developments in road pricing research. In this section, we briefly summarize recent studies related to our work, including AV research, joint road transportation management, and traffic optimization methods.(  1) Research on AVs. Many studies have highlighted the potential social benefits of AVs. Le Vine et al. [8] identified two benefits of road vehicle automation: (I) increased road capacity and (II) the freeing up the drivers’ in-car time for a wide range of economically valuable activities. Chen et al. [13] indicated that there are potential benefits of AVs to increase traffic safety, driver productivity, road capacity, and travel speed. Ji et al. [17] pointed out that connected AVs can be easily operated due to the application of information technology in AVs.Although existing AV developments and emerging innovations in AV technology indicate the huge potential for improving traffic safety and congestion, applications of AV technologies are as yet limited. In general, AV technologies are being developed to sense and make assessments about the environment in which the AV is traveling (e.g., other travelers, road signs, and traffic flow density) and to initiate the appropriate actions in response. However, these assessments fully depend on the proper functioning of the sensory devices, which remain in the research-and-development phase with numerous ongoing experiments [18]. Some studies have sought to improve AV performance via technical innovation. Häne et al. [19] developed an obstacle detection system for self-driving cars, using monocular cameras and wheel odometry. Aparicio et al. [20] aimed to improve the effectiveness of safety systems for active vulnerable road users (VRUs) that are currently on the market by expanding the scope of scenarios addressed by these systems and improving the overall system performance.Although currently immature AV technologies are being rapidly developed, it will be many years before AVs are widely adopted. As such, a long-term period of mixed AV and CV traffic flow is inevitable. Some researchers have suggested the expansion of dedicated AV areas to improve overall system traffic performance. For example, several studies have suggested the conversion of some traffic lanes into dedicated AV lanes to alleviate traffic congestion and improve traveler safety, since existing managed lanes are already equipped with communication systems [21]. Chen et al. [13] proposed the application of a time-dependent AV-lane design model on a general network for both AVs and CVs. Godsmark and Kakkar [22] proposed that AV areas can be designed to maximize the benefits realized from AVs, as well as to promote AV adoption. In addition, Chen et al. [23] proposed a mathematical framework for designing an optimal AV zone to achieve these goals.(  2) Joint Managements for Road Transportation. There has been an abundance of literatures published on the NDP and congestion pricing over the past half century. Readers can refer to Yang and H. Bell [4], Farahani et al. [3], and Yang and Huang [16] for comprehensive reviews and detailed discussions regarding the NDP and congestion pricing. Researchers also studied other kinds of joint implementation, such as joint management of road tolls and road credits. Jiang et al. [24] investigated simultaneous optimization of road tolls and tradable road credits in public-private mixed traffic networks. Wang and Zhang [7] examined the joint implementation of tradable credit and road pricing in public-private partnership networks considering UE-CN mixed equilibrium behaviors. In this section, we review recent studies related to the joint management of road transportation.Considering the development of network modelling to simultaneously determine network design strategy and road pricing, Koh et al. [25] studied joint optimal pricing and road capacity investment problems ranging from policy to technology perspectives. Zhang and van Wee [26] proposed a simultaneous toll-location and toll-level optimization model to maximize the network reserve capacity, which differs substantially from previous studies that aimed to minimize total travel time or maximize total social welfare. Wang et al. [27] proposed a bi-level programming model comprising a joint optimal-link-based tradable-credit-charging scheme and road capacity improvement. Their study results indicated that the synergistic effect of link-based credit charging and road capacity improvement enhanced urban transportation network performance. Xu et al. [28] proposed a discrete network design model with a road pricing scheme for minimizing total travel time under budgetary constraints. This optimal road capacity improvement and toll-level scheme considered the available budget levels and toll revenues.(  3) Traffic Optimization Methods. In recent years, a number of studies have focused on the development of algorithms for NDP and road pricing, including sensitivity-analysis-based [9, 29], cutting constraint [30], linearization [31, 32], and relaxation [27, 33] algorithms. Some metaheuristic algorithms have also been applied to solve these kinds of problems. For example, Meng et al. [5] proposed the hybrid genetic algorithm- (GA-) cost averaging (CA) method to solve the optimal-distance-based toll design problem for cordon-based congestion pricing schemes. Sun et al. [34] used a particle swarm optimization algorithm to design reliability-based traffic networks with advanced traveler information systems.


## 1.2. Positioning and Objective

Some researchers have considered the use of infrastructure adaption planning for AVs to reduce traffic congestion and improve traveler safety [21, 22, 35]. However, these works offered no integrated methods for solving traffic congestion. With this paper, we fill this gap by proposing a simultaneous optimization model of the NDP and congestion pricing for transportation networks with mixed AV and CV flow.Although network design and congestion pricing have long been subjects of study, to the best of our knowledge, no studies have offered a specialized solution method for a discrete NDP with continuous pricing. In this paper, we propose a relaxation-based method for solving this kind of problem.Specifically, our objectives in this paper are twofold. First, we propose a bi-level network design model of AV links and congestion pricing for improving traffic congestion, while considering traveler behavior with respect to route choice. Secondly, we propose a relaxation-based method for solving the above model, which can also be applied to solve a discrete NDP with continuous pricing.


## 1.3. Challenges, Our Solution Method, and Contributions

To achieve the above objectives, we have formulated an NDP with congestion pricing using bi-level programming, while also considering traveler behavior regarding route choice. Not surprisingly, this model is computationally challenging. The first difficulty is that the bi-level model is a NP-hard problem, even if it involves bi-level linear programming [36]. The second difficulty is that the variables in the upper level of the bi-level programming contain integer (network design variables) and continuous (pricing variables) aspects, which some previously developed bi-level programming algorithms for the NDP and pricing (e.g., Wang et al. [33], Wang et al. [27]) are unable to solve.To tackle these computational challenges, we decomposed the bi-level programming process into a number of subproblems. The subproblems for determining the upper bounds can be solved by the relaxation algorithm proposed by Wang et al. [27]. The subproblems for determining the lower bounds can be solved by the outer-approximation algorithm proposed by Wang et al. [33]. As the number of iterations increases, the gap between the lower and upper bounds decreases sharply and finally converges to zero.Contributions. This paper makes the following contributions:(1)
We propose a bi-level programming to formulate the NDP with congestion pricing for transportation networks with mixed AV and CV traffic flow. To the best of our knowledge, this is the first model that incorporates both network design and congestion pricing for this kind of network.(2)
We propose a relaxation-based method for solving the model, which can also be applied to solve a discrete NDP with continuous pricing.Managerial Insights.This paper also contributes to the following managerial insights:(1)
If we compare congestion pricing with network design, we find that congestion pricing is effective when AV market penetration is low and network design is effective when AV penetration is high. As such, road planners must apply different strategies to network with different AV market penetrations.(2)
Network design becomes more effective as the origin–destination (OD) demand is increasing, so it follows that AV promotion and AV link design may be the solution for alleviating traffic congestion when traffic demand continually increases.(3)
In the transitional period characterized by heterogeneous AV and CV travel modes, the NDP with congestion pricing strongly outperforms either network design or congestion pricing when both AVs and CVs have fairly large market penetrations. This finding indicates that the NDP with congestion pricing represents an effective management method for the transitional period when both AVs and CVs are operating.This paper is organized as follows. In Section2, we list the symbols used and propose our bi-level model for transportation systems in which both AV and CV modes are being used. In Section 3, we propose the use of the relaxation-based method for solving the bi-level model. In Section 4, we describe the numerical tests we conducted to analyze the proposed model and solution method. In Section 5, we conclude this paper with a brief summary and suggestions for future work.


## 2. Model Formulation

The network design problem (NDP) can be represented as a Stackelberg game between the road planner and travelers. The road planner can induce but not control traveler route choices. This game can be formulated as a bi-level optimization model, in which the planner in the upper level determines the network design and congestion pricing to minimize the total travel cost in the transportation network and the travelers determine their routes to minimize their individual travel costs. We list the set, parameter, and decision variable symbols as follows:Sets N: Set of nodes in the transportation network A: Set of links in the transportation network A ~: Set of candidate AV links in the transportation network, A~⊆A W: Set of origin–destination (OD) pairs in the transportation network K w A V: Path set for AV mode between OD pair w∈W K w C V: Path set for CV mode between OD pair w∈WParameters δ a , k: A binary coefficient which equals 1 if path k uses link a∈A; otherwise δa,k=0 c a: Link capacity of link a∈A∖A~ c a 1: Link capacity of link a∈A~ if link a is set to be AV link c a 2: Link capacity of link a∈A~ if link a remains to be regular link D w A V: Demands of AV mode for OD pair w∈W D w C V: Demands of CV mode for OD pair w∈W t a v a , C a: Travel-time cost function on link a∈A when the link flow and capacity are va and Ca, respectively L: A positive large numberDecision Variables x a: A binary decision variable. xa=1 if link a∈A~ is set to be AV link. Otherwise xa=0 τ a: Link-based pricing on a∈A~ for CV x: A vector defined as x=xa,a∈A~ τ: A vector defined as τ=τa,a∈A~ v a A V: Link flow of AV mode on link a v a C V: Link flow of CV mode on link a v a: Link flow on link a, which equals to vaAV+vaCV v: A vector defined as v=va,a∈A f k A V: Path flow of AV mode on path k f k C V: Path flow of CV mode on path k.In this study, we assume that the road planner will aim at minimizing the total travel-time cost in the network by the network design and congestion pricing. After being presented with a designed network and congestion pricing for CVs, all travelers will strive to minimize their individual travel costs and their route choices can be characterized by the UE principle.In addition, we assume that all links in the network are regular. However, links in candidate link setA~ can be converted to AV links and only AVs can operate on AV links. We note that the capacity of a link can be tripled by converting it from a regular to an AV link [12, 13]. It follows that pure AV flow will involve much less travel time when it passes through AV links. If some links in the candidate link set A~ are not converted to AV links, then the road planner can implement congestion pricing for CVs on these links. For example, we use the schematic in Figure 1 to illustrate network design and congestion pricing for a network comprising four nodes and five links.Figure 1
Schematic of a network with four nodes and five links.In this network, we consider link 1 and link 4 to be candidate links that can be converted to AV links. That is,A=1,2,3,4,5 and A~=1,4. However, we only choose link 1 to be an AV link and x1=1 and x4=0. It follows that link 4 is still a regular link and can be a tolled link for CVs that run on it.Based on the above assumptions, we can formulate the NDP bi-level programming (BLP) as shown below:[BLP](1)minx,τ∑a∈A∖A~tavax,τ,cavax,τ+∑a∈A~xatavax,τ,ca1vax,τ+∑a∈A~1-xatavax,τ,ca2vax,τs.t.(2)xa∈0,1,∀a∈A~,(3)0≤τa≤L1-xa,∀a∈A~,where flow v solves the following UE problem using link tolls and flow constraints for CVs:(4)minv∑a∈A∖A~∫0vataθ,cadθ+∑a∈A~xa∫0vataθ,ca1dθ+∑a∈A~1-xa∫0vataθ,ca2dθ+∑a∈A~τavaCVs.t.(5)∑k∈KwAVfkAV=DwAV,∀w∈W,(6)∑k∈KwCVfkCV=DwCV,∀w∈W,(7)vaAV=∑w∈W∑k∈KwAVδa,kfkAV,∀a∈A,(8)vaCV=∑w∈W∑k∈KwCVδa,kfkCV,∀a∈A,(9)va=vaAV+vaCV,∀a∈A,(10)fkAV≥0,∀k∈KwAV,∀w∈W,(11)fkCV≥0,∀k∈KwCV,∀w∈W.(12)xavaCV=0,∀a∈A~.In the above BLP, (1) and (4) are objective functions of upper-level and lower-level programs, respectively. The road planner in the upper level determines the network design variable x and congestion pricing variable τ, based on the responses of travelers being stable at UE. Constraint (2) ensures that any candidate AV link can be either an AV or regular link. Constraint (3) ensures that only regular links can be tolled links for CVs. Constraints (5)-(11) ensure flow balance in the network. Constraint (12) ensures that only regular links allow CVs to run on them.Suppose that the link travel-time cost function is the following Bureau of Public Roads (BPR) functiontava,Ca=ta01+0.15va/Ca4, where ta0 is the free-flow travel-time cost of link a. For a given network design x and congestion pricing τ, the lower-level programming is strictly convex and has a unique optimal solution for link flows. It follows that the lower-level programming can be replaced with its Karush–Kuhn–Tucker (KKT) conditions. The KKT conditions for the lower-level programming are as follows:(13)∑k∈KwAVfkAV=DwAV,∀w∈W,(14)∑k∈KwCVfkCV=DwCV,∀w∈W,(15)vaAV=∑w∈W∑k∈KwAVδa,kfkAV,∀a∈A,(16)vaCV=∑w∈W∑k∈KwCVδa,kfkCV,∀a∈A,(17)va=vaAV+vaCV,∀a∈A,(18)xavaCV=0,∀a∈A~,(19)∑a∈A~xatava,ca1δa,k+∑a∈A~1-xatava,ca2δa,k+∑a∈A∖A~tava,caδa,k-cwAV≥0,fkAV≥0,∀k∈KwAV,∀w∈W,(20)∑a∈A~xatava,ca1δa,k+∑a∈A~1-xatava,ca2δa,k+∑a∈A∖A~tava,caδa,k-cwAVfkAV=0,∀k∈KwAV,∀w∈W,(21)∑a∈A~xatava,ca1δa,k+∑a∈A~1-xatava,ca2δa,k+∑a∈A~τa+λaxaδa,k+∑a∈A∖A~tava,caδa,k-cwCV≥0,fkCV≥0,∀k∈KwCV,∀w∈W,(22)∑a∈A~xatava,ca1δa,k+∑a∈A~1-xatava,ca2δa,k+∑a∈A~τa+λaxaδa,k+∑a∈A∖A~tava,caδa,k-cwCVfkCV=0,∀k∈KwCV,∀w∈W.


## 3. Relaxation-Based Method for Network Design with Congestion Pricing

Solving the NDP with congestion pricing is a challenge since the decision variables of the road planner contain both discrete (AV link design) and continuous (pricing) variables. Wang et al. [33] proposed bi-level programming and a relaxation method for the discrete network design problem (DNDP). Our work extends the DNDP approach since we also consider continuous pricing variables. Here, we combine efficient and effective relaxation algorithms for the NDPs addressed in Wang et al. [27] and Wang et al. [33] and propose a relaxation-based method to solve the network design with congestion pricing.Let(23)Ωx,τ=x,τ:xandτsatisfyconstraints2-3,ΩvRP=v:vsatisfyconstraints5-12,ΩvUE=v:vsatisfyconstraints13-22.We can formulate the relaxed problem (RP) for the network design with congestion pricing when the traffic assignment follows the system optimal (SO) principle as follows. This enables us to obtain the optimal solution x∗ with SO traffic assignment.[RP](24)minx,0∈Ωx,τ,v∈ΩvRP∑a∈A∖A~tava,cava+∑a∈A~xatava,ca1va+∑a∈A~1-xatava,ca2vaIn the relaxation-based method, we solve [RP] by iteratively excluding the solutionx∗. We do so by adding the following constraint to [RP] iteratively:(25)∑alla∈A~thatsatisfyingxa∗=0xa+∑alla∈A~thatsatisfyingxa∗=11-xa≥1Here, we define the pricing problem (PP) when the network design variablex is given as x∗.[PP](26)minx∗,τ∈Ωx,τ,v∈ΩvUE∑a∈A∖A~tava,cava+∑a∈A~xatava,ca1va+∑a∈A~1-xatava,ca2vaThe relaxation-based method is as follows:Step  0. Define a set Ω-x=⌀ that contains all generated solutions for generating the cuts given by constraint (25). Define the upper bound UB=+∞, incumbent optimal solution xopt,τopt.Step  1. Reformulate [RP] as [RP-1], as follows:[RP-1](27)minx,0∈Ωx,τ,v∈ΩvRP∑a∈A∖A~tava,cava+∑a∈A~tava1,ca1va1+∑a∈A~tava2,ca2va2s.t.(28)va=va1+va2,∀a∈A~,0≤va1≤Lxa,∀a∈A~,0≤va2≤L1-xa,∀a∈A~,0≤τa≤Lxa,∀a∈A~,xa∈0,1,∀a∈A~,where va1 and va2 are auxiliary variables. Solve [RP-1] with the following constraints using the outer-approximation algorithm presented in Wang et al. [33]:(29)∑a∈A~1-x-axa+∑a∈A~x-a1-xa≥1,∀x-∈Ω-x.If the problem is infeasible, we have enumerated all feasible solutions and hencexopt,τopt is the optimal solution and we stop. Otherwise, obtain the provisional optimal design denoted by x∗ and the provisional optimal value denoted by ObjRP of [RP] under constraint (29). If UB≤ObjRP, xopt,τopt is the optimal solution, stop. Otherwise, go to step 2.Step  2. Solve [PP] by fixing x at x∗ and apply the relaxation algorithm presented in Wang et al. [27]. Then, we can obtain the optimal value ObjPP, optimal pricing τ∗, and vehicle flow v∗. If UB≤ObjPP, then x∗,τ∗ is not better than xopt,τopt and, hence, we set Ω-x:=Ω-x∪x∗ and go to step 1. Else, set UB=ObjPP and xopt,τopt=x∗,τ∗. If UB≤ObjRP and xopt,τopt is the optimal solution, stop. Otherwise, set Ω-x:=Ω-x∪x∗ and go to step 1.


## 4. Numerical Tests

### 4.1. Network Description

In the following sections, to evaluate the effectiveness of the proposed model and solution method, we present some numerical examples for a nine-node network with 18 links [37]. Suppose that the travel-time cost functions of all links are defined as having the following BPR form:(30)tava,Ca=ta01+0.15vaCa4,where ta0 is the free-flow travel-time cost on link a and Ca is the capacity of link a. Figure 2 shows the initial network without converting regular links to AV links. The tuple above each linka denotes the free-flow travel-time cost and initial capacity when all links are regular. There are four OD pairs in the network, and the OD demands of all the travel modes are shown at the bottom of Figure 2.Figure 2
Nine-node network.In the initial network, all links are regular links and all vehicles are allowed to operate on these links without congestion pricing. We can obtain vehicle flows in the initial network by solving UE problems (4)-(12); when setting candidate AV link set A~=⌀ without congestion pricing. After solving this UE problem for vehicle flows, we find that no AVs run on links (5,6), (6,5), (6,9), (7,8), (8,7), and (8,3) in the initial network. So we exclude these links from the candidate link set and form the following candidate link set:(31)A~=1,5,1,6,2,5,2,6,5,7,5,9,6,8,9,7,9,8,7,3,7,4,8,4.If any link a∈A~ is converted to an AV link, then the capacity of link a is tripled and only AVs are allowed to run on it. For any link a∈A~ that is not converted to an AV link, the road planner can implement congestion pricing for CVs.In the following tests, we used a personal computer with an Intel Core (TM) i7 4700MQ CPU, 16GB RAM, and Windows 7 Professional operating system. We coded the proposed solution method using Python and called Gurobi 7.5.2 and Ipopt 3.12.7 to solve the NDP with congestion pricing. We ran the codes for all cases in the following tests and the longest computation time was less than five minutes.


### 4.2. Convergence of Relaxation-Based Method

We tested the convergence of the relaxation-based method, and Figure3 shows the lower and upper bounds at each iteration of this method. We can see that the gap between lower and upper bounds decreases sharply and finally converges to zero. Table 1 shows the optimal network design with congestion pricing for this case. Table 2 shows the link flows in the network when the optimal network design with congestion pricing is implemented.Table 1
Optimal network design with congestion pricing.
Candidate link x a τ a (1,5) 1 0.000 (1,6) 0 4.756 (2,5) 0 3.272 (2,6) 0 5.821 (5,7) 1 0.000 (5,9) 0 3.350 (6,8) 0 8.732 (9,7) 0 3.132 (9,8) 0 1.532 (7,3) 1 0.000 (7,4) 1 0.000 (8,4) 0 4.593Table 2
Link flows in the network upon implementation of the optimal network design with congestion pricing.
Link AV link flow CV link flow (1,5) 35.000 0.000 (1,6) 0.000 35.000 (2,5) 35.000 0.000 (2,6) 0.000 35.000 (5,6) 0.000 0.000 (6,5) 0.000 0.000 (5,7) 55.774 0.000 (5,9) 14.226 0.000 (6,8) 0.000 42.768 (6,9) 0.000 27.232 (9,7) 4.450 18.119 (9,8) 9.775 9.113 (7,8) 0.000 18.119 (8,7) 0.000 0.000 (7,3) 30.000 0.000 (7,4) 30.225 0.000 (8,3) 0.000 30.000 (8,4) 9.775 40.000Figure 3
Lower and upper bounds at each iteration of the relaxation-based method.


### 4.3. Model Comparison

In this section, we use four models to demonstrate the efficiency of the NDP with congestion pricing. The first model is to do nothing, in that we set no links for AVs and no tolls for CVs. The second model is a pricing scheme for CVs without any network design. The third model is an NDP without congestion pricing. The fourth model is the NDP with congestion pricing, as proposed. The total travel-time costs associated with these four models are 5886.276, 5440.112, 3507.934, and 3342.627, respectively. We can clearly see that using both network design and congestion pricing can improve the traffic conditions with heterogeneous AV and CV travel modes. In addition, the road planner can implement these methods simultaneously, which realizes better results than implementing the network design or congestion pricing separately.


### 4.4. Sensitivity Analyses

Since many parameters can impact the total travel-time cost in a network, here, we perform sensitivity analyses. All tests in this section are based on the network proposed in Section4.1.Figure4 shows variances in the total travel-time cost against AV market penetrations. “ratio=3” indicates that the AV link capacity is tripled when it is converted from a regular to an AV link. We can see that a greater adoption of AVs always leads to less total travel-time cost for ratio = 2,2.5,3. However, this is not true for ratio = 1,1.5. This means that AVs should be promoted only when the AV technique is mature and AV link capacity can be increased significantly; otherwise, AV promotion may cause the opposite effect.Figure 4
Variances of total travel-time cost with AV market penetrations.When the AV technique matures, more people will choose the AV mode to benefit from its higher capacity and lower travel time. By fixing the total demand of the network, we tested the models described in Section4.3 at different AV market penetrations. Figure 5 shows a comparison of the four models, in which we can see that the NDP with congestion pricing is always the most effective. Also, we can see that congestion pricing is effective when the AV market penetration is low and network design is effective when AV penetration is high. The reason for this is clear: when AV market penetration is low, congestion pricing to control CVs is effective. When AV penetration is high, a network design for AVs is effective. This means that road planners should concentrate on different strategies for different AV market penetrations. In addition, we find that the NDP with congestion pricing strongly outperforms either NDP or pricing when both AVs and CVs have large market penetrations. This shows that the proposed NDP with congestion pricing can be an effective method for alleviating traffic congestion in the transitional period characterized by heterogeneous AV and CV travel modes.Figure 5
Four models at different AV market penetrations.Assuming that the initial demand is that shown in Figure2, Figures 6(a)–6(c) show variances in the total travel-time costs for the four models with increasing percentages of OD demand and AV market penetration. Given a fixed AV market penetration, we can see that the effect of pure congestion pricing becomes worse with increasing demand. However, the effect of a pure network design improves with increasing demand. The gap between the total travel-time cost by the NDP with congestion pricing and that by an NDP alone is almost the same even if the OD demand increases. Also, we can see that the NDP becomes more effective as OD demand increases, but congestion pricing does not. As such, we can infer that AV promotion and AV link design may be the best solution for alleviating traffic congestion as traffic demand continues to grow.Figure 6 (a)
Variances of total travel-time cost with increasing percentage of OD demand when AV market penetration = 20% (b)
Variances of total travel-time cost with increasing percentage of OD demand when AV market penetration = 50% (c)
Variances of total travel-time cost with increasing percentage of OD demand when AV market penetration = 80%Since high congestion pricing for CVs would generate public resentment, we set an upper bound for pricingτa. Figure 7 shows the variance of total travel-time cost with respect to the upper bound for congestion pricing. Clearly, setting a reasonable upper bound for congestion pricing cannot only reduce public discontent, but also can effectively reduce total travel-time cost.Figure 7
Variance of total travel-time cost with respect to the upper bound of congestion pricing.


## 4.1. Network Description

In the following sections, to evaluate the effectiveness of the proposed model and solution method, we present some numerical examples for a nine-node network with 18 links [37]. Suppose that the travel-time cost functions of all links are defined as having the following BPR form:(30)tava,Ca=ta01+0.15vaCa4,where ta0 is the free-flow travel-time cost on link a and Ca is the capacity of link a. Figure 2 shows the initial network without converting regular links to AV links. The tuple above each linka denotes the free-flow travel-time cost and initial capacity when all links are regular. There are four OD pairs in the network, and the OD demands of all the travel modes are shown at the bottom of Figure 2.Figure 2
Nine-node network.In the initial network, all links are regular links and all vehicles are allowed to operate on these links without congestion pricing. We can obtain vehicle flows in the initial network by solving UE problems (4)-(12); when setting candidate AV link set A~=⌀ without congestion pricing. After solving this UE problem for vehicle flows, we find that no AVs run on links (5,6), (6,5), (6,9), (7,8), (8,7), and (8,3) in the initial network. So we exclude these links from the candidate link set and form the following candidate link set:(31)A~=1,5,1,6,2,5,2,6,5,7,5,9,6,8,9,7,9,8,7,3,7,4,8,4.If any link a∈A~ is converted to an AV link, then the capacity of link a is tripled and only AVs are allowed to run on it. For any link a∈A~ that is not converted to an AV link, the road planner can implement congestion pricing for CVs.In the following tests, we used a personal computer with an Intel Core (TM) i7 4700MQ CPU, 16GB RAM, and Windows 7 Professional operating system. We coded the proposed solution method using Python and called Gurobi 7.5.2 and Ipopt 3.12.7 to solve the NDP with congestion pricing. We ran the codes for all cases in the following tests and the longest computation time was less than five minutes.


## 4.2. Convergence of Relaxation-Based Method

We tested the convergence of the relaxation-based method, and Figure3 shows the lower and upper bounds at each iteration of this method. We can see that the gap between lower and upper bounds decreases sharply and finally converges to zero. Table 1 shows the optimal network design with congestion pricing for this case. Table 2 shows the link flows in the network when the optimal network design with congestion pricing is implemented.Table 1
Optimal network design with congestion pricing.
Candidate link x a τ a (1,5) 1 0.000 (1,6) 0 4.756 (2,5) 0 3.272 (2,6) 0 5.821 (5,7) 1 0.000 (5,9) 0 3.350 (6,8) 0 8.732 (9,7) 0 3.132 (9,8) 0 1.532 (7,3) 1 0.000 (7,4) 1 0.000 (8,4) 0 4.593Table 2
Link flows in the network upon implementation of the optimal network design with congestion pricing.
Link AV link flow CV link flow (1,5) 35.000 0.000 (1,6) 0.000 35.000 (2,5) 35.000 0.000 (2,6) 0.000 35.000 (5,6) 0.000 0.000 (6,5) 0.000 0.000 (5,7) 55.774 0.000 (5,9) 14.226 0.000 (6,8) 0.000 42.768 (6,9) 0.000 27.232 (9,7) 4.450 18.119 (9,8) 9.775 9.113 (7,8) 0.000 18.119 (8,7) 0.000 0.000 (7,3) 30.000 0.000 (7,4) 30.225 0.000 (8,3) 0.000 30.000 (8,4) 9.775 40.000Figure 3
Lower and upper bounds at each iteration of the relaxation-based method.


## 4.3. Model Comparison

In this section, we use four models to demonstrate the efficiency of the NDP with congestion pricing. The first model is to do nothing, in that we set no links for AVs and no tolls for CVs. The second model is a pricing scheme for CVs without any network design. The third model is an NDP without congestion pricing. The fourth model is the NDP with congestion pricing, as proposed. The total travel-time costs associated with these four models are 5886.276, 5440.112, 3507.934, and 3342.627, respectively. We can clearly see that using both network design and congestion pricing can improve the traffic conditions with heterogeneous AV and CV travel modes. In addition, the road planner can implement these methods simultaneously, which realizes better results than implementing the network design or congestion pricing separately.


## 4.4. Sensitivity Analyses

Since many parameters can impact the total travel-time cost in a network, here, we perform sensitivity analyses. All tests in this section are based on the network proposed in Section4.1.Figure4 shows variances in the total travel-time cost against AV market penetrations. “ratio=3” indicates that the AV link capacity is tripled when it is converted from a regular to an AV link. We can see that a greater adoption of AVs always leads to less total travel-time cost for ratio = 2,2.5,3. However, this is not true for ratio = 1,1.5. This means that AVs should be promoted only when the AV technique is mature and AV link capacity can be increased significantly; otherwise, AV promotion may cause the opposite effect.Figure 4
Variances of total travel-time cost with AV market penetrations.When the AV technique matures, more people will choose the AV mode to benefit from its higher capacity and lower travel time. By fixing the total demand of the network, we tested the models described in Section4.3 at different AV market penetrations. Figure 5 shows a comparison of the four models, in which we can see that the NDP with congestion pricing is always the most effective. Also, we can see that congestion pricing is effective when the AV market penetration is low and network design is effective when AV penetration is high. The reason for this is clear: when AV market penetration is low, congestion pricing to control CVs is effective. When AV penetration is high, a network design for AVs is effective. This means that road planners should concentrate on different strategies for different AV market penetrations. In addition, we find that the NDP with congestion pricing strongly outperforms either NDP or pricing when both AVs and CVs have large market penetrations. This shows that the proposed NDP with congestion pricing can be an effective method for alleviating traffic congestion in the transitional period characterized by heterogeneous AV and CV travel modes.Figure 5
Four models at different AV market penetrations.Assuming that the initial demand is that shown in Figure2, Figures 6(a)–6(c) show variances in the total travel-time costs for the four models with increasing percentages of OD demand and AV market penetration. Given a fixed AV market penetration, we can see that the effect of pure congestion pricing becomes worse with increasing demand. However, the effect of a pure network design improves with increasing demand. The gap between the total travel-time cost by the NDP with congestion pricing and that by an NDP alone is almost the same even if the OD demand increases. Also, we can see that the NDP becomes more effective as OD demand increases, but congestion pricing does not. As such, we can infer that AV promotion and AV link design may be the best solution for alleviating traffic congestion as traffic demand continues to grow.Figure 6 (a)
Variances of total travel-time cost with increasing percentage of OD demand when AV market penetration = 20% (b)
Variances of total travel-time cost with increasing percentage of OD demand when AV market penetration = 50% (c)
Variances of total travel-time cost with increasing percentage of OD demand when AV market penetration = 80%Since high congestion pricing for CVs would generate public resentment, we set an upper bound for pricingτa. Figure 7 shows the variance of total travel-time cost with respect to the upper bound for congestion pricing. Clearly, setting a reasonable upper bound for congestion pricing cannot only reduce public discontent, but also can effectively reduce total travel-time cost.Figure 7
Variance of total travel-time cost with respect to the upper bound of congestion pricing.


## 5. Conclusions and Future Research

In this paper, we proposed a bi-level network design model comprising AV links and congestion pricing to alleviate traffic congestion when AVs and CVs are both operating in a transportation network. In this model, the upper-level road planner chooses the optimal network design for AV links and congestion pricing while lower-level travelers choose their routes based on their individual travel costs and thereby achieve user equilibrium. We conducted numerical tests on a nine-node network and the results reveal the feasibility of the proposed model and solution method. Our main findings are shown as follows:(1)
Both network design and congestion pricing can alleviate traffic congestion. The integrated optimization of a network design and congestion pricing can achieve better traffic conditions than either a single network design or a congestion pricing.(2)
If we compare the performance outcome of pure congestion pricing with that of a network design, we can see that congestion pricing is effective when AV market penetration is low and a network design is effective when AV penetration is high. As such, the road planner should employ different strategies for different AV market penetrations.(3)
Since network design becomes more effective as OD demand increases, it follows that AV promotion and AV link design may be the best solution for alleviating traffic congestion when traffic demand becomes increasingly large.(4)
In the transitional period characterized by heterogeneous AV and CV travel modes, the NDP with congestion pricing strongly outperforms either network design or congestion pricing alone when both AVs and CVs have fairly large market penetrations. In addition, if we add an appropriate upper bound for congestion pricing, we can reduce public discontent without losing the effectiveness of the NDP with congestion pricing.Based on our proposed model and results, we suggest the consideration of future studies as follows:(1)
We suggest NDP with a tradable credit scheme to alleviate traffic congestion. Although the proposed NDP with congestion pricing can alleviate traffic congestion and an appropriate upper bound for congestion pricing can reduce public discontent without losing its effectiveness, congestion pricing can be viewed as unfair or as a flat tax [38]. If we consider the NDP with a tradable credit scheme, then the problem of unfairness is fully resolved.(2)
Multiclasses of travelers can be considered. We can infer the relationship between the classes of travelers and the perceived value of their travel time, based on the population income distribution. This could be helpful in tackling real-world situations and yield interesting findings.(3)
We suggest optimal design with congestion pricing considering variational AV market penetration. In this paper, we considered AV market penetration to be exogenous. However, AV market penetration can be viewed as an endogenous variable and the evolution of this penetration can be forecast using prediction models, e.g., the diffusion model [13, 39]. Based on this assumption, a time-dependent NDP with congestion pricing could be formulated to alleviate traffic congestion over a long period.(4)
The optimal structure of intermodal transportation network is very important for both passenger traffic and logistics [40]; network design of intermodal transportation network with AVs might be an important research topic in the future.



---

*Source: 3435720-2018-06-27.xml*