Incorporating Queueing Dynamics into Schedule-Driven Traffic Control

1 Introduction

As traffic congestion in cities continues to increase, it is generally recognized that better optimization of traffic signals is crucial to future urban mobility, and this fact, together with emergence of ubiquitous sensing capabilities, has led to new thinking around real-time approaches to this long studied problem (e.g., [Wongpiromsarn et al., 2012; Varaiya, 2013; El-Tantawy et al., 2013; Duncan et al., 2014; Mitrovic et al., 2019; Smith, 2020]. One promising approach that has emerged in recent years and is aimed specifically at urban traffic control, has been referred to as scheduledriven traffic control. [Xie et al., 2012a; Xie et al., 2012b; Smith et al., 2013] This approach treats traffic control as a decentralized, online planning process, exploiting a novel formulation of the intersection control problem as a singlemachine scheduling problem (where input jobs are sequences of spatially proximate vehicle clusters representing queues and approaching platoons). This aggregate representation enables generation of near-optimal timing plans for individual intersections in real-time, which are then shared with neighboring intersections to achieve network level coordination. Original work demonstrated substantial traffic flow efficiency improvements over statically optimized timing plans in actual field test experiments [Smith et al., 2013]; and subsequent work has explored the further advantages of incorporating multi-modal traffic flows [Xie et al., 2014], integrating with queue management objectives [Hu and Smith, 2017a; Hu and Smith, 2017b], exploiting higher fidelity predictive models [Goldstein and Smith, 2019], upstream propagation of congestion information [Hu and Smith, 2018; Hu and Smith, 2019], control of vehicle speed in connected vehicle setting [Hu et al., 2019], use of stochastic sampling for modeling turning proportions [Dhamija et al., 2020], and learning of model parameters [Hu and Smith, 2020]. Already incorporating many of these advances, this schedule-driven traffic control technology is now deployed and operating in 8 North American cities.

Despite this success, there is room for further improvement. One key to the effectiveness of any schedule-driven traffic control algorithm is an ability to accurately predict when the sensed vehicles will arrive at and pass through the intersection. All prior work in schedule-driven traffic control has assumed a static vehicle arrival model to make this prediction (as originally proposed in [Xie et al., 2012a]). Initially, each vehicle cluster is associated with a free-flow arrival time, computed using a fixed free-flow speed estimate and the distance from vehicle sensor location to the intersection. In situations where queued vehicles are already present at the intersection, a delay proportional to the queue count (the number of the queued vehicles) is added to the free-flow arrival time, using the current queue count that remains unchanged, and this delay is propagated to all vehicle clusters within the planning horizon. The summation of the queueing delay and the free-flow arrival time to the end of queue is thus taken as a prediction of the estimated arrival time for each vehicle cluster.

One limitation of this static predictive model, however, is that it ignores the fact that the queue count and its incurred queueing delay should vary as different partial signal timing schedules (i.e., different possible futures) are explored during the online planning process. More specifically, the vehicle cluster's arrival time incorporating queueing delay depends on when the previously queued vehicles are discharged and when it joins the queue, and this time can be better predicted through the previous partial schedule's state and its free-flow arrival time. We would expect to be able to further boost the performance of the traffic signal control system by introducing the ability to predict queueing delay online in response to observed traffic behavior.

In this paper, we propose an online queue prediction algorithm that incorporates queueing dynamics into this forward search process for a signal timing schedule. Our algorithm computes a more accurate estimate of the delay a queued vehicle will experience than static queue estimation techniques without increasing overall search complexity. As each search state is generated, an incremental queueing delay relative to the previous queued vehicle within the horizon is projected, based on the previous state, the free-flow arrival time, and the queue dissipation model. The resulting total queueing delay is considered in addition to the original cumulative delay caused by signal operations when evaluating alternative partial schedules. With this extension, we are able to better capture not only how the intersection's queues vary over time but also the impact of vehicle stops on cumulative delay at the intersection. We demonstrate the potential of this approach through microscopic traffic simulation of a real-world road network, showing a 10 - 15% reduction in average wait times in heavy traffic scenarios over a schedule-driven variant that is utilizing the previous static predictive model.

2 Schedule-Driven Traffic Control

As noted above about the schedule-driven approach, the essential consequence of the single machine scheduling problem formulation of [Xie et al., 2012b] is that traffic flows are treated as sequences of clusters c over the planning (or prediction) horizon. Each cluster c is defined as (|c|, arr, dep), where |c|, arr and dep are number of vehicles, arrival time and departure time respectively. Vehicles approaching an intersection from the entry roads are clustered together if the time gap between them is less than a pre-specified time interval (e.g., 1 second). The clusters then become the input jobs that must be sequenced through intersection (i.e., the single machine). Once a vehicle departs the intersection, it is sensed and grouped into a new cluster by the downstream neighbor intersection. The sequences of clusters provide short-term variability of traffic flows for optimization and preserve the non-uniform nature of real-time flows.

More specifically, the input to the online planning process at the beginning of each planning cycle is a set C of phase cluster sequences, where a phase is a compatible traffic movement pattern such as East-West traffic flow. A phase cluster sequence CP,i for a given phase i is obtained by merging those constituent road cluster sequences CR,m that can proceed concurrently through the intersection and belong to the phase, where each CR,m consists of (|c|, arr, dep) triples that reflect each approaching or queued vehicle on entry road segment m and are ordered by increasing arr. The travel time on entry road m defines a finite horizon (Hm), and the prediction horizon H is the maximum over all road segments.

During planning, each cluster is viewed as a non-divisible job and a forward-recursion dynamic programming search is executed in a rolling horizon fashion to continually generate a phase schedule that minimizes the cumulative delay of all clusters. In practice, the planning cycle is repeated every second or two, to reduce the uncertainty associated with clusters and queues. The process constructs an optimal sequence of clusters that maintains the ordering of clusters along each road segment m, and each time a phase change is implied by the sequence.

Formally, the resulting control flow can be represented as a tuple (S, CCF ) shown in Figure 1, where S is a sequence of phase indices, i.e., (s1, · · · , s|S|), CCF contains the sequence of clusters (c1, · · · , c|S|), ci ∈ C and the corresponding starting time after being scheduled. More precisely, the delay that each cluster contributes to the cumulative delay ∑|S| k=1 d(ck) is

where ast is the actual start time that the vehicle is allowed to pass through, which is determined by arr and permitted start time (pst). For a partial schedule Sk, the corresponding state variables are defined as a tuple, (s, pd, t, d), where s is phase index and pd is duration of the last phase, t is the finish time of the kth cluster and d is the accumulative delay for all k clusters. The state variable of Sk can be updated from Sk-1, and the corresponding pst for ck is equal to t +MinSwitch(s, i), where MinSwitch(s, i) returns the minimum time required for switching from phase s to i and slti is the start-up lost time for clearing the queue in the phase i. The optimal sequence (schedule) C ∗CF is the one that incurs minimal delay for all vehicles.

3 Incorporating Queueing Dynamics into Scheduling

3.1 Queueing Delay

Other than the delay caused by the signal operations, i.e., d(c) = |c| · (ast - arr(c)), a cluster may experience an extra delay, known as queueing delay, if the cluster's constituent vehicles are forced to decelerate or stop due to queued vehicles in front of them. In the static vehicle arrival model utilized in previous work, this delay is considered to be proportional to current queue count (the number of the queued vehicles in front of the approaching cluster). This count is assumed to

Algorithm 1 Calculate qdinter and qdintra of c

Require: 1) pst, a0, a1, sk; 2) (s, pd, t, d) of Sk-1 1: i = sk; c = next job of phase i; qdinter, qdintra = 0 2: w =max(0, |c| - 1) ▷ exclude the first vehicle of c 3: if pst > arr(c) and c is not queued then ▷ c will stop 4: if s ̸= i and arr(c) > t then ▷ New phase starts 5: qdintra = w · (a0 - a1) 6: dep(c) = dep(c) + a0 + max(0, w - 1) · a1 7: else if arr(c) ≤ t then ▷ Queue already exists 8: qdinter = a1 9: dep(c) = dep(c) + w · a1 10: end if 11: qdintra = qdintra + (w + 1)w/2 · a1 12: end if 13: return (dep(c), qdinter, qdintra)

