{'fraction_non_alphanumeric': 0.04486289898071494, 'fraction_numerical': 0.011413121500693879, 'mean_word_length': 3.9020642739854563, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Modeling Toll Lanes and Dynamic Pricing Control

In this paper we address the problem of dynamic pricing for toll lanes on freeways. The proposed toll mechanism is broken up into two parts: (1) the supply side feedback control that computes the desired split ratios for the incoming traffic flows between the general purpose and the toll lanes; and (2) the demand side price setting algorithm that aims to enforce the computed split ratios. The split ratio controller is designed and tested in the context of the link-node Cell Transmission Model with the modified node model of in/out flow distribution. The equilibrium structure of this traffic model is presented; and the case, in which the existence of a toll lane is meaningful, is discussed. For the price setting, two alternative approaches are presented. The first one is commonly used, and it relies on the known Value of Time (VoT) distribution. Its shortcoming, however, is in the difficulty of the VoT distribution estimation. The second approach employs the auction mechanism, where travelers make bids on places in the toll lane. The advantage of this approach is that it enables direct control over how many vehicles will be allowed into the toll lane.


Introduction
Congestion pricing is an economics concept of using pricing mechanisms to charge the users of public roads for the negative effect on others generated by the demand in excess of available supply. It is one of a number of demand side traffic management strategies that address traffic congestion. Other known demand management strategies include: parking restrictions; park and ride facilities allowing parking at a distance and continuation by public transport or ride sharing; reduction of road capacity to force traffic onto other travel modes; road space rationing, where regulatory restrictions prevent certain types of vehicles from driving under certain circumstances or in certain areas; and policy approaches, which encourage greater use of existing alternatives through promotion, subsidies or restrictions.
Our focus will be on congestion pricing for Express Toll Lanes (ETL) and High Occupancy/ Toll (HOT) lanes. This type of facilities becomes ever more popular in the U.S. In San Francisco Bay Area alone, the Metropolitan Transportation Commission promises the implementation of 550-mile express lane network by 2035, and all of it with dynamic pricing strategies.
There were numerous studies on congestion pricing over the past two decades. Optimal tolls under stochastic user equilibria were devised in [29]. Deterministic static equilibrium model for urban transport networks with elastic demand and capacity constraints was presented in [12]. Optimization of tunnel tolls in Hong Kong was investigated in [39]. Yang and Bell talked about road pricing in the presence of congestion delay [38]. Other models of congestion toll were discussed in [15]. Wie and Tobin presented two pricing models -one static with the same day-to-day demand and road network capacity, and the other one with time varying traffic conditions and congestion tolls [37]. Bottleneck model with elastic demand was described in [1]. The model of bottleneck congestion was generalized and optimal peak-load toll was derived in [24]. Eliasson suggested optimal road pricing policy reducing aggregate travel time and distributing toll burden equally among travelers, although travelers had utlity functions with constant marginal utilities of time and money, and these marginal utilities were unobservable [11]. The second best pricing policy for a static transportation network, where not all links could be tolled, was presented in [35]. De Palma and Lindsey derived the optimal tolls formulae and analyzed them to reveal the separate influences of traveler heterogeneity, road network effects, fiscal effects and equity concerns [8]. In [36] the properties of various types of public and private pricing on a congested road network were explored, and it was shown that welfare-maximizing pricing was more efficient than the revenue-maximizing one. Game theoretical analysis of congestion pricing from its micro-foundations, interaction of two or more travelers, was performed in [20]. Simulation based analysis of various road pricing schemes was conducted in [7]. The analytical formulation of the optimal toll calculation for multi-class traffic was given in [16]. In [10] two dynamic pricing strategies, reactive (feedback) and proactive (feedforward) were considered and compared, favoring the latter. A comprehensive review of the current congestion pricing technologies was offered in [9].
It is important to mention the research targeted specifically at the dynamic pricing of managed toll lanes. A local feedback strategy for setting tolls is proposed in [42]. The control algorithm is similar to ALINEA [25], where the portion of vehicle flow allowed into the toll lane for a given time step is computed from the toll vehicle flow at the previous time step and the speed observed in the toll and the general purpose lanes. In the situation when the speed in the toll lane drops below 45 mph, the congestion in the toll lane is assumed, and tolls are increased quicker than otherwise. Proactive dynamic pricing methodology is described in [23]. Tolls are determined based on the cell transmission model (CTM) with stochastic demand and capacity. The road configuration with a single decision point is considered. A distance-based dynamic pricing strategy for toll lanes aimed at maximizing toll revenue is presented in [40]. Here the tolls are set based on the travel time prediction that is computed using the stochastic variation of the LWR model [3,21,27]. The optimization problem maximizing the expected toll revenue with constraints keeping the toll lane in free flow is solved. Yin and Lou delivered the proof of concept of a reactive self-learning approach for determining time-varying tolls in response to the detected traffic arrivals [41]. The approach learns in a sequential fashion motorists' willingness to pay and then determines pricing strategies based on a point-queue model. This result was extended in [22], where the CTM was used instead of the point-queue model, and tolls are set based on the predicted traffic state. These papers assume that toll lane should be kept in free flow, and the corresponding constraints are imposed. The logit model is used to implement the driver's lane choice.
In this paper, we approach dynamic pricing control from both, the supply and the demand sides with the main focus on the supply side. The supply side control is considered in the context of the Cell Transmission Model (CTM) [6] with the node model proposed in [31]. Here we extend the result of [14] by analyzing the equilibrium structure of the freeway traffic model with a single mainline, similarly to [14], but for a different node model. Then, we discuss when it makes sense to split the mainline into two lanes, the general purpose and the toll lanes, where the toll lane is supposed to be less congested than the general purpose one. It is important to note that activating a toll lane is not always beneficial for the freeway performance. Obviously, when the traffic density is low, a toll lane does not provide any advantage in terms of travel time and, thus, should be free. On the other hand, when the freeway is too congested, maintaining a toll lane in free flow may be harmful, as it will lead to large congestion spillback and degrade the throughput. We propose a supply side control algorithm that computes split ratios dividing the incoming flows between the general purpose and the toll lanes. Its goal is to keep the toll lane in free flow as long as possible, then, in the case of continuing excessive demand, allow the toll lane to congest up to the point when the toll lane becomes a general purpose lane in terms of its performance. When the congestion recedes, the control algorithm ensures that the toll lane frees up first. The objective is to maintain the same throughput as in the freeway with all lanes being general purpose. The idea of this control algorithm is inspired by the HERO coordinated ramp metering [26]. While in the case of ramp metering ramps are used as storage for the excess demand, the general purpose lane serves as the storage for the split ratio control. All proofs are given in the context of the proposed traffic model. Once the desired flow splits are computed by the split ratio controller, we achieve them by setting the toll rate -that is already a demand management. The common way of setting the price is to rely on the Value of Time (VoT) distribution [2], which is assumed to be known. Relying on the VoT distribution, though, makes our control indirect, as we can only estimate how much travelers are ready to pay. The alternative solution is to use the truthful auction, which we propose as a means of ensuring the desired split ratios.
The rest of the paper is organized as follows. Section 2 introduces the traffic model, describes its equilibrium structure and splitting the mainline into the general purpose and the toll lanes. Section 3 presents the split ratio control algorithm and provides examples. Section 4 is dedicated to pricing mechanisms, discussing the estimation of VoT distribution and proposing the auction algorithm as an alternative. The simulation of Interstate 680 South in Contra Costa County in California is discussed in Section 5. Ultimately, Section 6 concludes the paper.

Traffic Model
A road network is modeled by a directed graph G = (E, V ), where E is the set of edges (links), V is the set of vertices (nodes). A link e ∈ E is an ordered pair of nodes: e = (u, v), u, v ∈ V . In(v) denotes the set of incoming links of node v, Out(v) denotes the set of outgoing links of node v. Links without predecessors (whose begin nodes have no inputs) are called entrances. Links without successors (whose end nodes have no outputs) are called exits. Links other than entrances and exits are referred to as inner links. By E in and E out we denote the set of entrances and the set of exits, and assume that E in ∩ E out = ∅. Nodes correspond to road intersections, merges, diverges, or subdivide longer links into smaller ones.
Every inner link or exit e has the following characteristics, also known as a fundamental diagram: N e maximum number of vehicles in the link, F e capacity (in vehicles per time step), v e free flow speed, w e congestion wave speed.
For entrances only capacity and free flow speed need to be defined. The free flow speed and the congestion speed are measured in link per time step, 0 < v e , w e < 1.
Link e at time t contains n e (t) vehicles. Define the outflow demand, or the required outflow, of link e ∈ E at time t as f d e (t) = min{v e n e (t), F e }. Define the inflow supply, or the maximum inflow, of link e ∈ E \ E in at time t as f s e (t) = min{w e (N e − n e (t)), F e }. The number of vehicles in link e = (u, v) at time t + 1 is where f in e (t) is the total incoming flow for link e at time t: the incoming flow f in e (t) for every entrance e ∈ E in is given; f out e (t) is the total outgoing flow for link e at time t: the outgoing flow for exits e ∈ E out equals the outflow demand: f out e (t) = f d e (t).
Flows f e1,e2 (t) between adjacent links e 1 , e 2 , are determined by a node model that should satisfy the following conditions: (1) all flows between adjacent nodes f e1,e2 (t) are non-negative; (2) incoming flows don't exceed inflow supplies, except for entrances, f in e (t) ≤ f s e (t), e ∈ E \ E in ; and (3) outgoing flows don't exceed outflow demands, f out Conservation law (2.1) and the flow constraints ensure that if the number of vehicles at time t in each link n e (t) is positive and less than the maximum number of vehicles N e (that is, n e (t) ≥ 0 for all e ∈ E and n e (t) ≤ N e for all e ∈ E \ E in ), then the same holds for the next time step t + 1 (namely, n e (t + 1) ≥ 0 for e ∈ E, and n e (t + 1) ≤ N e for e ∈ E \ E in ). Moreover, if an exit link e ∈ E out , is in a free flow state at time t, v e n e (t) ≤ F e , then it will stay in a free flow state at time t + 1: v e n e (t + 1) ≤ F e .

Node Model
We use the node model proposed in [31]. Consider node v with m incoming and n outgoing links, m, n > 0. Let f d i (t) be an outflow demand of the ith incoming link at time t, and f s j (t) be an inflow supply of the jth outgoing link at time t as shown in Figure 1. Let f ij (t) be the flow from the ith incoming to the jth outgoing link. A node model determines flows f ij (t) from demands f d i (t), supplies f s j (t), a split ratio matrix B v (t) ∈ R m×n and priorities of the incoming links p i ≥ 0. [31] proposed that the priorities p i should be proportional to capacities F i of the incoming links. Alternatively, the priorities p i can be proportional to demands f d i (t), as suggested in [17] and implemented in [19].
Elements of the split ratio matrix B v (t) = {β ij (t)} j=1,...,n i=1,...,m are nonnegative, and n j=1 β ij (t) = 1. The split ratio matrix imposes the First-In-First-Out (FIFO) constraint on the flows f ij (t): Priority coefficients of the incoming links, p i , affect flows f ij (t), if a supply of some outgoing link is too small to accommodate a demand from the incoming links. This will be clarified later.
We now describe the algorithm for finding flows f ij . To simplify the notation, the time step t is omitted.
2. Define sets J(1), V j (1), and supply residualsf s j (1), j ∈ J(1): Sets V j (k) defined at each step k are the sets of incoming links i such that flows f ij are still to be defined. J(k) is a set of outgoing links j such that V j (k) = ∅. The supply residualf s j (k) is the inflow supply of link j to be distributed among incoming links in V j (k).
It's a set of incoming links such that their outflow demand does not exceed the rightful share in the inflow supply of the remaining outgoing links.
The first 3 steps are initialization steps. As explained in [31], in each iteration we define the reduction factors a j (step 5), which the incoming flows competing for the remaining supply of the jth outgoing link should be set proportional to, if they were not constrained by the demand of the corresponding incoming link, so f ij = a j p ij . Then, a minimum of a j , denoted byâ, whose index is, is selected and imposed on all incoming links from V. If some links are found to be demand-constrained (case 6a), their outgoing flow is set equal to demand, and those demand-constrained links U are removed from every V j . Otherwise (case 6b) the flows from V are supply-constrained with factorâ, and all links from V are removed from every V j . The algorithm stops when all flows have been defined. Since at least one incoming link is removed from all V j in each iteration, the algorithm finishes after at most m iterations.

Freeway Model
The model of a freeway without toll lanes described below is a combination of the Cell Transmission Model for networks, similar to [6], and the node model proposed in [31] and explained above.
A freeway network consists of mainline links, entrance links (mostly on-ramps), and exit links (mostly offramps). Links are connected to each other by nodes. Nodes correspond to junctions, merge and diverge points, and are also used to split long links into shorter ones. When a freeway network is built for simulation, nodes are typically placed so as to keep link lengths in the range between .1 and .2 miles.
The characteristics of the ith mainline link are: its capacity F i , the maximum number of vehicles it can contain N i , a free flow speed v i and a congestion speed w i . The capacity is measured in vehicles per time step, while both speeds are measured in link per time step, 0 < v i , w i < 1. The freeway contains K links, numbered from 1 to K, the entrance link numbered 0, and the exit link numbered K + 1. Additionally, there may be an on-ramp with capacity R i and free flow speed v r i < 1 attached to the beginning of mainline link i, and an off-ramp with capacity S i at the end of the ith link, i = 1, . . . , K. If there is no on-ramp at the beginning of the ith link, then R i = 0.
We now clarify how the model parameters, such as capacities and speeds, are normalized, that is, how the speeds measured in miles per hour are converted into the speeds measured in link per time step, and how the capacities measured in vehicles per hour per lane are converted into the capacities measured in vehicles per time step. Suppose L i is the length of mainline link i measured in miles, τ is the time step measured in hours, V i is the free flow speed in link i measured in miles per hour, W i is the congestion speed in link i measured in miles per hour, C i is the capacity of link i measured in vehicles per hour per lane, k i is the number of lanes in link i.
The speeds v r i and the capacities R i , S i are normalized in the same way. Hence the aforementioned inequalities v i , w i < 1 are equivalent to max{V i , W i } τ /L i < 1, which is the Courant -Friedrichs -Lewy condition (see [5]). For example, if the minimum link length L i is 0.2 miles, the maximum free flow speed v i is 60 mph, and the maximum congestion speed w i is 50 mph, then the maximum time step τ is 0.2/60 hours, which is 12 seconds. Denote n i (t) the number of vehicles in link i at time t. We assume that if the ith link is uncongested, that is, v i n i (t) ≤ F i , then the number of vehicles it contains doesn't influence the incoming flow for this link at time t, that is, This assumption is equivalent to the following inequality: Denote d i (t) the demand, or desired flow, at the ith on-ramp; r i (t) -the actual flow coming from on-ramp i to link i; and q i (t) -the number of vehicles queued at the ith on-ramp, at time t. Both flows, d i (t) and r i (t) are measured in vehicles per time step. Clearly, Denote f i (t) the flow from link i to link (i + 1); and s i (t) -the flow from link i to the corresponding off-ramp. The number of vehicles in mainline links evolves as: As for the entrance link 0 and the exit link K + 1, the same equality holds, except r i (t) = s i (t) = 0, i = 0, K + 1.
Since every exit remains in a free flow state once it's there, there is no need to take the state of exits into consideration: assuming that all exits, including link K + 1, are initially in a free flow state, and that inequality (2.5) holds, flows from mainline links to the exits are only constrained by the exit capacities.
F s i is the "inflow capacity" of the ith mainline link, that is, the maximum incoming flow if the link has enough space for them. F d i is the "outflow capacity" of the ith mainline link, that is, the maximum number of vehicles which can move from this link to link i + 1 per time step if link i + 1 has enough space for them. By introducing the outflow capacity we ensure that the off-ramp flow The incoming flows d(t) and f −1 (t) are given, other flows are determined by the node model (see Figure 3). For each node compute outflow demands for the on-ramp r d i (t) (if present) and the incoming (upstream) mainline link f d i−1 (t), and inflow supply for the outgoing (downstream) mainline link f s i (t): The flow out of exit link K + 1 equals the outflow demand, f K+1 (t) = f d K+1 (t). The flow from the last mainline link K to the exit link K + 1 is a minimum of the outflow demand of the upstream link and the inflow supply of the downstream link: Priorities of mainline links p f i , i = 0, . . . , K − 1, and priorities of on-ramps p r i , i = 1, . . . , K, are given, Suppose the priorities are normalized: and r i (t) as follows.
1. If the downstream mainline link can accomodate the demand from the on-ramp and the upstream link, , then the actual flows equal the demands: 2. Otherwise, if the outflow demand from upstream mainline link does not exceed its rightful share in the inflow supply of the downstream link, , then the flow from the upstream link equals the demand, f i−1 (t) = f d i−1 (t), and the flow from the on-ramp takes up the residual of the supply: 3. Otherwise, if the outflow demand from the on-ramp doesn't exceed its rightful share in the supply, In this case the flows are proportional to the priorities: These rules are derived from the general node model presented in subsection 2.1. Note that since does not exceed the off-ramp capacity S i−1 for the reasons mentioned after equation (2.9). Thus, both supply constraints -from the downstream link and from the off-ramp -are satisfied.

Equilibria of the Freeway Model
Suppose the incoming flows f −1 and d are constant, as well as priorities p f i , p r i and split ratios . . , K, and r(t + ∆t) = r for all ∆t = 0, 1, 2, . . . . Note that queue lengths n 0 , q are not included in the equilibrium. Queue lengths either stay constant or grow at a rate of (f It can be shown that inequalities r i ≤r i , i = 1, . . . , K, and f i ≤f i , i = 0, . . . , K + 1, hold for every equilibrium (n, f, r).
Theorems 2.1, 2.2 fully characterize the set of all equilibria corresponding to the incoming flows f −1 , d.
Note that this rule is similar to that in the node model. Again, the off-ramp capacity constraints are not violated due to the reasons mentioned after equation (2.9) and the fact that f ≤f ≤ F d .
Theorem 2.1 follows from lemma 2.1 and the node model.
Lemma 2.1 is purely technical, the proof is omitted.
Once the equilibrium flows r and f are known, the set E of equilibrium density vectors n is defined as follows. Let Letters u and c here mean uncongested and congested. We claim that n u ≤ n c whenever Indeed, this follows from inequality (2.5): U is the set of uncongested links: n i = n u i for i ∈ U ; C is the set of congested links: n i = n c i for i ∈ C. These conditions can be obtained directly from the node model. For m = 1, . . . , M define indices (2.21) It can be shown that i u m < i c m for each m = 1, . . . , M . Theorem 2.2. The set E of equilibrium vectors n is a direct product of sets E m corresponding to sets I m : The set E M +1 consists of a single vector, The set E m , m ∈ {1, . . . , M } either consists of a single vector, 24) or is a union The proof of theorem 2.2 for U = ∅ and C = ∅ can be found in [14]. Note that the equilibrium flows and densities and thus the queue growth depend on priorities p f , p r . One extreme case, p r i = 1, p f i = 0 for all i, is fully studied by [14]. Another extreme case is p r i = 0, p f i = 1 for all i. In this case all non-bottleneck links are uncongested, whereas the on-ramp just upstream of the last bottleneck is more congested than for any strictly positive on-ramp priorities p r .

Model of a Freeway with Toll Lanes
We model a freeway with toll lanes by splitting each mainline link into two parallel ones (see Figure 5), the first one (upper index 1) corresponds to toll lanes, the second one (upper index 2) corresponds to the general purpose lanes. Each of these two links has a separate exit.
. The maximum number of vehicles N ξ i , the maximum flows F ξ,d i , F ξ,s i , and priorities p ξ,s i , ξ = 1, 2, are defined in the same manner.
Outflow demands and inflow supplies are defined as in the freeway model: Travelers can only choose between the toll and the general purpose lanes when they enter the freeway. The freeway state and the toll both influence split ratios of the flow from the entrance into the mainline links. Denote those split ratios by Figure 6: Node model of a freeway with toll lanes.
Flows f ξ −1 (t) are given, flows out of the exit links equal demands: Other flows, namely f ξ i−1 (t), r ξ i (t), i = 1, . . . , K + 1, are determined by the following node model (see Figure 6). The time step t is implied, but omitted for simplicity. Compute potential flows Define and λ i = min{λ 1 i , λ 2 i }. Clearly, λ ξ i ≤ 1, therefore λ i ≤ 1. Finally, compute flows r ξ i and f ξ i−1 :  The proposed redistribution can be achieved by controlling the split ratios α 1 i , α 2 i of the on-ramp flows r i . This will be explained in the next section.

Control of Split Ratios
Here we present an on-ramp flow redistribution control algorithm which aims at bringing the toll lane into a free flow state and maintaining the free flow state of the toll lane, provided that queues at the entrances grow as slowly as possible.
For simplicity, assume that the first link does not have an on-ramp, and transform the model in such a way, that the link 0 becomes an on-ramp of link 1. Thus, there is no 0th link and f ξ,s 0 (t) ≡ 0, ξ = 1, 2.
We assume that all information about the current freeway state, namely, densities n ξ i (t) and queue lengths q i (t), is available. But we know nothing about the future: at time t no information about incoming flows d i (t + ∆t), ∆t = 0, 1, . . . , is available.
The pricing mechanism for using the toll lane changes split ratios α 1 i (t), α 2 i (t). This dependency will be discussed in section 4. In this section we assume that the split ratios α 1 i (t), α 2 i (t) can be set directly.
The algorithm for determining the split ratios of the on-ramp flow r i (t) at time step t is described next. The time step t is implied, but will be omitted for simplicity.

Queue Growth Rate Minimization
First, we determine a range of split ratios that minimize the queue growth rate. It only makes sense to consider such links i, where r d i > 0 and f 1,s To minimize the queue growth rate, λ(

1)
Our goal is to find A 1 i .
So the set A 1 i is either a segment or a point. The corresponding flow belongs to a segment [r 1,min

On-Ramp Flow Redistribution
In order not to redistribute on-ramp flows when the freeway is in a free flow state, introduce the following correction. Ifᾱ 1 i +ᾱ 2 i > 1 andᾱ 1 i > l 1 /(l 1 + l 2 ) (recall that l 1 and l 2 are the number of toll and general purpose lanes), let Compute the maximum maintainable level of densities for the toll lane n 1, * . A maintainable level of densities is a vector n 1, * corresponding to a free-flow state (β f i v i n 1, * i ≤ F 1,d i , i = 1, . . . , K), such that if n 1 (t) ≤ n 1, * and r 1 (t) = 0, then n 1 (t + 1) ≤ n 1, * . The maximum maintainable level of densities n 1, * is defined as follows. First, compute flows f 1, * i , i = K + 1, . . . , 1 as follows: . . , 1. After that, compute densities n 1, * Next, define the maximum free-flow equilibrium n 1,e . Let M be a number of on-ramps, i 1 < i 2 < · · · < i M be the indices of links with on-ramps, i 1 = 1 by assumption.
Is is easily shown that f 1,e ≤ f 1, * and n 1,e is an equilibrium corresponding to the on-ramp flow r 1,e : r 1,e The controller keeps the total number of vehicles between entrances m and m + 1 less than N 1,e (i m , i m+1 ), and the incoming flow f 1 im−1 + r 1 im less than equilibrium flow f 1,e im /β f im , if the minimum-queue-growth-rate constraint permits that.
If we knew flows r 1 im , deriving split ratios α 1 im , α 2 im would be easy: if r d im = 0 or λ * im = 0, then the on-ramp flow r im = 0 regardless of split ratios, otherwise α 1 So, we need to determine on-ramp flows r 1 im ∈ [r 1,min

Theorems
We now prove that the presented controller keeps the toll lane in a free-flow state, if the minimum-queuegrowth-rate condition allows it. Moreover, even if the toll lane is initially congested, it becomes almost uncongested in finite time.
The toll lane is considered as an independent system, and the upper index ξ = 1 is omitted for simplicity.
Theorem 3.1. Suppose n(t) ≤ n e and the inequality r im (t) + f d im−1 (t) ≤ f e im /β f im holds for all entrances i m . Then n(t + 1) ≤ n e .
Proof. Note that for m > 1, n im−1 (t) ≤ n e im−1 and This theorem means that if the state of the toll lane is in a "target zone" n(t) ≤ n e at time t, then it remains there at time t + 1 if the on-ramp flow demand r d (t) isn't too high and the general purpose lane isn't too congested near the entrances.
A similar lemma is proved in [14].
Suppose f e is an equilibrium flow, the inequalities hold for all links with on-ramps i m for all t, and

9)
for all t. Here n e i = f e i /(β f i v i ).
Proof of Theorem 3.2 (Outline). First transform the system to get rid of the off-ramps. Multiply the "inflow capacity" of the mainline link F s i , the on-ramp capacity R i , the maximum number of vehicles N i , the incoming flow d i (t), the number of vehicles in mainline link n i (t) and on the on-ramp q i (t) by Multiply the "outflow capacity" of the ith link F d i by µ i+1 . For the transformed system denoted byˆthe following equations hold: .
That is, the transformed system is equivalent to the initial system. Multiply the equilibrium flow f e i by µ i+1 . The inequalities Hence, it suffices to show that the theorem holds for the freeway with no off-ramps, but the inequality Consider the links between two adjacent on-ramps. Consider the clusters of links with n i (t) > n e i . It is easy to show that the downstream boundary of a cluster can only move downstream, one cluster cannot split into two or more, and new clusters cannot be created. So, starting from some point in time, the number of clusters remains constant and their downstream boundaries are fixed. Denote We shall prove that h m (t) → 0 as t → ∞ for all m.
If there are no clusters between on-ramps m and m + 1, then, clearly, h m = 0.
It is easily shown that h m (t) is decreasing and nonnegative, thus there exists lim t→∞ h m (t) ≥ 0. Suppose lim t→∞ h m (t) = δ > 0. Let i * m be the downstream boundary of the most upstream cluster between the on-ramps m and m + 1. Using lemma 3.1, it can be demonstrated that lim inf t→∞ n i (t) ≥ n e i , i = i * m + 1, . . . , i m+1 − 1. Consider only those time steps where the number of clusters and their downstream boundaries are stabilised (that is, do not change anymore) and n e i − η i ≤ n i (t) for some small η i > 0, say, We now demonstrate that the most upstream cluster disappears in finite time. Since h m (t) ≥ δ, Thus the following inequality holds: Consequently, at each time step t there exists i ∈ {i m , . . . , i * m − 1} such that This implies that oftener than every (i * m − t m ) steps the upstream cluster size will decrease by at least Therefore, the upstream cluster exists at most h m (t)(i * m − i m )/µ time steps. This contradicts our assumption that the number of clusters is stabilized. Thus h m (t) → 0 as t → 0, which concludes the proof.
Remark 3.1. In theorem 3.2 it would be sufficient to require that the inequality 3.9 holds only asymptotically, that is, The control algorithm attemps to satisfy the inequalities of theorem 3.2, n e i and f im−1 (t) + r im (t) ≤ f e im /β f im , at step 3. If that is impossible, a reduction coefficient γ m−1 is introduced at step 6 to reduce the flow from upstream links. If the requirements if the theorem can be met, then the toll lane becomes almost uncongested in finite time, that is, for arbitrarily small ε > 0 the density vector n 1 (t) is component-wise less than n 1,e + ε, starting from some time step t, regardless of the initial state. Some constraints, such as nonnegativity and boundedness, can be imposed on tolls. A toll is admissible if it satisfies all constraints. To narrow the set of split ratios corresponding to admissible tolls we could introduce additional requirements, for example, the minimization of queue length growth or the maximization of total flow through the node. Then an algorithm similar to the one presented above can be applied at each time step.

Examples
Consider a freeway with one on-ramp (in the first link) and no exits, except for the last link, (K + 1). All links have equal capacities, free flow speeds and congestion speeds, but the last link, K + 1, is a bottleneck with a lower capacity: F ξ K+1 < F ξ K = F ξ K−1 = · · · = F ξ 1 , ξ = 1, 2. The initial state of the freeway is an equilibrium. Scenario 1a: The number of uncongested links is too small for the toll lane to become fully uncongested: i < (K + 1)/2. Figure 9 illustrates this case, the densities (in vehicles per mile) are color-coded. incoming flow d 0 drops to the bottleneck capacity and the congestion is transferred from the toll lane to the general purpose lane. Figure 11 illustrates this scenario. Figure 11: Temporarily infeasible incoming flow (scenario 2). Densities. Now consider a freeway with two entrances (at the beginning and in the middle), and two exits (in the middle and at the end), see Figure 12. The last link, K + 1, is a bottleneck. The priorities p ξ,f i−1 , ξ = 1, 2 and p r i are equal to capacities: Figure 12: Freeway with two entrances and two exits.

Tolls as Actuators
Now that at a given entrance i, the split ratio controller computed the desired values α 1 i and α 2 i , our goal is to enforce them. It is done by setting the price for vehicles entering the toll lane. We consider two ways of setting the price: (1) using the known Value of Time distribution; and (2) setting up an auction. These are described next.

Value of Time Distribution
The Value of Time (VoT) is the marginal rate of substitution of travel time for money in a travelers' indirect utility function. In essence, this makes it the amount that a traveler would be willing to pay in order to save time, or the amount he would accept as a compensation for the lost time. The VoT varies considerably from traveler to traveler and depends upon the purpose of the journey. The estimation of the VoT was studied in [28,30,2,34].
We assume that the VoT distribution is known, ν(π), where π represents the price per time unit. For a given entrance i, we find the desired price of the time unit, π from the equation π 0 ν(π)dπ = α 2 i . (4.1) Figure 14 illustrates the VoT pricing mechanism. To continuously estimate the VoT distribution, we need to know the difference in travel time between the general purpose and the toll lanes, τ ; the number of vehicles in the general purpose lane, n 2 ; the price set for the toll lane, π τ ; and the amount of money collected, T , every certain time period. 1 This will give us enough information to infer the portion of travelers, whose VoT is higher or equal than π : n 1 = T π τ , and ∞ π ν(π)dπ = n 1 n 1 + n 2 . (4.2) Assuming price π varies, we could eventually, estimate ν(π ). It is rather crude approach, since in different time of day travelers' VoT is different, but it conveys the idea.
In the case of HOT lanes, where besides paying customers there may be high occupancy vehicles, we would need to know additionally the number of vehicles in the HOT lane, n 1 . Then, equation (4.2) is to be slightly modified: ∞ π ν(π)dπ = T π τ (n 1 + n 2 ) .
The main shortcoming of the VoT-based price setting is the difficulty of estimating the VoT distribution. If the estimate is too rough, we may end up with underutilized, if the price is too high, or overly congested, if the price is too low, toll lane, which will hinder the performance of the overall system reducing the total output flow.
To reduce the inaccuracy of the VoT based toll calculation, the continuing calibration of the willingness to pay must be performed. Such calibration would use a discrete choice model. Logit model based calibration is described in [23,22].

Auction
The alternative method of setting the price for a toll lane is an auction. The auction based scheme applied to a cordon area congestion pricing was described in [32]. Here we describe the auction mechanism for managed toll lane based on the idea of [13]. At time t, at the entrance i, H = r d i (t) travelers make bids b 1 , . . . , b H . Without loss of generality, we assume b 1 ≥ · · · ≥ b H . Let h = round(α 1 i H). Vehicles with bids b 1 , . . . , b h will be let into the toll lane, and each of them will pay b h generating b h h total revenue for the entrance i at time t.
The main advantage of the auction approach is its deterministic outcome: for each decision point i, we can achieve the desired split ratio coefficients α 1 i , α 2 i exactly.
adding auxiliary lanes and, notably, converting existing HOV lanes to HOT. 3 Modeling of improvement scenarios was done at UC Berkeley PATH using simulation Tools for Operational Planning (TOPL) [33].
In this Section we present the simulation for a 10-mile segment of I-680 South corridor extending from Martinez through Concord and Pleasant Hill to Walnut Creek, shown in Figure   A macroscopic CTM-based simulation model for the I-680 corridor was built and calibrated using TOPL and measurement data collected in the CSMP study. Three scenarios were simulated: 1. base case that reproduces existing conditions; Whereas the first scenario represents the reality, scenarios 2 and 3 are hypothetical and were explored as part of the planning exercise. The input demand was assumed the same in all three scenarios. Morning peak hours were simulated: from 5 to 10 AM. This is when travelers currently experience large delays at that segment of I-680S.
Speed contour maps resulting from the three simulations are shown in Figure 16. Contours on the left show the speed dynamics in the GP lane, and contours on the right correspond to the special lane, which in scenario 1 is HOV, in scenario 2 is GP and in scenario 3 is HOT. Black stripes on the left and on the right of the special lane contours correspond to locations, where there is no special lane. Tables 1 and 2 Table 2: Vehicle-hours of delay in the period from 5 to 10 AM in the three simulated cases. Total delay in the last column includes delay from on-ramp queues, which exists only in the base case.
In the base case scenario we observe large congestion in the GP lane, while the HOV lane has no congestion at all. Opening the HOV lane to everyone (scenario 2) helps a lot, as is evident from the delay table (Table 2), but congestion is not eliminated completely, and now both GP and HOV lanes have the same congestion pattern, so travelers have no mode choice. Not surprisingly, the HOT lane scenario shows the best performance of the three both in congestion mitigation and keeping the special lane as free as possible.
One interesting detail to notice is the slight reduction of the GP lane delay in scenario 3 compared to scenario 2. That happens despite the fact that the GP lane has more vehicles in scenario 3 than in scenario 2 ( Table  1). This happens because the HOT controller try to keep the flow in the GP lane as close to capacity as possible, and thus more vehicles travel with higher speed.

Conclusion
In this paper we described the toll lane control algorithm for freeways in the context of the link-node CTM with the modified node model. Its design was presented in two stages: (1) the supply control computing the desired split ratios for the incoming flows with the goal of keeping the toll lane in free flow as long as and as much as possible, yet fully utilized; and (2) the demand control, setting the price so that the flows between the toll and the general purpose lanes were distributed according to the computed split ratios.
We described the equilibrium of the traffic model and pointed out that activating the toll lane is meaningful only in the partially congested equilibrium, when the general purpose lane has enough storage space to accommodate extra vehicles from the toll lane without reducing the total output flow of the system. In free flow state with feasible demand there is obviously no need for the toll lane, as it does not provide the benefit of the shorter travel time. When the freeway is in the fully congested equilibrium, the deployment of a toll lane is not recommended either, as it can only harm the overall system performance by oversaturating the general purpose lane, creating queues at entrances and reducing the total output flow of the system.
The split ratio control algorithm presented in the paper behaves as follows: • in free flow state with feasible demand it is essentially non-active letting the mainline operate as one piece; • in the case of infeasible demand, the excess flow is directed into the general purpose lane, letting it to congest first; • once the general purpose lane is fully congested, the algorithm lets the toll lane to congest; • if it comes to the point when the toll lane is fully congested, the algorithm is deactivated, as there is nothing it can improve at this point, so the mainline returns back to one piece; • once the demand drops again, and the freeway starts to decongest, the algorithm first brings the toll lane into the free flow state, and then the general purpose lane.
All these manipulations with flows are done through split ratios at the end nodes of the entrance links. The control algorithm computes these split ratios.
The split ratio control algorithm can be extended to the case of HOT lanes. For that, however, one has to introduce and deal with multiple vehicle types, as described in [18]. In this case, two vehicle types will be needed: High Occupancy Vehicles (HOVs) and Single Occupancy Vehicles (SOVs). The HOV flow won't be controlled, but will be governed by the algorithm of finding the path of the least resistance, 4 presented in [18], whereas the SOVs will be subject to the toll control, and the available space in the general purpose and the HOT lanes will be computed accounting for both vehicle types.
Finally, we discussed two mechanisms for price setting -the VoT distribution and the auction. The former is commonly used, but provides only rough estimates of the actual traveler behavior, resulting mostly in the underutilization or oversaturation of the toll lane. The latter mechanism is hardly deployable at current time due to technical difficulties, but in the foreseeable future with the emerging technologies, especially, those of autonomous vehicles and ride shares, it looks promising.