Benders' decomposition for freeway network design under endogenous autonomous vehicles demand

Autonomous vehicles (AVs) have the potential to provide cost-effective mobility options along with overall system-level benefits in terms of congestion and vehicular emissions. Additional resource allocation at the network level, such as AV-exclusive lanes, can further foster the usage of AVs rendering this mode of travel more attractive than legacy vehicles (LV). In this study, we propose an integrated mixed-integer programming framework for optimal AV-exclusive lane design on a freeway network which accounts for commuters' demand split among AVs and LVs via a logit model. We incorporate the link transmission model (LTM) as the underlying traffic flow model. The LTM is modified to integrate two vehicle classes namely, LVs and AVs with a lane-based approach. The presence of binary variables to represent lane design and the logit model for endogenous demand estimation results in a nonconvex mixed-integer nonlinear program (MINLP) formulation. We propose a Benders' decomposition approach to tackle this challenging optimization problem. Our approach iteratively explores possible lane designs in the Benders' master problem and, at each iteration, solves a sequence of system-optimum dynamic traffic assignment (SODTA) problems which is shown to converge to fixed-points representative of logit-compatible demand splits. Further, we prove that the proposed solution method converges to a local optima of the nonconvex problem and identify under which conditions this local optima is a global solution. The proposed approach is implemented on two hypothetical freeway networks with single and multiple origins and destinations. Our numerical results reveal that the optimal lane design of freeway network is non-trivial and can inform on the value of accounting for endogenous demand in the proposed freeway network design problem.


