# Optimizing Road Networks for Automated Vehicles with Dedicated Links, Dedicated Lanes, and Mixed-Traffic Subnetworks

Authors: Bahman Madadi; Rob Van Nes; Maaike Snelder; Bart Van Arem
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

This study focuses on network configurations to accommodate automated vehicles (AVs) on road networks during the transition period to full automation. The literature suggests that dedicated infrastructure for AVs and enhanced infrastructure for mixed traffic (i.e., AVs on the same lanes with conventional vehicles) are the main alternatives so far. We utilize both alternatives and propose a unified mathematical framework for optimizing road networks for AVs by simultaneous deployment of AV-ready subnetworks for mixed traffic, dedicated AV links, and dedicated AV lanes. We model the problem as a bilevel network design problem where the upper level represents road infrastructure adjustment decisions to deploy these concepts and the lower level includes a network equilibrium model representing the flows as a result of the travelers’ response to new network topologies. An efficient heuristic solution method is introduced to solve the formulated problem and find coherent network topologies. Applicability of the model on real road networks is demonstrated using a large-scale case study of the Amsterdam metropolitan region. Our results indicate that for low AV market penetration rates (MPRs), AV-ready subnetworks, which accommodate AVs in mixed traffic, are the most efficient configuration. However, after 30% MPR, dedicated AV lanes prove to be more beneficial. Additionally, road types can dictate the viable deployment plan for certain parts of road networks. These insights can be used to guide planners in developing their strategies regarding road network infrastructure during the transition period to full automation.


---

## Body

## 1. Introduction

Automated vehicles (AVs) are expected to deliver various benefits to transport systems, including traffic efficiency [1–4]. However, reaching a high market penetration rate (MPR) of fully automated vehicles is a gradual process that can take several decades. Thus, for a long time, a heterogeneous mix of traffic with AVs and regular vehicles (RVs) on the roads will be inevitable. The mixed traffic in this transition period can reduce the traffic efficiency benefits expected to be provided by AVs and even negatively affect traffic flows [5, 6]. This period is referred to in [7] as the “dark age” of AVs.On the other hand, according to [8], the operating design domain (ODD) of highly automated vehicles (i.e., level-4 AVs) is limited. Therefore, these vehicles’ automated driving system (ADS) cannot be used in all roads and all driving conditions. In order for an ADS to operate without failure, it should only be activated within environments in which it can safely function. However, the exact ‏extent of level-4 ODDs is not clear at the moment. Analyses of AV tests in the U.S. indicate that existing AVs are not capable of using their ADS (i.e., operating in autopilot mode) without failure everywhere on regular infrastructure yet [9, 10].In order to extend the ODD of AVs and to amplify their traffic efficiency benefits, various infrastructure-based solutions have been suggested. Carreras et al.. [11] have classified road infrastructure based on the level of support it can provide for AVs and advocated cooperative automated driving enabled by infrastructure support elements such as static and dynamic digital maps, real-time microscopic traffic state data, and vehicle movement information to improve traffic flow performance. Soteropoulos et al.. [12] have proposed an automated drivability index for different roads in the network of Vienna to determine which roads are suitable for level-4 AVs from a technological standpoint. They conclude that deployment of level-4 AVs in streets with low drivability index would only be possible with major infrastructure adjustments. Lu and Blokpoel [13] have advocated intelligent infrastructure to support AVs. Rondinone et al. [14] have discussed vehicle to infrastructure (V2I) communications to support cooperative automated driving. Khoury et al. [15] have investigated the effects of a fully automated vehicle fleet on geometric design of roads. Lu et al. [16] have provided lists of infrastructure requirements for AVs under four future scenarios based on expert opinion. Farah et al. [17] have provided a review of studies indicating physical and digital infrastructure requirements to support AVs.Another potential solution for the transition period is dedicated AV lanes. Razmi et al. [18] identified the operational concepts and functional requirements of dedicated AV lanes. However, it has been shown that with a low percentage of AVs on a link, dedicating one or more lanes to AVs can lead to underutilization of dedicated lanes and a reduction of the overall link throughput [1,2]. Recognizing this, Chen et al. [19] considered the problem from a network perspective and proposed a model for deployment of a network of dedicated AV lanes over time. Conceição et al. [20] studied the reversible road network design problem with AVs. Ye and Wang [21] suggested dedicated AV links (i.e., stretches of roads dedicated to AVs) and congestion pricing for RVs. Then again, this is only suitable when the MPR of AVs is very high. Chen et al. [22] suggested dedicated AV zones; however, this is also relevant for networks with very high MPR of AVs. Moreover, dedicating parts of a network to one class of vehicles can compromise the accessibility of other vehicles and modes.Li et al. [23] proposed utilizing roadside units for V2I communication to overcome the connectivity gap in mixed traffic. This allows AVs to drive closer to their leading vehicles, which can increase link capacity in mixed traffic. Madadi et al. [24] suggested an AV-ready subnetwork where the infrastructure is enhanced to allow efficient use of ADS in mixed traffic. Furthermore, they proposed a model for optimal deployment of AV-ready subnetworks [25] and studied the evolution of these subnetworks over time with a multistage model [26]. The AV-ready subnetwork concept entails selecting a subset of roads that have the potential to meet certain design and quality requirements, upgrading them to meet these standards, and constructing a subnetwork (within the road network) that can facilitate uninterrupted, safe, and efficient operation of AVs in mixed traffic (i.e., on the same lane as RVs). The requirements include machine-readable and uniform lane markings and road signs, high road surface quality, high-definition digital maps, and V2I communication infrastructure [25]. This can ensure safety for all road users and increase link capacity. However, the potential link capacity increase with AVs in mixed traffic can be lower compared to configurations with segregated AV traffic.In conclusion, there seems to be an array of options available for transport planners and road authorities to accommodate AVs on road networks in different stages of the transition period to full automation. In order to make informed decisions, they need to test these solutions on their networks using transport models. However, the existing models for the mentioned design concepts are incompatible with each other. Therefore, exploring different AV network design concepts (e.g., dedicated lanes and mixed traffic subnetworks) requires several models, comparing them is difficult due to different assumptions in each model, and assessing the traffic impacts of their simultaneous deployment is not possible using the existing models. On the other hand, different AV MPRs and different environments (urban, rural, etc.) call for different network configurations. Moreover, the transition from low to high MPR of AVs will require evolution of road network designs to serve the AV demand appropriately. This means the best solution for the transition period might be a combination of different network configurations, which might change over time as well.Therefore, this study proposes a unified formulation for combining AV-ready subnetworks for mixed traffic, dedicated AV links, and dedicated AV lanes. The objective of the formulation is optimizing the costs and benefits of deploying the aforementioned network design concepts using a bilevel modeling framework. The upper level includes network-wide decisions with respect to the links to be selected as part of the AV-ready subnetwork, dedicated AV links, and dedicated AV lanes. The lower level represents a macroscopic network equilibrium model developed to capture the travelers’ route choice and the propagation of traffic throughout the network given a certain network topology for accommodating AVs. In order to solve the problem and find coherent network configurations, a heuristic solution procedure based on an evolutionary algorithm is developed in this study as well. Applicability of the proposed model is demonstrated on a realistic case study of the road network of the Amsterdam metropolitan region. Using extensive numerical experiments on this case study, we discuss important practical issues and considerations related to the deployment of the introduced design concept in real road networks, which are not observed in theoretical networks commonly used in academic studies. This paper further advances the discussion on dedicated infrastructure versus mixed traffic and allows planners to compare and combine different network configurations in order to find the most suitable design for their network based on the level of demand in different stages of the transition period using only one model. To the best of our knowledge, this is the first time such a combination is studied in the literature.The rest of this paper is organized as follows. Section2 presents the methodology, which includes the problem definition, a multiclass network equilibrium model, a combined deployment model of AV-ready subnetworks, dedicated AV links and dedicated AV lanes, and the solution procedure. Section 3 contains a description of a case study of the Amsterdam metropolitan region as well as numerical results and analysis. Finally, Section 4 offers the concluding remarks.


## 2. Model Description

In transport literature, strategic decisions regarding road networks are commonly modeled as bilevel network design problems (NDPs) [27, 28]. Studies that propose optimal network design concepts for AVs have followed this framework as well [19, 21, 25]. Therefore, we model the optimal deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes as a bilevel NDP. The upper level problem investigates where AV-ready links, dedicated AV links, and dedicated AV lanes should be deployed to maximize their societal benefits, while the lower level problem is a multiclass network equilibrium model based on a fixed-point formulation, which captures the travelers’ response to network topologies. In the following sections, the formal problem definition, assumptions, mathematical formulation of the problem, and the solution procedure are presented. For convenience, the notation used throughout this paper is presented in Table 1.Table 1
Notation.
NotationExplanationSetsWSet of origin-destination (OD) pairswRwSet of routesr between origin-destination (OD) pair wMSet of driving modesm∈0,1(0: manual driving (MD), 1: automated driving (AD))KSet of user classesk∈0,1 (0: RV, 1:AV)SSet of subnetworkss∈0,1,2,3(0: regular link, 1: AV-ready subnetwork, 2: dedicated AV link, 3: dedicated AV lane)AsSet of linksa that belongs to the subnetwork sASet of all original linksa in the network; A=A0∪A1∪A2∪A3ParametersμkMultinomial logit route choice parameter for classkγmPCE value of driving in modemηmValue of travel time (VoTT) in modemc¯m,aFixed driving cost of modem on link ata0Free flow travel time on linka (identical for both modes)ΛaOriginal (fixed) capacity of linkaΔasExtra capacity proportion (capacity gain) of subnetworkslaOriginal number of lanes of linkaδr,aw,kAssignment map: 1 if router between OD pair w for class k includes link a, 0 otherwiseDw,kDemand of classk and OD pair wσParameter converting peak hour travel cost to a yearly basisκasAdjustment cost of linka for subnetwork sπDiscount ratetLength of the planning horizonVariablesCrw,k(Route-based) travel cost of router between OD pair w for class kFrw,k(Route-based) flow of router between OD pair w for class kcm,a(Link-based) travel cost of modem on link afm,ak(Link-based) flow of classk in mode m on link aqm,aTotal flow (PCE-equivalent) in modem on link atm,aLink travel time in modem on link aΛm,aCapacity of linka for mode mTTCTotal system travel costTTTTotal system travel timeTTDTotal system travel distanceTACTotal adjustment costXaBinary variable: 1 if linka is upgraded for the AV-ready subnetwork (s=1), 0 otherwiseYaBinary variable: 1 if linka is turned to a dedicated AV link (s=2), 0 otherwiseZaBinary variable: 1 if a dedicated AV lane is included in linka (s=3), 0 otherwiseIaInteger variable: number of dedicated AV lanes on linka; Ia≤la−1


### 2.1. Problem Definition and Assumptions

Consider a road network represented by a directed graphGN,A whereNis the set of nodes andAis the set of directed arcs (links). There is at least one path (route) within the graph G that connects each origin-destination (OD) pair w. The set of links A1 represents the AV-ready subnetwork, the set of links A2 represents the subnetwork composed of dedicated AV links, and the set of links A3 represents the subnetwork with dedicated AV lanes. Binary variables Xa,Ya,Za∈0,1 denote these decisions (i.e., Xa=1;∀a∈A1,Ya=1;∀a∈A2,Za=1;∀a∈A3). The number of dedicated AV lanes on link a is denoted by Ia. Each link can only be selected for one subnetwork (i.e., Xa+Ya+Za≤1;∀a∈A). The remaining links in the network are represented by A0(i.e., Xa,Ya,Za,Ia=0;∀a∈A0). The set A1=A1∪A2∪A3 represents the set of links designated to ADSs to form a (weakly) connected graph G1N1,A1, which will be referred to as automated driving (AD) subnetwork throughout this article. Within G1, AVs activate their ADS, and outside of it, they drive manually. RVs are not allowed on dedicated AV links and lanes, but they are allowed on AV-ready links because these links are designated to mixed traffic. It is essential to notice this distinction between AV-ready links designated to mixed traffic and links as well as lanes dedicated to AVs. On links where a dedicated lane is available, the use of that lane is assumed mandatory for AVs. The set of AD links represented by A1 will be upgraded with roadside units and digital maps as well as clear and harmonized road signs and markings. This ensures safe operation of ADS within an extended ODD and allows AVs to keep shorter driving gaps while using their ADS, which improves traffic efficiency.


### 2.2. Multiclass Network Equilibrium Model with AV-Ready Subnetworks, Dedicated AV Links, and Dedicated AV Lanes

Two classes of vehicles, namely, RVs (class 0) and AVs (class 1), are considered here, as well as two driving modes, namely, manual driving (MD) denoted as mode 0 and AD denoted as mode 1. Using modes and classes is necessary since the class AV has both MD mode and AD mode available. RVs always drive in MD mode. AVs use the mode AD withinG1 and the mode MD within G0. The travelers’ route choice is captured via a multiuser class (MUC) stochastic user equilibrium (SUE), which is assumed to follow a multinomial logit model. Since one of the main impacts of the network configurations studied in this paper is changes in link travel time, this is explicitly discussed in the next subsection. Then, the mathematical formulation and the equilibrium conditions are presented in the following parts.


#### 2.2.1. Link Travel Time

The deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes affects link travel times. The most common approach to derive the travel time function of links with AVs in mixed traffic for macroscopic static traffic assignment models is considering shorter driving gaps for AVs [25, 29–31]. In this approach, the Bureau of Public Roads (BPR) travel time function is used along with a total link flow equivalent based on passenger car equivalent (PCE) values, which is the sum of class flows (RVs and AVs) multiplied by a scaling parameter (i.e., the PCE value) representing their driving time headways. Since the extent of the capacity increase due to the efficiency of AVs in mixed traffic depends on the proportion of RVs and AVs on each link, this PCE-based approach is appropriate for mixed traffic. It accounts for the proportion of AVs on each link and assumes shorter driving gaps between AVs and their leading vehicles. We elaborate on this in the following section.Regarding dedicated links and lanes, the assumption of increased capacity has been the prevailing method. Ye and Wang [21] assumed the capacity of a dedicated AV link to be triple the capacity of the regular link before conversion. Chen et al. [19] assumed the capacity of a dedicated AV lane to be 2.5 times the per-lane capacity of a regular link.Both aforementioned approaches are utilized to derive the network equilibrium model presented below.


#### 2.2.2. Mathematical Formulation of the Network Equilibrium Model

