How economics and machine learning can tackle transportation congestion.

Article written at the occasion of the XRCE 20th anniversary celebration, co-authored by Eduardo Cardenas, Christopher R. Dance, Stéphane Clinchant and Onno Zoeter.

However, as we all know, we do not live in an ideal world. And when we travel from A to B it’s not that simple. It’s you and your car… and a whole lot of other cars.

The aforementioned description is a common case of demand exceeding supply. It results in traffic jams and drivers circling blocks hunting for a vacant parking space. One way to solve this problem is by extending the supply. Governments deliberate and decide whether tax payers’ demand for new roads justifies the spending of tax money to build them. Ever since the introduction of cars, extending supply has been the predominant approach to solving this problem.

Yet demand is ever increasing and constructing new infrastructures is costly in terms of the direct costs of building garages and highways, and the indirect costs of reducing the amount of land available for housing and offices. There also are costs associated with environmental impact. So when infrastructure becomes congested it is worthwhile looking at alternative solutions such as a more efficient use of existing infrastructure commonly referred to as demand management.

Xerox researchers are developing algorithms that lie at the heart of demand management solutions. This article provides an introduction to the goals of demand management and offers a glimpse under the hood of a project to reduce parking congestion in the city of Los Angeles.

Demand management and the economics of transportation

The basic argument for demand management solutions in transportation dates back to at least the middle of the 20th century. Yet, because of technological and political difficulties, its use on the scale of a city has appeared only recently.

William Vickrey (Nobel laureate, 1996) provided a famous hour glass metaphor for traffic jams. In a simplified scenario, commuters start at one end of an hour glass on a road that takes them to the other end. At its narrowest part, this road has a certain maximum capacity which determines the rate of outflow. So when a large number of commuters join the traffic at 8:30 a.m. aiming to arrive at work at 9 a.m., not all of them will succeed. The bottleneck will cause a jam and some cars will have to wait. The outflow will be dictated by the bottleneck.

Let us examine the cars’ arrival times. Some will arrive at 8:45 a.m., some at 8:46 a.m., some at 9 a.m. and others at 9:10 a.m.  The majority of them will have spent a significant time in the traffic jam. Now consider a different world: one where the start time of each car is controlled. Suppose the journey without the jam takes 15 minutes. We would ask the car that arrives at 8:45 a.m. to leave at 8:30 a.m., the car that arrives at 8:46 a.m. to leave at 8:31 a.m. and so on. The result is that all cars arrive at exactly the same time as they did before, but now all of them only spend 15 minutes in free-flow traffic instead of the average of say 30 minutes because of the traffic jam. If you work with a value-of-time saved of $10 an hour, every person in the jam gains $2.50 per day.

The reason that it doesn’t already happen like this is that a majority of commuters would prefer to be in the car that leaves at 8:45 a.m. and arrives at 9 a.m. There also is no formal mechanism for drivers to coordinate their departure times. Vickrey argued that the current dynamics of traffic jams like these are an equilibrium state where people balance the cost of leaving too early and the risk of arriving too late.

The idea of demand management is to help drivers coordinate using time-differentiated tolling e.g., the closer to 8:45 a.m., the higher the toll. This would reduce the jam in the bottle neck in a way that ensures that the drivers who are least inconvenienced by leaving slightly earlier or later (or taking public transport) would be the ones to do so. This is the motivation for congestion charges such as those used in Stockholm and Singapore and the smart toll lanes around Los Angeles and Miami.

To conclude this stylized example: demand management aims at a more efficient use, instead of an expansion of infrastructure. Drivers are encouraged to avoid peak hours so that more cars can pass in free-flow conditions from A to B.

The reasoning is in principle not restricted to highway access but is valid for all publicly-owned utilities. The principles would apply equally well to parking and public transport. The fact that the infrastructure is paid for by public money and in a sense is owned by everybody doesn’t mean that it is put to best use if it is accessible for free.

Analytics and communication

Even though the principles are elegant and could provide a very effective solution to important problems in most people’s daily lives, it is also easy to see why they weren’t implemented directly in the 1950s. First, it is difficult to explain to drivers that they need to start paying directly for a service that was previously paid for by general tax money. The increase in efficiency can be hard to explain and in the original subsidized situation, some users who use the service significantly more than the average tax payer would pay more in a demand based system. These users will be very opposed to any proposed change.

Secondly, it is far from straightforward to predict how many cars will access a particular bottleneck, what the right rates need to be to incentivize drivers to avoid a potential traffic jam, and to notify drivers in a convenient and timely way. This was particularly true given the state of technology in the 1950s. However with today’s real-time sensing capabilities plus smartphone and satellite navigation communication possibilities, the prerequisites for effective solutions are available. Several large-scale projects already are in use. For example, Stockholm has time differentiated tolls to access the city centre; Singapore uses gantries to have time- and location-differentiated tolls, and San Francisco and Los Angeles use on-street parking sensors to let parking rates be guided by demand.

Xerox and demand management for parking

The LA parking solution, LA ExpressPark is implemented by Xerox for the Los Angeles Department of Transportation (LA DOT). The algorithms that harbour the analytics and economic trade-offs are designed by researchers at the Xerox Research Centre Europe in close collaboration with LA officials.

Since May 2013 all on-street parking spaces in downtown LA have been equipped with sensors. This gives real time information if a car is parked in a space or not. The data can be used to guide people to empty spaces using smartphone applications. In addition, machine learning methods can be used to understand and predict demand. In turn, pricing algorithms can use these models to adjust rates to demand.

During the project, algorithms are used to revise rates at roughly three month intervals. The Holy Grail is to iteratively find rates that make sure demand is so well spread out that every side of a block in LA’s grid is nearly always close to being full but has one or two spaces free. That way the spaces see good use and drivers can leave home, make a decision where to park, and are almost guaranteed not to have to circle round to find a free spot.

The project started in June 2012 and, with more than a year’s worth of experience, the detailed impact analysis will commence in 2013. From preliminary results we already know that the rates went down in more places than where they went up and that the average parking rate went down overall. Nevertheless, since the rates increased in very congested areas and decreased in the underutilized areas there is an overall slight increase in revenue. Most importantly, the desired state where blocks were neither underutilized nor congested, increased by 9 per cent.

Outlook

Xerox has a long history of innovations that have taken some of the dread or drudgery out of our daily lives. Consider the need for human copy typists before the invention of the copier or the difficulty of correcting an error in a piece of text written with a typewriter instead of a personal computer.

Advances of analytics in transportation have only just begun, so it remains to be seen if these innovations can have similar effects. But be assured we’re working hard to try to take some of the pain out of the daily commute and regular hunt for a parking space.