Introduction
As mobility demand increases, transport infrastructures remain under-utilized majorly due to various human factors e.g., slow reflexes, poor and heterogeneous driving behaviour, safety concerns etc. Automation in transport sector is gaining more attention than ever to minimize these human inputs to exploit transport resources in an efficient and sustainable way. This growing attention in automation translates to a projected growth of US$173B in global autonomous driving market by 2030 [30]. Potential benefits of autonomous vehicles (AV) include improved throughput [29,35,12], traffic safety [5], travel speed, energy consumption [20] and vehicular emissions [7].
Regardless of the benefits of AVs, one would be too naive to assume that AVs will be immediately adopted by legacy vehicle (LV) owners in near future. A more reasonable assumption would be the existence of a transition period where interactions between LVs and AVs exist, leading to a gradual increment in market penetration of AVs. This transition period will be crucial as safety might be compromised in mixed operations of LVs and AVs, especially in case of arterial networks, involving pedestrians, cyclists and signalized intersections. In these arterial networks with heterogeneous traffic, fewer AVs have been found to have a negative impact on the average travel speed and string stability of the traffic flow [34,31,22]. During this transition period, the safety concerns due to mixed vehicular interactions could be minimised with AV-exclusive lanes segregating AVs and LVs in a network, providing a smooth transition of the current transport system to an automation-heavy transport system. These dedicated lanes would be advantageous in the current situation of imperfect AV technologies, which pose critical problems in traffic safety during lane changing in a congested network with mixed traffic. At network intersections, reservation-based models have been shown to have the potential to increase intersection capacity [3,4,25,14]. More recently, Rey and Levin [27] proposed a hybrid network control policy in such networks with dedicated lanes that provide access to "blue phases" during which only AVs can traverse traffic intersections.
Yu et al. [39] adopted a microscopic traffic simulation method to investigate the efficiency and safety of mixed traffic on highways with AV-exclusive lanes. Although, the safety of mixed traffic was found to be worsened with low market penetration of AVs, the simulation results from the car-following models of this study showed an increment of up to 84% in throughput of the traffic network due to presence of AV-exclusive lanes. These dedicated lanes may also facilitate cooperative adaptive cruise control (CACC) contributing to better traffic flow performance [34], improved highway capacity [21], decrease in fuel consumption and emissions [24]. On freeways, CACC was found to significantly increase capacity with a moderate to high market penetration rate [29]. However, with a nave deployment strategy of AV-exclusive lanes, CACC was found to increase the total system travel time on freeways [19]. Talebpour et al. [32] simulated traffic flow under different penetrations rates of AVs on a two-lane and a four-lane freeway segment in Chicago, Illinois with mandatory and optional usage of AV-exclusive lanes. At market penetration rates of more than 50% for the two-lane highway and 30% for the four-lane highway, a potential benefit in terms of throughput and travel time reliability was observed in this study, with optional use of the AV-exclusive lanes yielding the most benefit. In another study, this optional use of AV-exclusive lanes was found to be beneficial only with a high market share of AVs [18].
Further, with the advent of AV technology in the market, it is critical to gain individual motivations for choosing to own or use AVs as a service. Hence, an endogenous demand model becomes imperative in such traffic flow modelling involving multiple vehicle classes. Based on a stated preference survey from 721 individuals living across Israel and North America, 44% of the sample population were found to prefer LVs over AVs [9]. Another stated choice survey for the adoption of shared AVs suggested service attributes including travel cost, travel time and waiting time to be critical determinants of the use of shared AVs [10].
To allow the transportation system to adapt with such disruptive technologies, we explore the potential benefits of introducing AV-exclusive lanes on freeways where the conflict points are considerably lesser than in local arterial networks and require minimal technological interventions. From previous studies, it is apparent that deploying AV-exclusive lanes in all links in a network may not be advantageous as it may significantly increase congestion and reduce throughput in the regular lanes; yet no systematic approach to identify the optimal location of AV-exclusive lanes has been proposed. In this work, we propose to investigate the problem of locating AV-exclusive lanes in a freeway network so as to reap maximum benefits of the deployed infrastructure.
We build on the literature of system optimum dynamic traffic assignment (SODTA) formulations to represent traffic dynamics, and obtain an analytical model amenable for exact optimization. Although a few studies [17,16,11,1] proposed SODTA approaches to model user route choice in general networks, this behavioral assumption is limiting, especially in the context of endogenous travel demand. Alternative approaches such as cross-nested and user-equilibrium models have also been proposed for characterizing different route choice principles [36,19], these research efforts are focused on static traffic assignment formulations or do not consider endogenous travel demand. To circumvent such assumptions, we focus on the design of freeway networks with single path per OD pair and we leave the study of general networks for future research. In this context, there are no route choice decisions, and the SODTA component of the formulation provides an analytical representation of traffic dynamics in the freeway network which maintains first-in-first-out (FIFO) conditions. Further, we do not model lane-changing behaviour of vehicles and do not account for vehicle holding in the network which is defined as the reluctance of vehicles moving forward from upstream to downstream links even with an availability of vacant spaces downstream [16,17].
For modelling the traffic flow in the network, we adopt the link transmission model (LTM) [38] and modify it to account for two vehicle classes: LVs and AVs. The LTM has been found to be useful to scale-up SODTA formulations for network design [1] as well as for solving routing problem for shared AVs in congested networks [11]. In the proposed formulation, we avoid mixed vehicular interactions of LVs and AVs by providing AV-exclusive lanes allowing AVs to behave autonomously only on AV-exclusive lanes and assume both LVs and AVs to behave identically on regular lanes. We capture the demand split of each vehicle class with a logit model, embedded in the proposed formulation. We model lane design decisions using binary variables, thus the proposed formulation results in a challenging non-convex MINLP.
We adopt a Benders' decomposition approach to implement this MINLP on a multi-OD freeway network which embeds a fixed-point algorithm in its sub-problem to account for endogenous travel demand.
This study makes the following contributions. We propose an optimization framework, involving an optimal design of dedicated lanes for AVs on a freeway network based on the demand of LVs and AVs which are endogenously calculated with a demand model embedded in the formulation. To the best of our knowledge, an integrated framework of this kind has not been explored in the literature. The computational complexity of such a nonconvex formulation is dealt with a Benders' decomposition approach in which the sub-problem embeds a fixed-point procedure to account for the endogenous demand model, retaining the linear structure of the underlying traffic flow model. We prove the existence of a fixed-point and our proposed algorithm always converges to this fixed-point. We also identify the conditions under which our algorithm is globally optimal. We implement the proposed algorithm on a freeway network which reveals that deploying a maximum of exclusive autonomous vehicles does not necessarily minimize network travel time.
This paper is organized into five sections. Section 2 presents the problem formulation followed by the solution methodology in Section 3. The proposed formulation is studied on two numerical networks, presented in Section 4. Section 5 presents the key findings of the study along with future research directions.

