Deployment of autonomous driving on bus rapid transit lanes: Synergy between autonomous vehicle speed and bus timetables

Abstract

This study investigates the use of autonomous vehicles in bus rapid transit lanes during the initial phases of autonomous driving development. The aim is to accelerate the advancement of autonomous driving technologies and enhance the efficiency of bus lane usage. We first develop a dynamic joint optimization model that adjusts autonomous vehicle speeds and bus timetables to minimize vehicle travel times while reducing bus passenger waiting times. We account for random variables such as stochastic passenger arrivals at bus stations and variable demand for autonomous vehicle travel by constructing a stochastic dynamic model. To address the computational challenges of large-scale scenarios, we implement a simulation-based heuristic algorithm framework. This framework is designed to efficiently produce high-quality solutions within feasible time limits. Our numerical studies on an actual bus line show that our approach significantly improves system throughput compared to existing benchmarks. Moreover, by strategically managing the entry of autonomous vehicles into the lane and modifying bus timetables, we further enhance the operational efficiency of the system.

Graphical abstract

Keywords

autonomous driving / bus rapid transit lane / timetable design / joint optimization

1 Introduction

The emergence of autonomous vehicles (AVs) has become a prominent topic in intelligent transportation in recent years and is recognized as a crucial component of the next industrial revolution. AVs offer advantages over manual driving vehicles, including improved safety, comfort, accessibility, and financial benefits. Autonomous driving technology has made remarkable advancements in recent years, with significant improvements in sensors, cameras, and vehicle-to-everything (V2X) communication systems. The Society of Automotive Engineers (SAE) classifies autonomous driving into six levels, L0 to L5, which can be broadly categorized into driver support systems (L0 to L2) and automated driving systems (L3 to L5). The industry’s recent focus has been on transitioning from Level 2 to Level 3 automation, a critical step toward achieving higher levels of autonomy and realizing the full potential of self-driving technology.

Autonomous driving technology has been under study in different countries since the 1960s. In 1966, mechanical antilock braking was proposed in standard production cars, followed by the invention of electronic cruise control two years later, marking the emergence of the modern vehicle control system. Progress in autonomous driving technology was gradual until DARPA (The Defense Advanced Research Project Agency, USA) organized three long-distance races for AVs in 2004, 2005, and 2007, as reported by Urmson et al. (2008). The innovative ideas proposed by participants resulted in significant advancements in autonomous driving technology. In recent years, major enterprises in the automotive and internet sectors have begun investing in this field, driven by the rapid development of artificial intelligence and sensor technology.

However, as mentioned above, currently most companies are at Level 2 or 3 of autonomous driving, far from Level 5, which represents complete automation. This disparity indicates a need for further technological advancement. In the initial phases of autonomous driving, integrating AVs into the existing transportation system may affect the operation of manually driven vehicles and presents significant safety challenges.

In light of safety considerations, one potential solution is the implementation of dedicated lanes exclusively for AVs, as suggested by Liu and Song (2019). However, the establishment of dedicated AV lanes comes with notable challenges. First, it requires a substantial budget for constructing new roads and developing the necessary infrastructure. Additionally, reallocating a portion of the current road network to accommodate AV lanes would reduce available road capacity, potentially leading to increased traffic congestion if not carefully planned.

Concurrently, the operations management of bus rapid transit (BRT) lanes faces noteworthy challenges. Public transportation plays a crucial role in efficiently meeting the growing travel demands while significantly alleviating traffic congestion on existing road infrastructure. The primary objective of establishing BRT lanes is to create dedicated thoroughfares for buses, ensuring uninterrupted transit and enhancing the appeal of public transport services. More specifically, implementing BRT lanes to prioritize buses has the potential to enhance the speed, capacity, and reliability of the bus system. However, BRT lanes often underutilize their road resources, resulting in significant wastage of road space. This inefficiency has spurred an alternative approach in the early stages of autonomous driving development, considering the deployment of AVs on BRT lanes as a way to segregate them from conventional vehicles and address safety concerns. Nonetheless, existing research on deploying AVs in BRT lanes has not provided a comprehensive analysis of the dynamic interactions between vehicles with different trajectories based on road characteristics. Moreover, considering the uncertainties in passenger and AV demand, developing a dynamic programming model could effectively enhance the efficiency of the mixed-use lane.

Specifically, there is a complex interrelation between AV driving behavior, particularly overtaking maneuvers, and bus timetables. In addition, both passenger travel demands and AV transit demands are stochastic and dynamically enter the lane. To address these challenges, we establish a dynamic joint optimization framework that utilizes detailed characterizations of AV driving behaviors. This framework enables the collaborative design of AV speeds on various road segments and bus timetables, striking a balance between travel costs and passenger waiting time costs. Furthermore, within this dynamic decision-making framework, operational strategies are adaptively refined based on real-time demand information, effectively responding to the impacts of sudden events such as congestion.

The main contributions of our research include:

1) Proposing a dynamic joint optimization model for AV speeds and bus schedules.

2) Developing an efficient heuristic algorithm, implemented within a simulation framework, for solving the proposed model.

3) Conducting numerical studies based on an actual bus line to validate the effectiveness of our approach and provide valuable insights for the deployment of AVs on BRT lanes.

2 Literature review

This study primarily focuses on autonomous driving capacity analysis, bus frequency setting, and transit network timetabling problems. In the following section, we will present relevant literature in these fields.

2.1 Capacity analysis of autonomous driving

