Coordinated Routing

In Kooperation mit TomTom

Bei Rückfragen zum Thema wenden Sie sich bitte an Prof. Dr. Natalia Kliewer

When drivers all choose their routes independently, this might lead to a suboptimal utilization of the road network – some roads can end up congested, while other are hardly used. Coordinated Routing refers to the idea to align route planning for multiple drivers such that the road network is used more efficiently.

Coordinated Routing is a popular research topic in Algorithmic Game Theory (AGT). Here, it is typically assumed that users have access to full information on the state of the network, such that in the absence of coordination, routes chosen individually by users form a Nash Equilibrium (NE), a state where no user can attain a better (i.e., faster) route by changing his route unilaterally. Under reasonable assumptions on travel time functions and network topology, it can be shown that in NE, users with the same origin and destination will always incur the same travel time.

The optimal set of routes for all users, i.e. the set of routes that minimizes the sum of all travel times, is commonly referred to as the System Optimum (SO). It can be shown that, again under reasonable assumptions on travel time functions and network topology, that the SO is in general superior to NE in terms of sum of all travel times. In certain cases, the ratio between NE and SO can even be unbounded, i.e. the NE can be infinitely less efficient than the SO. In AGT, the worst case ratio between NE and SO is called the Price of Anarchy (PoA), and the best case is called the Price of Stability (PoS).

AGT also proposes models where users form coalitions, and each coalition attempts to optimize the sum of travel times for all of its users. It has been shown that in these models, coalitions can have an adverse effect on system performance, and the worst case ratio between the NE of coalitions and the SO is called the Price of Collusion (PoC).

All the results on PoA, PoS, and PoC cited above heavily rely on the assumption that users form a NE when uncoordinated. However, this is hardly the case for car traffic in the real world, where users typically do not have full information on travel times in the road network around them. So while many roads in our cities get heavily congested during rush hours, drivers with very good local knowledge can usually find faster routes which avoid the worst traffic jams rather easily. And with the advent of navigation systems that receive detailed real-time traffic information, this opportunity to find better routes through traffic potentially becomes available to anyone. Moreover, the idea to routinely coordinate routes for many users is becoming more and more realistic today, where cars and mobile devices are becoming increasingly connected. This leads to the following research questions:

  • How can we expect traffic to change when more and more users have access to and make use of accurate real-time traffic information?
  • What would be the effect of introducing coordinated routing, and what could be a realistic and sensible coordination strategy?

Micro-simulation shall be used to model users with access to different kinds of technology and information travelling on the road network.

icon3_department_wirtschaftsinformatik
Visit www.or2017.de ...