Freeway network design problem
In this study, we develop an MINLP model for optimal AV-exclusive lane design along with endogenous estimation of AV demand. We develop this MINLP in three stages. To begin with, we propose a linear programming (LP) framework for a lane-based LTM formulation with fixed AV-exclusive lanes, fixed proportion of AVs in the network and a system level objective. Further, we introduce a binary variable to obtain optimal lane design for AVs for an improved system performance, resulting in a mixed-integer linear program (MILP). Finally, we bring in a logit model to estimate the endogenous demand for each vehicle class which introduces non-linearity in the model, resulting in an MINLP. We circumvent this non-linearity by proposing a fixed-point algorithm along with method of successive averages (MSA) to obtain convergence of the fixed-point as explained in Section 3.
Let G = (N, A) be a directed network where N is the set of nodes and A is the set of arcs. In the proposed formulation, each node of the network is represented by a set of incoming and outgoing arcs. The set of arcs is partitioned into three subsets: source centroid connectors denoted as A r , sink centroid connectors as A s , and physical links formed by the remaining links of the set; i.e., A\{A r ∪A s }. The set of origin-destination pairs is represented by K. Γ − (i) and Γ + (i) represent the set of predecessor and successor links of link i. Table  1 presents the rest of the notations of the proposed formulation.
We choose the total system travel time (TSTT) as the metric of system performance, consisting of travel times of two vehicle classes: LV and AV. The objective function in the TSTT lv and TSTT av can be obtained from the difference in cumulative inflows and outflows of each link, representing the number of LVs/AVs present on that link at each timestep and the number of timesteps they spend on that link. The underlying LTM provides these cumulative inflows and outflows as output as explained in Section 2.2. The total vehicular demand in the network is the sum of LVs and AVs in the network as follows.

Endogenous demand model
We denote the time-varying total vehicle demand at time t between each origin-destination pair in the network by D o,d (t) and assume it to be fixed in our formulation. D o,d (t) is presented as a sum of the demands of two vehicle classes, LVs and AVs, in Eq. (2).
Though, the total demand in the network is fixed, the demand corresponding to each vehicle class varies depending on the proportions of AVs (p o,d ) between each OD pair in the network and they are obtained from Eqs. (3a) and (3b).
In the proposed formulation, the demand for each vehicle class is endogenous to the proportions of AVs (p o,d ), which is obtained based on the attractiveness of the modes in the network. We adopt a logit model to quantify this attractiveness, as summarized in Eq. (4).
We assume that the utility of each mode depends only on the average travel times of all the vehicles of that mode between each OD pair. The average travel times of LV and AV are denoted by τ o,d lv and τ o,d av and the utility of each mode is obtained from Eqs. (5a) and (5b).
Here, β represents the total amount of utility gained while making a trip, whereas, β o,d τ lv and β o,d τav are the disutilities created per unit travel time by LVs and AVs respectively. We refer to a study by Wong et al. [37] to obtain the values of β o,d τ lv and β o,d τav . We modify the logit model presented in Eq. (4) with the difference in utilities between the modes where the utility functions consist of the coefficients (β o,d τ lv , β o,d τav ) of average travel times of corresponding modes, as presented in Eq. (6).
The OD average link travel times of each vehicle class are obtained from the lane-based formulation of LTM which is the underlying traffic flow model in the proposed formulation.

Network dynamics
The LTM, proposed by Yperman et al. [38], is a numerical solution method for dynamic network loading, developed based on the first order kinematic wave theory [15,28]. In this study, LTM is chosen as it involves fewer variables per link compared to models such as cell transmission model (CTM) [2]. We adapt the conventional LTM to accommodate two vehicle classes by introducing two types of lanes: AV-exclusive and regular lanes. An AV-exclusive lane differs from a regular lane in terms of following headway, capacity and speed of backward shockwave propagation. The difference in these traffic flow characteristics affects the fundamental diagrams of traffic flow significantly as explained in the following subsection.

Fundamental diagram
The fundamental diagram of traffic flow reflects the relationship among the macroscopic traffic flow parameters of a network: traffic flow, density and speed. These relationships approximate all possible stationary traffic states during the analysis period and provide significant insights regarding the overall behaviour of traffic in a network.
The shape of the fundamental diagrams depicting these relationships may vary depending on the assumptions and approximations of a study. Greenshields et al. [8] was the first to propose a parabolic relationship between traffic flow and density. Later on, Newell [23] provided a simplified approach to the kinematic wave theory of traffic flow and developed a triangular shaped fundamental diagram, defined by three parameters: a fixed free-flow speed (v f ), capacity or maximum flow (q) and a jam density (K jam ). Yperman et al. [38] adopted this simplified fundamental diagram while developing the LTM which is the underlying traffic flow model in our formulation.
In a network with AV-exclusive lanes, the macroscopic traffic flow parameters may be significantly affected by faster reaction times of AVs leading to reduced following headway, increased throughput and faster propagation of backward shockwave due to congestion. Levin and Boyles [13] found considerable difference in the shape of the fundamental diagram for different reaction times of a characteristic vehicle. This study also showed how capacity and wave speed increase as the AV proportion increases with the human drivers having double the reaction time of AVs. Tientrakool et al. [33] demonstrated that due to tighter time and space headways among vehicles, the capacity of a lane could be approximately tripled by converting it into an AV-exclusive lane. Hence, while comparing traffic flow on AV-exclusive and regular lane, the shape of the triangular fundamental diagram will be significantly different due to the changes in capacity (q) and backward wave speed (w) leading to the same jam density (K jam ).
In this study, we consider the AV-exclusive lanes to have double the capacity (q av = 2q lv ) and backward wave speed (w av = 2w lv ) of that of the regular lane while keeping the free-flow speed (v f ) and jam density (K jam ) the same for both lane types. The fundamental diagrams of traffic flow on both of these lane types is shown in Figure 1.