Emerging autonomous driving technology offers a promising means to enhance road capacity and alleviate traffic congestion (Tscharaktschiew and Evangelinos, 2019; Yu et al., 2021; Neufville et al., 2022). Autonomous vehicles, for instance, exhibit quicker reaction times compared to human drivers, enabling them to sense and predict lead vehicles’ acceleration and braking decisions. This capability results in reduced following distances, higher speeds, and an increase in road capacity. Furthermore, vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) technology further enhance efficiency by facilitating communication and centralized control, enabling AVs to utilize intersections and road networks effectively (Sun et al., 2022; Antonio and Maria-Dolores, 2022). Understanding the impact of AVs on road capacity is a complex challenge due to various factors. These factors include drivers’ choices, such as forming platoons or selecting autonomous driving levels, the level of traffic control technology used (distributed or centralized control), varying AV penetration rates in mixed traffic, and diverse road conditions, whether suitable for autonomous driving or not. Many researchers utilize simulations to analyze and assess the effects of AVs on road networks (van Arem et al., 2006; Aria et al., 2016). For example, van Arem et al. (2006) investigated the impact of platoons on flow stability and capacity on a freeway. Most studies suggest that capacity can significantly improve with moderate or even low AV penetration rates (Jerath and Brennan, 2012). However, other research argues that road capacity increases when the penetration rate reaches a high level (Shladover et al., 2012).

Other research takes a vehicle mechanics approach to the analysis. For instance, Swaroop et al. (1994) examined the impact of platoons on traffic instability and lane capacity, considering various platoon sizes and headways under different platoon policies, such as constant time gap or constant space. A subsequent study by Levin and Boyles (2016) employed a multiclass cell transmission model consistent with hydrodynamic theory to analyze capacity and backward wave speed. Chen et al. (2017) formulated traffic capacity in mixed traffic, accounting for AV penetration rate, micro/mesoscopic AV behavior, and lane utilization policies.

In summary, the influence of AVs on road capacity is multifaceted. However, the general trend indicates that road capacity increases with AV penetration rates due to advancements in V2V and V2I technology. Additionally, improved traffic control and road conditions also contribute to enhanced road capacity (Tscharaktschiew and Evangelinos, 2019).

2.2 Bus frequency setting

In managing a public transit system, decision-makers should strike a balance between enhancing user benefits and managing operational costs. One crucial tactical planning decision in this regard is the bus frequency setting (FS) problem, which involves determining the number of trips for one or more bus lines within a specified timeframe (Ibarra-Rojas et al., 2015). Increasing bus frequency leads to improved service quality and positive passenger feedback but also results in higher operational costs.

Initial research centered on solving the FS problem under fixed demand conditions using analytical models and heuristic methods (Newell, 1971; Salzborn, 1972; Schéele, 1980; Han and Wilson, 1982; Furth and Wilson, 1981). However, recent research has begun to consider the effects of random variables, such as stochastic demand and travel times (Hadas and Shnaiderman, 2012).

Some studies consider the impact of bus departure intervals on subsequent public transportation system operations. To address this issue, they have adopted bi-level approaches to tackle the FS problem (Constantin and Florian, 1995; Yu et al., 2015). In these approaches, frequency decisions are made at the upper level, while transit assignments are conducted at a lower level.

Moreover, specific FS models have explored the coordination of other modes of transportation, e.g., trucks (Shrivastava and Dhingra, 2002). These studies aim to optimize operational costs across different transportation modes in a systematic manner.

2.3 Transit Network Timetabling problem

The Transit Network Timetabling problem, commonly referred to as the TNT problem, pertains to determining the schedules of bus lines, including departure and arrival times at stops within a transit network for one or more bus lines (Ibarra-Rojas et al., 2015).

TNT problems closely relate to variations in demand during different time periods. For instance, Li et al. (2010) considered factors such as departure times, activity/trip chains, activity duration, and transit modes to create a more realistic passenger demand model. Some studies, e.g., de Palma and Lindsey (2001) further incorporated the time spent on boarding.

In TNT problems, there is often a focus on minimizing the cost associated with passenger waiting times (Castelli et al., 2004; Guihaire and Hao, 2010). For example, Wu et al. (2015) introduced slack time to optimize the total waiting time cost, particularly when dealing with stochastic travel times.

To facilitate transfers between different bus lines, some research concentrates on the number of synchronization events as an objective in TNT problems (Ceder and Tal, 2001). For instance, Ibarra-Rojas and Rios-Solis (2012) explored scheduling the arrival times of buses from different lines at the same transfer stop to more effectively manage the intervals between different trips.

The interaction between AVs and traditional manual vehicles presents challenges in the early stages of adopting autonomous driving technology. Additionally, if not planned properly, public transit systems may fail to fully utilize their carrying capacity. Consequently, researchers have begun to explore the synergistic operations of autonomous driving and bus systems. One common scenario involves deploying AVs on BRT lanes. For example, Chen et al. (2020) developed a cyclic space-time model for AVs on mixed-use lanes and proposed a sequential optimization method to solve it approximately. However, there has been insufficient exploration of the speed adjustments and overtaking maneuvers of AVs on BRT lanes, which are crucial for understanding the complex interactions between AVs and bus trajectories. Furthermore, optimizing operational strategies dynamically would provide significant benefits considering the uncertainties in travel demand for bus passengers and AVs. Unfortunately, this aspect has not been adequately addressed in the existing literature on the deployment of AVs in BRT lanes.

3 Model development

3.1 Model preliminaries

Our study focuses on the scenario in which AVs and buses coexist within a BRT lane. We refer to the points where AVs enter and exit the lane as “intersections.” Buses only stop at stations to facilitate passenger boarding and alighting. It is important to note that, due to BRT lane restrictions, AVs can only overtake at stations where the road is widened, as illustrated in Fig.1. In the dynamic decision-making process of the system, we assume that newly entering vehicles into the lane cannot obstruct the movement of vehicles already on the lane, in order to ensure a smooth travel experience for both bus passengers and AV drivers. The bus speed and the maximum AV speed are respectively denoted as v_{\mathrm{b}} and v_{\mathrm{a}}. To provide a comprehensive illustration of the operational dynamics between AVs and buses, we utilize Fig.2, which depicts travel distance curves over time. The x-axis denotes time, while the y-axis represents travel distance. In Fig.2, the gray curves depict the trajectories of buses, with horizontal segments indicating bus dwell times at specific stations where their distance remains constant. In contrast, the red curves represent the trajectories of AVs. Note that the red curve intersects the gray curve exclusively when the latter is horizontal, indicating that AVs can overtake a bus only when the bus is stationary at a station.