In order to represent new network topologies includingG1N1,A1 in mathematical terms, each link is virtually divided into two links, one per each mode of driving (mode 0 represents MD and mode 1 represents AD). Note that this does not change the actual performance of the network. On a link where a dedicated AV lane is present, Λ0,a represents the capacity of the regular part of the link with mode 0 and Λ1,a represents the capacity of the dedicated part of the link for mode 1. f0,a0 represents the flow of RVs (class 0) in MD mode (mode 0) on the regular part of the link, and f1,a1 represents the flow of AVs (class 1) in mode AD (mode 1) on the dedicated part of the link. The same holds for dedicated AV links, but since RVs are not allowed in dedicated AV links, the capacity of these links for mode MD is set to 0, thereby excluding this part of the link from the network. For AV-ready links, the capacity for both parts of the link is the same since in this case, the systematic split between the two driving modes is artificial, and both driving modes should have the same travel time. However, while calculating the total flow, the flow of AVs on these links is multiplied by a lower PCE value to represent their shorter driving gap. Therefore, the flows on both parts of these links are aggregated in order to compute the travel time on these links. On regular links that do not belong to the AD subnetwork, the capacity for AD mode is set to 0 and both classes will have their flows only in MD mode since it is the only mode allowed on these links. This is demonstrated in Figure 1 for a simple 4-link network including a regular link, an AV-ready link, a dedicated AV link, and a link with a dedicated AV lane.Figure 1
Summary of capacities and flows applied for each mode and class on each link type (links shown with red have a zero capacity, i.e., they are excluded from the traffic assignment).The following equations operationalize this concept in mathematical notations and represent the behavioral rules considered in our network equilibrium model (NEM) for any realization ofXa,Ya,Za,andIa given Xa+Ya+Za≤1,∀a∈A.The capacity of linka for mode m is defined as(1)Λ0,a=Λa−YaΛa−ZaΛalaIa+ε,∀a∈A,(2)Λ1,a=XaΔ1Λa+YaΔ2Λa+ZaΔ3ΛalaIa+ε,∀a∈A,where (1) defines link capacities for mode 0 based on whether the link is assigned to G1 or not. When Ya=1 (i.e., the link is selected as a dedicated AV link), the capacity for mode MD becomes 0. When Za=1 (i.e., one or more lanes of the link are dedicated to AVs), based on the number of selected lanes, a proportion of the link capacity will be subtracted from the link capacity for MD mode. In order to avoid undefined numbers in calculations when a capacity is set to 0, a very small value (ε) is added to all capacities. Note that this will force inadmissible flows to be practically 0. (2) defines capacities for mode AD based on the type of subnetwork to which links belong. This is similar to (1) with the addition of multiplying capacities by Δs to increase them based on the subnetwork type. The value of Δ1 is set to 1 to neutralize it, but this parameter is included in the model for consistency. The capacity effects of deploying AV-ready links is captured using a PCE-based approach to calculate the total flow, which is sensitive to the proportion of AVs on each link, making it a more suitable approach for modeling mixed traffic. A sensitivity analysis is provided in Section 3.2.6 to show the effects of using different values for these parameters. The flow and travel time of mode m on link a are defined as(3)qm,a=1−Xa∑k∈Kfm,ak+Xa∑k∈K∑j∈Mγjfj,ak,∀a∈A,∀m∈M,(4)tm,a=ta01+αaqm,aΛm,aba,∀a∈A,∀m∈M,where (3) shows how the PCE-equivalent of link flows is calculated to be used in the link travel time function for each mode. When Xa=1 (i.e., the link becomes an AV-ready link), the total flow is a summation of AV flows in AD mode multiplied by PCE value of the AD mode (which is lower than 1 to represent shorter driving gaps in AD mode) and RV flows in MD mode multiplied by the PCE value of MD mode (which is 1). In this case, both parts of the link will have the same total flow, thereby the same travel time. When Xa=0 (i.e., the link is not an AV-ready link), the total flow is a simple summation of flows of both classes; however, this leads to different total flows for each mode on each link type. On regular links, both classes only have nonzero flows in MD mode, so the total flow for MD mode will be the summation of class flows and the total flow in AD mode will be 0. On dedicated AV links, the only nonzero flow is the flow of AVs in AD mode. On links with dedicated AV lanes, RVs will have a nonzero flow in MD mode and AVs will have a nonzero flow in AD mode. This leads to the intended total flow on each link type for each mode. (4) shows how link travel time for each mode is calculated using the BPR function. Note that different combinations of capacities and total flows based on the subnetwork type and driving mode will be applied in (4), which results in different travel times for MD and AD modes on dedicated AV lanes and links but identical travel times for both modes in regular links and AV-ready links. Figure 1 summarizes the capacities and flows applied for each mode and class on each link type. For computational reasons, infeasible modes (e.g., flow of RVs in MD mode on dedicated links to AVs) are modeled with very large travel times via very small capacity values applied in (1) and (2).Link travel cost for each mode on each link is calculated as(5)cm,a=c¯m,a+ηmtm,a,∀a∈A,∀m∈M,where link travel cost is based on the link travel time for each mode multiplied by the value of travel time (VoTT) of that mode along with the fixed driving cost of the link in that mode. VoTT and fixed driving costs are assumed to be lower for AD mode since drivers can perform other activities in the car while ADS performs the driving task [32].The correspondence between link flows and route flows is ensured using a link-route incidence matrix (assignment map) for each class as follows:(6)∑w∈W∑r∈RwFrw,0δr,aw,0=f0,a0,∀a∈A,(7)∑w∈W∑r∈RwFrw,1δr,aw,1=f1,a1Xa+Ya+Za+f0,a11−Xa+Ya+Za,∀a∈A,where (6) and (7) ensure that the route flow of each class is assigned to the appropriate mode on each link based on the subnetwork type. On regular links (MD network), AV route flow is assigned to MD mode, and on the rest of the links (AD subnetwork), it is assigned to AD mode. The following equations carry out the same task for the correspondence between link and route costs.(8)∑w∈W∑r∈RwCrw,0δr,aw,0=c0,a,∀a∈A,(9)∑w∈W∑r∈RwCrw,1δr,aw,1=c1,aXa+Ya+Za+c0,a1−Xa+Ya+Za,∀a∈A.Finally, (10) guarantees the travel demand in each class for each OD pair is satisfied by equating the sum of all route flows for each OD pair and each class to their relevant demand, and (11) prohibits negative flows.(10)∑r∈RwFrw,k=Dw,k,∀w∈W,∀k∈K,(11)Frw,k≥0,∀w∈W,∀k∈K,∀r∈Rw.Equilibrium Conditions. The equilibrium condition of the NEM based upon Brouwer’s fixed-point theorem [33–35] is to find an F∗ that solves(12)F−PFD=0,∀F=Frw,k∈Π,where F is the vector of route flow Frw,k. The set Π represents the set of flows Frw,k that satisfy (1)–(11), i.e., Π=Frw,k|1−11 defines the feasible region of the NEM. Vector D is the vector of travel demand Dw,k, and P is the vector of route choice probability Pr|w,k that represents the proportion of the travelers of class k between OD pair w who take the route r. Solving (12) yields Pr|w,k∗=Fr∗w,k/Dw,k, which for the case of the multiclass multinomial logit SUE leads to the following well-known route choice probabilities [36]:(13)Fr∗w,kDw,k=Pr|w,k∗=expμkCr∗w,k∑r∈RwexpμkCr∗w,k,∀w∈W,∀k∈K.


### 2.3. Deployment of AV-Ready Subnetwork, Dedicated AV Links, and Dedicated AV Lanes

The optimal deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes (the upper level problem) investigates where AV-ready links, dedicated AV links, and dedicated AV lanes should be deployed to maximize their societal benefits. The upper level decision variables are as follows.Xa is a binary decision variable taking the value 1 when link a is selected as an AV-ready link. Ya is a binary decision variable taking the value of 1 when link a is selected as a dedicated AV link. Ia is an integer decision variable denoting the number of dedicated AV lanes on link a. Za is an auxiliary binary variable taking the value of 1 when link a contains one or more dedicated AV lanes. Mathematical formulation of the upper level problem is given below.(14)MinXa,Ya,IaZU=∑tσTTC1+πt+TAC,s.t.1−12,(15)TTC=∑k∈K∑w∈W∑r∈RwFrw,kCrw,k,(16)TAC=∑a∈AXaκa1+Yaκa2+ZaIaκa3,(17)Ia≤la−1,∀a∈A,(18)Xa+Ya+Za≤1,∀a∈A,(19)1−ZaIa=0,∀a∈A,(20)Za≤Ia,∀a∈A,(21)pG1N1,A1n,n′≥1,∀n,n′∈N1,(22)Xa,Ya,Za∈0,1,Ia∈Z≥0,∀a∈A.In this formulation, (14) represents the objective function (OF), which minimizes the sum of total adjustment cost (TAC) and the net present value of the total travel cost (TTC), given the entire planning horizon. One morning peak hour is considered in this study, and TTC of this period is converted to a yearly basis with a parameter σ. This yearly value is discounted with a discount rate of π for t years, which is the useful lifetime of the infrastructure adjustments. The effects of the construction period itself are not considered here. The first set of constraints for the upper level problem is the lower level problem defined by (1)–(12), which means the upper level should be evaluated when the lower level is at equilibrium. (15) shows how TTC is calculated based on equilibrium flows and costs obtained from the lower level problem. TAC in (16) is the summation of link adjustment costs for all subnetworks. (17) ensures the number of dedicated AV lanes is less than the number of lanes on each link. (18) guarantees each link can be selected only for one subnetwork. (18)–(20) force Za to take the value of 1 when Ia is greater than 0, and 0 otherwise. (22) denotes admissible values for the upper level decision variables. Finally, (21) expresses a connectivity constraint, imposed in order to find coherent networks. It signifies that for two nodes n and n′ within the graph G1N1,A1 where the AD mode is allowed, there must exist at least one undirected path connecting the two nodes. The purpose of this constraint is preventing the solution method from finding networks with disconnected components. Since the AD mode is only allowed within G1, having networks with separate components (i.e., disconnected networks) leads to switching frequently between MD and AD mode, which is best to be avoided. This imposes extra requirements on the solution method, which are discussed below.


### 2.4. Solution Methods

Regarding the lower level problem, Daganzo [35] has shown the existence and uniqueness of a solution for the fixed-point formulation of the multimode multiclass SUE problem with asymmetric link costs in terms of the PCE-equivalent of flows. This holds when the feasible region of a NEM is compact and convex, and all the functions are continuous, which is the case for the NEM-FP defined by (1)–(12). There are numerous solution methods available for solving FP problems. For a review, the reader is referred to [34, 37]. In this study, we use an efficient sequential linear approximation algorithm with step sizes according to the method of successive averages (MSA) introduced in [38] to solve the lower level equilibrium problem.The upper level problem on the other hand is more challenging to solve. Bilevel NDPs with discrete upper level decision variables and multiclass SUE lower level problems are among the most challenging problems in transport literature and are often solved using heuristic procedures [27, 28]. Solving such problems, particularly for large-scale networks, calls for efficient solution procedures. Moreover, the connectivity requirement denoted by constraint (21) makes the problem even more difficult to solve, since existing methods for solving NDPs do not produce connected graphs. Therefore, we have developed a heuristic solution procedure based on an evolutionary algorithm in this study to solve the upper level problem. However, before introducing the solution procedure, we provide five definitions that are necessary in order to comprehend how the solution method operates and deals with the connectivity constraint. These definitions are illustrated ‏in Figure 2.‏Figure 2
An example AD subnetwork. Nodes 3-7-9-10-11 are boundary nodes, links (5,9)-(6,10)-(7,11) are inner boundary links, and links (9,13)-(10-14)-(11,15)-(11,12)-(7,8)-(3-4)-(9,10)-(10,11) are outer boundary links.Definition 1.
Any noden incident to at least one link included in an AD subnetwork represented by G1N1,A1 is included in that AD subnetwork (i.e., n∈N1).Definition 2.
The degree of a node belonging to each graph (e.g.,G,G0,G1) is the number of links incident to that node within the graph in which that node is included.Definition 3.
A boundary noden∗∈N1 for an AD subnetwork represented by a directed graph G1N1,A1 is a node included in G1with a degree less than the degree of the corresponding node n in the underlying graph GN,A (i.e., the graph representing the original road network).Definition 4.
An outer boundary linka∗∈A0 for an AD subnetwork is a link incident to a boundary node n∗∈N1 of the AD subnetwork but not included in the graph G1 representing the AD subnetwork.Definition 5.
An inner boundary linka∗∈A1 for an AD subnetwork is a link included in the graph G1 representing the AD subnetwork and incident only to boundary nodes with the degree of 1.
Note that the boundary nodes of an AD subnetwork and the inner boundary links are included in the subnetwork while the corresponding outer boundary links are not included in that subnetwork.


#### 2.4.1. Evolutionary Heuristic Solution Procedure

The evolutionary heuristic solution introduced here is inspired by evolutionary metaheuristics and takes advantage of this specific problem’s structure to efficiently generate connected subnetworks and solve the problem. Using extensive computational experiments, it is shown in [25] that an evolutionary local search algorithm tailored to the problem can efficiently find coherent and connected AV-ready subnetworks. Therefore, in this study, we develop another evolutionary algorithm that modifies and extends the procedure of the mentioned algorithm to find coherent subnetworks including AV-ready links, dedicated AV links, and dedicated AV lanes in an efficient manner.The purpose of the solution procedure is to determine the values ofXa,Ya,Za,andIa (which uniquely define a graph G1N1,A1) in order to minimize (14) and satisfy constraints (15)–(22). Since every AD subnetwork represented by G1N1,A1 is built from scratch, we can start with a simple connected graph as an initial feasible solution and iteratively modify this graph to improve the value of the OF in (14) using operations that preserve the connectivity requirement of constraint (21) until no further improvement can be obtained by modifying the graph. To avoid termination of the procedure in local minima, a population of solutions is evolved through several generations to acquire a good solution at the end. The steps of the solution procedure are summarized in Table 2. This is followed by the description of the operations used in the procedure.Table 2
Solution procedure.
Solution steps1Initialize population2Measure fitness of all individuals3For each generation j4Assign an operation to each individuali based on parameters (possible operations are extension, reduction, and merging)5For each individual i6Perform the operation assigned to the individuali7Measure fitness of the individuali8End9Perform regeneration10Increment generation number11If stopping criteria met: terminate12End


#### 2.4.2. Evolutionary Heuristic Operations

(1) Initialization. During the initialization process, a population of individual solutions is generated. Each individual solution includes one link selected via a roulette wheel prioritizing links with higher capacity. A subnetwork type s is randomly assigned to each link. With the addition of each link, the nodes incident to that link are added to the graph G1 as well. Note that any graph including one link and its incident nodes satisfies constraint (21). This process will provide a pool of diverse and connected solutions to start the algorithm. The size of the population is an algorithm parameter.(2) Fitness Evaluation. Fitness evaluation is based on the value of the upper level of (ZU) in (14). This value is obtained by assigning a value to each (upper level) decision variable and solving the lower level problem (NEM-FP).(3) Extension Operation. In this operation, first a subnetwork s is randomly selected for extension (e.g., dedicated AV link). Next, the outer boundary links of the graph (i.e., the set of links a∗∈A0) are specified (see Definition 4). Then, a sample of them is selected based on a roulette wheel prioritizing higher capacities and added to the graph. When the subnetwork type is dedicated AV lanes (i.e., s=3), the number of lanes Ia is assigned at random. All nodes incident to any link added to G1 are added to it as well. The sample size is an algorithm parameter. When the input of this operation meets constraint (21), the output is guaranteed to meet this constraint as well.(4) Reduction Operation. In this operation, first the inner boundary links of the graph (i.e., the set of links a∗∈A1) are determined (see Definition 5). Then, a sample of them is selected based on a roulette wheel prioritizing links with lower capacity and removed from the graph. The corresponding nodes that are not incident to any other link in G1 are eliminated as well. This sample size is also an algorithm parameter. This operation preserves the connectivity constraint (21) as well, since it only removes links from the boundaries of a graph.(5) Merging Operation. Unlike extension and reduction operations, which require an individual solution, the merging operation first selects a merging partner from among the population based on a roulette wheel prioritizing the fitness value. Then, the merged graph is the union of the links and nodes in both graphs (merging parents) with their subnetwork type s unchanged. When there is a conflict (e.g., a link is included in both graphs and is a dedicated AV link in one graph but an AV-ready link in the other), it is resolved by inheriting from the fitter parent. That is, the values of Xa,Ya,Za,andIa for a conflicting link a in a merging offspring are equal to those values of the merging parent with better fitness value.(6) Regeneration. At the end of each generation, the fittest individuals among the parents (from the previous generation) and the offspring (resulting from the operations in the current generation) survive to repopulate the next generation.


## 2.1. Problem Definition and Assumptions

Consider a road network represented by a directed graphGN,A whereNis the set of nodes andAis the set of directed arcs (links). There is at least one path (route) within the graph G that connects each origin-destination (OD) pair w. The set of links A1 represents the AV-ready subnetwork, the set of links A2 represents the subnetwork composed of dedicated AV links, and the set of links A3 represents the subnetwork with dedicated AV lanes. Binary variables Xa,Ya,Za∈0,1 denote these decisions (i.e., Xa=1;∀a∈A1,Ya=1;∀a∈A2,Za=1;∀a∈A3). The number of dedicated AV lanes on link a is denoted by Ia. Each link can only be selected for one subnetwork (i.e., Xa+Ya+Za≤1;∀a∈A). The remaining links in the network are represented by A0(i.e., Xa,Ya,Za,Ia=0;∀a∈A0). The set A1=A1∪A2∪A3 represents the set of links designated to ADSs to form a (weakly) connected graph G1N1,A1, which will be referred to as automated driving (AD) subnetwork throughout this article. Within G1, AVs activate their ADS, and outside of it, they drive manually. RVs are not allowed on dedicated AV links and lanes, but they are allowed on AV-ready links because these links are designated to mixed traffic. It is essential to notice this distinction between AV-ready links designated to mixed traffic and links as well as lanes dedicated to AVs. On links where a dedicated lane is available, the use of that lane is assumed mandatory for AVs. The set of AD links represented by A1 will be upgraded with roadside units and digital maps as well as clear and harmonized road signs and markings. This ensures safe operation of ADS within an extended ODD and allows AVs to keep shorter driving gaps while using their ADS, which improves traffic efficiency.


## 2.2. Multiclass Network Equilibrium Model with AV-Ready Subnetworks, Dedicated AV Links, and Dedicated AV Lanes

Two classes of vehicles, namely, RVs (class 0) and AVs (class 1), are considered here, as well as two driving modes, namely, manual driving (MD) denoted as mode 0 and AD denoted as mode 1. Using modes and classes is necessary since the class AV has both MD mode and AD mode available. RVs always drive in MD mode. AVs use the mode AD withinG1 and the mode MD within G0. The travelers’ route choice is captured via a multiuser class (MUC) stochastic user equilibrium (SUE), which is assumed to follow a multinomial logit model. Since one of the main impacts of the network configurations studied in this paper is changes in link travel time, this is explicitly discussed in the next subsection. Then, the mathematical formulation and the equilibrium conditions are presented in the following parts.