persist throughout the planning horizon and is not recomputed as different partial schedules are expanded.

To better capture the queueing dynamics in these situations, we propose to incorporate an alternative vehicle arrival model where queueing delay evolves as a function of different partial signal timing schedules (i.e., different possible futures) that are explored during the online planning process. More specifically, as the search states representing different partial schedules are expanded to incorporate the next approaching cluster, the possibility of queuing delay is assessed. If the arr of the next cluster to be added to the schedule, computed using a fixed free-flow speed estimate and the distance from vehicle sensor location to the intersection, is less than the finish time t of the previous search state (i.e., the intersection departure time of the previous cluster), then this cluster is determined to have joined the queue. In this case, the headway (i.e., the temporal gap between two adjacent queued vehicles) of all preceding vehicles in the queue ahead of the cluster is summed and added to the cluster's free-flow arr as the queueing delay, and arr and dep of the vehicle clusters will be thus delayed.

To incorporate the queueing delay into the objective, a queueing delay that is relative to ast is added to the original cluster delay, and the total delay contributed by cluster c is rewritten as

where qd(c) is the queueing delay of c and can be de determined through the search process and a queue dissipation model that will be introduced in the next section.

3.2 Queue DissipationModel

The total queueing delay for a single vehicle due to the existing standing queue can be estimated using the following relationship adopted from [Head, 1995]):