Traffic flow propagation
The LTM keeps track of the vehicular flow in the network with cumulative inflows and outflows of each link at each time-step. We develop a lane-based LTM where the vehicle class-specific cumulative inflows and outflows from each lane i towards destination k at time t are denoted by z k+ i,lv (t) z k+ i,av (t) and z k− i,lv (t) z k− i,av (t) respectively. The demand corresponding to each vehicle class is loaded into the network as the cumulative inflow to the source centroid connectors as shown in Eqs. (7a) and (7b).
The cumulative inflow to the other lanes at time t is defined as the sum of transfer flows from all the incoming lanes predecessor (Γ − ) to that lane over all the timesteps up until t. We define these in Eqs. (8a) and (8b).
Similarly, the cumulative outflows (z k− i,lv (t), z k− i,av (t)) from a lane at time t is defined as the sum of transfer flows to all the outgoing lanes successor (Γ + ) to that lane over all the timesteps up until t. We define these in Eqs. (9a) and (9b).
The LTM has been built based on three flow components: sending flow, receiving flow and transfer flow. Sending flow is defined as the amount of vehicular flow allowed to go out from link i to link j respecting its flow capacity. Yperman et al. [38] Eqs. (11a) and (11b) present the capacity constraints on sending flow for regular and candidate AV lanes respectively. On regular lanes, the total flow of LVs and AVs is restricted to the capacity of regular lanes (δq lv ) whereas, on candidate AV lanes, we introduce a binary In the LTM, the receiving flow is defined as the amount of vehicular flow allowed to be received at link j from link i depending on the congestion level and the capacity of link j.
The receiving flow constraint, as presented in Eq. (12), is derived based on the backward propagation of a congested traffic state from the downstream boundary of a link which reaches the upstream boundary L i wav time units later. Here, w av denotes the backward wave speed of the congested traffic state.
Similar to Eqs. (11a) and (11b), Eqs. (13a) and (13b) represent the capacity constraint on receiving flow of a link with the binary parameter, b, depending on the lane being a regular or candidate AV lane.
In the proposed formulation, LVs are restricted from entering an AV-exclusive lane. We formulate integer-linear constraints to implement this restriction in our model as presented in Eqs. (14a) and (14b). Using the binary lane design variable (b i ), the transfer flow of LVs at any timestep is either restricted or kept free, i.e., equal to the capacity of regular lane, for a downstream AV-exclusive or regular lane respectively.
Eqs. (15a) and (15b) conclude the lane-based LTM formulation ensuring the exit of all the vehicles that entered into the network and reaching their respective destinations at the end of the last timestep (t).

MINLP formulation
In the LTM, the cumulative inflows and outflows of each lane at each timestep track the vehicular flow in the network. The difference between these inflows and outflows of a lane at each timestep represents the number of vehicles present in that lane for δ time units, where δ is the duration of each timestep. Hence, the sum of these differences over all the lanes, OD pairs and timesteps will provide the TSTT of each vehicle class in the network as follows.
The average travel times are estimated based on the number of timesteps each vehicle spends on each link, averaged over the total demand of that vehicle class as presented in Eqs.
We rewrite the objective function of the proposed MINLP presented in Eq. (1) as follows.
Note that, as LVs are restricted on AV-exclusive lanes, we fix at least one path with regular lanes between each OD-pair in our model for movement of LVs. The resulting MINLP formulation FNDP represents the freeway network design problem. The remaining variables are used to account for congestion effects and endogenous travel demand. Travel demand is loaded into the network through the source centroid connectors as expressed in Eqs. (3a) and (3b). At the completion of the trips, Eqs. (15a) and (15b) ensures that vehicles leave the network through the sink centroid connectors. On a freeway, these source and sink centroid connectors represent on-and off-ramps respectively. If the network is unable to accept demand due to congestion on the freeway, vehicles may be held at on-ramps which are assumed to have sufficiently large capacities. Since waiting time is penalized in the objective function, the outputs of the proposed formulation can be interpreted as the level of control at the freeway on-ramps.
We analyse the proposed model in the following sections.