### 2.2.1. Link Travel Time

The deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes affects link travel times. The most common approach to derive the travel time function of links with AVs in mixed traffic for macroscopic static traffic assignment models is considering shorter driving gaps for AVs [25, 29–31]. In this approach, the Bureau of Public Roads (BPR) travel time function is used along with a total link flow equivalent based on passenger car equivalent (PCE) values, which is the sum of class flows (RVs and AVs) multiplied by a scaling parameter (i.e., the PCE value) representing their driving time headways. Since the extent of the capacity increase due to the efficiency of AVs in mixed traffic depends on the proportion of RVs and AVs on each link, this PCE-based approach is appropriate for mixed traffic. It accounts for the proportion of AVs on each link and assumes shorter driving gaps between AVs and their leading vehicles. We elaborate on this in the following section.Regarding dedicated links and lanes, the assumption of increased capacity has been the prevailing method. Ye and Wang [21] assumed the capacity of a dedicated AV link to be triple the capacity of the regular link before conversion. Chen et al. [19] assumed the capacity of a dedicated AV lane to be 2.5 times the per-lane capacity of a regular link.Both aforementioned approaches are utilized to derive the network equilibrium model presented below.


### 2.2.2. Mathematical Formulation of the Network Equilibrium Model

In order to represent new network topologies includingG1N1,A1 in mathematical terms, each link is virtually divided into two links, one per each mode of driving (mode 0 represents MD and mode 1 represents AD). Note that this does not change the actual performance of the network. On a link where a dedicated AV lane is present, Λ0,a represents the capacity of the regular part of the link with mode 0 and Λ1,a represents the capacity of the dedicated part of the link for mode 1. f0,a0 represents the flow of RVs (class 0) in MD mode (mode 0) on the regular part of the link, and f1,a1 represents the flow of AVs (class 1) in mode AD (mode 1) on the dedicated part of the link. The same holds for dedicated AV links, but since RVs are not allowed in dedicated AV links, the capacity of these links for mode MD is set to 0, thereby excluding this part of the link from the network. For AV-ready links, the capacity for both parts of the link is the same since in this case, the systematic split between the two driving modes is artificial, and both driving modes should have the same travel time. However, while calculating the total flow, the flow of AVs on these links is multiplied by a lower PCE value to represent their shorter driving gap. Therefore, the flows on both parts of these links are aggregated in order to compute the travel time on these links. On regular links that do not belong to the AD subnetwork, the capacity for AD mode is set to 0 and both classes will have their flows only in MD mode since it is the only mode allowed on these links. This is demonstrated in Figure 1 for a simple 4-link network including a regular link, an AV-ready link, a dedicated AV link, and a link with a dedicated AV lane.Figure 1
Summary of capacities and flows applied for each mode and class on each link type (links shown with red have a zero capacity, i.e., they are excluded from the traffic assignment).The following equations operationalize this concept in mathematical notations and represent the behavioral rules considered in our network equilibrium model (NEM) for any realization ofXa,Ya,Za,andIa given Xa+Ya+Za≤1,∀a∈A.The capacity of linka for mode m is defined as(1)Λ0,a=Λa−YaΛa−ZaΛalaIa+ε,∀a∈A,(2)Λ1,a=XaΔ1Λa+YaΔ2Λa+ZaΔ3ΛalaIa+ε,∀a∈A,where (1) defines link capacities for mode 0 based on whether the link is assigned to G1 or not. When Ya=1 (i.e., the link is selected as a dedicated AV link), the capacity for mode MD becomes 0. When Za=1 (i.e., one or more lanes of the link are dedicated to AVs), based on the number of selected lanes, a proportion of the link capacity will be subtracted from the link capacity for MD mode. In order to avoid undefined numbers in calculations when a capacity is set to 0, a very small value (ε) is added to all capacities. Note that this will force inadmissible flows to be practically 0. (2) defines capacities for mode AD based on the type of subnetwork to which links belong. This is similar to (1) with the addition of multiplying capacities by Δs to increase them based on the subnetwork type. The value of Δ1 is set to 1 to neutralize it, but this parameter is included in the model for consistency. The capacity effects of deploying AV-ready links is captured using a PCE-based approach to calculate the total flow, which is sensitive to the proportion of AVs on each link, making it a more suitable approach for modeling mixed traffic. A sensitivity analysis is provided in Section 3.2.6 to show the effects of using different values for these parameters. The flow and travel time of mode m on link a are defined as(3)qm,a=1−Xa∑k∈Kfm,ak+Xa∑k∈K∑j∈Mγjfj,ak,∀a∈A,∀m∈M,(4)tm,a=ta01+αaqm,aΛm,aba,∀a∈A,∀m∈M,where (3) shows how the PCE-equivalent of link flows is calculated to be used in the link travel time function for each mode. When Xa=1 (i.e., the link becomes an AV-ready link), the total flow is a summation of AV flows in AD mode multiplied by PCE value of the AD mode (which is lower than 1 to represent shorter driving gaps in AD mode) and RV flows in MD mode multiplied by the PCE value of MD mode (which is 1). In this case, both parts of the link will have the same total flow, thereby the same travel time. When Xa=0 (i.e., the link is not an AV-ready link), the total flow is a simple summation of flows of both classes; however, this leads to different total flows for each mode on each link type. On regular links, both classes only have nonzero flows in MD mode, so the total flow for MD mode will be the summation of class flows and the total flow in AD mode will be 0. On dedicated AV links, the only nonzero flow is the flow of AVs in AD mode. On links with dedicated AV lanes, RVs will have a nonzero flow in MD mode and AVs will have a nonzero flow in AD mode. This leads to the intended total flow on each link type for each mode. (4) shows how link travel time for each mode is calculated using the BPR function. Note that different combinations of capacities and total flows based on the subnetwork type and driving mode will be applied in (4), which results in different travel times for MD and AD modes on dedicated AV lanes and links but identical travel times for both modes in regular links and AV-ready links. Figure 1 summarizes the capacities and flows applied for each mode and class on each link type. For computational reasons, infeasible modes (e.g., flow of RVs in MD mode on dedicated links to AVs) are modeled with very large travel times via very small capacity values applied in (1) and (2).Link travel cost for each mode on each link is calculated as(5)cm,a=c¯m,a+ηmtm,a,∀a∈A,∀m∈M,where link travel cost is based on the link travel time for each mode multiplied by the value of travel time (VoTT) of that mode along with the fixed driving cost of the link in that mode. VoTT and fixed driving costs are assumed to be lower for AD mode since drivers can perform other activities in the car while ADS performs the driving task [32].The correspondence between link flows and route flows is ensured using a link-route incidence matrix (assignment map) for each class as follows:(6)∑w∈W∑r∈RwFrw,0δr,aw,0=f0,a0,∀a∈A,(7)∑w∈W∑r∈RwFrw,1δr,aw,1=f1,a1Xa+Ya+Za+f0,a11−Xa+Ya+Za,∀a∈A,where (6) and (7) ensure that the route flow of each class is assigned to the appropriate mode on each link based on the subnetwork type. On regular links (MD network), AV route flow is assigned to MD mode, and on the rest of the links (AD subnetwork), it is assigned to AD mode. The following equations carry out the same task for the correspondence between link and route costs.(8)∑w∈W∑r∈RwCrw,0δr,aw,0=c0,a,∀a∈A,(9)∑w∈W∑r∈RwCrw,1δr,aw,1=c1,aXa+Ya+Za+c0,a1−Xa+Ya+Za,∀a∈A.Finally, (10) guarantees the travel demand in each class for each OD pair is satisfied by equating the sum of all route flows for each OD pair and each class to their relevant demand, and (11) prohibits negative flows.(10)∑r∈RwFrw,k=Dw,k,∀w∈W,∀k∈K,(11)Frw,k≥0,∀w∈W,∀k∈K,∀r∈Rw.Equilibrium Conditions. The equilibrium condition of the NEM based upon Brouwer’s fixed-point theorem [33–35] is to find an F∗ that solves(12)F−PFD=0,∀F=Frw,k∈Π,where F is the vector of route flow Frw,k. The set Π represents the set of flows Frw,k that satisfy (1)–(11), i.e., Π=Frw,k|1−11 defines the feasible region of the NEM. Vector D is the vector of travel demand Dw,k, and P is the vector of route choice probability Pr|w,k that represents the proportion of the travelers of class k between OD pair w who take the route r. Solving (12) yields Pr|w,k∗=Fr∗w,k/Dw,k, which for the case of the multiclass multinomial logit SUE leads to the following well-known route choice probabilities [36]:(13)Fr∗w,kDw,k=Pr|w,k∗=expμkCr∗w,k∑r∈RwexpμkCr∗w,k,∀w∈W,∀k∈K.


## 2.2.1. Link Travel Time

The deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes affects link travel times. The most common approach to derive the travel time function of links with AVs in mixed traffic for macroscopic static traffic assignment models is considering shorter driving gaps for AVs [25, 29–31]. In this approach, the Bureau of Public Roads (BPR) travel time function is used along with a total link flow equivalent based on passenger car equivalent (PCE) values, which is the sum of class flows (RVs and AVs) multiplied by a scaling parameter (i.e., the PCE value) representing their driving time headways. Since the extent of the capacity increase due to the efficiency of AVs in mixed traffic depends on the proportion of RVs and AVs on each link, this PCE-based approach is appropriate for mixed traffic. It accounts for the proportion of AVs on each link and assumes shorter driving gaps between AVs and their leading vehicles. We elaborate on this in the following section.Regarding dedicated links and lanes, the assumption of increased capacity has been the prevailing method. Ye and Wang [21] assumed the capacity of a dedicated AV link to be triple the capacity of the regular link before conversion. Chen et al. [19] assumed the capacity of a dedicated AV lane to be 2.5 times the per-lane capacity of a regular link.Both aforementioned approaches are utilized to derive the network equilibrium model presented below.


## 2.2.2. Mathematical Formulation of the Network Equilibrium Model

In order to represent new network topologies includingG1N1,A1 in mathematical terms, each link is virtually divided into two links, one per each mode of driving (mode 0 represents MD and mode 1 represents AD). Note that this does not change the actual performance of the network. On a link where a dedicated AV lane is present, Λ0,a represents the capacity of the regular part of the link with mode 0 and Λ1,a represents the capacity of the dedicated part of the link for mode 1. f0,a0 represents the flow of RVs (class 0) in MD mode (mode 0) on the regular part of the link, and f1,a1 represents the flow of AVs (class 1) in mode AD (mode 1) on the dedicated part of the link. The same holds for dedicated AV links, but since RVs are not allowed in dedicated AV links, the capacity of these links for mode MD is set to 0, thereby excluding this part of the link from the network. For AV-ready links, the capacity for both parts of the link is the same since in this case, the systematic split between the two driving modes is artificial, and both driving modes should have the same travel time. However, while calculating the total flow, the flow of AVs on these links is multiplied by a lower PCE value to represent their shorter driving gap. Therefore, the flows on both parts of these links are aggregated in order to compute the travel time on these links. On regular links that do not belong to the AD subnetwork, the capacity for AD mode is set to 0 and both classes will have their flows only in MD mode since it is the only mode allowed on these links. This is demonstrated in Figure 1 for a simple 4-link network including a regular link, an AV-ready link, a dedicated AV link, and a link with a dedicated AV lane.Figure 1
Summary of capacities and flows applied for each mode and class on each link type (links shown with red have a zero capacity, i.e., they are excluded from the traffic assignment).The following equations operationalize this concept in mathematical notations and represent the behavioral rules considered in our network equilibrium model (NEM) for any realization ofXa,Ya,Za,andIa given Xa+Ya+Za≤1,∀a∈A.The capacity of linka for mode m is defined as(1)Λ0,a=Λa−YaΛa−ZaΛalaIa+ε,∀a∈A,(2)Λ1,a=XaΔ1Λa+YaΔ2Λa+ZaΔ3ΛalaIa+ε,∀a∈A,where (1) defines link capacities for mode 0 based on whether the link is assigned to G1 or not. When Ya=1 (i.e., the link is selected as a dedicated AV link), the capacity for mode MD becomes 0. When Za=1 (i.e., one or more lanes of the link are dedicated to AVs), based on the number of selected lanes, a proportion of the link capacity will be subtracted from the link capacity for MD mode. In order to avoid undefined numbers in calculations when a capacity is set to 0, a very small value (ε) is added to all capacities. Note that this will force inadmissible flows to be practically 0. (2) defines capacities for mode AD based on the type of subnetwork to which links belong. This is similar to (1) with the addition of multiplying capacities by Δs to increase them based on the subnetwork type. The value of Δ1 is set to 1 to neutralize it, but this parameter is included in the model for consistency. The capacity effects of deploying AV-ready links is captured using a PCE-based approach to calculate the total flow, which is sensitive to the proportion of AVs on each link, making it a more suitable approach for modeling mixed traffic. A sensitivity analysis is provided in Section 3.2.6 to show the effects of using different values for these parameters. The flow and travel time of mode m on link a are defined as(3)qm,a=1−Xa∑k∈Kfm,ak+Xa∑k∈K∑j∈Mγjfj,ak,∀a∈A,∀m∈M,(4)tm,a=ta01+αaqm,aΛm,aba,∀a∈A,∀m∈M,where (3) shows how the PCE-equivalent of link flows is calculated to be used in the link travel time function for each mode. When Xa=1 (i.e., the link becomes an AV-ready link), the total flow is a summation of AV flows in AD mode multiplied by PCE value of the AD mode (which is lower than 1 to represent shorter driving gaps in AD mode) and RV flows in MD mode multiplied by the PCE value of MD mode (which is 1). In this case, both parts of the link will have the same total flow, thereby the same travel time. When Xa=0 (i.e., the link is not an AV-ready link), the total flow is a simple summation of flows of both classes; however, this leads to different total flows for each mode on each link type. On regular links, both classes only have nonzero flows in MD mode, so the total flow for MD mode will be the summation of class flows and the total flow in AD mode will be 0. On dedicated AV links, the only nonzero flow is the flow of AVs in AD mode. On links with dedicated AV lanes, RVs will have a nonzero flow in MD mode and AVs will have a nonzero flow in AD mode. This leads to the intended total flow on each link type for each mode. (4) shows how link travel time for each mode is calculated using the BPR function. Note that different combinations of capacities and total flows based on the subnetwork type and driving mode will be applied in (4), which results in different travel times for MD and AD modes on dedicated AV lanes and links but identical travel times for both modes in regular links and AV-ready links. Figure 1 summarizes the capacities and flows applied for each mode and class on each link type. For computational reasons, infeasible modes (e.g., flow of RVs in MD mode on dedicated links to AVs) are modeled with very large travel times via very small capacity values applied in (1) and (2).Link travel cost for each mode on each link is calculated as(5)cm,a=c¯m,a+ηmtm,a,∀a∈A,∀m∈M,where link travel cost is based on the link travel time for each mode multiplied by the value of travel time (VoTT) of that mode along with the fixed driving cost of the link in that mode. VoTT and fixed driving costs are assumed to be lower for AD mode since drivers can perform other activities in the car while ADS performs the driving task [32].The correspondence between link flows and route flows is ensured using a link-route incidence matrix (assignment map) for each class as follows:(6)∑w∈W∑r∈RwFrw,0δr,aw,0=f0,a0,∀a∈A,(7)∑w∈W∑r∈RwFrw,1δr,aw,1=f1,a1Xa+Ya+Za+f0,a11−Xa+Ya+Za,∀a∈A,where (6) and (7) ensure that the route flow of each class is assigned to the appropriate mode on each link based on the subnetwork type. On regular links (MD network), AV route flow is assigned to MD mode, and on the rest of the links (AD subnetwork), it is assigned to AD mode. The following equations carry out the same task for the correspondence between link and route costs.(8)∑w∈W∑r∈RwCrw,0δr,aw,0=c0,a,∀a∈A,(9)∑w∈W∑r∈RwCrw,1δr,aw,1=c1,aXa+Ya+Za+c0,a1−Xa+Ya+Za,∀a∈A.Finally, (10) guarantees the travel demand in each class for each OD pair is satisfied by equating the sum of all route flows for each OD pair and each class to their relevant demand, and (11) prohibits negative flows.(10)∑r∈RwFrw,k=Dw,k,∀w∈W,∀k∈K,(11)Frw,k≥0,∀w∈W,∀k∈K,∀r∈Rw.Equilibrium Conditions. The equilibrium condition of the NEM based upon Brouwer’s fixed-point theorem [33–35] is to find an F∗ that solves(12)F−PFD=0,∀F=Frw,k∈Π,where F is the vector of route flow Frw,k. The set Π represents the set of flows Frw,k that satisfy (1)–(11), i.e., Π=Frw,k|1−11 defines the feasible region of the NEM. Vector D is the vector of travel demand Dw,k, and P is the vector of route choice probability Pr|w,k that represents the proportion of the travelers of class k between OD pair w who take the route r. Solving (12) yields Pr|w,k∗=Fr∗w,k/Dw,k, which for the case of the multiclass multinomial logit SUE leads to the following well-known route choice probabilities [36]:(13)Fr∗w,kDw,k=Pr|w,k∗=expμkCr∗w,k∑r∈RwexpμkCr∗w,k,∀w∈W,∀k∈K.