We divide the entire operational horizon of the BRT lane into discrete time periods (t=0,. ..,T), each with a duration of h. Within each period, we optimize the speeds of AVs and bus timetables, taking into consideration factors such as real-time travel information for buses and AVs on the BRT lane, passenger waiting at bus stations, and AVs waiting at intersections. Once the operational plan for the current period is determined, the system progresses to the next period, as depicted in Fig.3. This dynamic process continues until the specified time horizon concludes. For computational tractability, we employ a myopic policy, meaning we do not factor in the long-term implications of present decisions on future operational costs.

To enhance our model’s scalability, each vehicle node in our framework can represent not just a single AV, but also a fleet of AVs with similar behaviors. This is characterized by:

i) All AVs within the same fleet sharing the same origin and destination.

ii) Consistency in the driving behaviors among AVs within the same fleet.

In this context, we use {\mu }_{ij} to represent the safety distance between adjacent fleets i and j, which depends on their fleet sizes.

3.2 Dynamic model

We use {\mathcal{K}}_1 to represent the set of stations and {\mathcal{K}}_2 to represent the set of intersections. We use \mathcal{K}={\mathcal{K}}_1\cup {\mathcal{K}}_2 to represent the set of all nodes on the lane, consecutively indexed by 1 through K. Additionally, l_k indicates the distance between nodes k and k+1. We denote by {\tilde{\mathcal{A}}}_t the set of AVs that entered the lane before period t; {\tilde{\mathcal{B}}}_t the set of buses that have departed before period t; \{{\tilde{a}}_n^k: k\in \mathcal{K},n\in {\tilde{\mathcal{A}}}_t\} , the arrival time of AV n at node k; \{ {\tilde{b}}_n^k,k\in \mathcal{K},n\in {\tilde{\mathcal{B}}}_t\} the arrival time of bus n at node k, and \{ {\tilde{g}}_n^k:k\in \mathcal{K},n\in {\tilde{\mathcal{B}}}_t\}, the departure time of bus n at node k. As such, {\tilde{a}}_n^k, {\tilde{b}}_n^k, and {\tilde{g}}_n^k describe the driving information of AVs and buses on the BRT lane, thus representing the system states at the beginning of period t. For given system states, we can further calculate f_n^k and u_n^k, for \mathrm{\forall }k\in \mathcal{K},n\in {\tilde{\mathcal{A}}}_t, representing the earliest and latest arrival time of the AV driving behind AV n at node k, respectively. Before conducting a joint optimization of bus timetables and AV speeds, it is necessary to update the information of recently arrived AVs and bus passengers in each time period. We use {\psi }_{ij}^t to represent the number of bus passengers traveling from stations i to j,\mathrm{\forall }i,j\in {\mathcal{K}}_1; and {\mathcal{A}}_t to represent the set of AVs arriving in period t, with their origin set denoted by \{o^i: i\in {\mathcal{A}}_t\} and destination set denoted by \{e^i: i\in {\mathcal{A}}_t\}, as shown in Fig.4. In light of the considerable capacity of buses (often accommodating more passengers than available seats), we assume that all arriving passengers will board the bus for their journey. In addition, we define \mu as the travel cost per unit time and c as the fixed cost for utilizing a new bus.

We define {\mathit{X}}_{\mathit{t}} as the decision variable vector in period t, which is categorized into three distinct groups. The first group pertains to the driving behaviors of AVs, where \{ a_i^k: k\in \mathcal{K},i\in {\mathcal{A}}_t,e^i\ge k\ge o^i\}, represents the arrival time of AV i at node k. The second group includes decisions related to bus timetables, with {\tau }_t denoting the bus departure interval in period t; {\delta }_t^i, for i=1,\dots ,B, indicating whether i buses have been utilized in period t; and \{d_t^k:k\in {\mathcal{K}}_1\} representing bus dwell time at station k in period t. The third group characterizes the relationship between AVs and buses, with all variables being binary. \{{\mathit{\text{z}}}_{ij}:i, j\in {\mathcal{A}}_t\}, represents the relationship between newly entered AVs, equalling one if AV i is behind AV j, and 0 otherwise. \{{\widetilde{\mathit{\text{z}}}}_{ij}:i \in {\mathcal{A}}_t, j\in {\tilde{\mathcal{A}}}_t\}, represents the relationship between newly entered AVs and AVs already on the lane, equalling one if AV i is driving behind and next to AV j, and 0 otherwise. {\{\tilde{y}}_{ij}^k: i\in {\mathcal{A}}_t, j\in {\tilde{\mathcal{B}}}_t, k\in \mathcal{K}\}, indicates the relationship between newly entered AVs and buses already on the lane, equalling one if AV i is driving behind and next to bus j at node k, and 0 otherwise. We define {\mathcal{B}}_t= \{1, \dots ,B\} and \{y_{ij}^k:i\in {\mathcal{A}}_t,j\in {\mathcal{B}}_t,k\in \mathcal{K}\}, signifies the relationship between newly entered AVs and newly utilized buses, equalling one if AV i is driving behind and next to bus j at node k, and 0 otherwise. In the following model, we use subscript i to denote the vehicle in the i-th leading position in {\tilde{\mathcal{B}}}_t and {\mathcal{B}}_t. Refer to Table A1 in Appendix A for a detailed notation description.