Fixed-point analysis
To motivate the design of a dedicated solution method and to provide insights into the behavior of FNDP, we consider a simplified version of the model wherein the endogenous demand p and the lane design b are assumed fixed. This simplified model is called SP(b, p) and presented below.
The variables involved in Model SP(b, p) are transfer flows y ∈ Y and cumulative inflows and outflows z ∈ Z. We consider a single-OD network with two links with fixed AV-exclusive lanes as illustrated in Figure 2, where the fixed AV lanes are shown in blue. The first link consists of three regular lanes and one AV-exclusive lane followed by a capacity drop on the second link which has one LV and one AV-exclusive lane. We solve SP(b, p) for a series of OD proportions of AVs (p o,d ) and calculate the corresponding logit-derived proportion of AVs (p o,d logit ) using Eq. (6) based on the optimal solution of SP(b, p). Note that if p = p logit , then the demand splits are logit-compatible, i.e. equilibrated, and this solution corresponds to a fixed-point. We define this fixed-point as follows.
Definition 1 (Fixed-point). Let F : P → P be a continuous function of the OD proportion vector p ∈ P. We say that p is a fixed-point if F (p) = p. The regular and AV-exclusive lanes differ from each other in terms of capacity and backward wave speed of congestion propagation. In this study network, the capacity (4320 veh/hr) and backward wave speed (28.4 km/hr) of an AV-exclusive lane is taken as double that of an regular lane due to the inter-connectivity of AVs leading to better traffic flow and faster congestion propagation. The length and jam density of the links are 800m and 200 veh/km respectively with a free-flow speed of 90 km/hr for both vehicle classes. The demand is loaded through the source centroid connector 1 into the network. The capacity and jam density of the source and sink centroid connectors are set to very high values with a negligible length for instantaneous loading of demand into the network based on available network capacity. The values of these network parameters are provided in Table 2.    We observe that all fixed-points have equal TSTT. This experiment highlights that fixed-points may be non-unique, but may also correspond to identical TSTT. From Figure 3, we observe that in each case, the line plot depicting the relationship between p and p logit crosses the reference line at least once, referring to the existence of at least one fixed-point satisfying the logit model. We prove this existence of at least one fixed-point with Proposition 1. Proof. We show that we can construct such a continuous function F (p). Let h(p) be the function mapping the OD proportion vector p to the optimal solution of the linear program SP(b, p) for fixed lane design vector b as defined by (2). Let z ∈ Z be the vector of cumulative inflow and outflow and let y ∈ Y be the vector of transfer flows obtained after solving SP(b, p), formally: Let g(z, y) be the function mapping the optimal cumulative inflows and outflows, and transfer flows to average, class-based (LV and AV) OD travel times (τ lv , τ av ) ∈ T as defined in Eqs. (17a) and (17b): Finally, let f (τ lv , τ av ) be the function mapping average class-based OD travel times to OD proportion p ∈ P via the proposed logit model as defined in (6): Let F (p) = f (g(h(p))), F is a continuous function from the compact convex set P to itself. By Brouwer's theorem, there exists at least one fixed-point p such that F (p) = p.
In Section 3, we develop the solution methodology to solve the non-linear Model 1 with variable lane design and endogenous demand based on the embedded logit model.