where a0 and a1 are parameters that can be selected on the basis of the particular intersection and Nq is the number of vehicles already in the queue. The interpretation of this model is that a0 is a sum of the initial headway and residual start-up lost time for the second vehicle in the queue, and the following

Algorithm 2 Calculate (pd, t, d) of Sk

Require: 1) (s, pd, t, d) of Sk-1 ; 2) sk

1: i = sk; c = next job of phase i 2: Compute qd, and update dep(c) and pst: a: pst = t +MinSwitch(s, i); b: (dep(c), qdinter, qdintra) =Algorithm 1, given (pst, a0, a1), input 1) and 2); ▷ Queueing dynamics c: pst = pst + qdinter; ▷ insert qdinter if needed 3: ast =max(arr(c), pst) ▷ Actual start time of c 4: if s ̸= i and pst > arr(c) then ast = ast + slti 5: end if 6: t = ast +dep(c) -arr(c) ▷ Actual finish time of c 7: if s ̸= i then pd = t -pst 8: else pd = pd+ (t -pst) 9: end if 10: d = d+ |c| · (ast -arr(c)) + qdintra ▷ Total delay 11: return (pd, t, d)

vehicles joining the queue experience an additional headway a1. Since the initial speed is small, a0 should be greater than a1. With this model, we can estimate how much delay a queued vehicle will experience before being dissipated and the headway relative to the previous queued vehicle. Although the model can be extended to a more complicated polynomial or non-linear functional form, our experimental data shows that a linear model is sufficient to model dissipation. The parameters can be selected by field experiments or learned by online learning algorithms.

To retain the efficiency of generating longer-horizon plans, we define two types of queueing delay for a vehicle cluster that contains multiple vehicles: 1) intra-cluster queueing delay and 2) inter-cluster queueing delay. Intra-cluster queueing delay is the delay experienced by all vehicles other than the first vehicles within the cluster, and it can cause the enlargement of the cluster (i.e., dep(c) increases). Inter-cluster queueing delay, alternatively, is the delay experienced by the first vehicle within the cluster if there are already one or more queued clusters in front of it, and the pst will be delayed. For the example of Figure 1, the stop of cluster (2, 1) causes a qdinter between (2, 1) and (2, 2), and the stop of (2, 2) causes qdinter between (2, 2) and (2, 3) and qdintra within (2, 3). With these definitions, Equation 2 can be rewritten as

where qdinter and qdintra are the inter-cluster and intracluster queueing delay and qd(c) = |c| · qdinter + qdintra. qdintra and qdinter can be calculated given a0, a1 and the state tuple (s, pd, t, d) by Algorithm 1.

In Algorithm 2, we describe how the search state Sk is expanded from Sk-1, given the previous tuple (s, pd, t, d), based on a greedy realization of planned signal sequence. Algorithm 1 is executed at Line 2 of Algorithm 2, and then qdinter, qdintra, and dep(c) are derived for revising pst and delay contribution accordingly. Then, ast is determined by the maximum of arr and pst at Line 3 of Algorithm 2. If arr is less than pst, this means that the cluster will stop and the both types of queueing delay should be included. We consider two cases after knowing the cluster will stop. First, if a cluster joins an existing queue, then its qdintra is calculated based on the following theorem:

