Throughput of Freeway Networks under Ramp Metering Subject to Vehicle Safety Constraints

The network is modeled as a directed acyclic graph. The nodes represent either junctions (merge or diverge), or sources/sinks; the edges represent either single-lane freeway segments that connect two junctions, or on- and off-ramps that connect sources to merge nodes and diverge nodes to sinks, respectively; see Figure 1. We refer to any subset of the freeway segments as the mainline. For simplicity, we assume that each source has exactly one outgoing on-ramp, and each sink has exactly one incoming off-ramp. We distinguish between two types of merge node: on-ramp nodes, which have at least one incoming on-ramp, and regular merge nodes (or simply merge nodes), which have no incoming on-ramp. Similarly, we distinguish between an off-ramp node and a diverge node. We denote the set of on-ramp nodes by $\mathcal{M}$. For simplicity, we assume that each on-ramp node has exactly one incoming on-ramp edge. Thus, $\mathcal{M}$ also specifies the set of on-ramp edges. For on-ramp $i\in\mathcal{M}$, we let $\mathcal{M}_{i}^{+}$ be the set of its successor on-ramps, i.e., the set of all on-ramps that are immediately downstream of on-ramp $i$. An element of $\mathcal{M}_{i}^{+}$ is denoted by $i^{+}$. Similarly, we let $\mathcal{M}_{i}^{-}$ be the set of its predecessor on-ramps. We say that two edges are adjacent if the head of one edge is the tail of the other edge. A route is a sequence of adjacent edges, with the first edge being an on-ramp and the last edge being an off-ramp. The collection of all routes is denoted by $\mathcal{P}$.

Vehicles arrive to on-ramps according to some exogenous stochastic process and join the on-ramp queues. For any on-ramp, we assume a point queue model with unlimited capacity. We also assume that vehicles that reach their destination off-ramp node, immediately leave the network without creating any obstruction. Once a vehicles is released from an on-ramp into the mainline, it follows standard speed and safety rules, which will be explained in the following section.

Vehicles have the same length $L$, the same acceleration and braking capabilities, and are equipped with V2V and V2I communication systems. The exact information communicated by a vehicle will be specified in Section III, where we introduce our ramp metering policy. We use the term ego vehicle to refer to a specific vehicle under consideration, and denote it by $e$. Consider a vehicle following scenario and let $v_{e}$ (resp. $v_{l}$) be the speed of the ego vehicle (resp. its leading vehicle), and $S_{e}$ be the safety distance between the two vehicles required to avoid collision. We assume that $S_{e}$ satisfies $S_{e}=hv_{e}+S_{0}+\frac{v^{2}_{e}-v^{2}_{l}}{2|a_{\min}|}$, which is calculated based on an emergency stopping scenario with details given in [14]. Here, $h>0$ is a safe time headway constant, $S_{0}>0$ is an additional constant gap, and $a_{\min}<0$ is the minimum possible deceleration of the leading vehicle. We consider two general modes of operation for each vehicle: the speed tracking mode and the safety mode. The main objective in the speed tracking mode is to adjust and maintain the speed to the free flow speed $V_{f}$ when the ego vehicle is far from any leading vehicle; the main objective in the safety mode is to avoid rear-end collision once the ego vehicle gets close to the leading vehicle.

We assume that vehicles obey the following rules:

• (VC1)

  The ego vehicle maintains the constant speed $V_{f}$ if:

  • (a)

    it is at a safe distance with respect to its leading vehicle ¹¹1At a diverge node, the leading vehicle is uniquely determined by the ego vehicle’s route choice., i.e., $y_{e}\geq S_{e}$, where $y_{e}$ is the distance between the two vehicles. Note that if its leading vehicle is also at the constant speed $V_{f}$, then $y_{e}\geq S_{e}=hV_{f}+S_{0}$. This distance is equivalent to a time headway of at least $\tau:=h+(S_{0}+L)/V_{f}$ between the front bumpers of the two vehicles.

  • (b)

    it is near a merge node and predicts to be at a safe distance with respect to its leading vehicle after reaching the merging node, i.e., $\hat{y}_{e}(t_{m})\geq\hat{S}_{e}(t_{m}):=h\hat{v}_{e}(t_{m})+S_{0}+\frac{\hat{v}_{e}^{2}(t_{m})-\hat{v}_{\hat{l}}^{2}(t_{m})}{2|a_{\min}|}$, where $t_{m}$ is the time the ego vehicle predicts to reach the merge node, $\hat{y}_{e}$ is the predicted distance between the two vehicles, and $\hat{v}$ is the predicted speed. Each vehicle uses the following speed prediction rule to calculate its predicted time of merging, position, and speed: if in the speed tracking mode, it assumes that it remains in this mode in the future; if in the safety mode, it assumes a constant speed trajectory. These information are then communicated among all vehicles near a merge node via V2V communication.

• (VC2)

  there exists $T_{\text{free}}$ such that for any initial condition, vehicles reach the free flow equilibrium after at most $T_{\text{free}}$ time if no other vehicle is released from the on-ramps. The free flow equilibrium refers to a state where each vehicle is moving at the constant speed $V_{f}$ and will maintain this speed in the future if no additional vehicle is released from the on-ramps.