Define M as a sufficiently large number. According to the above definition, the joint optimization model is formulated as follows.

(1)\underset{{\mathit{X}}_{\mathit{t}}}{min}\mu \left(\sum _{i\in {\mathcal{A}}_t}{a}_i^{e_i}+\sum _{i,j\in \mathcal{K}}\frac{{\psi }_{ij}{\tau }_t}{2}+\sum _{i,j\in \mathcal{K}}\sum _{k=i+1}^{j-1}{\psi }_{ij}{d}_t^k\right)+c\sum _{i=1}^{B}i{\delta }_t^i,

(2)\sum _{i=1}^B{\delta }_t^i=1,

(3)({\delta }_t^i-1)M+i {\tau }_t\le h\mathrm{\forall }i=1,\dots ,B ,

(4)(1- {\delta }_t^i)M+(i+1 ){\tau }_t\ge h \mathrm{\forall }i= 1,\dots ,B,

(5){\mathit{\text{z}}}_{ij}+{\mathit{\text{z}}}_{ji}=1 \mathrm{\forall }i, j\in {\mathcal{A}}_t,

(6)\sum _{j\in {\tilde{\mathcal{A}}}_t}{\widetilde{\mathit{\text{z}}}}_{ij}=1 ,\mathrm{\forall } i\in {\mathcal{A}}_t,

(7)a_i^k\ge a_j^k+ {\mu }_{ij}/v_a+ \left({\mathit{\text{z}}}_{ij}-1\right)M,\mathrm{\forall }k\in \mathcal{K},i,j\in {\mathcal{A}}_t,

(8)a_i^k\ge f_j^k+ \left({\widetilde{\mathit{\text{z}}}}_{ij}-1\right)M,\mathrm{\forall }k\in \mathcal{K},i\in {\mathcal{A}}_t,j \in {\tilde{\mathcal{A}}}_t,

(9)a_i^k\le u_j^k+ \left(1-{\widetilde{\mathit{\text{z}}}}_{ij}\right)M,\mathrm{\forall }k\in \mathcal{K},i\in {\mathcal{A}}_t,j \in {\tilde{\mathcal{A}}}_t,

(10)\sum _{j\in {\tilde{\mathcal{B}}}_t}{\tilde{y}}_{ij}^k+\sum _{j\in {\mathcal{B}}_t}{y}_{ij}^k=1, \mathrm{\forall } e^i\ge k\ge o^i,i\in {\mathcal{A}}_t,

(11)y_{ij}^k \le y_{ij}^{k-1}+ y_{i,j+1}^{k-1},\mathrm{\forall }k- 1,k\in \mathcal{K},i\in {\mathcal{A}}_t,j ,j+1\in {\mathcal{B}}_t,

(12){\tilde{y}}_{ij}^k\le {\tilde{y}}_{ij}^{k-1}+{\tilde{y}}_{i,j+1}^{k-1},\mathrm{\forall }k- 1,k\in \mathcal{K},i\in {\mathcal{A}}_t,j ,j+1\in {\tilde{\mathcal{B}}}_t,

(13)a_i^k\ge {\tilde{b}}_j^k+{\mu }_{ij} /v_a+ ({\tilde{y}}_{ij}^k- 1)M, \mathrm{\forall }k\in \mathcal{K},i\in {\mathcal{A}}_t,j \in {\tilde{\mathcal{B}}}_t,

(14)\begin{array}{r}{a}_i^k\le {\tilde{b}}_{j+1}^k-{\mu }_{j+1,i}/v_b+(1-{\tilde{y}}_{ij}^k)M,\\ \mathrm{\forall }k\in \mathcal{K},i\in {\mathcal{A}}_t,j,j+1\in {\tilde{\mathcal{B}}}_t,\end{array}

(15)\begin{array}{r}{a}_i^{k-1}\ge {\tilde{g}}_j^{k-1}+{\mu }_{ij}/v_a+({\tilde{y}}_{ij}^k-1)M,\\ \mathrm{\forall }k-1,k\in \mathcal{K},i\in {\mathcal{A}}_t,j\in {\tilde{\mathcal{B}}}_t,\end{array}

(16)\begin{array}{rl}& a_i^k\ge j{\tau }_t+{\displaystyle \sum _{m=1}^{k-1}}\left(d_t^m+{\displaystyle \frac{l_m}{v_b}}\right)+{\mu }_{ij}/v_a+(y_{ij}^k-1)M,\\ & \mathrm{\forall }k\in \mathcal{K},i\in {\mathcal{A}}_t,j\in {\mathcal{B}}_t,\end{array}

(17)\begin{array}{c}{a}_i^k\le \left(j+1\right){\tau }_t+{\displaystyle \sum _{m=1}^{k-1}}\left(d_t^m+{\displaystyle \frac{l_m}{v_b}}\right)-{\mu }_{j+1,i}/v_b+({1-y}_{ij}^k)M,\\ \mathrm{\forall }k\in \mathcal{K},i\in {\mathcal{A}}_t,j\in {\mathcal{B}}_t,\end{array}

(18)\begin{array}{c}{a}_i^{k-1}\ge j{\tau }_t+{\displaystyle \sum _{m=1}^{k-2}}\left(d_t^m+{\displaystyle \frac{l_m}{v_b}}\right)+d_t^{k-1}+{\mu }_{ij}/v_a+(y_{ij}^k-1)M,\\ \mathrm{\forall }k-1,k\in \mathcal{K},i\in {\mathcal{A}}_t,j\in {\mathcal{B}}_t,\end{array}

(19)y_{ij}^k =y_{ij}^{k-1}, \mathrm{\forall }k- 1\in \mathcal{K},k\in {\mathcal{K}}^{\mathcal{\ast }}, i\in {\mathcal{A}}_t, j\in {\mathcal{B}}_t,