Theorem 1. If a cluster c joins an existing queue, the incurred queueing delay within the cluster is O(|c|2 ) and can be calculated by qdintra = (|c|-1)|c| 2 · a1

Proof. The queueing delay experienced by the second vehicle within the cluster is a1; The one experienced by the third vehicle is 2a1 contributed by the queueing delay from the previous vehicle and itself, and so on. qdintra experienced by the vehicles within c other than the first vehicle is thus

Then, qdinter is set to a1 and added to pst when the cluster joins an existing queue. Its contribution to the cumulative delay is |c| · a1. Equation 4 can be rewritten as

Second, if a new phase has just started in the currently expanded search state, then the second vehicle within the added cluster will experience headway a0 instead of a1 and the rest of vehicles will still experience a1 instead. Therefore, the queueing delay needs to be offset by the difference (a0 - a1). Note that there is no qdinter in this case since it is the first cluster in the new phase.

3.3 Online Planning with Queueing Delay

In this section, we describe how to integrate queueing delay into the online planning algorithm and predict the queue count. The goal is to improve traffic control performance by utilizing a more accurate predictive queueing model.

First, before computing the schedule, we determine whether a vehicle is queued or not given the snapshot of current queue count. Then, all vehicles approaching the intersection are clustered together based on the free-flow arr at their free-flow speed. In other words, approaching vehicles are clustered according to their geometrical proximity. After clustering, we delay arr of the queued clusters based on the snapshot by adding Equation 3 according to the queue count they observe when joining the queue, and this delayed arr will serve as a part of the initial state for building the schedule.

When computing the schedule, each cluster will be checked if it joins a queue. If so, dep(c) of the free-flow clusters will be increased, and the queueing delay is computed to update pst and the objective as described in Algorithm 2 and 1 at each expansion step of the search.The physical interpretation of this update is that the stop due to the current queue expands the cluster duration dur by a1 · max(0, |c| - 1) and increases the gap between clusters' arrival time by qdinter.

Since the previously queued clusters will depart the intersection at the ast = max(pst, arr(c)) that is determined by the schedule, we can predict the queue count at any future time points within the horizon H by tracking the number of the dissipated vehicles and the number of vehicles joining the queue at each search state. Three cases mentioned in Algorithm 1 are necessarily considered for predicting the queue count: a) If the cluster does not stop, the queue count of this cluster is 0. b) If the cluster stops and a queue does not exist

Algorithm 3 Predict Q(Sk) given Sk-1 and ck Require: 1) Sk-1,Q(Sk-1); 2) ck-1 and ck 1: l(Sk) = 0;ptr = ck-1 2: while max(phase start, arr(ck-1)) < ast(ptr) do 3: if t(ptr) < arr(ck) then ▷ check end time t of ptr 4: l(Sk) = l(Sk) + |ptr| ▷ ptr is dissipated 5: end if 6: ptr = previous cluster of the cluster ptr 7: end while 8: Q(Sk) = Q(Sk-1) + |ck-1| - l(Sk)

(i.e., a start of a new phase), the queue count is 0 as well. c) If the cluster stops and a queue already exists, given the queue count of the previous state, then the queue count of the current state is represented as

where Q(Sk) is the observed queue count of the partial schedule Sk for ck, and l(Sk) is the number of dissipated vehicles between the arrivals of ck and ck-1.

More specifically, the number of the vehicles joining the queue at each state is simply |ck-1| of the previous cluster in the same road cluster sequence CR,m on road segment m. However, knowing the number of the dissipated vehicles requires to count how many vehicles whose end times t fall within the range between two adjacent arrivals are dissipated. An algorithm that computes Q(Sk) in the case c) is provided in Algorithm 3,

Since the extension does not generate additional states during the search, it retains the efficiency of scheduling with longer horizons, and the complexity is still polynomial in |H| = H/δ, the number of time steps in H [Xie et al., 2012b], given a time resolution δ.

Currently, the baseline arr for calculating delay is assumed to be arrival time of the vehicle cluster if moving according to the static arrival model. In the following section, a concept of minimum guaranteed queue is introduced to define the objective (cumulative delay) for taking both queueing delay and signal delay into consideration.

3.4 MinimumGuaranteed Queue