In order to have a complete description of the network, we also need to specify the demand at the microscopic level. We will do this in the next section.

For convenience in the analysis, we adopt a discrete time setting with time steps of size $\tau$, where $\tau$ is the minimum safe time headway at the free flow speed defined in Section II-B. Let vehicles arrive to on-ramp $i\in\mathcal{M}$ according to an i.i.d. Bernoulli process with parameter $\lambda_{i}\in[0,1]$. The arrival processes are assumed to be independent across different on-ramps. That is, at any given time step, the probability that a vehicle arrives at the $i$-th on-ramp is $\lambda_{i}$ independent of everything else. We let $\lambda:=[\lambda_{i}]$. A vehicle arriving to on-ramp $i$, chooses to take route $p\in\mathcal{P}$ with probability $R_{ip}\in[0,1]$ independent of everything else. Naturally, for every on-ramp $i$, $\sum_{p}R_{ip}=1$, and $R_{ip}=0$ for any $p$ that is not compatible with the network topology. We assume that the vehicles do not change their route choice while in the network. We stack the routing probabilities in a routing matrix $R=[R_{ip}]$. Let $\rho_{i}=\sum_{j}\sum_{p:i\in p}\lambda_{j}R_{jp}$ be the average induced load on on-ramp $i$, where the notation $i\in p$ means that on-ramp $i$’s node is on route $p$. This is the average number of arrivals in the network that wants to cross on-ramp $i$’s node in order to reach their destination. The performance of a ramp metering policy is quantified in terms of the maximum demand it can handle. We will formalize this in the next section.

To conveniently track vehicle locations in discrete time, we introduce the notion of slot. A slot is associated with a particular point on the mainline at a particular time. Consider the maximum number of distinct slots that can be placed on a freeway segment, such that the distance between adjacent slots is $hV_{f}+S_{0}+L$, i.e., the minimum safety distance at the free flow speed as per (VC1) plus the vehicle length. Consider a configuration of these slots at $t=0$. At the end of each time step $\tau$, each slot replaces the next slot with the last slot replacing the first slot of that segment. Without loss of generality, we let the location of the first and last slots of each segment coincide with the tail and head of that segment at the end of each time step. Thus, if the ego vehicle is released from an on-ramp at the end of a given time step, its location coincides with a slot.

For $i\in\mathcal{M}$, let $Q_{i}(t)$ be the set of the route choices of the vehicles waiting at on-ramp $i$, arranged in the order of their arrival, at time $t$. We use $|Q_{i}(t)|$ to denote the queue size at on-ramp $i$ at time $t$. Let $|Q(t)|=[|Q_{i}(t)|]$ be the vector of queue sizes at all the on-ramps at time $t$. A ramp metering policy is a function $\pi(t)=[\pi_{i}(t)]$, where $\pi_{i}(t)=1$ if a vehicle is released from on-ramp $i$ at time $t$, and $\pi_{i}(t)=0$ otherwise. The key metric we use to evaluate the performance of a ramp metering policy is its throughput, which is defined as follows: for a given ramp metering policy $\pi$ and routing matrix $R$, let $U_{\pi,R}$ be the set of $\lambda$’s for which $\limsup_{t\to\infty}\mathbb{E}\left[|Q_{i}(t)|\right]<\infty$ for all $i\in\mathcal{M}$. We say that the network is under-saturated if $\lambda\in U_{\pi,R}$; otherwise, it is called saturated. The throughput is the boundary of the set $U_{\pi,R}$. We are interested in finding a ramp metering policy $\pi$ such that for every $R$ and any other policy $\pi^{\prime}$, we have $U_{\pi^{\prime},R}\subseteq U_{\pi,R}$. We say such a policy maximizes the throughput.

In this section we present and analyze our ramp metering policy. The policy presented is coordinated, in the sense that each on-ramp may require information from other parts of the network in addition to the information obtained from its vicinity. However, it does not require any information about the demand or the route choice of the vehicles, i.e., it is reactive [15]. The policy operates under synchronous cycles of fixed length during which each on-ramp does not release more vehicles than its queue size at the beginning of the cycle. The synchronization of cycles is done once offline. This policy allocates a fixed maximum release rate to each on-ramp. In addition, it imposes dynamic minimum time gap criterion between release of successive vehicles from the same on-ramp. Changing the time gap between release of successive vehicles by an on-ramp is akin to changing its release rate. An inner approximation to the throughput of this policy is provided, and is then compared to an outer approximation.

V2I communication requirements: This policy uses information about $|Q|$ (if $T>1$) and $X_{f}$. After a finite time, the mainline vehicles only communicate $X_{f_{1}}$ to all the on-ramps at the end of each update period $T_{\text{per}}$. The number of vehicles that constitute $X_{f_{1}}$ is no more than the total number of slots. Furthermore, at the end of each time step during a cycle, the vehicles near an on-ramp communicate their state to that on-ramp for the safety gap evaluation.