Benders' decomposition approach
In this section, we propose a decomposition approach with variable lane design and endogenous demand for each vehicle class. The purpose of this development is to identify the crucial locations in a network where providing an AV-exclusive lane will reap the maximum benefit for a given AV demand. As LVs are restricted on AV-exclusive lanes, it is necessary to deploy AV-exclusive lanes judiciously to cater to both vehicle classes keeping the social welfare into perspective. We introduce Benders' decomposition method for this purpose which iteratively explores possible lane designs in a master problem and, at each iteration, solves a sequence of SODTA problems which is shown to converge to fixed-points representative of logit-compatible demand splits.
Benders' decomposition approach eases up the computation burden of a mathematical model by partitioning the overall formulation into a relaxed master problem with mainly integer variables and a subproblem with all the continuous variables. For a detailed review of Benders' approach, one can refer to Rahmaniani et al. [26]. For problems with minimizing objective function, such as the proposed model in this study, the relaxed master problem provides a lower bound at each iteration of Benders' method. Whereas, the subproblem handles the complicated constraints of the original problem which is solved iteratively for each relaxed solution of the master problem. At each iteration until convergence, the Benders' method generates either a feasibility cut or an optimality cut towards obtaining the optimal solution. A feasibility cut is generated to eliminate an infeasible solution provided by the subproblem, preventing the master to produce it again. On the other hand, if the sub-problem solution is feasible, an upper bound is obtained and an optimality cut is derived towards closing the optimality gap.
In our decomposition of Model FNDP, we only retain binary lane design variables b in the master problem MP, which is summarized below: In the proposed model, the subproblem (SP(b, p)) is initiated by fixing the set of binary lane design variables. Depending on the feasibility of the subproblem, dual prices or rays for each constraint are calculated, followed by solving the master problem which provides the values for the next set of binary lane design variables. This iterative process continues until we reach an exact solution of the objective function.
The subproblem in the proposed formulation consists of two components: the lanebased LTM with system-level objective function and an endogenous demand model. As the endogenous demand model introduces non-linearity in the formulation, we develop a fixed-point algorithm for solving the subproblem as explained in the following subsection.

Fixed-point algorithm
The endogenous demand model is crucial to study the effect of infrastructural changes such as AV-exclusive lanes on AV demand. Note that, the formulation without the endogenous demand model is a useful model by itself as it can estimate the progressive deployment of AV-exclusive lanes in a network corresponding to incremental penetration of AV demand. However, this model does not account for the effect of these AV-exclusive lanes on the demand of each vehicle class.
We adopt the logit model for endogenously estimate the demand for each vehicle class. As the logit model is nonlinear, we use a fixed-point algorithm to separate the endogenous demand component from the SODTA formulation. The fixed-point algorithm estimates the proportion of AVs (p o,d ) in an iterative process involving the logit model, presented in Eq. (6). The Algorithm 1 presented in the next subsection, keeps the nonlinear logit model out of the MILP, keeping it a linear mathematical formulation. The new proportion of AV demand is obtained based on the difference in utilities between the modes, substituted in the logit model (as shown in Eq. (6)), which is fed back to Model 2 for subsequent iterations. We adopt the method of successive averages (MSA) for convergence of the fixed-point algorithm which is based on a predetermined move size along the descent direction. Note that MSA is guaranteed to converge after a certain number of iterations by providing lesser weightage to subsequent solutions at each iteration. This iterative process of MSA may disregard the instability in the fixed-point solution. We monitor this instability by checking the value of p o,d before and after implementing MSA.
The Benders' decomposition algorithm along with fixed-point algorithm is presented in Algorithm 1. We next prove that Algorithm 1 converges to a local optima of Model FNDP in Proposition 2 and identify under which conditions this local optima is a global solution in Proposition 3.  Proof. If all fixed-points have equal TSTT, then Benders' cuts are guaranteed to never overestimate the lower bound Z obtained from solving the master problem MP. Hence, all local optima of Model FNDP have equal and minimal TSTT.

Algorithm 1: Benders decomposition with fixed-point algorithm for
(Solve logit model with free-flow travel times) Proposition 3 identifies the conditions under which the solution of the proposed algorithm is globally optimal. Although we are not able to mathematically prove that in the presence of multiple fixed points all fixed points yield identical TSTT, in our investigations we consistently observe this behavior on congested freeway networks.
In the next section, we implement this algorithm on a single-OD and a multi-OD network.

Numerical experiments
The proposed formulation is implemented on the same single OD network ( Figure 2) presented in Section 2 along with a multi-OD freeway network ( Figure 6).