According to Equation 1, each cluster contributes a time difference between the ast and the free-flow arr to the cumulative delay. After taking queueing delay into account, ast is offset by a queueing delay (equally a headway), i.e, qdinter, and qdintra are added according to Equation 4. In turn, the delay contribution of each cluster should include the total queueing delay caused by all previous queued vehicles other than the signal delay. However, to define the cluster delay correctly, arr should be a delayed arr in which we assume each cluster will experience its own minimum queue count if the corresponding green phase persists.

Definition 1 (Minimum Guaranteed Queue). Minimum Guaranteed Queue (MGQ) is the minimum queue count a moving cluster observes when it joins the queue under an assumption that the corresponding phase stays green until the cluster exits.

MGQ is used to specify arr of the cluster delay (i.e., Equation 5) when both qdintra and qdinter are considered and taken as a baseline to define delay. Meanwhile, the minimum queueing delay without any intervention of the traffic signal can be calculated directly from MGQ. However, since MGQ is irrelevant to any state transition, the solutions will only differ by a constant if another baseline arr, e.g., arr at the free-flow speed, is applied.

Theorem 2. The solutions of any baseline arr will only differ by a constant compared to the arr calculated with MGQ.

Proof. arr is not state-dependent due to the traffic signal operations. Therefore, we can replace it with any baseline arr without compromising the optimality of the solution.

Due to Theorem 2, we simply use the free-flow arr to compute the schedule without loss of optimality unless there is a need for acquiring the actual cost of the schedule.

4 Experimental Evaluation

In this section, we compare the above described online queue prediction algorithm to three other real-time traffic control methods. First, we include the two most recent variants of the schedule-driven traffic control system: a) The variant that ensures queueing stability (i.e., that queues will not increase without bound) [Hu and Smith, 2017a; Hu and Smith, 2017b] serves as the primary benchmark since this version has been proved to be effective in several North America cities [Smith, 2020], and b) the more recent bidirectional extension that utilizes the downstream congestion information [Hu and Smith, 2018; Hu and Smith, 2019] is also included as another point of comparison. We implement new versions of each of these two extensions that incorporate online queue prediction. Second, we compare to a variant of backpressure adaptive control [Wongpiromsarn et al., 2012; Varaiya, 2013] that makes decisions based on the estimated queue count and ensures queueing stability. 1

To evaluate our approach, we simulate performance on a two-intersection model and a real world network. The twointersection model is used to estimate model parameters. The real world network is used to evaluate the performance of planning with queueing delay in a larger complex real network and real traffic pattern. The simulation model was developed in VISSIM, a commercial microscopic traffic simulation software package. We assume that each vehicle has its own route as it passes through the network and measure how long a vehicle must wait for its turn to pass through the intersections (the delay). Tested traffic volume is averaged over sources at network boundaries. To assess the performance boost provided by the proposed algorithm, we measure the average waiting time of all vehicles over five runs. All simulations run for 1 hour of simulated time. Results for a given experiment are averaged across all simulation runs with different random seeds.

1 Note also that previous research with the baseline scheduledriven approach has shown its comparative advantage over prior online planning approaches to real-time traffic signal control [Xie et al., 2012a].

6

Since the headway parameters a0 and a1 are critical for computing the queueing delay, setting them correctly could affect how the queueing dynamics are modeled. We consider a simple two-intersection model with 2-way, single lane, and multi-directional traffic flow as controlled experiments. The source of traffic is assumed to be stationary and set to 500 cars/hour. In Figure 2, three scenarios are plotted. We can see that the three lines actually fit the queue dissipation model (i.e., Equation 3) closely, which can be characterized by an intercept (i.e., a0) and a slope (i.e., a1). The difference between them is in whether vehicles experience a signal delay or not. If the signal delay is larger than 0, an additional start-up lost time should be added to the average delay, leading to an upper shift of the line. We use a linear function to approximate the line without the signal delay, and the estimations of a0 and a1 are approximately (5.8s, 2.4s). We then apply these values to a larger complex network. For non-stationary traffic, a0 and a1 can be adjusted adaptively through tracking arrival and departure of vehicles. It is worth noting that the performance of this model shows the same trend as the following urban network model.