## 2.3. Deployment of AV-Ready Subnetwork, Dedicated AV Links, and Dedicated AV Lanes

The optimal deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes (the upper level problem) investigates where AV-ready links, dedicated AV links, and dedicated AV lanes should be deployed to maximize their societal benefits. The upper level decision variables are as follows.Xa is a binary decision variable taking the value 1 when link a is selected as an AV-ready link. Ya is a binary decision variable taking the value of 1 when link a is selected as a dedicated AV link. Ia is an integer decision variable denoting the number of dedicated AV lanes on link a. Za is an auxiliary binary variable taking the value of 1 when link a contains one or more dedicated AV lanes. Mathematical formulation of the upper level problem is given below.(14)MinXa,Ya,IaZU=∑tσTTC1+πt+TAC,s.t.1−12,(15)TTC=∑k∈K∑w∈W∑r∈RwFrw,kCrw,k,(16)TAC=∑a∈AXaκa1+Yaκa2+ZaIaκa3,(17)Ia≤la−1,∀a∈A,(18)Xa+Ya+Za≤1,∀a∈A,(19)1−ZaIa=0,∀a∈A,(20)Za≤Ia,∀a∈A,(21)pG1N1,A1n,n′≥1,∀n,n′∈N1,(22)Xa,Ya,Za∈0,1,Ia∈Z≥0,∀a∈A.In this formulation, (14) represents the objective function (OF), which minimizes the sum of total adjustment cost (TAC) and the net present value of the total travel cost (TTC), given the entire planning horizon. One morning peak hour is considered in this study, and TTC of this period is converted to a yearly basis with a parameter σ. This yearly value is discounted with a discount rate of π for t years, which is the useful lifetime of the infrastructure adjustments. The effects of the construction period itself are not considered here. The first set of constraints for the upper level problem is the lower level problem defined by (1)–(12), which means the upper level should be evaluated when the lower level is at equilibrium. (15) shows how TTC is calculated based on equilibrium flows and costs obtained from the lower level problem. TAC in (16) is the summation of link adjustment costs for all subnetworks. (17) ensures the number of dedicated AV lanes is less than the number of lanes on each link. (18) guarantees each link can be selected only for one subnetwork. (18)–(20) force Za to take the value of 1 when Ia is greater than 0, and 0 otherwise. (22) denotes admissible values for the upper level decision variables. Finally, (21) expresses a connectivity constraint, imposed in order to find coherent networks. It signifies that for two nodes n and n′ within the graph G1N1,A1 where the AD mode is allowed, there must exist at least one undirected path connecting the two nodes. The purpose of this constraint is preventing the solution method from finding networks with disconnected components. Since the AD mode is only allowed within G1, having networks with separate components (i.e., disconnected networks) leads to switching frequently between MD and AD mode, which is best to be avoided. This imposes extra requirements on the solution method, which are discussed below.


## 2.4. Solution Methods

Regarding the lower level problem, Daganzo [35] has shown the existence and uniqueness of a solution for the fixed-point formulation of the multimode multiclass SUE problem with asymmetric link costs in terms of the PCE-equivalent of flows. This holds when the feasible region of a NEM is compact and convex, and all the functions are continuous, which is the case for the NEM-FP defined by (1)–(12). There are numerous solution methods available for solving FP problems. For a review, the reader is referred to [34, 37]. In this study, we use an efficient sequential linear approximation algorithm with step sizes according to the method of successive averages (MSA) introduced in [38] to solve the lower level equilibrium problem.The upper level problem on the other hand is more challenging to solve. Bilevel NDPs with discrete upper level decision variables and multiclass SUE lower level problems are among the most challenging problems in transport literature and are often solved using heuristic procedures [27, 28]. Solving such problems, particularly for large-scale networks, calls for efficient solution procedures. Moreover, the connectivity requirement denoted by constraint (21) makes the problem even more difficult to solve, since existing methods for solving NDPs do not produce connected graphs. Therefore, we have developed a heuristic solution procedure based on an evolutionary algorithm in this study to solve the upper level problem. However, before introducing the solution procedure, we provide five definitions that are necessary in order to comprehend how the solution method operates and deals with the connectivity constraint. These definitions are illustrated ‏in Figure 2.‏Figure 2
An example AD subnetwork. Nodes 3-7-9-10-11 are boundary nodes, links (5,9)-(6,10)-(7,11) are inner boundary links, and links (9,13)-(10-14)-(11,15)-(11,12)-(7,8)-(3-4)-(9,10)-(10,11) are outer boundary links.Definition 1.
Any noden incident to at least one link included in an AD subnetwork represented by G1N1,A1 is included in that AD subnetwork (i.e., n∈N1).Definition 2.
The degree of a node belonging to each graph (e.g.,G,G0,G1) is the number of links incident to that node within the graph in which that node is included.Definition 3.
A boundary noden∗∈N1 for an AD subnetwork represented by a directed graph G1N1,A1 is a node included in G1with a degree less than the degree of the corresponding node n in the underlying graph GN,A (i.e., the graph representing the original road network).Definition 4.
An outer boundary linka∗∈A0 for an AD subnetwork is a link incident to a boundary node n∗∈N1 of the AD subnetwork but not included in the graph G1 representing the AD subnetwork.Definition 5.
An inner boundary linka∗∈A1 for an AD subnetwork is a link included in the graph G1 representing the AD subnetwork and incident only to boundary nodes with the degree of 1.
Note that the boundary nodes of an AD subnetwork and the inner boundary links are included in the subnetwork while the corresponding outer boundary links are not included in that subnetwork.


### 2.4.1. Evolutionary Heuristic Solution Procedure

The evolutionary heuristic solution introduced here is inspired by evolutionary metaheuristics and takes advantage of this specific problem’s structure to efficiently generate connected subnetworks and solve the problem. Using extensive computational experiments, it is shown in [25] that an evolutionary local search algorithm tailored to the problem can efficiently find coherent and connected AV-ready subnetworks. Therefore, in this study, we develop another evolutionary algorithm that modifies and extends the procedure of the mentioned algorithm to find coherent subnetworks including AV-ready links, dedicated AV links, and dedicated AV lanes in an efficient manner.The purpose of the solution procedure is to determine the values ofXa,Ya,Za,andIa (which uniquely define a graph G1N1,A1) in order to minimize (14) and satisfy constraints (15)–(22). Since every AD subnetwork represented by G1N1,A1 is built from scratch, we can start with a simple connected graph as an initial feasible solution and iteratively modify this graph to improve the value of the OF in (14) using operations that preserve the connectivity requirement of constraint (21) until no further improvement can be obtained by modifying the graph. To avoid termination of the procedure in local minima, a population of solutions is evolved through several generations to acquire a good solution at the end. The steps of the solution procedure are summarized in Table 2. This is followed by the description of the operations used in the procedure.Table 2
Solution procedure.
Solution steps1Initialize population2Measure fitness of all individuals3For each generation j4Assign an operation to each individuali based on parameters (possible operations are extension, reduction, and merging)5For each individual i6Perform the operation assigned to the individuali7Measure fitness of the individuali8End9Perform regeneration10Increment generation number11If stopping criteria met: terminate12End


### 2.4.2. Evolutionary Heuristic Operations

(1) Initialization. During the initialization process, a population of individual solutions is generated. Each individual solution includes one link selected via a roulette wheel prioritizing links with higher capacity. A subnetwork type s is randomly assigned to each link. With the addition of each link, the nodes incident to that link are added to the graph G1 as well. Note that any graph including one link and its incident nodes satisfies constraint (21). This process will provide a pool of diverse and connected solutions to start the algorithm. The size of the population is an algorithm parameter.(2) Fitness Evaluation. Fitness evaluation is based on the value of the upper level of (ZU) in (14). This value is obtained by assigning a value to each (upper level) decision variable and solving the lower level problem (NEM-FP).(3) Extension Operation. In this operation, first a subnetwork s is randomly selected for extension (e.g., dedicated AV link). Next, the outer boundary links of the graph (i.e., the set of links a∗∈A0) are specified (see Definition 4). Then, a sample of them is selected based on a roulette wheel prioritizing higher capacities and added to the graph. When the subnetwork type is dedicated AV lanes (i.e., s=3), the number of lanes Ia is assigned at random. All nodes incident to any link added to G1 are added to it as well. The sample size is an algorithm parameter. When the input of this operation meets constraint (21), the output is guaranteed to meet this constraint as well.(4) Reduction Operation. In this operation, first the inner boundary links of the graph (i.e., the set of links a∗∈A1) are determined (see Definition 5). Then, a sample of them is selected based on a roulette wheel prioritizing links with lower capacity and removed from the graph. The corresponding nodes that are not incident to any other link in G1 are eliminated as well. This sample size is also an algorithm parameter. This operation preserves the connectivity constraint (21) as well, since it only removes links from the boundaries of a graph.(5) Merging Operation. Unlike extension and reduction operations, which require an individual solution, the merging operation first selects a merging partner from among the population based on a roulette wheel prioritizing the fitness value. Then, the merged graph is the union of the links and nodes in both graphs (merging parents) with their subnetwork type s unchanged. When there is a conflict (e.g., a link is included in both graphs and is a dedicated AV link in one graph but an AV-ready link in the other), it is resolved by inheriting from the fitter parent. That is, the values of Xa,Ya,Za,andIa for a conflicting link a in a merging offspring are equal to those values of the merging parent with better fitness value.(6) Regeneration. At the end of each generation, the fittest individuals among the parents (from the previous generation) and the offspring (resulting from the operations in the current generation) survive to repopulate the next generation.


## 2.4.1. Evolutionary Heuristic Solution Procedure

The evolutionary heuristic solution introduced here is inspired by evolutionary metaheuristics and takes advantage of this specific problem’s structure to efficiently generate connected subnetworks and solve the problem. Using extensive computational experiments, it is shown in [25] that an evolutionary local search algorithm tailored to the problem can efficiently find coherent and connected AV-ready subnetworks. Therefore, in this study, we develop another evolutionary algorithm that modifies and extends the procedure of the mentioned algorithm to find coherent subnetworks including AV-ready links, dedicated AV links, and dedicated AV lanes in an efficient manner.The purpose of the solution procedure is to determine the values ofXa,Ya,Za,andIa (which uniquely define a graph G1N1,A1) in order to minimize (14) and satisfy constraints (15)–(22). Since every AD subnetwork represented by G1N1,A1 is built from scratch, we can start with a simple connected graph as an initial feasible solution and iteratively modify this graph to improve the value of the OF in (14) using operations that preserve the connectivity requirement of constraint (21) until no further improvement can be obtained by modifying the graph. To avoid termination of the procedure in local minima, a population of solutions is evolved through several generations to acquire a good solution at the end. The steps of the solution procedure are summarized in Table 2. This is followed by the description of the operations used in the procedure.Table 2
Solution procedure.
Solution steps1Initialize population2Measure fitness of all individuals3For each generation j4Assign an operation to each individuali based on parameters (possible operations are extension, reduction, and merging)5For each individual i6Perform the operation assigned to the individuali7Measure fitness of the individuali8End9Perform regeneration10Increment generation number11If stopping criteria met: terminate12End


## 2.4.2. Evolutionary Heuristic Operations

(1) Initialization. During the initialization process, a population of individual solutions is generated. Each individual solution includes one link selected via a roulette wheel prioritizing links with higher capacity. A subnetwork type s is randomly assigned to each link. With the addition of each link, the nodes incident to that link are added to the graph G1 as well. Note that any graph including one link and its incident nodes satisfies constraint (21). This process will provide a pool of diverse and connected solutions to start the algorithm. The size of the population is an algorithm parameter.(2) Fitness Evaluation. Fitness evaluation is based on the value of the upper level of (ZU) in (14). This value is obtained by assigning a value to each (upper level) decision variable and solving the lower level problem (NEM-FP).(3) Extension Operation. In this operation, first a subnetwork s is randomly selected for extension (e.g., dedicated AV link). Next, the outer boundary links of the graph (i.e., the set of links a∗∈A0) are specified (see Definition 4). Then, a sample of them is selected based on a roulette wheel prioritizing higher capacities and added to the graph. When the subnetwork type is dedicated AV lanes (i.e., s=3), the number of lanes Ia is assigned at random. All nodes incident to any link added to G1 are added to it as well. The sample size is an algorithm parameter. When the input of this operation meets constraint (21), the output is guaranteed to meet this constraint as well.(4) Reduction Operation. In this operation, first the inner boundary links of the graph (i.e., the set of links a∗∈A1) are determined (see Definition 5). Then, a sample of them is selected based on a roulette wheel prioritizing links with lower capacity and removed from the graph. The corresponding nodes that are not incident to any other link in G1 are eliminated as well. This sample size is also an algorithm parameter. This operation preserves the connectivity constraint (21) as well, since it only removes links from the boundaries of a graph.(5) Merging Operation. Unlike extension and reduction operations, which require an individual solution, the merging operation first selects a merging partner from among the population based on a roulette wheel prioritizing the fitness value. Then, the merged graph is the union of the links and nodes in both graphs (merging parents) with their subnetwork type s unchanged. When there is a conflict (e.g., a link is included in both graphs and is a dedicated AV link in one graph but an AV-ready link in the other), it is resolved by inheriting from the fitter parent. That is, the values of Xa,Ya,Za,andIa for a conflicting link a in a merging offspring are equal to those values of the merging parent with better fitness value.(6) Regeneration. At the end of each generation, the fittest individuals among the parents (from the previous generation) and the offspring (resulting from the operations in the current generation) survive to repopulate the next generation.


## 3. Case Study: Amsterdam Metropolitan Region

### 3.1. Description