Single OD freeway network with fixed lane design
We implement the solution methodology presented in Section 3 on the single OD freeway network with fixed lane design for AVs. As mentioned earlier, the presence of the binary lane design variable makes the proposed formulation a mixed-integer linear program, whereas, the endogenous demand model introduces non-linearity due to the structure of the logit model. We develop the fixed-point algorithm to circumvent non-linearity and Benders decomposition method to handle the binary lane design variable in the master problem. To understand the performance of the fixed-point algorithm alone, we first implement Model 2 on the single OD network with fixed dedicated lanes for AVs. We initialize the algorithm with a proportion of AV obtained from Eq. (6) substituting the free-flow travel time between the OD pairs. Model 2 is solved at each iteration of this algorithm. The value of p o,d is updated at each iteration with the proportion (p logit ) obtained by the endogenous demand model until convergence where a fixed-point is reached (p = p logit ). The network characteristics of this test network is same as presented in Table 2. A time-varying demand profile is selected for this analysis which is loaded into the network every 2 minutes for the first 8 minutes of a total analysis period of 100 minutes. The total demand is 2950 vehicles which includes both LVs and AVs. Note that, the objective function of the proposed formulation takes into account the waiting time of vehicles at the source centroid connector depending on the available capacity in the network. We consider a timestep (δ) of 30 seconds at which the cumulative inflows and outflows of each link are updated by the underlying LTM. For a single OD network with fixed dedicated lanes for AVs with β o,d τav = 0.0018, we plot this convergence of the fixed-point algorithm in Figure 5. Figure 5 shows that the algorithm converges to a fixed-point after 67 iterations at p = 0.68 which is one of the fixed points presented by the purple dot in Figure 4. At convergence, the value of the objective function (TSTT) is found to be 2604430 veh-sec with a computation time of 24.067 seconds.
In this case study on a single OD network with fixed AV-exclusive lanes, we observe that the fixed-point algorithm performs well with fast convergence. In Subsection 4.2, we introduce the Benders' decomposition method to handle variable lane design problem on a multi-OD network.

Multi-OD freeway network
We implement the proposed model with Benders method and fixed-point algorithm on a multi-OD freeway network, presented in Figure 6. This 27km long freeway consists of 6 OD pairs, 9 links, 4 on-ramps and 4 off-ramps. Each of these links has either 2 or 3 lanes as shown in Figure 6 where one lane in each link, showed in green colour, belongs to the set of candidate AV lanes (A av ) which could potentially converted into an AV-exclusive lane for better system performance. The total vehicular demand is considered to be 3000  We design 7 experiments to study the performance of our algorithm. Apart from the base case, the proposed algorithm is implemented for different demand (±25%), capacity of AV lanes (±25%) and coefficient of average AV travel times (±25%). The performance of Algorithm 1 for these different scenarios is presented in Table 3. We observe that it is not beneficial to convert all candidate AV lanes to AV-exclusive lanes. For example, 7 out of 9 candidate lanes are converted to AV-exclusive lanes for the base case which remains the same for the reduced demand case as well. However, for an increased demand, a lesser number of lanes are converted to AV lanes (6). This could be due to increased LV demand which requires more regular lanes in the network. In case of an increased AV lane capacity, the system performance is significantly enhanced by allocating more AV-exclusive lanes (8) compared to the reduced AV-lane capacity case (5). On the other hand, the coefficient of average AV travel times is found to have no effect on AV lane design in the network. These deployed AV-exclusive lanes are found to decrease the TSTT by around 10% in all the scenarios, with a maximum improvement of 12.71% for increased AV-lane capacity. Hence, AV-exclusive lanes are always found to have a positive impact in network performance.
The computation time of the proposed algorithm varied from around 0.5 to 4 hours on an Intel(R) Core(TM) i7-6700 @3.40GHz CPU with 16GB RAM. The base case was found to converge within 2 hours with 55 iterations of Benders and a total of 269 fixed-point iterations. Interestingly, the change in the capacity of AV-exclusive lanes is found to have the maximum effect on computation time of the proposed algorithm with a 10 times increment in computation time for inflated capacity compared to the deflated capacity of AV lanes. Similar increment in the number of Benders and fixed-point iterations is also observed in these cases with inflated and deflated capacities. Table 4 summarizes the optimal proportion of AVs (p o,d ) obtained from the endogenous demand model in different scenarios. We initialize the values of p o,d by substituting freeflow travel times of vehicles in the logit model Eq. (4). Due to the structure of the logit model, the initial p o,d values are found to be inversely proportional to the free-flow travel time between OD pairs and vary from 0.28 to 0.44. As the free-flow travel times on regular and AV-exclusive lanes are the same, this variation is solely due to the difference in the coefficient of travel times in the logit model. In congested traffic conditions the proposed algorithm estimates these p o,d to be around 0.57 to 0.83. In the base case, the OD pair (3,17) is found to have the maximum value of p o,d with a value of 0.76, whereas the OD pair (3,9) requires the least proportion with a value of 0.63. With a reduction in total demand, this proportion is found to be reduced by a maximum of 10%. Whereas, with increased demand, the maximum increment in p o,d is only around 4.6%. This could be due to the increased total demand which require fewer AV-exclusive lanes, as shown in Table 3, to cater for the increased LV demand. Hence, increasing p o,d may not provide much improvement in system level performance. On the other hand, p o,d values are not found to be affected significantly with inflated and deflated capacity of AV-exclusive lanes. However, the different coefficients of the average travel times of AVs (β av ) are found to considerably affect the AV proportions. A reduction in this coefficient means that average travel time will create less disutility for AVs rendering this mode more attractive than AVs and vice-versa. The output from the proposed algorithm shows similar effect with a maximum increment of 12% in p o,d for a 25% reduction in β av and a maximum of 15.7% decrease with an increment in β av . We present the average travel times LVs and AVs on each link for all the 7 experiments in Tables 5 and 6. As mentioned earlier, the proposed algorithm triggers 7 out 9 candidate AV lanes into AV-exclusive lanes. These exclusive lanes are found to have a significant effect on the average travel times of LVs with a maximum reduction of 45% for the base case. Similar improvement is observed for other demand scenarios as well with a maximum reduction of 41 and 46% respectively for LVs. These maximum reductions are mainly observed on the waiting times of vehicles on on-ramps. With a deflated capacity of the proposed AV lanes, the average reduction of average travel times on congested links is found to be around 8% with a maximum reduction of 23% in the first on-ramp of the network. Whereas, the inflated capacity provided a average reduction of 12% in the travel times with a maximum reduction of 52%. In the case with reduced β o,d τav value, the average reduction of travel times for LVs are found to be 5.6% compared to the case with increased β o,d τav value where this reduction is 14%. This output is quite intuitive as the reduced a β o,d τav will create less impedance on the mode choice decisions of users based on AV travel times, leading to more AVs in the network and less travel time benefits of for LV users.
With the proposed AV-exclusive lanes, the average travel times of AVs are found to be reduced by an average of 15%. Note that, these average travel times correspond to AVs on both regular and exclusive lanes. The maximum reduction of 60% is observed for the waiting time on source connector 10. The average reductions in travel times are around 16.4% and 13.4% for the reduced and increased demand cases respectively. The deflated and inflated capacities of the AV-exclusive lanes reduced the average AV travel times of AVs by 12.8 and 120 120 120 120 120 120 120 120 120 120 12 120 120 120 120 120 120 120 120 120 120 14 120 120 120 120 120 120 120 120 120 120 16 120 120 120 120 120 120 120 120 120 120 17.5% respectively with a maximum reduction of 64% for the inflated capacity case. With an decreased and increased β o,d τav the average reduction in the average travel times are around 16.4 and 15% respectively.  120  120  120  120  120  120  120  120  120  14  120  120  120  120  120  120  120  120  120  120  16 120 120 120 120 120 120 120 120 120 120

