In recent years, the automotive industry has been rapidly advancing toward connected vehicles with higher degrees of autonomous capabilities. This trend opens up many new possibilities for AI-based efficient traffic management. This paper investigates traffic optimization through the setting and broadcasting of dynamic and adaptive tolls under the assumption that the cars will be able to continually reoptimize their paths as tolls change. Previous work has studied tolling policies that result in optimal traffic flow and several traffic models were developed to compute such tolls. Unfortunately, applying these models in practice is infeasible due to the dynamically changing nature of typical traffic networks. Moreover, this paper shows that previously developed tolling models that were proven to yield optimal flow in theory may not be optimal in real-life simulation. Next, this paper introduces an efficient tolling scheme, denoted tolling, for setting dynamic and adaptive tolls. We evaluate the performance of -tolling using a traffic micro-simulator. -tolling is shown to reduce average travel time by up to 35% over using no tolls and by up to 17% when compared to the current state-of-the-art tolling scheme.
other agents (also known as the marginal cost) results in
optimal flow [Pigou, 1920; Beck
Modern simulation tools and computational power allow
for much more fine-grained simulation of traffic networks,
referred to as micro-simulation models. Using such a
realistic traffic simulator we demonstrate the potential of using
tolls for reducing average travel time and increasing
average utility. In this paper we show (empirically) that
computing tolls using a macro-model does not lead to optimal
performance in a realistic simulator. We explain this effect by
noting that macro-models assume deterministic conditions,
and have a number of unrealistic features. In recent years,
researchers have relaxed the assumptions of the first
macroscopic tolling models to incorporate responsiveness to
roadway disruptions such as accidents [de Palma and Lindsey,
1998; Yang, 1999a,b; Lindse
In response to the suboptimal performance of existing macro-models, this paper introduces a novel tolling scheme denoted -tolling. -tolling approximates the marginal cost of each link using only two variables (current travel time and free flow travel time) and one parameter. Due to its simplicity, -tolling is fast to compute, adaptive to current traffic, and accurate. We prove that, under some assumptions, -tolling results in tolls that are equivalent to the marginal cost and demonstrate that it can lead to near-optimal performance in practice. 2
This section defines the notion of user equilibrium (UE) and system optimum (SO). Applying tolls is then introduced as a mechanism that allows UE and SO to coincide. The marginal cost toll (MCT) policy is then presented followed by some macroscopic traffic models that approximate it. We discuss some of the drawbacks of such macro-models, which provides the motivation for the current study.
Consider a directed network G = (V; E), where V and E are the set of nodes and links respectively. Suppose that the demand (flow rates) between every pair of nodes is known. In this paper we assume that the travel time on a link e 2 E is a function of its flow (xe) and is represented using a nondecreasing function te(xe) (also called volume delay or linkperformance functions). In practice, the Bureau of Public Roads (BPR) function te(xe) = Te(1 + ( Cxee ) ) is commonly used as the delay function, where Te is the free flow travel time and Ce is the capacity of link e. and are parameters whose default values are 0.15 and 4 respectively.
When agents choose routes selfishly, a state of equilibrium,
called user equilibrium (UE) [Wardrop, 1952], is reached in
which all used routes between an origin-destination (OD) pair
have equal and minimal travel time. The link flow rates
corresponding to this state can be obtained by solving a non-linear
convex program that minimizes the Beckmann potential
function (Pe2E R0xe te(xe) dx) Beck
The system optimal (SO) problem can be formulated using
a set of constraints similar to those used for computing UE
but replacing the objective function with Pe2E xete(xe). As
mentioned before, all agents do not experience equal and
minimal travel times at the SO state which incentivizes agents to
switch routes. Instead, if an optimal tolling policy is applied,
the flows resulting from a UE assignment in which agents
minimize the generalized cost (time + toll) coincides with the
SO solution. MCT is proven to be such a policy (UE=SO)
[Pigou, 1920; Beck
The focus of this paper is methods that approximate the
marginal cost. Most of these methods assume that demand
on each link is constant. In such cases MCT can be formally
defined as follows: given a link (e) and flow (xe) the toll
applied to e equals the change in travel time caused by an
infinitesimal flow ( dtdex(xee) ) multiplied by the number of agents
A number of researchers have attempted to develop
macromodels that approximate MCT for a given system [Yang et
al., 2004; Han and
In order to evaluate the effectiveness of different tolling models on traffic flow optimization, we used a modified version of the Autonomous Intersection Manager (AIM) microsimulator [Dresner and Stone, 2008]. On the one hand, AIM is very realistic in the sense that it allows simulating accelerations of individual vehicles in response to traffic conditions. On the other hand, due to computational limitations, AIM cannot scale to large road networks (only up to 3 3 grid network). For our experiments AIM was chosen since, unlike other simulators, it allows non deterministic traffic behavior, provides (direct) measurements on vehicle following distances, lane changes, gap acceptance, etc. 3.1
AIM provides a multiagent framework for simulating autonomous vehicles on a road network grid; it presents a realistic traffic flow model that allows experimenting with adaptive tolling. The AIM simulator uses two types of agents: intersection managers, one per intersection, and driver agents, one per vehicle. Intersection managers are responsible for directing the vehicles through the intersections, while the driver agents are responsible for controlling the vehicles to which they are assigned. To improve the throughput and efficiency of the system, the driver agents “call ahead” to the intersection manager and request a path reservation (space-time sequence) within the intersection. The intersection manager then determines whether or not this request can be met. If the intersection manager approves a driver agent’s request, the driver agent must follow the assigned path through the intersection. On the other hand, if the intersection manager rejects a driver agent’s request, the driver agent may not pass through the intersection but may attempt to request a new reservation.
At every intersection, the driver agent navigator runs an A search [Hart et al., 1968] to determine the shortest path leading to the destination of the vehicle associated with it. The navigator then directs the driver agent to drive via the shortest route. This behavior ensures that each vehicle acts greedily with respect to minimizing travel time. Next, we describe the required enhancements to the standard AIM simulator [Dresner and Stone, 2008] necessary to simulate realistic tolling experiments. In order to evaluate adaptive-tolling using AIM the following modifications were required: • Link toll: each link (e) in the road network is associated with a toll, tolle, which can adapt in real-time according to traffic conditions. • Link travel time: each link stores: (1) an estimated travel time, te, that is based on real-time observed flow speed, and (2) an estimated free flow travel time Te, that is based on the link’s length divided by its speed limit. • Route selection: when a car has several routes leading to its destination, the driver agent chooses the route (r = e1; e2; :::; e3) that minimizes P t V OT + tolle, where V OT is the monetary value2erOfe time. • Value Of Time: each driver agent is associated with a randomly generated V OT that is drawn from a normal distribution. We assume monetary units are chosen such that the mean value is 1¢ per second, and assume a standard deviation of 0.2. V OT represents the value (in cents) of one second for the driver. A driver with V OT = x is willing to pay up to x¢ in order to reduce travel time by 1 second. 3.3
This paper uses a macroscopic model to approximate MCT.
This model is used to solve the convex program described
in Section 2 using Algori
One of the main contributions of this paper is an empirical demonstration that setting tolls based on macro-models can lead to suboptimal results when evaluated in a more realistic micro-simulator. This section presents these empirical results, which motivate our new tolling scheme as presented in the next section. 4.1
Figure 1 illustrates an exemplar road network that demonstrate the impact of tolls that adapt to traffic demand. The speed limit across all roads is 25 meters per second. Each horizontal road is 142 meters long, and each vertical road is 192 meters long. We examined a scenario in which agents enter the network from a single source, the top road (incoming arrow), and leave the network from one of two destinations (outgoing arrows) D1 or D2. All roads are composed of two lanes per direction and assumed to have infinite capacity1 except the two vertical roads in the middle of the network (Congestible link #1 and #2), which possess only one lane (capacity = 1,908 agents per hour). An agent entering the system and heading towards D1 (or symmetrically D2) has two possible routes to choose from: a short route (668 m) or a long route (964 m). Each agent chooses one of the two routes according to the distance, traffic conditions, and tolls associated with it. This road network represents a special case where if most agents are heading to D1 (or symmetrically D2) then link #1 (#2) should be tolled while link #2 (#1) should not. We define z (or symmetrically 1 z) to be the proportion of agents heading to D1 (D2). The incoming traffic rate was set to 2,160 agents per lane per hour. First, we computed, in a brute-force manner, the toll values that optimize average travel time for each z 2 f0:0; 0:1; 0:2; :::; 1g. We considered tolling only congestible link #2. Tolling uncongestible links is unnecessary as there is no congestion externality associated with travel on these links. Moreover, there is no reason to toll both congestible links simultaneously (#1 and #2) since any of the two possible routes (leading from source to Di) includes exactly one of these links. A negative toll value for link #2 is symmetrical to a positive toll on link #1. We distinguish between the optimal adaptive toll and the optimal static toll. The optimal adaptive toll is the toll value that minimizes travel time for a given z value. The optimal static toll is the toll value that minimizes travel time over all z values (assuming equal weighting of the z values, i.e., all z values have the same probability), found to 1The capacity on roads with two lanes is higher than the rate in which agents are spawned. Hence, we consider such roads as having infinite capacity. z 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 be 10 in this example. While it might seem like the optimal static toll should be zero, asymmetries in the model arising from differences between left and right turns affect junction delays and skew the optimal static toll to one side.
Optimal adaptive tolls for each z value are presented in Table 1. Notice that as the z value increases, the optimal toll steadily decreases. Intuitively, when all agents go to one destination (z = 0 or z = 1) we need more of them to choose the longer route to achieve the optimal system flow, thus requiring a more extreme toll. When z 0:5, a zero toll is optimal since agents that choose their longer route will only make congestion worse for agents going to the other destination. As a result, enforcing tolls for 0:2 < z < 0:8 did not result in a significant improvement over enforcing no tolls. The reason that Table 1 present values different than zero for that range stems from noise and asymmetries in the model. 4.3
We compared the empirically optimal tolls against the toll values predicted by the macro-model. Toll values calculated by the macro-model are also presented in Table 1. Table 1 also presents average travel time under different tolling policies (for now ignore the -tolls column). Though the macromodel obtains near optimal results for the extreme z values and z = 0:5, it is sub-optimal for intermediate values. One explanation for this phenomenon is that the stylized congestion models assume that delays on a link are a function solely of flow on that link, ignoring interactions between links at intersections. For the extreme z values this assumption is more reasonable because almost all agents on congestible links are heading in the same direction. However for the intermediate values (excluding 0:5) the agents on the congestible links encounter traffic on the bottom horizontal link (by cars taking the longer route) causing changes in the capacity of the congestible links that cannot be captured by a stylized model. These results lead us to the following conclusions: 1. Tolls can reduce average travel time by up to 11% compared to applying no tolls (see z = 0). 2. Static tolls might have a negative effect in some cases (see z < 0:6). 3. The macro-model fails to achieve system optimal in some cases reaching up to 10% suboptimality (see z = 0:3).
Both static and adaptive macro-model based tolls (a) result in suboptimal performance and (b) require that the demand over all OD pairs is known and fixed. As a result, neither is applicable to real-world traffic. There is thus, a need for a new tolling scheme that is dynamic, adaptive, and results in near-optimal traffic flow. 5
This section introduces the main technical contribution of the paper, a new tolling scheme denoted -tolling. Unlike macroscopic models, -tolling is adaptive to unknown and changing link capacities and demands. We first define -tolling and then prove, under mild assumptions, that it is equivalent to MCT.
-tolling is defined over a directed network G = (V; E) (a road network for example) with a set of current flow values (traffic volume for example). The output of -tolling is a set of toll values, one toll value per link. We use te to denote the current flow time on link e 2 E. Recall that Te denotes the free flow travel time and tolle to denote the toll value assigned to link e. For each link (e), -tolling assigns a toll equivalent to the difference between the current flow time (te) and the free flow time (Te) multiplied by a parameter ( ). More formally: -tolle = (te Te). As a rule of thumb, should be correlated to the mean VOT. High values result in high toll values which are needed to influence agents with high VOT. Calculating -tolle requires a constant amount of time. As a result, the complexity of computing tolls for an entire network is (E).
Next we prove that -tolling is equivalent to MCT under some conditions. This is a desirable property, since MCT results in system optimal (see Section 2). First, we list the assumptions under which the above statement holds:
1. The delay on each link is expressed by the BPR volume delay function, te(xe) = Te(1 + ( Cxee ) ). 2. Changes in traffic flow are negligible between the time an agent plans its route and the time it traverses the network.
Lemma 1 Under the above assumptions, the tolls computed by -tolling are equivalent to the MCT.
Proof: We express the BPR volume delay function as: (1) te(xe) = Te + axe where a = Te Ce . MCT is defined as the derivative of the delay function ( dte(xe) ) multiplied by dxe the flow (xe). Calculating MCT requires knowing the future flow but under Assumption 2 we can use current flow instead. So we get: (2) M CTe = xe dtdex(xee) = xe( axe 1) = axe = (Te + axe Te).
Combining (1) and (2) we get: M CTe = (te Te) = -tolle.
The main theoretical differences between -tolling and macroscopic models are summarized in Table 2. In the next section we study the differences in performance using the adapted AIM simulator.
Although the assumptions made in this section might not hold in all possible traffic networks, we provide experimental results showing that in realistic simulations, -tolling improves traffic flow and may achieve near optimal flow. 6
This section analyzes the performance of -tolling on a representative road network. We then generalize our findings and show they also hold for randomly generated networks. We begin by comparing the system performance when using tolling on the exemplar road network (presented in Figure 1). Table 1 also presents the average travel time for -tolling. Unlike the macro-model, -tolling achieves performance that is similar to the optimal. We do not report the toll values for -tolling as they are dynamically changing across the simulation.
Next, we present results for larger networks. In such networks finding the optimal tolls in a brute force manner is infeasible.2 For the following experiments we used grid networks of size 3 3 that include 9 intersection (see Figure 3 for an example). Agents enter at the same rate of 300 agents per hour from any incoming lane (a road with three lanes, for example, spawns 900 agents per hour). Each agent entering the system is assigned one of two possible exit roads with equal probability (0.5). Each agent is also assigned two alternative exits. Exiting via an alternative exit imposes a predefined, randomly generated, delay.3 We justify allowing alternative exits as follows, in many real-life scenarios, several routes, usually of different length, may lead an agent to its destination. For example, a driver exiting Manhattan and heading to Queens will prefer to exit via Queens Midtown Tunnel, it can suffer some delay and exit from Ed Koch Queensboro Bridge or suffer a severe delay while exiting via Williamsburg Bridge. Following this logic, we view the simulated network as part of a larger road network in which agents may use paths outside of the network to reach their final destination.
Some roads in the simulated network are more congestible than others i.e., the number of lanes varies. The number of lanes for each road was randomly picked from [1; 4]. We ran the simulator for 5000 seconds for each reported setting.4 In the following experiments we used an upper bound on toll values equal to 25¢.5 The upper bound is set for two reasons: (1) avoiding overcharging in links with temporary heavy congestion (2) avoiding oscillation in congestion caused by overpricing: heavy congestion may cause a steep increase to the toll value which later leads to the link being vacated which leads the toll value to reduce to zero. Zero toll value results, again, in heavy congestion. Applying no cap on toll values resulted in up to 5% reduced utility. We report three different measurements: • Time - the average travel time. • Utility - the average utility (in cents). Where utility is defined for each agent as its travel time multiplied by its VOT plus the summation of tolls paid by it. • Standardized Utility (SU) - toll revenue may be redistributed back to the drivers in the form of road improvements or tax reductions. We define refund as the sum of collected tolls divided by the number of agents that exited the system. SU is defined as average utility minus refund. 6.1
The purpose of our first experiment is to determine how different values affect system performance. For this experiment we used a single randomly generated instance of a 3 3 2Examining different combinations of toll assignment to all links in the system leads to an exponential blowup.
3When each agent is assigned only one possible exit, distributing traffic becomes impossible in many cases. For such scenarios, imposing tolls did not have a positive effect in our experiments.
4When running the simulator, in order to allow the system to balance, we exclude data from the first 500 seconds.
5The output from the macro-model contained no toll greater than 25¢. Hence we deduced that greater tolls won’t have a positive affect and we set the cap accordingly. road network - depicted in Figure 3. Average travel time, Utility and SU for different values are presented in Figure 2. Notice that = 0 represent the case where no tolls are used.
Setting = 80 gives an improvement of 35% in average travel time over no tolls. = 80 also gives an improvement of 35.01% for SU over no tolls. values greater than 80 result in average travel times that are not significantly worse or better. Increasing (up to 80) results in higher toll values which better distribute congestion. However, higher tolls also negatively impact utility as drivers are forced to pay more. Utility is maximized with = 8 which gives a 6.96% improvement over no tolls. We also report performance when tolls as computed by the macro-model are used, given as a dashed (red) line across the result graphs. -tolling outperforms macromodel tolling for 4 by up to 18% in both average travel time and SU. On the other hand, macro-model tolling exceeds by 6.25% when utility is considered. The main reason for the macro-model’s advantage w.r.t utility is that tolling imposes higher toll values. -tolling (with = 8) collected a total of $1,921 while macro-model tolling collected only $825. Unfortunately, we observed that higher tolls are required to better distribute congestion and optimize system performance. On the other hand, we believe that standard utility is a more relevant measurement for performance comparison between the models. In real road networks tolls are most often used to fund road maintenance, effectively redistributing the money collected back to the public. When SU is considered, delta tolling significantly outperforms the macromodel in all but very low . Moreover, macro-model tolling relies on static traffic conditions and so, unlike -tolling it is not applicable to real-life, dynamic road networks. 6.2
In order to validate that the results obtained from a single randomized instance are representative, we reran the same experiment using 50 different randomized road networks. Each of these networks is a 3 3 grid, similar to the representative road network, but the exit roads, alternative exits, alternative exits’ delay, and number of lanes per road are randomized. Table 3 shows results for three representative values (8, 20, 80) compared to no tolling. = 8 and = 80 are chosen since they maximized performance with respect to utility and travel time/SU. = 20 represents a good balance between utility and travel time.
We observe that the advantage of -tolling is robust to changes in network topology. For the general case, -tolling achieves an improvement over no tolling of 29.2%, 9.31% and 30.28% in Time, Utility and SU respectively.
This paper considers applying tolls to road networks in order to direct the route choice of self-interested agents towards a system optimal. The notion of such a tolling scheme is becoming more practical as cars are becoming increasingly autonomous and the computational effort required to evaluate several alternative routes is becoming more feasible.
This paper makes two main contributions. First, using a traffic micro-simulator (AIM), we provide empirical evidence suggesting that stylized macroscopic traffic models are unable to approximate optimal tolls accurately. Given this finding and the fact that such models require full knowledge of demand and supply and assume that these remain fixed, we conclude that using such models to set tolls in real-life road networks is impractical. This conclusion leads us to the second contribution, the presentation and evaluation of a new tolling scheme, denoted -tolling. We provide theoretical and empirical evidence that -tolling results in near-optimal system performance while being adaptive to traffic conditions and computationally feasible.
Our ongoing research agenda includes evaluating the performance of -tolling in dynamic environments, in which traffic demand and supply is time varying. 8
A portion of this work has taken place in the Learning Agents Research Group (LARG) at UT Austin. LARG research is supported in part by NSF (CNS-1330072, CNS-1305287), ONR (21C184-01), and AFOSR (FA9550-14-1-0087). Peter Stone serves on the Board of Directors of, Cogitai, Inc. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy on objectivity in research. The authors would also like to acknowledge the support of the Data-Supported Transportation Operations & Planning Center and the National Science Foundation under Grant No. 1254921.