The concept of optimal AD subnetworks with AV-ready subnetworks, dedicated AV links, and dedicated AV lanes is demonstrated in this section using a case study of the road network of the Amsterdam metropolitan region. The network and demand data of the VENOM model [39] are used here. They are based on the real network and demand patterns of the Amsterdam metropolitan region. The original network includes 52,812 directed links, 19,734 nodes, and 3722 transportation zones. In this case study, the transportation zones are aggregated to 102 zones (10,124 OD pairs) and all the links that are not used in the traffic assignment of the base case scenario (in the morning peak) are eliminated. Therefore, the considered study area contains 12,781 links and 6,642 OD pairs. The network and the equilibrium flows in the base case are shown in Figure 3(a). The calibrated demand matrices in VENOM model for the year 2004 are used to extract the demand for cars. The demand for AVs is considered via four scenarios with 10%, 30%, 50%, and 90% MPR of AVs. All demand from, to, and through the study area is considered in the traffic assignment to calculate the equilibrium flows (NEM-FP). Network performance indicators are reported for the OD pairs inside the study area. One average morning peak hour is modeled in this study, which is assumed to account for 10% of the daily traffic, and the value of TTC obtained is converted to a yearly basis using σ=10×30×12 for calculation of the OF value in (14). The value of discount rate π is 4%, which is the common value used for public investments in the Netherlands, and the length of the planning horizon t is assumed to be 10 years. All OF values reported in this study are divided by 106 for convenience. The base case traffic pattern is shown in Figure 3(b).Figure 3
Feasible links for AD subnetwork and base case traffic patterns in Amsterdam network. (a) Feasible links for AD subnetwork. (b) Base case traffic patterns.
(a)(b)The capacity gain from converting a regular link to a dedicated AV link is assumed to be 100%Δa2=2, and the capacity gain of converting a lane to a dedicated AV lane is assumed to be 50% Δa3=1.5. Studies that proposed deployment of networks of dedicated AV links [21] and lanes [19] have used the values 3 and 2.5 for Δa2 and Δa3, respectively. However, microsimulation studies of dedicated AV lanes suggest that these values are overly optimistic (see, for instance, [1, 2, 4]). Therefore, we have selected the input values for capacity gains according to the results of the mentioned microsimulation studies and performed a sensitivity analysis (reported in Section 3.2.6) to investigate the effect of deviations from these values on model results. Converting a link to an AV-ready link for mixed traffic does not lead to any explicit capacity increase Δa1=1. Instead, the PCE value of driving in AD mode γ1 on AV-ready links is assumed to be 0.9 for AV MPRs below 40% and 0.8 for above 40% AV MPR [40]. The PCE value of driving in MD mode γ0 is set to 1. VoTT for MD mode η0 is 9 €/h, and VoTT for AD mode η1 is 80% of this value [32]. Fixed driving cost per kilometer for MD mode c¯0,a is 0.19 €/km. For the AD mode, c¯1,a is 80% of 0.19 €/km when AV MPR is below 40% and 60% of 0.19 €/km when AV MPR is above above 40% [41, 42]. These values are similar to those used in [25] where a sensitivity analysis is also provided, which shows that minor deviations from these values will not significantly impact the results. The logit model route choice parameter μk value used for both classes is −0.5 [43].Regarding the parameters of the upper level solution algorithm, the population size is 600, maximum number of generations is 500, the sample size for extension and reduction operations is 0.1% of the number of decision variables, and the population fractions assigned to operations extension, reduction, and merging are 0.2, 0.2, and 0.6, respectively. The number of iterations used for the convergence of the lower level solution algorithm is 50. These values were selected after extensive hyperparameter tuning with the aim of obtaining the lowest possible value for the objective function in each scenario with feasible computation times.Motorways, major regional roads, and main urban roads are considered feasible links for AD subnetwork in this case study. The purpose of this selection is to avoid complex interactions including AVs and vulnerable road users that might compromise safe operation of AVs in AD mode. This is consistent with the findings of AV accident reports, which indicate that around 90% of the accidents involving AVs have occurred at urban intersections [44]. Moreover, about half of the AV disengagements in California have happened in small urban streets [9], which are not considered as feasible links in this study. A total of 3,402 links is considered feasible in this case study. They are also depicted in Figure 3(a).As for the adjustment costsκas, different values per kilometer are used for each road type and each subnetwork type. The adjustment cost value for AV-ready links κa1 is assumed to be 50,000 €/km for motorways, 75,000 €/km for regional roads, and 100,000 €/km for urban roads. The reason for the increase in adjustment costs from motorways to regional roads and urban roads is that motorways generally have higher quality standards and require minimal interaction with other road users due to segregated traffic and off-grade intersections. Regional roads can have lower standards and require more interaction with other road users, thereby requiring higher adjustment costs to make them suitable for AVs. Finally, urban roads are the most challenging ones for AVs due to complex interactions between AVs and other road users. Therefore, they have the highest adjustment costs. Figure 4 depicts road types in Amsterdam case study. For dedicated AV links, κa2 is twice the value of κa1 for each road type. The adjustment cost values for dedicated AV lanes κa3 are 50% higher than the values of κa1 for each road type. In real applications, these values can be estimated in more detail by experts.Figure 4
Road types and number of lanes for feasible AD subnetwork links in Amsterdam road network. (a) Road types. (b) Number of lanes.
(a)(b)


### 3.2. Results and Analysis

In this section, we first discuss the consistency of AD subnetworks generated by the evolutionary heuristic solution method proposed in this study for real road networks. Then, we discuss the impacts of simultaneous deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes on road network performance, the usage of different road types in the network, and the usage of AD mode on different road types and subnetworks. In addition, we evaluate the distribution of TTC, TTT, and TTD on each subnetwork. Computation times of the experiments are discussed at the end of this section.


#### 3.2.1. Consistency of AD Subnetworks in Real Road Networks

Figure5 depicts the graphs obtained by the heuristic solution method introduced earlier as (near) optimal AD subnetworks in all four scenarios. In this section, we discuss three characteristics related to the logical consistency of AD subnetworks in real road networks, which are not observed in theoretical networks that are commonly used as case studies in scientific literature. These characteristics are connectivity, suboptimality, and continuity in network hierarchy. We briefly discuss them in the following.Figure 5
AD subnetworks obtained by the evolutionary heuristic solution for the Amsterdam case study. (a) 10% MPR. (b) 30% MPR. (c) 50% MPR. (d) 90% MPR.(1) Connectivity. Connectivity of a graph representing an AD subnetwork (constraint (21)) is an undeniable requirement for the efficiency of AD mode. However, common solution methods for NDP are not equipped to cope with this constraint effectively. It is shown in [25] that without this constraint, incoherent subnetworks with numerous disconnected islands of links can be obtained as (near) optimal solutions. Tailored algorithms such as the evolutionary algorithm developed in this study can satisfy this constraint in an efficient manner, yet they do not necessarily find the global optimum of the problem.(2) Suboptimality. Suboptimality of the results is another characteristic that needs to be considered. The solutions provided by the heuristic algorithm introduced in this study are not necessarily optimal. The algorithm effectively copes with the connectivity constraint and generates plausible solutions with reasonable computation times, yet there is no guarantee for optimality of the solutions. This is caused by the well-known complexity of bilevel NDPs with discrete decision variables along with the large problem size due to the use of a realistic road network that makes the problem very challenging to solve for the global optimum. Therefore, this might introduce some degree of inconsistency in the resulting graphs as well.(3) Continuity. When considering three types of subnetworks, it seems plausible to expect long stretches of roads selected for each single subnetwork, which are connected to each other at junctions. However, as demonstrated in Figure 4, road types (and consequently the network hierarchy) are not fully continuous in the network of Amsterdam; there are long stretches of roads that are classified as urban roads in some parts and as regional roads in some other parts. In addition, there are many stretches of roads in this network with fluctuating number of lanes. Perhaps these phenomena can be observed in all real road networks. Since each subnetwork is more suitable for certain types of roads with certain number of lanes, the discontinuity in road types and lane numbers causes discontinuity in subnetwork types. For instance, single-lane roads, which constitute a large proportion of roads in this network, as well as motorway on-ramps and off-ramps and main regional roads with occasional single-lane stretches in between are not feasible for dedicated AV lanes. These types of links are suitable for mixed traffic at any AV MPR during the transition period. This also explains the gaps with AV-ready links in between stretches of dedicated AV lanes. Comparing the (near) optimal graphs obtained by the solution method (Figure 5) with the map of the Amsterdam network including the number of lanes and road types (Figure 4) corroborates this notion.


#### 3.2.2. Network Performance

Table3 summarizes the performance of the road network in presence of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes using three key performance indicators (KPIs), namely, TTC, TTT, and TTD. Furthermore, three criteria for assessing the trade-off between costs and benefits of deploying AD subnetworks are reported. These criteria are OF, TAC, and total discounted travel cost saving (TDTCS). TDTCS represents the net present value of TTC savings (compared to the base case) in each scenario over the entire planning horizon.Table 3
Key performance indicators for network of Amsterdam (indexing is based on the base case).
Class0% MPR (base case)TTC (€)TTT (h)TTD (km)All cars611,70435,6561,530,51410% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV89.52%89.22%89.85%AV8.87%9.91%10.03%All cars17,647323,021,01498.39%99.13%99.88%73,918,28930% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV69.93%70.12%69.72%AV26.25%29.30%30.12%All cars17,288766,422,53096.18%99.42%99.84%108,941,63750% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV49.14%48.54%49.79%AV40.02%48.23%50.30%All cars16,0372,174,874,40489.16%96.77%100.09%111,967,17190% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV9.70%9.42%10.00%AV73.92%91.21%90.45%All cars15,0453,288,394,04883.61%100.63%100.45%111,280,505The values of TDTCS in all scenarios are substantially higher than TAC values (e.g., for 50% MPR, the TDTCS to TAC ratio is approximately 20). This means the benefits significantly outweigh the infrastructure adjustment costs. In general, the results show a steady decrease in TTC with the increase in MPR of AVs. The decrease in TTC is rather linear until 30% AV MPR, but there is a sharp acceleration in the decrease starting from 50% AV MPR. Moreover, the AV class observes a larger proportion of TTC benefits compared to the RV class in all scenarios; nonetheless, RVs are better off in terms of TTC compared to the base case in all scenarios. This indicates a major improvement in overall network performance with combined deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes.TTT values are also less than the base case values for all classes in all scenarios except for 30% MPR where RVs observe a minor increase in TTT (in proportion to their market size). However, the general magnitude of the decrease in TTT is smaller compared to TTC. One interpretation for this phenomenon is that in addition to congestion relief and more traffic efficiency due to rerouting, a proportion of the gains in TTC is due to lower VoTT values for AD mode.TTD for all vehicles is slightly decreasing until 30% MPR, and then it starts to increase. Nevertheless, RVs and AVs exhibit different trajectories in this regard. For RVs, in all scenarios, TTD values (proportional to their market size) are lower compared to the base case, while the values of TTD for AVs are slightly higher in all scenarios compared to the base case. This is mostly due to rerouting of AVs towards parts of the network with dedicated infrastructure. It is noteworthy that both classes have lower TTT in most scenarios despite the overall higher TTD.The OF values steadily decrease with higher MPR of AVs. This is because larger reductions in TTC values are possible with higher AV MPR, while total adjustment cost (TAC) values stay rather steady after 30% MPR scenario. A remarkable observation is that the TAC value of the 90% MPR scenario is marginally lower compared to 50% MPR, even though OF and TTC values are lower. This means higher traffic efficiency benefits can become available with high MPR of AVs even with less investment on infrastructure.


#### 3.2.3. Distribution of Traffic among Road Types

The next factor we analyze in this paper is the impact of AD subnetwork deployment on the usage of different road types. We focus on 50% MPR scenario to show the usage of different road types and compare statistics of RVs and AVs. Table4 summarizes the distribution of network performance indicators on different road types indexed according to the base case values for the 50% MPR scenario. Therefore, comparing the values of RV and AV rows with 50% (and similarly the values of “all cars” rows with 100%) shows the percentage difference in each performance indicator on each road type compared to the base case scenario.Table 4
Distribution of network performance indicators on different road types for 50% MPR (indexing is based on the values of the base case scenario).
ClassMotorwayRegional roadUrban roadTTC (€)RV48.98%48.52%49.31%AV33.62%37.58%45.01%All cars82.60%86.10%94.32%Base case227,514 (100%)116,651 (100%)186,053 (100%)TTT (h)RV47.60%47.12%48.98%AV48.16%45.59%48.51%All cars95.76%92.70%97.48%Base case8,821 (100%)6,078 (100%)13,314 (100%)TTD (km)RV49.71%49.76%49.92%AV50.65%50.20%49.68%All cars100.36%99.96%99.60%Base case779,589 (100%)326,060 (100%)348,571 (100%)Table4 shows that the TTD on motorways for the 50% MPR scenario is higher compared to the base case, while regional roads and urban roads are used less intensively in this scenario compared to the base case. It is also evident that RVs have lower usages of all road types (i.e., they opt for shorter routes) compared to the base case scenario, whereas AVs travel more using motorways and regional roads and less using urban roads (i.e., they opt for longer routes). This can logically be explained by the fact that most motorways and regional roads are part of the AD subnetwork. TTC and TTT values are lower in all road types for both classes in spite of higher TTD, with motorways and regional roads showing the highest impacts for AVs.Since motorways generally are the safest roads, the shift of traffic towards motorways can provide traffic safety benefits. However, AD subnetworks attract AVs towards roads that are higher in network hierarchy and RVs towards lower ones, which leads to uneven distribution of traffic safety benefits between AV and RV classes.


#### 3.2.4. Distribution of ADS Usage among Different Subnetworks

Table5 summarizes the statistics related to performance indicators for the AV class and AD mode, as well as the usage of each subnetwork and its impact on network performance indicators. The autopilot column is the summation of the values of all three subnetworks. In all scenarios, around 70% of TTD for AVs is in AD mode, which is very high given that the length of all feasible roads for AD subnetworks A1 is 26% of the length of all roads in the network. Yet this approximately 70% of TTD for the AV class in AD mode only accounts for approximately 43% of TTT and 50% of TTC of this class on average. This is partly due to the efficiency of AD mode and partly due to the compartmentalization of traffic among different road types as a result of the combined AD subnetwork deployment that draws AVs towards main roads having higher speeds and partially repels RVs from them.Comparing the ratios of TTC and TTT to TTD for different subnetworks reveals that dedicated AV lanes provide more traffic efficiency benefits in comparison to the AV-ready subnetwork. The reason is the higher capacity gains of dedicated AV lanes. On the other hand, dedicated AV links are rarely selected in (nearly) optimal plans since they can compromise the accessibility of RVs when there is no alternative route for them. Even when there are alternative routes available, rerouting all RV traffic can direct too much flow to certain links and lead to inefficient distribution of traffic throughout the network.Regarding the distance traveled in AV-ready subnetwork and dedicated AV lanes, in 10% MPR scenario, the AV-ready subnetwork is chosen more frequently with 63% of the TTD of AV class versus 7% for dedicated AV lanes. However, as MPR of AVs increases, this balance shifts towards dedicated AV lanes until the 50% MPR scenario when 46% of the TTD of AVs is on these lanes while the share of AV-ready subnetwork drops to 28%. With the increase of AV MPR to 90%, the ratio changes to 39% versus 34% in favor of dedicated AV lanes. The transition from 50% to 90% can be explained by the fact that there are many two-lane roads in the network, and thus assigning 50% of the capacity to 90% of traffic is not efficient considering that dedicated AV lanes are more expensive than AV-ready links. In this case, the extra capacity gain of dedicated lanes does not compensate for the loss of cost and efficiency.In order for dedicated AV lanes to be efficient in terms of traffic distribution, the number of these lanes should be proportional to the share of traffic to which the lanes are dedicated. However, in real networks, situations such as the one mentioned earlier with 90% AV volume and only 50% of capacity (i.e., one out of two lanes) available for them are inevitable.Table 5
Network performance indicators for the AV class in all subnetworks (indexing is based on AV class column).
AV-ready subnetworkDedicated AV linksDedicated AV lanesAutopilot (AD mode)AV class10% MPRTTC (€)44.83%0.06%4.59%49.47%100.00%TTT (h)38.21%0.06%3.31%41.55%100.00%TTD (km)62.57%0.08%7.07%69.72%100.00%30% MPRTTC (€)28.82%0.12%23.43%52.37%100.00%TTT (h)26.58%0.11%16.94%43.63%100.00%TTD (km)37.52%0.15%35.52%73.19%100.00%50% MPRTTC (€)19.49%0.11%28.39%47.99%100.00%TTT (h)18.89%0.11%23.84%42.84%100.00%TTD (km)27.72%0.15%45.57%73.44%100.00%90% MPRTTC (€)22.36%0.05%26.57%48.97%100.00%TTT (h)20.20%0.04%24.92%45.16%100.00%TTD (km)34.09%0.07%39.15%73.31%100.00%


#### 3.2.5. Distance Coverage of Subnetworks

As it is shown in Table6, considering all four scenarios, 51–59% of all roads selected for all subnetworks are motorways, 27–30% are regional roads, and 13–19% are urban roads. Motorways constitute around two-thirds of dedicated AV lanes in all scenarios while regional roads have a slightly higher share of the other one-third compared to urban roads. For the AV-ready subnetwork, the ratios change drastically in different scenarios. At 10% MPR, more than half of AV-ready links are motorways, and regional roads cover around two-third of the rest. Starting from 30% MPR, regional roads have the highest share of AV-ready links with percentages slightly less than 50% of AV-ready links in most scenarios. Urban roads contribute to around 20% of AV-ready links in all scenarios except for 10% MPR when their share is slightly more than 10%.Table 6
Distance coverage of each subnetwork (km) in each road type.
10% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways46.43%0.09%12.03%58.55%Regional roads25.09%0.28%2.35%27.82%Urban roads10.90%0.19%2.63%13.63%All roads82.42%0.66%17.01%1,064 (100%)30% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways19.33%0.15%31.70%51.18%Regional roads19.94%0.38%9.55%29.87%Urban roads10.54%0.46%7.87%18.95%All roads49.89%0.99%49.20%1,309 (100%)50% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways14.18%0.08%36.81%51.07%Regional roads18.52%0.30%10.98%29.80%Urban roads9.91%0.38%8.77%19.13%All roads42.61%0.76%56.55%1,312 (100%)90% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways16.32%0.08%34.71%51.11%Regional roads18.23%0.23%11.21%29.67%Urban roads9.92%0.15%9.08%19.22%All roads44.47%0.46%55.07%1,311 (100%)The total length of the AV-ready subnetwork and dedicated AV lanes follows a similar trend to the distance traveled in each subnetwork, which was discussed in the previous section, with AV-ready links having a larger share at first (10% MPR), dedicated AV lanes reaching them at 30% MPR, and the ratio slightly balancing in 90% MPR again. Share of dedicated AV links is insignificant in all scenarios.Therefore, regarding suitability of each subnetwork for different AV MPRs, it can be concluded that AV-ready subnetworks are more suitable for low MPRs of AVs. However, with the increase in AV MPR, dedicated AV lanes become more effective until a point where the share of AVs gets so high that their traffic efficiency benefits can be fully realized, even in mixed traffic. It is noteworthy that certain parts of road networks such as on-ramps, off-ramps, and single-lane roads are exclusively suitable for mixed traffic as long as RVs are on the roads.