(20){\tilde{y}}_{ij}^k={\tilde{y}}_{ij}^{k-1}, \mathrm{\forall }k- 1\in \mathcal{K},k\in {\mathcal{K}}^{\mathcal{\ast }}, i\in {\mathcal{A}}_t, j\in {\tilde{\mathcal{B}}}_t,

(21)a_i^k\ge a_i^{k-1}+l_{k-1}/v_a,\mathrm{\forall } k-1,k\in \mathcal{K},i\in {\mathcal{A}}_t,

(22)a_i^k\le a_i^{k-1}+l_{k-1}/v_b,\mathrm{\forall } k-1,k\in \mathcal{K},i\in {\mathcal{A}}_t,

(23){\mathit{\text{z}}}_{ij},{\widetilde{\mathit{\text{z}}}}_{ij},{\delta }_t^i, {\tilde{y}}_{ij}^k,y_{ij}^k\in \{0,1\},

(24)a_i^k, {\tau }_t\in {\mathbb{R}}^{+} .

The objective function (1) consists of the following components: the total travel cost for AVs, \mu \sum _{i\in {\mathcal{A}}_t}{a}_i^{e_i}, the total waiting cost for bus passengers, \mu \sum _{i,j\in \mathcal{K}}{\psi }_{ij} {\tau }_t/2+\mu {\sum }_{i,j\in \mathcal{K}}\sum _{k=i+1}^{j-1} {\psi }_{ij}{d}_t^k (the first component calculates passengers’ waiting cost at stations, the second component represents passengers’ waiting cost on buses due to station dwelling, as shown in Fig.5), and the fixed cost of the utilized buses, c\sum _{i=1}^{B}i{\delta }_t^i.

Constraints (2)–(4) determine the number of newly utilized buses in period t, as shown in Fig.6, where Constraint (2) ensures that the number of buses falls within the range from one to the upper limit B (where {\delta }_t^i equals 1 if i buses have been utilized in period t); Constraints (3) and (4) establish the relationship between the number of buses and the bus departure interval. Constraints (5)–(9) ensure a safe distance between AVs, as shown in Fig.7. Specifically, Constraint (5) defines the relationship between any two AVs entering the BRT lane in the current period, Constraints (6) implies that an AV entering the lane in the current period will drive behind and next to exactly one AV already on the lane. Constraints (7)–(9) set the minimum distance between two adjacent AVs. Constraints (10)–(12) describe the relationship between AVs and buses, as illustrated in Fig.8. At different stations, there is precisely one bus (whether newly entered or already on the lane) driving in front of and next to any AV upon its arrival. Constraints (13)–(18) determine AV arrival times at various nodes. Specifically, one AV should arrive at stations after the leading bus arrives but before the trailing bus arrives. It should also depart from the previous station after the front bus leaves. Constraints (19) and (20) prohibit overtaking at stations that have not been widened. The set of these stations is denoted by {\mathcal{K}}^{\mathcal{\ast }}. Finally, constraints (21) and (22) constrain AV speeds within the range [ v_{\mathrm{b}},v_{\mathrm{a}}], while constraints (23) and (24) specify binary or nonnegative values for the variables.

Upon solving the preceding optimization problem in periodt, we determine the system states for the next period using the following transition functions. Among them, Constraints (25) and (26) update the sets of buses and AVs already on the BRT lane; Constraints (27) and (28) respectively calculate the arrival times of AVs and buses at different nodes. Finally, we update {\tilde{g}}_i^k as {\tilde{b}}_i^k+d_t^k for i\in {\tilde{\mathcal{B}}}_{t+1},k\in \mathcal{K}.

(25)\begin{array}{c}{\tilde{\mathcal{B}}}_{t+1}=\{i:i\in {\tilde{\mathcal{B}}}_t,{\tilde{b}}_i^K\ge \left(t+1\right)h\}\\ \cup \left\{i:i\in {\mathcal{B}}_t,i\le {\displaystyle \sum _{j=1}^B}j{\delta }_t^j,ht+i{\tau }_t+{\displaystyle \sum _{m=1}^{K-1}}\left(d_t^m+{\displaystyle \frac{l_m}{v_b}}\right)\ge \left(t+1\right)h\right\}.\end{array}

(26){\tilde{\mathcal{A}}}_{t+1}=\{i:i\in {\tilde{\mathcal{A}}}_t, {\tilde{a}}_i^{e_i}\ge \left(t+1\right)h\}\cup \left\{i:i\in {\mathcal{A}}_t,a_i^{e_i}\ge \left(t+1\right)h\right\} .