Conclusion
In this study, we proposed an optimization framework to solve a multi-OD freeway network design problem for optimal lane design under endogenous AV demand. Due to the presence of binary lane design variables and the endogenous demand model, the proposed formulation results in a nonconvex MINLP. We tackle this challenging problem by introducing Benders' decomposition approach which iteratively explores possible lane designs in the master problem and at each iteration solves a sequence of SODTA problems which is shown to converge to fixed-points representative of logit-compatible demand splits. The proposed approach is implemented on two hypothetical freeway networks with single and multiple origins and destinations. On the single-OD network, the fixed-point algorithm is found to converge at multiple fixed points providing different proportions of AV demand. However, these multiple fixed-points are found to have no effect on the objective function of the problem. Here, we prove that for a fixed lane design, there exists at least one fixed-point representing the proportion of AV demand in the network. We also prove that the proposed solution method converges to a local optima of the nonconvex problem and identify under which conditions this local optima is a global solution.The numerical results on the multi-OD network show that it is not beneficial in terms of system performance to provide AV lanes for all the links in the network.
We observe that the optimal lane design of freeway network is non-trivial and can inform on the value of accounting for endogenous demand in the proposed freeway network design. The proposed model may also be useful for designing ramp metering for a freeway network with AV-exclusive lanes. The following limitations may be examined in future research. The proposed algorithm is designed for a multi-OD freeway network with single path between each OD pair, hence route choice modelling is averted. We do not model lane-changing behaviour nor attempt to model vehicle holding issues. This work can also be extended by investigating user equilibrium (UE) vs SO route choice in an arterial network with dedicated AV lanes incorporating mixed vehicular interactions.