#### 3.2.6. Sensitivity Analysis

In this study, we used the knowledge available so far in academic literature to estimate the values of extra capacity gain and infrastructure adjustment costs for AV-ready subnetworks, dedicated AV lanes, and dedicated AV links. However, these values are estimates with high uncertainty, and the real values might deviate from these estimates. Therefore, we perform a sensitivity analysis for these parameters to investigate the impacts of deviations from these values on results. We provide two sensitivity analysis variations for each subnetwork, namely, the optimistic case and the pessimistic case. In the optimistic case, the analyzed subnetwork is assumed to be more efficient with regard to the trade-off between capacity gain and adjustment cost compared to the original scenario in order to estimate the upper bound of the subnetwork’s impacts. This is achieved via decreasing the link adjustment cost by 50% and increasing the link capacity by 50% (for AV-ready subnetwork, the increase in capacity is realized via decreasing the PCE value for AVs within the subnetwork). For the pessimistic case, the analyzed subnetwork is assumed to be less efficient by means of 50% higher adjustment cost and 50% lower capacity gain compared to the original scenario in order to estimate the lower bound of the subnetwork’s impacts. Table7 summarizes the results of the sensitivity analysis for the 50% MPR scenario.Table 7
Sensitivity analysis for 50% MPR scenario.
Analyzed subnetworkParameter deviationPerformance deviationCapacityΔasCostκasPCEγ1OFTTCTTTTTDTACAV-ready subnetwork—-50%−50%−01.24%−00.89%−01.85%+00.06%−50.66%—+50%+50%+03.66%+03.41%+04.83%−00.06%+37.08%Dedicated AV links+50%−50%—+00.51%+00.54%+00.98%00.00%−03.61%−50%+50%—+00.40%+00.41%+00.65%+00.05%−01.21%Dedicated AV lanes+50%−50%—+00.03%+00.20%+00.11%+00.07%−23.70%−50%+50%—+01.68%+01.51%+03.14%−00.03%+25.43%Notable changes in KPIs (i.e., TTC, TT, and TTD) due to deviations in capacity and adjustment cost parameters are TTT and TTC increases (maximum 5% compared to the original 50% MPR scenario) in pessimistic variations of AV-ready subnetworks and dedicated AV lanes. This was to be expected, particularly since both capacity and link adjustment cost were modified simultaneously. The rest of the variations indicate no major deviation in KPIs. Conversely, for TAC, significant changes are observed in all variations, with AV-ready subnetwork showing the most sensitivity (37–49% change), dedicated AV lanes showing relatively lower sensitivity (around 25% change), and dedicated AV links displaying the least sensitivity (less than 5%) to deviations in adjustment cost and capacity changes. This means with reasonable deviations in values of input parameters, comparable gains in KPIs can be achieved, only with more or less budget depending on the direction of the deviations. Regarding the trade-off between costs and benefits, among all sensitivity analysis scenarios considered here, the lowest value of the TDTCS to TAC ratio, which is approximately 20 in the original 50% scenario, is around 18, which belongs to the pessimistic scenario for the AV-ready subnetwork. These are useful insights for planners since they show that when deploying AD subnetworks, the main uncertain factor is the amount of budget required for the project, yet the improvement in the performance of the network is rather stable with moderate deviations in input.


#### 3.2.7. A Note on Computations

The mathematical model and the solution algorithm introduced in this study were coded in MATLAB and ran on a Windows PC with a Core i5-8600 CPU @ 3.10 GHz and 32 GB RAM. Since population-based algorithms such as the one developed in this study can be implemented more efficiently using parallel computation architectures, the Parallel Computation Toolbox in MATLAB with 6 computation units was used to utilize the efficiency of parallel computing in order to perform fitness evaluations for multiple solutions simultaneously. Moreover, sparse matrices in MATLAB were used for all matrix operations on assignment maps to minimize the computation times of the MSA-based algorithm used to solve the lower level problem. It is noteworthy that since assignment maps for large-scale networks include very few nonzero elements (i.e., they are very sparse), matrix operations using sparse matrices in MATLAB are significantly more efficient compared to regular matrix and loop operations. The lower level problem contained 12,781 continuous decision variables (12,781 links in the network) and the upper level problem included 3,402 integer decision variables (3,402 feasible links for the AD subnetwork). The average computation time for an optimization run in this study was approximately 28 hours.


## 3.1. Description

The concept of optimal AD subnetworks with AV-ready subnetworks, dedicated AV links, and dedicated AV lanes is demonstrated in this section using a case study of the road network of the Amsterdam metropolitan region. The network and demand data of the VENOM model [39] are used here. They are based on the real network and demand patterns of the Amsterdam metropolitan region. The original network includes 52,812 directed links, 19,734 nodes, and 3722 transportation zones. In this case study, the transportation zones are aggregated to 102 zones (10,124 OD pairs) and all the links that are not used in the traffic assignment of the base case scenario (in the morning peak) are eliminated. Therefore, the considered study area contains 12,781 links and 6,642 OD pairs. The network and the equilibrium flows in the base case are shown in Figure 3(a). The calibrated demand matrices in VENOM model for the year 2004 are used to extract the demand for cars. The demand for AVs is considered via four scenarios with 10%, 30%, 50%, and 90% MPR of AVs. All demand from, to, and through the study area is considered in the traffic assignment to calculate the equilibrium flows (NEM-FP). Network performance indicators are reported for the OD pairs inside the study area. One average morning peak hour is modeled in this study, which is assumed to account for 10% of the daily traffic, and the value of TTC obtained is converted to a yearly basis using σ=10×30×12 for calculation of the OF value in (14). The value of discount rate π is 4%, which is the common value used for public investments in the Netherlands, and the length of the planning horizon t is assumed to be 10 years. All OF values reported in this study are divided by 106 for convenience. The base case traffic pattern is shown in Figure 3(b).Figure 3
Feasible links for AD subnetwork and base case traffic patterns in Amsterdam network. (a) Feasible links for AD subnetwork. (b) Base case traffic patterns.
(a)(b)The capacity gain from converting a regular link to a dedicated AV link is assumed to be 100%Δa2=2, and the capacity gain of converting a lane to a dedicated AV lane is assumed to be 50% Δa3=1.5. Studies that proposed deployment of networks of dedicated AV links [21] and lanes [19] have used the values 3 and 2.5 for Δa2 and Δa3, respectively. However, microsimulation studies of dedicated AV lanes suggest that these values are overly optimistic (see, for instance, [1, 2, 4]). Therefore, we have selected the input values for capacity gains according to the results of the mentioned microsimulation studies and performed a sensitivity analysis (reported in Section 3.2.6) to investigate the effect of deviations from these values on model results. Converting a link to an AV-ready link for mixed traffic does not lead to any explicit capacity increase Δa1=1. Instead, the PCE value of driving in AD mode γ1 on AV-ready links is assumed to be 0.9 for AV MPRs below 40% and 0.8 for above 40% AV MPR [40]. The PCE value of driving in MD mode γ0 is set to 1. VoTT for MD mode η0 is 9 €/h, and VoTT for AD mode η1 is 80% of this value [32]. Fixed driving cost per kilometer for MD mode c¯0,a is 0.19 €/km. For the AD mode, c¯1,a is 80% of 0.19 €/km when AV MPR is below 40% and 60% of 0.19 €/km when AV MPR is above above 40% [41, 42]. These values are similar to those used in [25] where a sensitivity analysis is also provided, which shows that minor deviations from these values will not significantly impact the results. The logit model route choice parameter μk value used for both classes is −0.5 [43].Regarding the parameters of the upper level solution algorithm, the population size is 600, maximum number of generations is 500, the sample size for extension and reduction operations is 0.1% of the number of decision variables, and the population fractions assigned to operations extension, reduction, and merging are 0.2, 0.2, and 0.6, respectively. The number of iterations used for the convergence of the lower level solution algorithm is 50. These values were selected after extensive hyperparameter tuning with the aim of obtaining the lowest possible value for the objective function in each scenario with feasible computation times.Motorways, major regional roads, and main urban roads are considered feasible links for AD subnetwork in this case study. The purpose of this selection is to avoid complex interactions including AVs and vulnerable road users that might compromise safe operation of AVs in AD mode. This is consistent with the findings of AV accident reports, which indicate that around 90% of the accidents involving AVs have occurred at urban intersections [44]. Moreover, about half of the AV disengagements in California have happened in small urban streets [9], which are not considered as feasible links in this study. A total of 3,402 links is considered feasible in this case study. They are also depicted in Figure 3(a).As for the adjustment costsκas, different values per kilometer are used for each road type and each subnetwork type. The adjustment cost value for AV-ready links κa1 is assumed to be 50,000 €/km for motorways, 75,000 €/km for regional roads, and 100,000 €/km for urban roads. The reason for the increase in adjustment costs from motorways to regional roads and urban roads is that motorways generally have higher quality standards and require minimal interaction with other road users due to segregated traffic and off-grade intersections. Regional roads can have lower standards and require more interaction with other road users, thereby requiring higher adjustment costs to make them suitable for AVs. Finally, urban roads are the most challenging ones for AVs due to complex interactions between AVs and other road users. Therefore, they have the highest adjustment costs. Figure 4 depicts road types in Amsterdam case study. For dedicated AV links, κa2 is twice the value of κa1 for each road type. The adjustment cost values for dedicated AV lanes κa3 are 50% higher than the values of κa1 for each road type. In real applications, these values can be estimated in more detail by experts.Figure 4
Road types and number of lanes for feasible AD subnetwork links in Amsterdam road network. (a) Road types. (b) Number of lanes.
(a)(b)


## 3.2. Results and Analysis

In this section, we first discuss the consistency of AD subnetworks generated by the evolutionary heuristic solution method proposed in this study for real road networks. Then, we discuss the impacts of simultaneous deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes on road network performance, the usage of different road types in the network, and the usage of AD mode on different road types and subnetworks. In addition, we evaluate the distribution of TTC, TTT, and TTD on each subnetwork. Computation times of the experiments are discussed at the end of this section.


### 3.2.1. Consistency of AD Subnetworks in Real Road Networks

Figure5 depicts the graphs obtained by the heuristic solution method introduced earlier as (near) optimal AD subnetworks in all four scenarios. In this section, we discuss three characteristics related to the logical consistency of AD subnetworks in real road networks, which are not observed in theoretical networks that are commonly used as case studies in scientific literature. These characteristics are connectivity, suboptimality, and continuity in network hierarchy. We briefly discuss them in the following.Figure 5
AD subnetworks obtained by the evolutionary heuristic solution for the Amsterdam case study. (a) 10% MPR. (b) 30% MPR. (c) 50% MPR. (d) 90% MPR.(1) Connectivity. Connectivity of a graph representing an AD subnetwork (constraint (21)) is an undeniable requirement for the efficiency of AD mode. However, common solution methods for NDP are not equipped to cope with this constraint effectively. It is shown in [25] that without this constraint, incoherent subnetworks with numerous disconnected islands of links can be obtained as (near) optimal solutions. Tailored algorithms such as the evolutionary algorithm developed in this study can satisfy this constraint in an efficient manner, yet they do not necessarily find the global optimum of the problem.(2) Suboptimality. Suboptimality of the results is another characteristic that needs to be considered. The solutions provided by the heuristic algorithm introduced in this study are not necessarily optimal. The algorithm effectively copes with the connectivity constraint and generates plausible solutions with reasonable computation times, yet there is no guarantee for optimality of the solutions. This is caused by the well-known complexity of bilevel NDPs with discrete decision variables along with the large problem size due to the use of a realistic road network that makes the problem very challenging to solve for the global optimum. Therefore, this might introduce some degree of inconsistency in the resulting graphs as well.(3) Continuity. When considering three types of subnetworks, it seems plausible to expect long stretches of roads selected for each single subnetwork, which are connected to each other at junctions. However, as demonstrated in Figure 4, road types (and consequently the network hierarchy) are not fully continuous in the network of Amsterdam; there are long stretches of roads that are classified as urban roads in some parts and as regional roads in some other parts. In addition, there are many stretches of roads in this network with fluctuating number of lanes. Perhaps these phenomena can be observed in all real road networks. Since each subnetwork is more suitable for certain types of roads with certain number of lanes, the discontinuity in road types and lane numbers causes discontinuity in subnetwork types. For instance, single-lane roads, which constitute a large proportion of roads in this network, as well as motorway on-ramps and off-ramps and main regional roads with occasional single-lane stretches in between are not feasible for dedicated AV lanes. These types of links are suitable for mixed traffic at any AV MPR during the transition period. This also explains the gaps with AV-ready links in between stretches of dedicated AV lanes. Comparing the (near) optimal graphs obtained by the solution method (Figure 5) with the map of the Amsterdam network including the number of lanes and road types (Figure 4) corroborates this notion.


### 3.2.2. Network Performance

Table3 summarizes the performance of the road network in presence of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes using three key performance indicators (KPIs), namely, TTC, TTT, and TTD. Furthermore, three criteria for assessing the trade-off between costs and benefits of deploying AD subnetworks are reported. These criteria are OF, TAC, and total discounted travel cost saving (TDTCS). TDTCS represents the net present value of TTC savings (compared to the base case) in each scenario over the entire planning horizon.Table 3
Key performance indicators for network of Amsterdam (indexing is based on the base case).
Class0% MPR (base case)TTC (€)TTT (h)TTD (km)All cars611,70435,6561,530,51410% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV89.52%89.22%89.85%AV8.87%9.91%10.03%All cars17,647323,021,01498.39%99.13%99.88%73,918,28930% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV69.93%70.12%69.72%AV26.25%29.30%30.12%All cars17,288766,422,53096.18%99.42%99.84%108,941,63750% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV49.14%48.54%49.79%AV40.02%48.23%50.30%All cars16,0372,174,874,40489.16%96.77%100.09%111,967,17190% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV9.70%9.42%10.00%AV73.92%91.21%90.45%All cars15,0453,288,394,04883.61%100.63%100.45%111,280,505The values of TDTCS in all scenarios are substantially higher than TAC values (e.g., for 50% MPR, the TDTCS to TAC ratio is approximately 20). This means the benefits significantly outweigh the infrastructure adjustment costs. In general, the results show a steady decrease in TTC with the increase in MPR of AVs. The decrease in TTC is rather linear until 30% AV MPR, but there is a sharp acceleration in the decrease starting from 50% AV MPR. Moreover, the AV class observes a larger proportion of TTC benefits compared to the RV class in all scenarios; nonetheless, RVs are better off in terms of TTC compared to the base case in all scenarios. This indicates a major improvement in overall network performance with combined deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes.TTT values are also less than the base case values for all classes in all scenarios except for 30% MPR where RVs observe a minor increase in TTT (in proportion to their market size). However, the general magnitude of the decrease in TTT is smaller compared to TTC. One interpretation for this phenomenon is that in addition to congestion relief and more traffic efficiency due to rerouting, a proportion of the gains in TTC is due to lower VoTT values for AD mode.TTD for all vehicles is slightly decreasing until 30% MPR, and then it starts to increase. Nevertheless, RVs and AVs exhibit different trajectories in this regard. For RVs, in all scenarios, TTD values (proportional to their market size) are lower compared to the base case, while the values of TTD for AVs are slightly higher in all scenarios compared to the base case. This is mostly due to rerouting of AVs towards parts of the network with dedicated infrastructure. It is noteworthy that both classes have lower TTT in most scenarios despite the overall higher TTD.The OF values steadily decrease with higher MPR of AVs. This is because larger reductions in TTC values are possible with higher AV MPR, while total adjustment cost (TAC) values stay rather steady after 30% MPR scenario. A remarkable observation is that the TAC value of the 90% MPR scenario is marginally lower compared to 50% MPR, even though OF and TTC values are lower. This means higher traffic efficiency benefits can become available with high MPR of AVs even with less investment on infrastructure.


### 3.2.3. Distribution of Traffic among Road Types