(27){\tilde{a}}_i^k=\{\begin{array}{l}{a}_i^k,\mathrm{i}\mathrm{f}i\in {\tilde{\mathcal{A}}}_{t+1}\cap {\mathcal{A}}_t,k\in \mathcal{K}\\ {\tilde{a}}_i^k,\mathrm{i}\mathrm{f}i\in {\tilde{\mathcal{A}}}_{t+1}\cap {\tilde{\mathcal{A}}}_t,k\in \mathcal{K}\end{array},

(28){\tilde{b}}_i^k=\{\begin{array}{l}ht+i{\tau }_t+{\displaystyle \sum _{m=1}^{k-1}}\left(d_t^m+{\displaystyle \frac{l_m}{v_b}}\right),\mathrm{i}\mathrm{f}i\in {\tilde{\mathcal{B}}}_{t+1}\cap {\mathcal{B}}_t,k\in \mathcal{K}\\ {\tilde{b}}_i^k,\mathrm{i}\mathrm{f}i\in {\tilde{\mathcal{B}}}_{t+1}\cap {\tilde{\mathcal{B}}}_t,k\in \mathcal{K}\end{array}.

It is important to note that Problem (1) is a mixed-integer programming model characterized by a significant number of discrete and continuous variables, which makes exact solutions challenging, especially on a large scale. In addition, incorporating demand stochasticity into dynamic programming problems introduces the Bellman equation, which is susceptible to the well-known curses of dimensionality. To meet real-world demands for timely responses, it is essential to develop a methodological framework capable of efficiently deriving approximate optimal solutions within a reasonable computation time.

4 Algorithm design

Although the dynamic model has been implemented as discussed in the previous section, the number of AVs involved falls significantly short of the capacity of the BRT lane while still meeting computational time requirements. To address this constraint and enhance the scalability of our framework, we propose a heuristic algorithm based on neighborhood search in this section. Neighborhood search is a commonly used method for solving large-scale combinatorial optimization problems. In each iteration, a better solution is found by searching for the “neighborhood” of the current solution. In our problem, constructing neighborhoods based on AV driving rules allows us to balance accuracy, computational time, and interpretability. This algorithm is used to tackle the optimization problem for each period within the dynamic model.

4.1 Simulation platform

We establish a simulation framework to model AV travel processes alongside predefined bus timetables. This framework incorporates essential input parameters, such as bus departure intervals and station dwell times, to facilitate precise calculations of arrival and departure times for each bus at every station. Additionally, the input includes details about the set of AVs entering the BRT lane, including their entry sequence.

The simulation framework produces essential output data, specifically detailing the arrival times of each AV at every node. To ensure the operational efficiency of the system, we adhere to a set of predefined AV driving rules:

i) AVs are designed to closely follow the AVs in front of them.

ii) AVs will overtake stationary buses at stations unless obstructed by other leading AVs.

iii) The entry of AVs must not disrupt bus operations.

These rules essentially determine the driving sequence of the AVs. Following the constraints regarding the AVs’ arrival times at different nodes, as outlined in Section 3, we can derive details for the AV driving process under given bus timetables. Within our framework, if adding more AVs disrupts bus operations, we define this condition as the lane having reached its capacity. Clearly, the capacity is directly influenced by bus departure intervals, which we will investigate more thoroughly in our numerical studies.

4.2 Neighborhood search algorithm

In this subsection, we present a detailed introduction to the simulation-based heuristic algorithm for bus timetable optimization. As shown in Fig.9, it includes the following steps:

Step 0: Initialize at time period t=0 and system state {\mathbf{s}}_t=\varnothing, where t=0 represents the beginning of operations and {\mathbf{s}}_t=\varnothing indicates an empty lane;

Step 1: Start with the initial iteration number n=0 and {\mathbf{\Omega }}_n={\mathbf{\Omega }}_t ({\mathbf{\Omega }}_t represents the set of feasible solutions in period t). Initialize {\mathit{k}}_{\sigma }=\varnothing ({\mathit{k}}_{\sigma } denotes the optimal solution);

Step 2: Divide {\mathbf{\Omega }}_n into M equal subsets \left\{{\mathbf{\Omega }}_n^1,{\mathbf{\Omega }}_n^2,\dots ,{\mathbf{\Omega }}_n^M\right\} and randomly select a solution {\mathit{k}}_{\mathit{i}}\in {\mathbf{\Omega }}_n^i;

Step 3: Calculate the objective function value f\left({\mathbf{s}}_t,{\mathit{k}}_i\right),\mathrm{\forall }{\mathit{k}}_i\in \{{\mathit{k}}_1,{\mathit{k}}_2,\dots , {\mathit{k}}_M\}, and determine the optimal solution by {\mathit{k}}_{\sigma }\in \mathit{a}\mathit{r}\mathit{g}\underset{k_i}{\mathit{m}\mathit{i}\mathit{n}} f\left(s_t,k_i\right);

Step 4: If n reaches the maximum iteration number N, proceed to step 5; otherwise, update {\mathbf{\Omega }}_{\mathit{n}} to {\mathbf{\Omega }}_{\mathit{n}}^{\sigma }, increment n by 1, and return to step 2;

Step 5: If t reaches the maximum period T, finish the process; otherwise, transition to {\mathbf{s}}_{t+1}, increment t by 1, and return to step 1.

This algorithm employs a systematic approach to solving large-scale combinatorial optimization problems using a combination of neighborhood search heuristics and the Latin hypercube sampling strategy. The Latin hypercube sampling strategy enhances the efficiency of sampling, resulting in higher-quality solutions.

5 Numerical studies

In this section, numerical experiments are conducted on a real-world transportation network to validate the effectiveness of the proposed methodology framework. The objective is to explore the impact of various traffic elements in BRT lanes on the system’s operational performance through sensitivity analysis. Additionally, the results from different scenarios are compared to provide detailed recommendations for deploying AVs in BRT lanes. The experimentation is performed using Visual Studio 2012 on a computer with Intel(R) Core(TM) i5-4460 CPU @ 3.20 GHz and 16 GB RAM. A detailed description of the dataset is provided in Appendix B.

5.1 Performance of the heuristic algorithm

As mentioned previously, the proposed heuristic algorithm is employed to address computational complexity in large-scale scenarios. The convergence of the heuristic method is assessed initially. Fig.10 illustrates the convergence curve of the proposed algorithm, depicting the variation of the objective function with respect to the iteration number. It is evident that the objective value stabilizes after approximately 6 iterations, indicating the rapid convergence of the simulation-based heuristic framework in efficiently discovering high-quality solutions within the computational time requirements of real-world scenarios. In the subsequent analysis, the system operations scheme is established based on 10 iterations for each case.

5.2 System throughput

In this subsection, we initially investigate the effect of departing buses on system capacity. Full capacity is reached when the addition of another AV starts to hinder bus operations, causing delays in scheduled bus arrivals. Fig.11 illustrates the maximum number of AVs that can enter the BRT lane without disrupting the bus timetable, highlighting the rapid decrease in system capacity as the number of buses increases.