We now provide a necessary condition for under-saturation, against which we benchmark the sufficient condition in Theorem 1. Let $\bar{D}_{\pi,p}(m\tau)$ be the cumulative number of vehicles that has crossed point $p$ on the mainline up to time $m\tau$, $m\in\mathbb{N}_{0}$, under the ramp-metering policy $\pi$. Then, the crossing rate at point $p$ is defined as $\bar{D}_{\pi,p}(m\tau)/m$ and the “long-run” crossing rate is $\limsup_{m\rightarrow\infty}\bar{D}_{\pi,p}(m\tau)/m$. Recall the definition of $\rho_{i}$ for on-ramp $i$’s node. We can extend this definition to every node in the network that is not a source or sink. Let $\rho:=\max_{i}\rho_{i}$, where $i$ is any node that is not a source or sink.

In this section, we compare the total travel time under the DRRA policy and ALINEA [5], which is a macroscopic ramp metering policy. We also add the safety filter (M3) on top of ALINEA, and use the name Safe-ALINEA to refer to the resulting policy. An on-ramp’s outflow in the ALINEA policy is determined according to the following equation:

Here, $r(\cdot)$ is the on-ramp’s outflow, $K_{r}$ is a positive design constant, $o(\cdot)$ is the occupancy of the mainline downstream of the on-ramp, and $\hat{o}$ is the desired occupancy. We use time steps of size $60\leavevmode\nobreak\ [\text{s}]$, $K_{r}=70\leavevmode\nobreak\ [\text{veh/h}]$ [5], and $\hat{o}=13\leavevmode\nobreak\ \%$ corresponding to the capacity flow. For the DRRA policy, we use the following parameters: $T=13$, $T_{\text{per}}=2\tau$, $\gamma_{1}=50$, $\gamma_{2}=10$, $\theta^{\circ}=0.1$, $\beta=1.01$, and $a_{i}=b_{i}=1$, $i=1,2,3$. The network is a ring road with perimeter $1860\leavevmode\nobreak\ [\text{m}]$ and $3$ on- and off-ramps. The on-ramps are located symmetrically at locations $0$, $600$, and $1200$; the off-ramps are also located symmetrically $155\leavevmode\nobreak\ [\text{m}]$ upstream of each on-ramp. We consider a congested initial condition where the initial number of vehicles on the mainline is $100$; each vehicle is at the constant speed of $6.7\leavevmode\nobreak\ [\text{m/s}]$, and is at the distance $h\times 6.7+S_{0}\approx 14.1\leavevmode\nobreak\ [\text{m}]$ from its leading vehicle. The details of the vehicle following behavior is given in [1]. We also let $\lambda=0.54$ and

where columns specify the off-ramps.

We evaluate the average Total Travel Time (TTT_n), which is computed by averaging the total travel time of the first $n$ vehicles that complete their trips. The total travel time of a vehicle equals its waiting time in an on-ramp queue plus the time it spends on the freeway to reach its destination. Figure 3 shows the simulation result. From the figure, we can see that the DRRA policy provides significant improvement in the TTT_n compared to the Safe-ALINEA policy. In fact, the network becomes saturated under the Safe-ALINEA policy, which implies that the TTT_n will grow steadily with $n$.

The second network is a symmetric three-legged merge junction; see Figure 4(a). The total length of freeway segments on each leg is $310\leavevmode\nobreak\ [\text{m}]$. on-ramps $1$ and $2$ are located at the beginning, while on-ramp $3$ is located in the middle of their corresponding legs. Similarly, off-ramps $1$ and $2$ are in the middle, while off-ramp $3$ is at the end of their corresponding legs. The mainline is initially empty and

The on-ramps use the DRRA policy with $T=1$ and other parameters chosen similar to Section IV-A. In addition, the release times of on-ramps $1$ and $2$ are set to $t=(2m+1)\tau$ and $t=(2m+2)\tau$, respectively, while $t=m\tau$ for on-ramp $3$, $m\in\mathbb{N}_{0}$ (thus, $a_{i}=1$, $b_{i}=2$, $i\in[2]$, and $a_{3}=b_{3}=1$). For the given routing matrix, the inner and outer estimates of the under-saturation region given by Theorems 1 and 2 are $\lambda<1/2$ and $\lambda<5/9$, respectively. From simulations, the under-saturation regions of the DRRA policy and its non-reactive version are estimated to be $\lambda<1/2$ and $\lambda<5/9$, respectively. This suggest that there is a gap between the inner and outer estimates of the under-saturation region in the DRRA policy, but not in its non-reactive version.

The third network is constructed by making the second network cyclic; see Figure 4(b). The length of the additional segment in this network is $610\leavevmode\nobreak\ [\text{m}]$. The mainline is initially empty and

The on-ramps again use the DRRA policy with the same parameters as in the previous section. The inner and outer estimates of the under-saturation region are $\lambda<1/3$ and $\lambda<5/9$, respectively. From simulations, the under-saturation regions of the DRRA policy and its non-reactive version are estimated to be $\lambda<0.4$ and $\lambda<5/9$, respectively. Therefore, Theorem 1 holds for this cyclic network. Based on the simulation results and the results in [1] given for a ring road network, we conjecture that Theorem 1 holds for general cyclic networks.