The network model we consider for a more complex scenario is based on the St. Albert neighborhood of Canada as shown in Figure 3. The network consists of 11 intersections that basically have multiple phases. It can be seen as a two-way corridor network. To explore how the proposed algorithm performs under different traffic patterns and demands, we evaluate two traffic patterns: AM and PM rush hour, and categorize traffic demand into three different groups: low (AM/PM 116.18/66.55 cars/hour), medium (AM/PM 249.27/99.82 cars/hour), and high (AM/PM 332.36/133.10 cars/hour). The low demand data is extracted from the field data of St. Albert of 6-9am, 1/6/2020 - 1/8/2020, and ramped up to generate two other demands.

Table 1 shows that both versions of the proposed method are basically comparable except that the one combining with benchmark (i.e., ensure queueing stability) performs better than the other by 2.4% under the AM high demand case. In the following results, we mainly consider this variant to present our evaluation. It shows the online queue prediction to yield a delay improvement over the benchmark and the bi-directional extension of about 13%/19% and an improvement of about 20% over backpressure control for the AM high traffic demand case. For the number of stops, the improvements are 24%, 23% and 48% respectively. For low and medium traffic, the de-

Average Delay (second) and Number of Stops

lay and the stops of the proposed approach are generally better than the three approaches. The online queue prediction enabling planning with the queueing delay prevents the decision making from falling into short-sighted decisions and allows it to outperform backpressure, which only utilizes current queue counts to make decisions. On the other hand, compared to the benchmark, which is actually comparable to the bi-directional extension, taking the queueing delay into account more accurately captures realistic traffic variation and improves the schedule. Moreover, from the AM high demand case, we can see that maintaining queueing stability and using prediction are both crucial for reducing congestion.

For the PM rush hour, although the demand is not as large as the AM rush hour, several dominating roads are present instead of a single main road like the AM rush, requiring better coordination among the intersections. Because of the lower demand, the backpressure approach is not able to reduce delay through the simple queueing policy. Contrarily, the backpressure's weakness to coordinate intersections is to worsen the delay of entire network, so it has the largest delay among four approaches under the PM low demand. The proposed online queue prediction is generally better than the benchmark and the bi-directional extension, even in PM rush hour it has shorter queues. The benefits come from the fact that the proposed vehicle arrival model is more accurate at predicting arrival times.

Figure 4 also shows the average queue counts of two bottleneck intersections, Boudreau-Bellerose and BoudreauCampbell, under the AM high demand scenario. The average queue count of four roads at both intersections are shown. The proposed approach has the shortest queue, compared to the benchmark and the backpressure approach respectively. As can be seen, the use of online queue prediction reduces the queue count and balances the queues among four roads through planning. For example, compared to the backpressure, although the proposed approach has longer queues at the first three roads of Boudreau-Bellerose, the reduction of the queue count on the forth road is significant in return. It is the same for the third road at Boudreau-Campbell.

According to Algorithm 3, future queue count is predicted during generating schedule and tracking arrivals/departures of the clusters. In Table 2, two comparisons on different phases (i.e., 2 and 8) at Boudreau-Sir Winston Churchill (SWC) intersection are made. We take the second and the third cluster (i.e., c2 and c3) as predictions of the future queue count. Due to the uncertainty of arrival time, the measured queue count that is within a window (e.g., ±3 or ±5 second) and has the smallest error is chosen to compute root-mean-square error (RMSE). The prediction error is around 1 vehicle, and the average lookahead h(second) could be up to 40 second.

5 Conclusion

In this work, we considered the limitations of prior approaches to schedule-driven traffic control that rely on a static arrival model without regard to the fact that the queue count and the incurred delay should vary as different partial signal timing schedules are explored during the online planning process. An online queue prediction algorithm is proposed to achieve better delay and number of stops in circumstances of high traffic demand. In this algorithm, each scheduling agent computes queueing delay of each cluster dynamically, as states are expanded during the search process, given the previous state and the free-flow arrival time, and predicts the arrival time dynamically. Experimental results showed that the proposed approach improves cumulative delay overall in comparison to the schedule-driven traffic control approaches using a static vehicle arrival model and a backpressure approach, and that solutions provide substantial gain in highly congested scenarios.

Acknowledgements

Stephen F. Smith's work was supported in part by the National Science Foundation, under award #2038612, and the Mobility21 University Transportation Center at CMU.