Next, we assess the system throughput of the BRT lane accommodating a mixed flow of AVs and buses. This throughput is measured by the traffic volume per unit time when the number of AVs entering the lane reaches its critical state (the maximum system capacity). Specifically, we compare the performance of our proposed optimization model with two alternative strategies: the “entry control” strategy (where AVs are sorted by arrival time, and those likely to cause congestion are denied entry) and the “first-come, first-in” service strategy, where AVs that arrive first are given priority access to the lane.

As shown in Fig.12, the results indicate that the proposed optimization framework initially experiences a rapid increase in system throughput with rising AV demand. However, this growth rate slows once the demand exceeds a certain threshold. This pattern emerges because higher AV demand results in more AVs passing through the system per unit time, leading to a rapid escalation in system throughput. However, as the number of AVs continues to rise, congestion from their interactions hampers the growth rate of throughput. Significantly, our findings demonstrate that the proposed optimization model significantly enhances system throughput compared to the two benchmark strategies. This underscores the efficacy of our optimization framework in improving the efficiency of BRT lanes. Conversely, the “first-come, first-in” strategy performs the poorest, lacking any regulation of AV entry.

5.3 Impact of AV deployment

This section examines the effect of AV deployment on the system. Specifically, we analyze the operational status of AVs and buses under various AV demand scenarios.

5.3.1 Impact of AV demand on bus operations

Fig.13 and Fig.14 depict the impact of AV demand on bus operational costs and passenger waiting times, respectively. These figures reveal closely aligned trends. Initially, with a low number of AVs, the original stopping time of buses at stations is sufficient to accommodate AV overtaking demands, resulting in minimal observable impact. However, as the number of AVs increases, the system must extend the dwell time of buses at stations to facilitate AV driving, which in turn leads to an increase in passenger wait times. Moreover, our analysis highlights that the influence of AVs on bus operations primarily lies in the prolonged dwell times and the associated cost of passenger wait times, while their effect on other costs is relatively insignificant.

5.3.2 Impact of AV demand on AV operations

Fig.15 and Fig.16 demonstrate the correlation between AV demand and average AV speed. As the number of AVs on the road increases, congestion intensifies due to the interplay of AV driving trajectories. Consequently, the average speed of AV vehicles decreases, leading to longer travel times and decreased system efficiency. Therefore, implementing appropriate regulations on the number of AVs entering the lanes based on the system’s status can effectively mitigate congestion and enhance road utilization efficiency.

5.4 Effect of joint optimization

Finally, we compare various optimization schemes to evaluate their impact on system operational costs. Specifically, we assess the performance of joint optimization, separate optimization of AV speeds and bus timetables, and no optimization. All schemes utilize the same objective function, which is the total system cost. The results are summarized in Tab.1. Our observations indicate that the joint optimization model, which balances the operations of autonomous vehicles and buses, achieves a mutually beneficial situation compared to separate optimization or no optimization. This validates the effectiveness of the joint optimization of AV speeds and bus timetables in enhancing the operational efficiency of mixed traffic flow and supports the efficacy of our proposed optimization framework in guiding the deployment of AVs in BRT lanes.

6 Concluding remarks

In summary, we have developed a dynamic mixed-integer linear programming model for the joint optimization of AV speeds and bus timetables on BRT lanes, incorporating stochastic factors such as passenger waiting times and AV travel demand. To enhance the scalability of our framework, we have proposed a simulation-based heuristic algorithm, enabling the generation of high-quality feasible solutions within a reasonable timeframe. Through numerical analysis, we have gained valuable managerial insights into the deployment of AVs in BRT lanes. First, our proposed joint optimization framework significantly enhances the system throughput of the AV-bus mixed traffic system, demonstrating notable improvements in operational efficiency compared to separate optimization of the two vehicle types. Furthermore, with a limited number of AVs, the adoption of autonomous driving can enhance road utilization efficiency without significantly impacting buses. However, as the demand for AVs increases, lane congestion may occur, resulting in significant delays for both bus passengers and AVs. Lastly, the speed discrepancies between AVs and buses greatly influence AV trajectories. Thus, adjusting bus departure frequencies and station dwell times can effectively improve system operational efficiency.

7 Appendix A

8 Appendix B

Data description

We chose Beijing’s Bus Rapid Transit Line 1 for our numerical studies because it offers an appropriate number of intersections and stations for analysis. It comprises 16 stations, 22 intersections, and has a total length of approximately 13 km. Tab.2 provides details about the positional relationships of nodes within BRT Line 1, where s_i represents the ith bus station, I_i denotes the ith intersection, and the “Position” column indicates the distance in meters from each node to the first station.

Our numerical analysis utilizes various parameters, which are presented in Tab.3. It is worth noting that the minimum and maximum values for bus speed are the same, implying a constant bus speed of 40 km/h As for the upper limit of AV speed, a sensitivity analysis was conducted, varying it from 60 to 120 km/h to assess its impact on system operations. Similarly, the departure time interval ranges from 1 to 10 min in the numerical experiments. Fig.17 displays the average daily bus passenger demand on BRT Line 1 in October 2015. The x-axis represents the departing station, the y-axis represents the arriving station, and the z-axis represents the corresponding demand values. It is important to note that our analysis considers the BRT lane in one direction only, resulting in a triangular demand distribution. This means that there may be passengers traveling from station i to station j (where i ≤ j), but no passengers traveling from station j to station i.

References

[1] Antonio G P, Maria-Dolores C, (2022). Multi-agent deep reinforcement learning to manage connected autonomous vehicles at tomorrows intersections. IEEE Transactions on Vehicular Technology, 71( 7): 7033–7043