The next factor we analyze in this paper is the impact of AD subnetwork deployment on the usage of different road types. We focus on 50% MPR scenario to show the usage of different road types and compare statistics of RVs and AVs. Table4 summarizes the distribution of network performance indicators on different road types indexed according to the base case values for the 50% MPR scenario. Therefore, comparing the values of RV and AV rows with 50% (and similarly the values of “all cars” rows with 100%) shows the percentage difference in each performance indicator on each road type compared to the base case scenario.Table 4
Distribution of network performance indicators on different road types for 50% MPR (indexing is based on the values of the base case scenario).
ClassMotorwayRegional roadUrban roadTTC (€)RV48.98%48.52%49.31%AV33.62%37.58%45.01%All cars82.60%86.10%94.32%Base case227,514 (100%)116,651 (100%)186,053 (100%)TTT (h)RV47.60%47.12%48.98%AV48.16%45.59%48.51%All cars95.76%92.70%97.48%Base case8,821 (100%)6,078 (100%)13,314 (100%)TTD (km)RV49.71%49.76%49.92%AV50.65%50.20%49.68%All cars100.36%99.96%99.60%Base case779,589 (100%)326,060 (100%)348,571 (100%)Table4 shows that the TTD on motorways for the 50% MPR scenario is higher compared to the base case, while regional roads and urban roads are used less intensively in this scenario compared to the base case. It is also evident that RVs have lower usages of all road types (i.e., they opt for shorter routes) compared to the base case scenario, whereas AVs travel more using motorways and regional roads and less using urban roads (i.e., they opt for longer routes). This can logically be explained by the fact that most motorways and regional roads are part of the AD subnetwork. TTC and TTT values are lower in all road types for both classes in spite of higher TTD, with motorways and regional roads showing the highest impacts for AVs.Since motorways generally are the safest roads, the shift of traffic towards motorways can provide traffic safety benefits. However, AD subnetworks attract AVs towards roads that are higher in network hierarchy and RVs towards lower ones, which leads to uneven distribution of traffic safety benefits between AV and RV classes.


### 3.2.4. Distribution of ADS Usage among Different Subnetworks

Table5 summarizes the statistics related to performance indicators for the AV class and AD mode, as well as the usage of each subnetwork and its impact on network performance indicators. The autopilot column is the summation of the values of all three subnetworks. In all scenarios, around 70% of TTD for AVs is in AD mode, which is very high given that the length of all feasible roads for AD subnetworks A1 is 26% of the length of all roads in the network. Yet this approximately 70% of TTD for the AV class in AD mode only accounts for approximately 43% of TTT and 50% of TTC of this class on average. This is partly due to the efficiency of AD mode and partly due to the compartmentalization of traffic among different road types as a result of the combined AD subnetwork deployment that draws AVs towards main roads having higher speeds and partially repels RVs from them.Comparing the ratios of TTC and TTT to TTD for different subnetworks reveals that dedicated AV lanes provide more traffic efficiency benefits in comparison to the AV-ready subnetwork. The reason is the higher capacity gains of dedicated AV lanes. On the other hand, dedicated AV links are rarely selected in (nearly) optimal plans since they can compromise the accessibility of RVs when there is no alternative route for them. Even when there are alternative routes available, rerouting all RV traffic can direct too much flow to certain links and lead to inefficient distribution of traffic throughout the network.Regarding the distance traveled in AV-ready subnetwork and dedicated AV lanes, in 10% MPR scenario, the AV-ready subnetwork is chosen more frequently with 63% of the TTD of AV class versus 7% for dedicated AV lanes. However, as MPR of AVs increases, this balance shifts towards dedicated AV lanes until the 50% MPR scenario when 46% of the TTD of AVs is on these lanes while the share of AV-ready subnetwork drops to 28%. With the increase of AV MPR to 90%, the ratio changes to 39% versus 34% in favor of dedicated AV lanes. The transition from 50% to 90% can be explained by the fact that there are many two-lane roads in the network, and thus assigning 50% of the capacity to 90% of traffic is not efficient considering that dedicated AV lanes are more expensive than AV-ready links. In this case, the extra capacity gain of dedicated lanes does not compensate for the loss of cost and efficiency.In order for dedicated AV lanes to be efficient in terms of traffic distribution, the number of these lanes should be proportional to the share of traffic to which the lanes are dedicated. However, in real networks, situations such as the one mentioned earlier with 90% AV volume and only 50% of capacity (i.e., one out of two lanes) available for them are inevitable.Table 5
Network performance indicators for the AV class in all subnetworks (indexing is based on AV class column).
AV-ready subnetworkDedicated AV linksDedicated AV lanesAutopilot (AD mode)AV class10% MPRTTC (€)44.83%0.06%4.59%49.47%100.00%TTT (h)38.21%0.06%3.31%41.55%100.00%TTD (km)62.57%0.08%7.07%69.72%100.00%30% MPRTTC (€)28.82%0.12%23.43%52.37%100.00%TTT (h)26.58%0.11%16.94%43.63%100.00%TTD (km)37.52%0.15%35.52%73.19%100.00%50% MPRTTC (€)19.49%0.11%28.39%47.99%100.00%TTT (h)18.89%0.11%23.84%42.84%100.00%TTD (km)27.72%0.15%45.57%73.44%100.00%90% MPRTTC (€)22.36%0.05%26.57%48.97%100.00%TTT (h)20.20%0.04%24.92%45.16%100.00%TTD (km)34.09%0.07%39.15%73.31%100.00%


### 3.2.5. Distance Coverage of Subnetworks

As it is shown in Table6, considering all four scenarios, 51–59% of all roads selected for all subnetworks are motorways, 27–30% are regional roads, and 13–19% are urban roads. Motorways constitute around two-thirds of dedicated AV lanes in all scenarios while regional roads have a slightly higher share of the other one-third compared to urban roads. For the AV-ready subnetwork, the ratios change drastically in different scenarios. At 10% MPR, more than half of AV-ready links are motorways, and regional roads cover around two-third of the rest. Starting from 30% MPR, regional roads have the highest share of AV-ready links with percentages slightly less than 50% of AV-ready links in most scenarios. Urban roads contribute to around 20% of AV-ready links in all scenarios except for 10% MPR when their share is slightly more than 10%.Table 6
Distance coverage of each subnetwork (km) in each road type.
10% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways46.43%0.09%12.03%58.55%Regional roads25.09%0.28%2.35%27.82%Urban roads10.90%0.19%2.63%13.63%All roads82.42%0.66%17.01%1,064 (100%)30% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways19.33%0.15%31.70%51.18%Regional roads19.94%0.38%9.55%29.87%Urban roads10.54%0.46%7.87%18.95%All roads49.89%0.99%49.20%1,309 (100%)50% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways14.18%0.08%36.81%51.07%Regional roads18.52%0.30%10.98%29.80%Urban roads9.91%0.38%8.77%19.13%All roads42.61%0.76%56.55%1,312 (100%)90% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways16.32%0.08%34.71%51.11%Regional roads18.23%0.23%11.21%29.67%Urban roads9.92%0.15%9.08%19.22%All roads44.47%0.46%55.07%1,311 (100%)The total length of the AV-ready subnetwork and dedicated AV lanes follows a similar trend to the distance traveled in each subnetwork, which was discussed in the previous section, with AV-ready links having a larger share at first (10% MPR), dedicated AV lanes reaching them at 30% MPR, and the ratio slightly balancing in 90% MPR again. Share of dedicated AV links is insignificant in all scenarios.Therefore, regarding suitability of each subnetwork for different AV MPRs, it can be concluded that AV-ready subnetworks are more suitable for low MPRs of AVs. However, with the increase in AV MPR, dedicated AV lanes become more effective until a point where the share of AVs gets so high that their traffic efficiency benefits can be fully realized, even in mixed traffic. It is noteworthy that certain parts of road networks such as on-ramps, off-ramps, and single-lane roads are exclusively suitable for mixed traffic as long as RVs are on the roads.


### 3.2.6. Sensitivity Analysis

In this study, we used the knowledge available so far in academic literature to estimate the values of extra capacity gain and infrastructure adjustment costs for AV-ready subnetworks, dedicated AV lanes, and dedicated AV links. However, these values are estimates with high uncertainty, and the real values might deviate from these estimates. Therefore, we perform a sensitivity analysis for these parameters to investigate the impacts of deviations from these values on results. We provide two sensitivity analysis variations for each subnetwork, namely, the optimistic case and the pessimistic case. In the optimistic case, the analyzed subnetwork is assumed to be more efficient with regard to the trade-off between capacity gain and adjustment cost compared to the original scenario in order to estimate the upper bound of the subnetwork’s impacts. This is achieved via decreasing the link adjustment cost by 50% and increasing the link capacity by 50% (for AV-ready subnetwork, the increase in capacity is realized via decreasing the PCE value for AVs within the subnetwork). For the pessimistic case, the analyzed subnetwork is assumed to be less efficient by means of 50% higher adjustment cost and 50% lower capacity gain compared to the original scenario in order to estimate the lower bound of the subnetwork’s impacts. Table7 summarizes the results of the sensitivity analysis for the 50% MPR scenario.Table 7
Sensitivity analysis for 50% MPR scenario.
Analyzed subnetworkParameter deviationPerformance deviationCapacityΔasCostκasPCEγ1OFTTCTTTTTDTACAV-ready subnetwork—-50%−50%−01.24%−00.89%−01.85%+00.06%−50.66%—+50%+50%+03.66%+03.41%+04.83%−00.06%+37.08%Dedicated AV links+50%−50%—+00.51%+00.54%+00.98%00.00%−03.61%−50%+50%—+00.40%+00.41%+00.65%+00.05%−01.21%Dedicated AV lanes+50%−50%—+00.03%+00.20%+00.11%+00.07%−23.70%−50%+50%—+01.68%+01.51%+03.14%−00.03%+25.43%Notable changes in KPIs (i.e., TTC, TT, and TTD) due to deviations in capacity and adjustment cost parameters are TTT and TTC increases (maximum 5% compared to the original 50% MPR scenario) in pessimistic variations of AV-ready subnetworks and dedicated AV lanes. This was to be expected, particularly since both capacity and link adjustment cost were modified simultaneously. The rest of the variations indicate no major deviation in KPIs. Conversely, for TAC, significant changes are observed in all variations, with AV-ready subnetwork showing the most sensitivity (37–49% change), dedicated AV lanes showing relatively lower sensitivity (around 25% change), and dedicated AV links displaying the least sensitivity (less than 5%) to deviations in adjustment cost and capacity changes. This means with reasonable deviations in values of input parameters, comparable gains in KPIs can be achieved, only with more or less budget depending on the direction of the deviations. Regarding the trade-off between costs and benefits, among all sensitivity analysis scenarios considered here, the lowest value of the TDTCS to TAC ratio, which is approximately 20 in the original 50% scenario, is around 18, which belongs to the pessimistic scenario for the AV-ready subnetwork. These are useful insights for planners since they show that when deploying AD subnetworks, the main uncertain factor is the amount of budget required for the project, yet the improvement in the performance of the network is rather stable with moderate deviations in input.


### 3.2.7. A Note on Computations

The mathematical model and the solution algorithm introduced in this study were coded in MATLAB and ran on a Windows PC with a Core i5-8600 CPU @ 3.10 GHz and 32 GB RAM. Since population-based algorithms such as the one developed in this study can be implemented more efficiently using parallel computation architectures, the Parallel Computation Toolbox in MATLAB with 6 computation units was used to utilize the efficiency of parallel computing in order to perform fitness evaluations for multiple solutions simultaneously. Moreover, sparse matrices in MATLAB were used for all matrix operations on assignment maps to minimize the computation times of the MSA-based algorithm used to solve the lower level problem. It is noteworthy that since assignment maps for large-scale networks include very few nonzero elements (i.e., they are very sparse), matrix operations using sparse matrices in MATLAB are significantly more efficient compared to regular matrix and loop operations. The lower level problem contained 12,781 continuous decision variables (12,781 links in the network) and the upper level problem included 3,402 integer decision variables (3,402 feasible links for the AD subnetwork). The average computation time for an optimization run in this study was approximately 28 hours.


## 3.2.1. Consistency of AD Subnetworks in Real Road Networks

Figure5 depicts the graphs obtained by the heuristic solution method introduced earlier as (near) optimal AD subnetworks in all four scenarios. In this section, we discuss three characteristics related to the logical consistency of AD subnetworks in real road networks, which are not observed in theoretical networks that are commonly used as case studies in scientific literature. These characteristics are connectivity, suboptimality, and continuity in network hierarchy. We briefly discuss them in the following.Figure 5
AD subnetworks obtained by the evolutionary heuristic solution for the Amsterdam case study. (a) 10% MPR. (b) 30% MPR. (c) 50% MPR. (d) 90% MPR.(1) Connectivity. Connectivity of a graph representing an AD subnetwork (constraint (21)) is an undeniable requirement for the efficiency of AD mode. However, common solution methods for NDP are not equipped to cope with this constraint effectively. It is shown in [25] that without this constraint, incoherent subnetworks with numerous disconnected islands of links can be obtained as (near) optimal solutions. Tailored algorithms such as the evolutionary algorithm developed in this study can satisfy this constraint in an efficient manner, yet they do not necessarily find the global optimum of the problem.(2) Suboptimality. Suboptimality of the results is another characteristic that needs to be considered. The solutions provided by the heuristic algorithm introduced in this study are not necessarily optimal. The algorithm effectively copes with the connectivity constraint and generates plausible solutions with reasonable computation times, yet there is no guarantee for optimality of the solutions. This is caused by the well-known complexity of bilevel NDPs with discrete decision variables along with the large problem size due to the use of a realistic road network that makes the problem very challenging to solve for the global optimum. Therefore, this might introduce some degree of inconsistency in the resulting graphs as well.(3) Continuity. When considering three types of subnetworks, it seems plausible to expect long stretches of roads selected for each single subnetwork, which are connected to each other at junctions. However, as demonstrated in Figure 4, road types (and consequently the network hierarchy) are not fully continuous in the network of Amsterdam; there are long stretches of roads that are classified as urban roads in some parts and as regional roads in some other parts. In addition, there are many stretches of roads in this network with fluctuating number of lanes. Perhaps these phenomena can be observed in all real road networks. Since each subnetwork is more suitable for certain types of roads with certain number of lanes, the discontinuity in road types and lane numbers causes discontinuity in subnetwork types. For instance, single-lane roads, which constitute a large proportion of roads in this network, as well as motorway on-ramps and off-ramps and main regional roads with occasional single-lane stretches in between are not feasible for dedicated AV lanes. These types of links are suitable for mixed traffic at any AV MPR during the transition period. This also explains the gaps with AV-ready links in between stretches of dedicated AV lanes. Comparing the (near) optimal graphs obtained by the solution method (Figure 5) with the map of the Amsterdam network including the number of lanes and road types (Figure 4) corroborates this notion.


## 3.2.2. Network Performance

Table3 summarizes the performance of the road network in presence of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes using three key performance indicators (KPIs), namely, TTC, TTT, and TTD. Furthermore, three criteria for assessing the trade-off between costs and benefits of deploying AD subnetworks are reported. These criteria are OF, TAC, and total discounted travel cost saving (TDTCS). TDTCS represents the net present value of TTC savings (compared to the base case) in each scenario over the entire planning horizon.Table 3
Key performance indicators for network of Amsterdam (indexing is based on the base case).
Class0% MPR (base case)TTC (€)TTT (h)TTD (km)All cars611,70435,6561,530,51410% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV89.52%89.22%89.85%AV8.87%9.91%10.03%All cars17,647323,021,01498.39%99.13%99.88%73,918,28930% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV69.93%70.12%69.72%AV26.25%29.30%30.12%All cars17,288766,422,53096.18%99.42%99.84%108,941,63750% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV49.14%48.54%49.79%AV40.02%48.23%50.30%All cars16,0372,174,874,40489.16%96.77%100.09%111,967,17190% MPRClassOFTDTCS (€)TTC (€)TTT (h)TTD (km)TAC (€)RV9.70%9.42%10.00%AV73.92%91.21%90.45%All cars15,0453,288,394,04883.61%100.63%100.45%111,280,505The values of TDTCS in all scenarios are substantially higher than TAC values (e.g., for 50% MPR, the TDTCS to TAC ratio is approximately 20). This means the benefits significantly outweigh the infrastructure adjustment costs. In general, the results show a steady decrease in TTC with the increase in MPR of AVs. The decrease in TTC is rather linear until 30% AV MPR, but there is a sharp acceleration in the decrease starting from 50% AV MPR. Moreover, the AV class observes a larger proportion of TTC benefits compared to the RV class in all scenarios; nonetheless, RVs are better off in terms of TTC compared to the base case in all scenarios. This indicates a major improvement in overall network performance with combined deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes.TTT values are also less than the base case values for all classes in all scenarios except for 30% MPR where RVs observe a minor increase in TTT (in proportion to their market size). However, the general magnitude of the decrease in TTT is smaller compared to TTC. One interpretation for this phenomenon is that in addition to congestion relief and more traffic efficiency due to rerouting, a proportion of the gains in TTC is due to lower VoTT values for AD mode.TTD for all vehicles is slightly decreasing until 30% MPR, and then it starts to increase. Nevertheless, RVs and AVs exhibit different trajectories in this regard. For RVs, in all scenarios, TTD values (proportional to their market size) are lower compared to the base case, while the values of TTD for AVs are slightly higher in all scenarios compared to the base case. This is mostly due to rerouting of AVs towards parts of the network with dedicated infrastructure. It is noteworthy that both classes have lower TTT in most scenarios despite the overall higher TTD.The OF values steadily decrease with higher MPR of AVs. This is because larger reductions in TTC values are possible with higher AV MPR, while total adjustment cost (TAC) values stay rather steady after 30% MPR scenario. A remarkable observation is that the TAC value of the 90% MPR scenario is marginally lower compared to 50% MPR, even though OF and TTC values are lower. This means higher traffic efficiency benefits can become available with high MPR of AVs even with less investment on infrastructure.


