Solving Road Congestion Problems with Algorithms?

State-of-the-art in-car navigation systems contribute to preventing road congestion, because avoiding traffic jams helps dissolving it. Currently, the more advanced systems already are using both historic travel times as well as recently observed travel times to estimate future travel times for road segments, and base their route navigation advice upon these estimates. However, in our publication on Intention-Aware Routing of Electric Vehicles, we show that estimated travel times can be made even more accurate by also including the navigation advice for other vehicles, even though this may be dependent on later traffic conditions.

The published article shows the effect of exchanging such information on the combined travel and charging time of Electric Vehicles (EVs). The driving range of EVs depends on their installed battery capacity, which is limited because batteries are large, heavy, and costly. Consequently, for longer drives they need to recharge, in a way similar to the refueling of fossil-fuel-based vehicles. Very different, however, is the time it typically takes for such a refill: for EVs this can typically take 30 minutes, even on the fastest charger available. This is a problem in particular when the capacity at recharging stations is limited: if a driver arrives at a charging station (with an almost empty battery) and has to wait for another car to be charged first, this has a detrimental effect on the total travel time. Apart from the solution to design such charging stations for peak capacity requirements, solutions have been proposed to better coordinate the time and location where vehicles charge.

For example, a charging station could offer a reservation system where drivers can book a charging slot in advance as soon as they know at what time they will arrive at the station. Systems like these have been around for many years in other domains, e.g., for administration purposes at governmental front desks, restaurants, etc.. However, this system leads to significant inefficiencies when arrival conditions are uncertain. In particular this holds for travel times, since these may be very uncertain especially around peak times when such reservations matter. Reserving a larger time window introduces extra (lost opportunity) costs on the side of the charging station, or booking a later slot introduces extra costs on the side of the driver.

The solution proposed and evaluated in our research is a cooperative one, where all drivers share and coordinate their charging plans among themselves (conditional on encountered delays). We show which algorithmic solution can be used to combine stochastic information based on historic travel information with stochastic plans (policies) for routing and charging, and how this can be used for coordinating these policies. We show that this results in significantly reduced total travel times. If now only cars could use this system to coordinate road usage…

See also this fun video presentation on our work made by Sebastian Stein.

• 
•