[2] Aria E, Olstam J, Schwietering C, (2016). Investigation of automated vehicle effects on driver’s behavior and traffic performance. Transportation Research Procedia, 15: 761–770

[3] Castelli L, Pesenti R, Ukovich W, (2004). Scheduling multimodal transportation systems. European Journal of Operational Research, 155( 3): 603–615

[4] Ceder A, Tal O, (2001). Designing synchronization into bus timetables. Transportation Research Record: Journal of the Transportation Research Board, 1760( 1): 28–33

[5] Chen D, Ahn S, Chitturi M, Noyce D A, (2017). Towards vehicle automation: Roadway capacity formulation for traffic mixed with regular and automated vehicles. Transportation Research Part B: Methodological, 100: 196–221

[6] Chen X, Lin X, He F, Li M, (2020). Modeling and control of automated vehicle access on dedicated bus rapid transit lanes. Transportation Research Part C, Emerging Technologies, 120: 102795

[7] Constantin I, Florian M, (1995). Optimizing frequencies in a transit network: A nonlinear bi-level programming approach. International Transactions in Operational Research, 2( 2): 149–164

[8] de Palma A, Lindsey R, (2001). Optimal timetables for public transportation. Transportation Research Part B: Methodological, 35( 8): 789–813

[9] Furth P G, Wilson N H, (1981). Setting frequencies on bus routes: Theory and practice. Transportation Research Record: Journal of the Transportation Research Board, ( 818): 1–7

[10] Guihaire V, Hao J K, (2010). Transit network timetabling and vehicle assignment for regulating authorities. Computers & Industrial Engineering, 59( 1): 16–23

[11] Hadas Y, Shnaiderman M, (2012). Public-transit frequency setting using minimum-cost approach with stochastic demand and travel time. Transportation Research Part B: Methodological, 46( 8): 1068–1084

[12] Han A F, Wilson N H, (1982). The allocation of buses in heavily utilized networks with overlapping routes. Transportation Research Part B: Methodological, 16( 3): 221–232

[13] Ibarra-Rojas O J, Delgado F, Giesen R, Muñoz J C, (2015). Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B: Methodological, 77: 38–75

[14] Ibarra-Rojas O J, Rios-Solis Y A, (2012). Synchronization of bus timetabling. Transportation Research Part B: Methodological, 46( 5): 599–614

[15] Jerath K, Brennan S N, (2012). Analytical prediction of self-organized traffic jams as a function of increasing ACC penetration. IEEE Transactions on Intelligent Transportation Systems, 13( 4): 1782–1791

[16] Levin M W, Boyles S D, (2016). A multiclass cell transmission model for shared human and autonomous vehicle roads. Transportation Research Part C, Emerging Technologies, 62: 103–116

[17] Li Z C, Lam W H, Wong S C, Sumalee A, (2010). An activity-based approach for scheduling multimodal transit services. Transportation, 37( 5): 751–774

[18] Liu Z, Song Z, (2019). Strategic planning of dedicated autonomous vehicle lanes and autonomous vehicle/toll lanes in transportation networks. Transportation Research Part C, Emerging Technologies, 106: 381–403

[19] Neufville R, Abdalla H, Abbas A, (2022). Potential of connected fully autonomous vehicles in reducing congestion and associated carbon emissions. Sustainability, 14( 11): 6910

[20] Newell G F, (1971). Dispatching policies for a transportation route. Transportation Science, 5( 1): 91–105

[21] Salzborn F J, (1972). Optimum bus scheduling. Transportation Science, 6( 2): 137–148

[22] Schéele S, (1980). A supply model for public transit services. Transportation Research Part B: Methodological, 14( 1–2): 133–146

[23] Shladover S E, Su D, Lu X Y, (2012). Impacts of cooperative adaptive cruise control on freeway traffic flow. Transportation Research Record: Journal of the Transportation Research Board, 2324( 1): 63–70

[24] Shrivastava P, Dhingra S L, (2002). Development of coordinated schedules using genetic algorithms. Journal of Transportation Engineering, 128( 1): 89–96

[25] Sun P, Nam D, Jayakrishnan R, (2022). An eco-driving algorithm based on vehicle to infrastructure (V2I) communications for signalized intersections. Transportation Research Part C: Emerging Technologies, 144: 103876

[26] Swaroop D V A H G, Hedrick J K, Chien C C, Ioannou P, (1994). A comparision of spacing and headway control laws for automatically controlled vehicles 1. Vehicle System Dynamics, 23( 1): 597–625

[27] Tscharaktschiew S, Evangelinos C, (2019). Pigouvian road congestion pricing under autonomous driving mode choice. Transportation Research Part C, Emerging Technologies, 101: 79–95

[28] Urmson C, Anhalt J, Bagnell D, Baker C, Bittner R, Clark M N, Ferguson D, (2008). Autonomous driving in urban environments: Boss and the urban challenge. Journal of Field Robotics, 25( 8): 425–466

[29] van Arem B, van Driel C J G, Visser R, (2006). The impact of cooperative adaptive cruise control on traffic-flow characteristics. IEEE Transactions on Intelligent Transportation Systems, 7( 4): 429–436

[30] Wu Y, Tang J, Yu Y, Pan Z, (2015). A stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time. Transportation Research Part C: Emerging Technologies, 2015, 52: 15–31

[31] Yu B, Kong L, Sun Y, Yao B, Gao Z, (2015). A bi-level programming for bus lane network design. Transportation Research Part C: Emerging Technologies, 55: 310–327

[32] Yu H, Jiang R, He Z, Zheng Z, Li L, Liu R, Chen X, (2021). Automated vehicle-involved traffic flow studies: A survey of assumptions, models, speculations, and perspectives. Transportation research, Part C: Emerging technologies, 127: 103101

RIGHTS & PERMISSIONS

Higher Education Press