Delta-Tolling: Adaptive Tolling for Optimizing Traffic Throughput Guni Sharon1 , Josiah Hanna1 , Tarun Rambha2 , Michael Albert1 , Peter Stone1 , Stephen D. Boyles2 1 Department of Computer Science, 2 Department of Civil Engineering The University of Texas at Austin, Austin, TX 78712 USA Abstract other agents (also known as the marginal cost) results in opti- mal flow [Pigou, 1920; Beckmann et al., 1956; Braess, 1969]. In recent years, the automotive industry has been The damage inflicted by a given agent is evaluated through rapidly advancing toward connected vehicles with the marginal slowdown caused by it and is commonly evalu- higher degrees of autonomous capabilities. This ated using stylized traffic models. Such stylized models take a trend opens up many new possibilities for AI-based “macroscopic” view of traffic, where delay can be expressed efficient traffic management. This paper investi- as a smooth function of travel demand. We hereafter refer gates traffic optimization through the setting and to such models as macro-models. The marginal slowdown, broadcasting of dynamic and adaptive tolls under evaluated by such models, is then used to infer appropriate the assumption that the cars will be able to contin- tolls. However these macro-models make many approxima- ually reoptimize their paths as tolls change. tions and assumptions that don’t hold in practice. Previous work has studied tolling policies that re- Modern simulation tools and computational power allow sult in optimal traffic flow and several traffic mod- for much more fine-grained simulation of traffic networks, els were developed to compute such tolls. Unfortu- referred to as micro-simulation models. Using such a real- nately, applying these models in practice is infeasi- istic traffic simulator we demonstrate the potential of using ble due to the dynamically changing nature of typ- tolls for reducing average travel time and increasing aver- ical traffic networks. Moreover, this paper shows age utility. In this paper we show (empirically) that comput- that previously developed tolling models that were ing tolls using a macro-model does not lead to optimal per- proven to yield optimal flow in theory may not be formance in a realistic simulator. We explain this effect by optimal in real-life simulation. Next, this paper in- noting that macro-models assume deterministic conditions, troduces an efficient tolling scheme, denoted ∆- and have a number of unrealistic features. In recent years, tolling, for setting dynamic and adaptive tolls. We researchers have relaxed the assumptions of the first macro- evaluate the performance of ∆-tolling using a traf- scopic tolling models to incorporate responsiveness to road- fic micro-simulator. ∆-tolling is shown to reduce way disruptions such as accidents [de Palma and Lindsey, average travel time by up to 35% over using no tolls 1998; Yang, 1999a,b; Lindsey, 2009; Boyles et al., 2010] and by up to 17% when compared to the current and to the total level of travel demand [Nagae and Aka- state-of-the-art tolling scheme. matsu, 2006; Chen and Subprasom, 2007; Gardner et al., 2008, 2011]. However, the effectiveness of all of these models is still restricted by the use of simplifying assumptions such 1 Introduction as constant and known demand and capacity for each link. In recent years, communication and computation capabili- In response to the suboptimal performance of existing ties have become increasingly common onboard vehicles. macro-models, this paper introduces a novel tolling scheme Such capabilities present opportunities for developing safer, denoted ∆-tolling. ∆-tolling approximates the marginal cost cleaner and more efficient road networks. This paper com- of each link using only two variables (current travel time and bines knowledge from mechanism design, game theory, net- free flow travel time) and one parameter. Due to its simplicity, work flow optimization, and multi-agent simulations for in- ∆-tolling is fast to compute, adaptive to current traffic, and vestigating responsive pricing, as a scheme for managing and accurate. We prove that, under some assumptions, ∆-tolling optimizing traffic flow. results in tolls that are equivalent to the marginal cost and It has been known for nearly a century that drivers seek- demonstrate that it can lead to near-optimal performance in ing to minimize their private travel times need not minimize practice. the total level of congestion. In other words, self-interested drivers may reach an equilibrium that is not optimal from a 2 Motivation system perspective. On the other hand, charging each agent This section defines the notion of user equilibrium (UE) and with an amount equivalent to the damage it inflicts on all system optimum (SO). Applying tolls is then introduced as a mechanism that allows UE and SO to coincide. The marginal A number of researchers have attempted to develop macro- cost toll (MCT) policy is then presented followed by some models that approximate MCT for a given system [Yang et macroscopic traffic models that approximate it. We discuss al., 2004; Han and Yang, 2009]. However, a major drawback some of the drawbacks of such macro-models, which pro- of such macro-models is that they are static and do not capture vides the motivation for the current study. the time-varying nature of traffic. They also assume that the delay on each link is a function of its flow and hence neglect 2.1 Computing User Equilibrium effects of intersections and traffic shocks. Although there has Consider a directed network G = (V, E), where V and E been some research on congestion pricing using finer traffic are the set of nodes and links respectively. Suppose that the flow models, most of the existing models either assume com- demand (flow rates) between every pair of nodes is known. plete knowledge of demand distribution over time [Wie and In this paper we assume that the travel time on a link e ∈ E Tobin, 1998; Joksimovic et al., 2005] or are restricted to find- is a function of its flow (xe ) and is represented using a non- ing tolls on freeways in which travelers choose only between decreasing function te (xe ) (also called volume delay or link- parallel tolled and free general-purpose lanes [Gardner et al., performance functions). In practice, the Bureau of Public 2013, 2015; Yin and Lou, 2009]. This limitation motivates xe β Roads (BPR) function te (xe ) = Te (1 + α( C e ) ) is com- us to employ a simulation framework to replicate traffic in a monly used as the delay function, where Te is the free flow more realistic manner, evaluate the performance of existing travel time and Ce is the capacity of link e. α and β are pa- macro-models, and develop new methods to determine opti- rameters whose default values are 0.15 and 4 respectively. mal tolls while adapting to unknown and changing demand. When agents choose routes selfishly, a state of equilibrium, called user equilibrium (UE) [Wardrop, 1952], is reached in 3 Simulation which all used routes between an origin-destination (OD) pair have equal and minimal travel time. The link flow rates corre- In order to evaluate the effectiveness of different tolling mod- sponding to this state can be obtained by solving a non-linear els on traffic flow optimization, we used a modified ver- convex sion of the Autonomous Intersection Manager (AIM) micro- Pprogram R x that minimizes the Beckmann potential func- tion ( e∈E 0 e te (xe ) dx) Beckmann et al. [1956]. This ob- simulator [Dresner and Stone, 2008]. On the one hand, AIM jective ensures that the KKT (Karush-Kuhn-Tucker) condi- is very realistic in the sense that it allows simulating accel- tions [Kuhn and Tucker, 1951; Karush, 1939] of the convex erations of individual vehicles in response to traffic condi- program correspond to Wardrop’s UE principle [Wardrop, tions. On the other hand, due to computational limitations, 1952]. The constraints of the optimization problem include AIM cannot scale to large road networks (only up to 3 × 3 non-negativity and flow conservation constraints. This model, grid network). For our experiments AIM was chosen since, also known as the traffic assignment problem (see Patriksson unlike other simulators, it allows non deterministic traffic be- [1994] for a thorough overview), has been widely studied be- havior, provides (direct) measurements on vehicle following cause of the mathematically appealing properties associated distances, lane changes, gap acceptance, etc. with convex programming. 3.1 Autonomous Intersection Manager Simulator 2.2 Computing System Optimum AIM provides a multiagent framework for simulating au- The system optimal (SO) problem can be formulated using tonomous vehicles on a road network grid; it presents a realis- a set of constraints similar to those usedP for computing UE tic traffic flow model that allows experimenting with adaptive but replacing the objective function with e∈E xe te (xe ). As tolling. The AIM simulator uses two types of agents: inter- mentioned before, all agents do not experience equal and min- section managers, one per intersection, and driver agents, one imal travel times at the SO state which incentivizes agents to per vehicle. Intersection managers are responsible for direct- switch routes. Instead, if an optimal tolling policy is applied, ing the vehicles through the intersections, while the driver the flows resulting from a UE assignment in which agents agents are responsible for controlling the vehicles to which minimize the generalized cost (time + toll) coincides with the they are assigned. To improve the throughput and efficiency SO solution. MCT is proven to be such a policy (UE=SO) of the system, the driver agents “call ahead” to the inter- [Pigou, 1920; Beckmann et al., 1956; Braess, 1969]. In MCT section manager and request a path reservation (space-time each agent is charged a toll that is equal to the increase in sequence) within the intersection. The intersection manager travel time it inflicts on all other agents. Unfortunately, know- then determines whether or not this request can be met. If the ing in advance the marginal impact of an agent on traffic is intersection manager approves a driver agent’s request, the infeasible in practice. driver agent must follow the assigned path through the inter- section. On the other hand, if the intersection manager rejects 2.3 Approximating Marginal-Cost Tolls a driver agent’s request, the driver agent may not pass through The focus of this paper is methods that approximate the the intersection but may attempt to request a new reservation. marginal cost. Most of these methods assume that demand At every intersection, the driver agent navigator runs an A∗ on each link is constant. In such cases MCT can be formally search [Hart et al., 1968] to determine the shortest path lead- defined as follows: given a link (e) and flow (xe ) the toll ap- ing to the destination of the vehicle associated with it. The plied to e equals the change in travel time caused by an in- navigator then directs the driver agent to drive via the shortest finitesimal flow ( dtdx e (xe ) e ) multiplied by the number of agents route. This behavior ensures that each vehicle acts greedily currently on this link (xe ). with respect to minimizing travel time. Next, we describe the required enhancements to the standard AIM simulator [Dres- ner and Stone, 2008] necessary to simulate realistic tolling experiments. 3.2 Enhancements to the AIM Simulator 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 P chooses the route (r = to its destination, the driver agent Figure 1: Exemplar road network within the AIM simulator. e1 , e2 , ..., e3 ) that minimizes e∈r te × V OT + tolle , where V OT is the monetary value Of time. speed limit across all roads is 25 meters per second. Each • Value Of Time: each driver agent is associated with horizontal road is 142 meters long, and each vertical road is a randomly generated V OT that is drawn from a nor- 192 meters long. We examined a scenario in which agents en- mal distribution. We assume monetary units are chosen ter the network from a single source, the top road (incoming such that the mean value is 1¢ per second, and assume arrow), and leave the network from one of two destinations a standard deviation of 0.2. V OT represents the value (outgoing arrows) D1 or D2. All roads are composed of two (in cents) of one second for the driver. A driver with lanes per direction and assumed to have infinite capacity1 ex- V OT = x is willing to pay up to x¢ in order to reduce cept the two vertical roads in the middle of the network (Con- travel time by 1 second. gestible link #1 and #2), which possess only one lane (capac- ity = 1,908 agents per hour). An agent entering the system 3.3 Macroscopic Model and heading towards D1 (or symmetrically D2) has two pos- This paper uses a macroscopic model to approximate MCT. sible routes to choose from: a short route (668 m) or a long This model is used to solve the convex program described route (964 m). Each agent chooses one of the two routes ac- in Section 2 using Algorithm B [Dial, 2006]. Algorithm B is cording to the distance, traffic conditions, and tolls associated a bush-based/origin-based algorithm which exploits the fact with it. This road network represents a special case where if that at equilibrium, all used routes carrying demand from a most agents are heading to D1 (or symmetrically D2) then particular origin must belong to an acyclic subgraph in which link #1 (#2) should be tolled while link #2 (#1) should not. each destination can be reached from the origin (such a sub- We define z (or symmetrically 1 − z) to be the proportion of graph is also called a bush). At each iteration, the algorithm agents heading to D1 (D2). The incoming traffic rate was set maintains a collection of bushes (one for each origin), shifts to 2,160 agents per lane per hour. agents within a bush to minimize their generalized costs, and adds/removes links in a bush until equilibrium is reached. 4.2 Computing the Optimal Tolls Closeness to equilibrium is measured using average excess First, we computed, in a brute-force manner, the toll cost, which represents the average of the difference between values that optimize average travel time for each z ∈ each agent’s generalized cost and the least cost path at the {0.0, 0.1, 0.2, ..., 1}. We considered tolling only congestible current flow solution. In the experiments presented in this pa- link #2. Tolling uncongestible links is unnecessary as there per, the algorithm was terminated when the average excess is no congestion externality associated with travel on these cost of the flow solution dropped below 1E-13. links. Moreover, there is no reason to toll both congestible links simultaneously (#1 and #2) since any of the two possi- 4 Empirical Evaluation: Macroscopic Model ble routes (leading from source to Di) includes exactly one of these links. A negative toll value for link #2 is symmetrical to One of the main contributions of this paper is an empirical a positive toll on link #1. We distinguish between the optimal demonstration that setting tolls based on macro-models can adaptive toll and the optimal static toll. The optimal adaptive lead to suboptimal results when evaluated in a more realistic toll is the toll value that minimizes travel time for a given z micro-simulator. This section presents these empirical results, value. The optimal static toll is the toll value that minimizes which motivate our new tolling scheme as presented in the travel time over all z values (assuming equal weighting of the next section. z values, i.e., all z values have the same probability), found to 4.1 Exemplar Road-Network 1 The capacity on roads with two lanes is higher than the rate in Figure 1 illustrates an exemplar road network that demon- which agents are spawned. Hence, we consider such roads as having strate the impact of tolls that adapt to traffic demand. The infinite capacity. Toll Values AVG Travel Time (seconds) z Optimal Macro Model No Tolls Static Tolls Optimal Tolls Macro Tolls ∆-Tolls 0.0 15 14.8 46.0 47.6 40.9* 40.3* 40.5* 0.1 10 14.8 43.2 45.1 39.1* 39.3* 39.0* 0.2 10 14.8 38.4 40.8 35.8* 38.4 36.9* 0.3 10 14.8 34.3 35.1 33.8 37.7 33.1* 0.4 0 14.8 31.7 32.4 31.7 36.8 31.4 0.5 5 -5.3 30.8 31.2 30.8 30.9 30.9 0.6 5 -14.8 31.1 31.5 31.1 34.7 31.6 0.7 -5 -14.8 32.2 32.2 32.2 35.2 32.8 0.8 -10 -14.8 37.0 34.1* 34.1* 36.2 35.8* 0.9 -10 -14.8 40.7 36.2* 36.2* 36.8* 36.5* 1.0 -15 -14.8 43.1 39.0* 38.5* 38.1* 38.7* Table 1: The left side of the table shows the empirical optimal and macro-model predicted toll values (imposed on link #2) for different z values. The right side shows average travel times when no tolls, static tolls, optimal tolls, macro-model tolls and ∆-tolls are applied as calculated by the AIM simulator. * indicates statistical significance over no tolls (using unpaired t-test with pvalue = 0.05). be −10 in this example. While it might seem like the optimal 2. Static tolls might have a negative effect in some cases static toll should be zero, asymmetries in the model arising (see z < 0.6). from differences between left and right turns affect junction 3. The macro-model fails to achieve system optimal in delays and skew the optimal static toll to one side. some cases reaching up to 10% suboptimality (see z = Optimal adaptive tolls for each z value are presented in Ta- 0.3). ble 1. Notice that as the z value increases, the optimal toll steadily decreases. Intuitively, when all agents go to one des- Both static and adaptive macro-model based tolls (a) result tination (z = 0 or z = 1) we need more of them to choose in suboptimal performance and (b) require that the demand the longer route to achieve the optimal system flow, thus re- over all OD pairs is known and fixed. As a result, neither is quiring a more extreme toll. When z ≈ 0.5, a zero toll is applicable to real-world traffic. There is thus, a need for a optimal since agents that choose their longer route will only new tolling scheme that is dynamic, adaptive, and results in make congestion worse for agents going to the other destina- near-optimal traffic flow. tion. As a result, enforcing tolls for 0.2 < z < 0.8 did not result in a significant improvement over enforcing no tolls. 5 Delta-tolling The reason that Table 1 present values different than zero for that range stems from noise and asymmetries in the model. This section introduces the main technical contribution of the paper, a new tolling scheme denoted ∆-tolling. Unlike macro- 4.3 Evaluating Optimal Tolls Using a scopic models, ∆-tolling is adaptive to unknown and chang- Macro-Model ing link capacities and demands. We first define ∆-tolling and then prove, under mild assumptions, that it is equivalent to We compared the empirically optimal tolls against the toll MCT. values predicted by the macro-model. Toll values calculated ∆-tolling is defined over a directed network G = (V, E) (a by the macro-model are also presented in Table 1. Table 1 road network for example) with a set of current flow values also presents average travel time under different tolling poli- (traffic volume for example). The output of ∆-tolling is a set cies (for now ignore the ∆-tolls column). Though the macro- of toll values, one toll value per link. We use te to denote model obtains near optimal results for the extreme z values the current flow time on link e ∈ E. Recall that Te denotes and z = 0.5, it is sub-optimal for intermediate values. One the free flow travel time and tolle to denote the toll value explanation for this phenomenon is that the stylized conges- assigned to link e. For each link (e), ∆-tolling assigns a toll tion models assume that delays on a link are a function solely equivalent to the difference between the current flow time (te ) of flow on that link, ignoring interactions between links at in- and the free flow time (Te ) multiplied by a parameter (β). tersections. For the extreme z values this assumption is more More formally: ∆-tolle = β(te − Te ). As a rule of thumb, β reasonable because almost all agents on congestible links are should be correlated to the mean VOT. High β values result heading in the same direction. However for the intermediate in high toll values which are needed to influence agents with values (excluding 0.5) the agents on the congestible links en- high VOT. Calculating ∆-tolle requires a constant amount of counter traffic on the bottom horizontal link (by cars taking time. As a result, the complexity of computing tolls for an the longer route) causing changes in the capacity of the con- entire network is Θ(E). gestible links that cannot be captured by a stylized model. Next we prove that ∆-tolling is equivalent to MCT under These results lead us to the following conclusions: some conditions. This is a desirable property, since MCT re- 1. Tolls can reduce average travel time by up to 11% com- sults in system optimal (see Section 2). First, we list the as- pared to applying no tolls (see z = 0). sumptions under which the above statement holds: Macro-model ∆-tolling infeasible.2 For the following experiments we used grid net- Parameters Required works of size 3×3 that include 9 intersection (see Figure 3 for α yes no an example). Agents enter at the same rate of 300 agents per β yes yes hour from any incoming lane (a road with three lanes, for ex- Variables Required ample, spawns 900 agents per hour). Each agent entering the Demands yes no Ce yes no system is assigned one of two possible exit roads with equal Te yes yes probability (0.5). Each agent is also assigned two alternative te no yes exits. Exiting via an alternative exit imposes a predefined, Properties Satisfied randomly generated, delay.3 We justify allowing alternative Adaptive no yes exits as follows, in many real-life scenarios, several routes, MCT yes yes usually of different length, may lead an agent to its destina- tion. For example, a driver exiting Manhattan and heading Table 2: The different parameters, variables and properties of to Queens will prefer to exit via Queens Midtown Tunnel, it ∆-tolling and macro-model tolling. MCT refers to approxi- can suffer some delay and exit from Ed Koch Queensboro mating the marginal cost. 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 1. The delay on each link is expressed by the BPR volume outside of the network to reach their final destination. xe β delay function, te (xe ) = Te (1 + α( C ) ). e Some roads in the simulated network are more congestible 2. Changes in traffic flow are negligible between the time than others i.e., the number of lanes varies. The number of an agent plans its route and the time it traverses the net- lanes for each road was randomly picked from [1, 4]. We ran work. the simulator for 5000 seconds for each reported setting.4 In the following experiments we used an upper bound on toll Lemma 1 Under the above assumptions, the tolls computed values equal to 25¢.5 The upper bound is set for two reasons: by ∆-tolling are equivalent to the MCT. (1) avoiding overcharging in links with temporary heavy con- Proof: We express the BPR volume delay function as: gestion (2) avoiding oscillation in congestion caused by over- (1) te (xe ) = Te + axe β where a = Te Ceα β . MCT is defined pricing: heavy congestion may cause a steep increase to the toll value which later leads to the link being vacated which as the derivative of the delay function ( dtdx e (xe ) e ) multiplied by leads the toll value to reduce to zero. Zero toll value results, the flow (xe ). Calculating MCT requires knowing the future again, in heavy congestion. Applying no cap on toll values flow but under Assumption 2 we can use current flow instead. resulted in up to 5% reduced utility. We report three different So we get: measurements: (2) M CTe = xe dtdx e (xe ) = xe (βaxe β−1 ) = βaxe β = e • Time - the average travel time. β(Te + axe β − Te ). Combining (1) and (2) we get: • Utility - the average utility (in cents). Where utility is M CTe = β(te − Te ) = ∆-tolle .  defined for each agent as its travel time multiplied by its The main theoretical differences between ∆-tolling and VOT plus the summation of tolls paid by it. macroscopic models are summarized in Table 2. In the next • Standardized Utility (SU) - toll revenue may be redis- section we study the differences in performance using the tributed back to the drivers in the form of road improve- adapted AIM simulator. ments or tax reductions. We define refund as the sum of Although the assumptions made in this section might not collected tolls divided by the number of agents that ex- hold in all possible traffic networks, we provide experimen- ited the system. SU is defined as average utility minus tal results showing that in realistic simulations, ∆-tolling im- refund. proves traffic flow and may achieve near optimal flow. 6.1 Representative Road Network 6 Empirical Evaluation: Delta-Tolling The purpose of our first experiment is to determine how dif- This section analyzes the performance of ∆-tolling on a rep- ferent β values affect system performance. For this experi- resentative road network. We then generalize our findings and ment we used a single randomly generated instance of a 3 × 3 show they also hold for randomly generated networks. We 2 begin by comparing the system performance when using ∆- Examining different combinations of toll assignment to all links in the system leads to an exponential blowup. tolling on the exemplar road network (presented in Figure 1). 3 When each agent is assigned only one possible exit, distribut- Table 1 also presents the average travel time for ∆-tolling. ing traffic becomes impossible in many cases. For such scenarios, Unlike the macro-model, ∆-tolling achieves performance that imposing tolls did not have a positive effect in our experiments. is similar to the optimal. We do not report the toll values for 4 When running the simulator, in order to allow the system to ∆-tolling as they are dynamically changing across the simu- balance, we exclude data from the first 500 seconds. lation. 5 The output from the macro-model contained no toll greater than Next, we present results for larger networks. In such net- 25¢. Hence we deduced that greater tolls won’t have a positive affect works finding the optimal tolls in a brute force manner is and we set the cap accordingly. Figure 2: Average travel time, utility and standardized utility as a function of β for the representative road network. β Time Utility SU 0.0 69.9 -70.0 -70.0 8.0 51.4* -63.5 -51.1* 20.0 50.3* -67.0 -49.8* 80.0 49.5* -76.6 -48.8* Table 3: Average travel time, utility, and SU for β values 8, 20, 80. These β values represent a trade-off between the three metrics. *Denotes a statistically significant improve- ment over no tolling (using a paired t-test with pvalue = 0.05). lected only $825. Unfortunately, we observed that higher tolls are required to better distribute congestion and optimize sys- tem performance. On the other hand, we believe that standard Figure 3: A representative road network. Each agent is as- utility is a more relevant measurement for performance com- signed one of to destinations (D1, D2). A1 and A2 denote parison between the models. In real road networks tolls are alternative destinations for D1 and D2 respectively. The time most often used to fund road maintenance, effectively redis- penalty associated with each alternative destination is given tributing the money collected back to the public. When SU is in parenthesis. considered, delta tolling significantly outperforms the macro- model in all but very low β. Moreover, macro-model tolling relies on static traffic conditions and so, unlike ∆-tolling it is road network - depicted in Figure 3. Average travel time, Util- not applicable to real-life, dynamic road networks. ity 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 6.2 General Case travel time over no tolls. β = 80 also gives an improvement of 35.01% for SU over no tolls. β values greater than 80 result In order to validate that the results obtained from a single ran- in average travel times that are not significantly worse or bet- domized instance are representative, we reran the same exper- ter. Increasing β (up to 80) results in higher toll values which iment using 50 different randomized road networks. Each of better distribute congestion. However, higher tolls also nega- these networks is a 3 × 3 grid, similar to the representative tively impact utility as drivers are forced to pay more. Utility road network, but the exit roads, alternative exits, alternative is maximized with β = 8 which gives a 6.96% improvement exits’ delay, and number of lanes per road are randomized. over no tolls. We also report performance when tolls as com- Table 3 shows results for three representative β values (8, 20, puted by the macro-model are used, given as a dashed (red) 80) compared to no tolling. β = 8 and β = 80 are chosen line across the result graphs. ∆-tolling outperforms macro- since they maximized performance with respect to utility and model tolling for β ≥ 4 by up to 18% in both average travel travel time/SU. β = 20 represents a good balance between time and SU. On the other hand, macro-model tolling ex- utility and travel time. ceeds by 6.25% when utility is considered. The main rea- We observe that the advantage of ∆-tolling is robust to son for the macro-model’s advantage w.r.t utility is that ∆- changes in network topology. For the general case, ∆-tolling tolling imposes higher toll values. ∆-tolling (with β = 8) achieves an improvement over no tolling of 29.2%, 9.31% collected a total of $1,921 while macro-model tolling col- and 30.28% in Time, Utility and SU respectively. 7 Conclusions Kurt Dresner and Peter Stone. A multiagent approach to au- This paper considers applying tolls to road networks in order tonomous intersection management. Journal of artificial to direct the route choice of self-interested agents towards a intelligence research, pages 591–656, 2008. system optimal. The notion of such a tolling scheme is be- Lauren Gardner, Jennifer Duthie, Avinash Unnikrishnan, and coming more practical as cars are becoming increasingly au- S. Travis Waller. Robust pricing for networks with demand tonomous and the computational effort required to evaluate uncertainty, 2008. Presented at the 87th Annual Meeting several alternative routes is becoming more feasible. of the Transportation Research Board, Washington, DC. This paper makes two main contributions. First, using a Lauren Gardner, Stephen D. Boyles, and S. Travis Waller. traffic micro-simulator (AIM), we provide empirical evidence Quantifying the benefit of responsive pricing and travel suggesting that stylized macroscopic traffic models are un- information in the stochastic congestion pricing problem. able to approximate optimal tolls accurately. Given this find- Transportation Research Part A, 45:204–218, 2011. ing and the fact that such models require full knowledge of demand and supply and assume that these remain fixed, we Lauren Gardner, Hillel Bar-Gera, and Stephen D. Boyles. De- conclude that using such models to set tolls in real-life road velopment and comparison of choice models and tolling networks is impractical. This conclusion leads us to the sec- schemes for high-occupancy/toll (HOT) facilities. Trans- ond contribution, the presentation and evaluation of a new portation Research Part B, 55:142–153, 2013. tolling scheme, denoted ∆-tolling. We provide theoretical Lauren Gardner, Stephen D. Boyles, Hillel Bar-Gera, and empirical evidence that ∆-tolling results in near-optimal and Kelly Tang. Robust tolling schemes for high- system performance while being adaptive to traffic conditions occupancy/toll (HOT) facilities under variable demand. and computationally feasible. Transportation Research Record, 2450:152–162, 2015. Our ongoing research agenda includes evaluating the per- Deren Han and Hai Yang. Congestion pricing in the absence formance of ∆-tolling in dynamic environments, in which of demand functions. Transportation Research Part E: Lo- traffic demand and supply is time varying. gistics and Transportation Review, 45(1):159 – 171, 2009. 8 Acknowledgments Peter E Hart, Nils J Nilsson, and Bertram Raphael. A for- mal basis for the heuristic determination of minimum cost A portion of this work has taken place in the Learning Agents paths. Systems Science and Cybernetics, IEEE Transac- Research Group (LARG) at UT Austin. LARG research is tions on, 4(2):100–107, 1968. supported in part by NSF (CNS-1330072, CNS-1305287), ONR (21C184-01), and AFOSR (FA9550-14-1-0087). Peter Dusica Joksimovic, Michiel C.J. Bliemer, and Piet H.L. Bovy. Stone serves on the Board of Directors of, Cogitai, Inc. The Optimal toll design problem in dynamic traffic networks terms of this arrangement have been reviewed and approved with joint route and departure time choice. Transportation by the University of Texas at Austin in accordance with its Research Record: Journal of the Transportation Research policy on objectivity in research. The authors would also like Board, 1923(1):61–72, 2005. to acknowledge the support of the Data-Supported Trans- William Karush. Minima of functions of several variables portation Operations & Planning Center and the National Sci- with inequalities as side constraints. PhD thesis, Masters ence Foundation under Grant No. 1254921. thesis, Dept. of Mathematics, Univ. of Chicago, 1939. References H. W. Kuhn and A. W. Tucker. Nonlinear programming. In Proceedings of the Second Berkeley Symposium on Mathe- M. J. Beckmann, C. B. McGuire, and C. B. Winston. Studies matical Statistics and Probability, pages 481–492, Berke- in the Economics of Transportation. Yale University Press, ley, Calif., 1951. University of California Press. New Haven, CT, 1956. Robin Lindsey. Cost recovery from congestion tolls with Stephen D. Boyles, Kara M. Kockelman, and S. Travis stochastic capacity and demand. Journal of Urban Eco- Waller. Congestion pricing under operational, supply-side nomics, 66(1):16–24, 2009. uncertainty. Transportation Research Part C, 18(4):519– 535, 2010. T. Nagae and T. Akamatsu. Dynamic revenue management of a toll road project under transportation demand uncertainty. Dietrich Braess. Über ein Paradoxon aus der Verkehrspla- Networks and Spatial Economics, 6:345–357, 2006. nung. Unternehmensforschung, 12:258–268, 1969. M. Patriksson. The Traffic Assignment Problem — Models Anthony Chen and Kitti Subprasom. Analysis of regulation and Methods. VSP, Utrecht, Netherlands, 1994. and policy of private toll roads in a build-operate-transfer scheme under demand uncertainty. Transportation Re- Arthur C. Pigou. The Economics of Welfare. Macmillan and search Part A, 41(6):537–558, 2007. Co., London, 1920. Andr’e de Palma and Robin Lindsey. Information and usage John G. Wardrop. Some theoretical aspects of road traffic of congestible facilities under different pricing regimes. research. Proceedings of the Institution of Civil Engineers, Canadian Journal of Economics, 31(3):666–692, 1998. Part II, 1:352–362, 1952. Robert B. Dial. A path-based user-equilibrium traffic assign- Byung-Wook Wie and Roger L. Tobin. Dynamic congestion ment algorithm that obviates path storage and enumeration. pricing models for general traffic networks. Transportation Transportation Research Part B, 40(10):917–936, 2006. Research Part B: Methodological, 32(5):313 – 327, 1998. Hai Yang, Qiang Meng, and Der-Horng Lee. Trial-and-error implementation of marginal-cost pricing on networks in the absence of demand functions. Transportation Research Part B: Methodological, 38(6):477 – 493, 2004. Hai Yang. Evaluating the benefits of a combined route guid- ance and road pricing system in a traffic network with re- current congestion. Transportation, 26:299–322, 1999. Hai Yang. System optimum, stochastic user equilibrium, and optimal link tolls. Transportation Science, 33(4):354–360, 1999. Y. Yin and Y. Lou. Dynamic tolling strategies for managed lanes. Journal of Transportation Engineering, 135(2):45– 52, 2009.