## 3.2.3. Distribution of Traffic among Road Types

The next factor we analyze in this paper is the impact of AD subnetwork deployment on the usage of different road types. We focus on 50% MPR scenario to show the usage of different road types and compare statistics of RVs and AVs. Table4 summarizes the distribution of network performance indicators on different road types indexed according to the base case values for the 50% MPR scenario. Therefore, comparing the values of RV and AV rows with 50% (and similarly the values of “all cars” rows with 100%) shows the percentage difference in each performance indicator on each road type compared to the base case scenario.Table 4
Distribution of network performance indicators on different road types for 50% MPR (indexing is based on the values of the base case scenario).
ClassMotorwayRegional roadUrban roadTTC (€)RV48.98%48.52%49.31%AV33.62%37.58%45.01%All cars82.60%86.10%94.32%Base case227,514 (100%)116,651 (100%)186,053 (100%)TTT (h)RV47.60%47.12%48.98%AV48.16%45.59%48.51%All cars95.76%92.70%97.48%Base case8,821 (100%)6,078 (100%)13,314 (100%)TTD (km)RV49.71%49.76%49.92%AV50.65%50.20%49.68%All cars100.36%99.96%99.60%Base case779,589 (100%)326,060 (100%)348,571 (100%)Table4 shows that the TTD on motorways for the 50% MPR scenario is higher compared to the base case, while regional roads and urban roads are used less intensively in this scenario compared to the base case. It is also evident that RVs have lower usages of all road types (i.e., they opt for shorter routes) compared to the base case scenario, whereas AVs travel more using motorways and regional roads and less using urban roads (i.e., they opt for longer routes). This can logically be explained by the fact that most motorways and regional roads are part of the AD subnetwork. TTC and TTT values are lower in all road types for both classes in spite of higher TTD, with motorways and regional roads showing the highest impacts for AVs.Since motorways generally are the safest roads, the shift of traffic towards motorways can provide traffic safety benefits. However, AD subnetworks attract AVs towards roads that are higher in network hierarchy and RVs towards lower ones, which leads to uneven distribution of traffic safety benefits between AV and RV classes.


## 3.2.4. Distribution of ADS Usage among Different Subnetworks

Table5 summarizes the statistics related to performance indicators for the AV class and AD mode, as well as the usage of each subnetwork and its impact on network performance indicators. The autopilot column is the summation of the values of all three subnetworks. In all scenarios, around 70% of TTD for AVs is in AD mode, which is very high given that the length of all feasible roads for AD subnetworks A1 is 26% of the length of all roads in the network. Yet this approximately 70% of TTD for the AV class in AD mode only accounts for approximately 43% of TTT and 50% of TTC of this class on average. This is partly due to the efficiency of AD mode and partly due to the compartmentalization of traffic among different road types as a result of the combined AD subnetwork deployment that draws AVs towards main roads having higher speeds and partially repels RVs from them.Comparing the ratios of TTC and TTT to TTD for different subnetworks reveals that dedicated AV lanes provide more traffic efficiency benefits in comparison to the AV-ready subnetwork. The reason is the higher capacity gains of dedicated AV lanes. On the other hand, dedicated AV links are rarely selected in (nearly) optimal plans since they can compromise the accessibility of RVs when there is no alternative route for them. Even when there are alternative routes available, rerouting all RV traffic can direct too much flow to certain links and lead to inefficient distribution of traffic throughout the network.Regarding the distance traveled in AV-ready subnetwork and dedicated AV lanes, in 10% MPR scenario, the AV-ready subnetwork is chosen more frequently with 63% of the TTD of AV class versus 7% for dedicated AV lanes. However, as MPR of AVs increases, this balance shifts towards dedicated AV lanes until the 50% MPR scenario when 46% of the TTD of AVs is on these lanes while the share of AV-ready subnetwork drops to 28%. With the increase of AV MPR to 90%, the ratio changes to 39% versus 34% in favor of dedicated AV lanes. The transition from 50% to 90% can be explained by the fact that there are many two-lane roads in the network, and thus assigning 50% of the capacity to 90% of traffic is not efficient considering that dedicated AV lanes are more expensive than AV-ready links. In this case, the extra capacity gain of dedicated lanes does not compensate for the loss of cost and efficiency.In order for dedicated AV lanes to be efficient in terms of traffic distribution, the number of these lanes should be proportional to the share of traffic to which the lanes are dedicated. However, in real networks, situations such as the one mentioned earlier with 90% AV volume and only 50% of capacity (i.e., one out of two lanes) available for them are inevitable.Table 5
Network performance indicators for the AV class in all subnetworks (indexing is based on AV class column).
AV-ready subnetworkDedicated AV linksDedicated AV lanesAutopilot (AD mode)AV class10% MPRTTC (€)44.83%0.06%4.59%49.47%100.00%TTT (h)38.21%0.06%3.31%41.55%100.00%TTD (km)62.57%0.08%7.07%69.72%100.00%30% MPRTTC (€)28.82%0.12%23.43%52.37%100.00%TTT (h)26.58%0.11%16.94%43.63%100.00%TTD (km)37.52%0.15%35.52%73.19%100.00%50% MPRTTC (€)19.49%0.11%28.39%47.99%100.00%TTT (h)18.89%0.11%23.84%42.84%100.00%TTD (km)27.72%0.15%45.57%73.44%100.00%90% MPRTTC (€)22.36%0.05%26.57%48.97%100.00%TTT (h)20.20%0.04%24.92%45.16%100.00%TTD (km)34.09%0.07%39.15%73.31%100.00%


## 3.2.5. Distance Coverage of Subnetworks

As it is shown in Table6, considering all four scenarios, 51–59% of all roads selected for all subnetworks are motorways, 27–30% are regional roads, and 13–19% are urban roads. Motorways constitute around two-thirds of dedicated AV lanes in all scenarios while regional roads have a slightly higher share of the other one-third compared to urban roads. For the AV-ready subnetwork, the ratios change drastically in different scenarios. At 10% MPR, more than half of AV-ready links are motorways, and regional roads cover around two-third of the rest. Starting from 30% MPR, regional roads have the highest share of AV-ready links with percentages slightly less than 50% of AV-ready links in most scenarios. Urban roads contribute to around 20% of AV-ready links in all scenarios except for 10% MPR when their share is slightly more than 10%.Table 6
Distance coverage of each subnetwork (km) in each road type.
10% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways46.43%0.09%12.03%58.55%Regional roads25.09%0.28%2.35%27.82%Urban roads10.90%0.19%2.63%13.63%All roads82.42%0.66%17.01%1,064 (100%)30% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways19.33%0.15%31.70%51.18%Regional roads19.94%0.38%9.55%29.87%Urban roads10.54%0.46%7.87%18.95%All roads49.89%0.99%49.20%1,309 (100%)50% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways14.18%0.08%36.81%51.07%Regional roads18.52%0.30%10.98%29.80%Urban roads9.91%0.38%8.77%19.13%All roads42.61%0.76%56.55%1,312 (100%)90% MPRRoad typeAV-ready subnetworkDedicated AV linksDedicated AV lanesAll subnetworksMotorways16.32%0.08%34.71%51.11%Regional roads18.23%0.23%11.21%29.67%Urban roads9.92%0.15%9.08%19.22%All roads44.47%0.46%55.07%1,311 (100%)The total length of the AV-ready subnetwork and dedicated AV lanes follows a similar trend to the distance traveled in each subnetwork, which was discussed in the previous section, with AV-ready links having a larger share at first (10% MPR), dedicated AV lanes reaching them at 30% MPR, and the ratio slightly balancing in 90% MPR again. Share of dedicated AV links is insignificant in all scenarios.Therefore, regarding suitability of each subnetwork for different AV MPRs, it can be concluded that AV-ready subnetworks are more suitable for low MPRs of AVs. However, with the increase in AV MPR, dedicated AV lanes become more effective until a point where the share of AVs gets so high that their traffic efficiency benefits can be fully realized, even in mixed traffic. It is noteworthy that certain parts of road networks such as on-ramps, off-ramps, and single-lane roads are exclusively suitable for mixed traffic as long as RVs are on the roads.


## 3.2.6. Sensitivity Analysis

In this study, we used the knowledge available so far in academic literature to estimate the values of extra capacity gain and infrastructure adjustment costs for AV-ready subnetworks, dedicated AV lanes, and dedicated AV links. However, these values are estimates with high uncertainty, and the real values might deviate from these estimates. Therefore, we perform a sensitivity analysis for these parameters to investigate the impacts of deviations from these values on results. We provide two sensitivity analysis variations for each subnetwork, namely, the optimistic case and the pessimistic case. In the optimistic case, the analyzed subnetwork is assumed to be more efficient with regard to the trade-off between capacity gain and adjustment cost compared to the original scenario in order to estimate the upper bound of the subnetwork’s impacts. This is achieved via decreasing the link adjustment cost by 50% and increasing the link capacity by 50% (for AV-ready subnetwork, the increase in capacity is realized via decreasing the PCE value for AVs within the subnetwork). For the pessimistic case, the analyzed subnetwork is assumed to be less efficient by means of 50% higher adjustment cost and 50% lower capacity gain compared to the original scenario in order to estimate the lower bound of the subnetwork’s impacts. Table7 summarizes the results of the sensitivity analysis for the 50% MPR scenario.Table 7
Sensitivity analysis for 50% MPR scenario.
Analyzed subnetworkParameter deviationPerformance deviationCapacityΔasCostκasPCEγ1OFTTCTTTTTDTACAV-ready subnetwork—-50%−50%−01.24%−00.89%−01.85%+00.06%−50.66%—+50%+50%+03.66%+03.41%+04.83%−00.06%+37.08%Dedicated AV links+50%−50%—+00.51%+00.54%+00.98%00.00%−03.61%−50%+50%—+00.40%+00.41%+00.65%+00.05%−01.21%Dedicated AV lanes+50%−50%—+00.03%+00.20%+00.11%+00.07%−23.70%−50%+50%—+01.68%+01.51%+03.14%−00.03%+25.43%Notable changes in KPIs (i.e., TTC, TT, and TTD) due to deviations in capacity and adjustment cost parameters are TTT and TTC increases (maximum 5% compared to the original 50% MPR scenario) in pessimistic variations of AV-ready subnetworks and dedicated AV lanes. This was to be expected, particularly since both capacity and link adjustment cost were modified simultaneously. The rest of the variations indicate no major deviation in KPIs. Conversely, for TAC, significant changes are observed in all variations, with AV-ready subnetwork showing the most sensitivity (37–49% change), dedicated AV lanes showing relatively lower sensitivity (around 25% change), and dedicated AV links displaying the least sensitivity (less than 5%) to deviations in adjustment cost and capacity changes. This means with reasonable deviations in values of input parameters, comparable gains in KPIs can be achieved, only with more or less budget depending on the direction of the deviations. Regarding the trade-off between costs and benefits, among all sensitivity analysis scenarios considered here, the lowest value of the TDTCS to TAC ratio, which is approximately 20 in the original 50% scenario, is around 18, which belongs to the pessimistic scenario for the AV-ready subnetwork. These are useful insights for planners since they show that when deploying AD subnetworks, the main uncertain factor is the amount of budget required for the project, yet the improvement in the performance of the network is rather stable with moderate deviations in input.


## 3.2.7. A Note on Computations

The mathematical model and the solution algorithm introduced in this study were coded in MATLAB and ran on a Windows PC with a Core i5-8600 CPU @ 3.10 GHz and 32 GB RAM. Since population-based algorithms such as the one developed in this study can be implemented more efficiently using parallel computation architectures, the Parallel Computation Toolbox in MATLAB with 6 computation units was used to utilize the efficiency of parallel computing in order to perform fitness evaluations for multiple solutions simultaneously. Moreover, sparse matrices in MATLAB were used for all matrix operations on assignment maps to minimize the computation times of the MSA-based algorithm used to solve the lower level problem. It is noteworthy that since assignment maps for large-scale networks include very few nonzero elements (i.e., they are very sparse), matrix operations using sparse matrices in MATLAB are significantly more efficient compared to regular matrix and loop operations. The lower level problem contained 12,781 continuous decision variables (12,781 links in the network) and the upper level problem included 3,402 integer decision variables (3,402 feasible links for the AD subnetwork). The average computation time for an optimization run in this study was approximately 28 hours.


## 4. Conclusions

In this study, we proposed a unified formulation for simultaneous deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes and modeled the problem as a bilevel network design problem. The upper level represents the decisions regarding links to be selected as part of the mentioned subnetworks to optimize the trade-off between infrastructure adjustment cost and the total system travel cost, while the lower level includes a network equilibrium model that captures the travelers’ responses to new network topologies with their route choices. We proposed a heuristic solution method to solve the problem and demonstrated the applicability of the model as well as the solution method on the large-scale road network of the Amsterdam metropolitan region.The results indicated that simultaneous deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes is effective and can deliver meaningful network performance improvements in terms of TTC and TTT while causing a slight increase in TTD, particularly for AVs. We also showed that TDTCS values significantly outweigh TAC values in all scenarios, especially after reaching 50% AV MPR where TDTCS can be as much as 20 times higher than TAC. Even in the pessimistic scenarios considered in the sensitivity analysis with higher link adjustment costs and lower capacity gains, this ratio is never less than 18 for the 50% MPR scenario.One essential finding of this study is that different subnetworks are relevant for different AV MPRs. For lower MPRs, AV-ready subnetworks, which accommodate AVs in mixed traffic, appear to be the most efficient configuration, but after 30% AV MPR, dedicated AV lanes prove to be more beneficial, particularly for motorways. This can be used as a guideline for planners to develop their strategies regarding road network infrastructure during the transition period to full automation. In addition, the results suggest that road types play a crucial role in the choice of network configuration as well. Motorway on-ramps and off-ramps, single-lane roads, and major regional roads that include sections with a single lane are almost exclusively selected for mixed traffic in (near) optimal configurations, while the majority of dedicated AV lanes appear on motorways.Dedicated AV links were rarely selected by our model because compromising the accessibility of RVs was penalized in this study. Furthermore, the radial structure of the Amsterdam network does not offer many alternative routes, which makes it more difficult to satisfy the RV demand when some links are dedicated to AVs and there is no alternative route for RVs. Even when there are alternative routes available for RVs, rerouting all RV traffic can direct too much flow to certain links and lead to inefficient distribution of traffic throughout the network. Nonetheless, dedicated AV links might be a viable option for urban areas with grid networks that provide more possibilities for compartmentalization of traffic. Moreover, these links might be useful as dedicated links for automated shuttles to be used as public transport in order to serve the demand of the class of travelers who do not have access to vehicles.Based on the sensitivity analysis, it can be concluded that despite the uncertain development path of AVs, network performance benefits delivered by simultaneous deployment of AV-ready subnetworks, dedicated AV links, and dedicated AV lanes are rather stable, and the most uncertain factor of the deployment project is the required budget for deployment. Furthermore, it was shown that the results depend more on the design concept (mixed traffic and dedicated links and lanes) rather than input parameters and the deployment cost of each concept, at least in 50% AV MPR scenario. This means that the inherent characteristics of the design concepts themselves have a stronger influence on the results compared to their deployment cost and capacity gains.It was shown in this study that the optimal deployment plan of AD subnetworks is dependent on the level of AV demand. Our results indicate that AV-ready subnetworks for mixed traffic are the most suitable configuration for low MPRs of AVs, and after 30% AV MPR, dedicated AV lanes become more relevant. Yet the results also indicate that for 90% AV MPR, AV-ready subnetworks are more suitable than dedicated AV lanes for about half of the roads in the network. This suggests that developing a multistage model that starts each stage with the network topology obtained during the previous stage can be beneficial as well. However, according to our model, there is no noticeable difference between the 50% MPR scenario and the 90% MPR scenario with respect to the location of links to include in the AD subnetwork. This implies that if the costs of changing dedicated AV lanes to AV-ready links for mixed traffic were to be relatively low, a scenario-based approach would be sufficient for real applications.Possible improvements of the model and future research directions are listed below.Incorporation of a time dimension into the problem by considering a multistage bilevel network design model.Considering other objectives in addition to TTC and TAC, such as traffic safety, emissions, and accessibility.Using dynamic traffic assignment models including detailed representation of intersections.Modeling other travel modes including public transport, active modes, and combined modes.



---

*Source: 8853583-2021-03-26.xml*