members & address research industrial partners teaching publications gallery home page of the group
    clickable logo

Combinatorial Optimization & Graph Algorithms

TU logo

contents
.

department
 .  group
 .  .  members & address
 .  .  research
 .  .  .  traffic
 .  .  .  .  path-based flows
 .  .  .  . route guidance
 .  .  publications
 .  .  cooperation with industry
 .  .  teaching
 .  .  project gallery
 .  .  events
 .  .  internals
 .  .  search

Algorithms for Optimal Route Guidance

Participants: Georg Baier,
Ekkehard Köhler,
Katharina Lankau,
Rolf H. Möhring,
Supported by: Bundesministerium für Bildung und Forschung
DaimlerChrysler, Berlin

Project description:
Have you been in a traffic jam lately? Studies show that this could happen much more often in the near future! Both individual traffic and commercial traffic will increase dramatically in the next couple of years. To cope with the problems that are brought about by the much higher volume of traffic, more and more vehicles will get equipped with so-called route guidance systems. They guide the driver by visual and acoustic indicators to the destination, which has been entered at the beginning of a trip.

Normally these systems compute their routes based on digital maps, the current positions obtained by Global Positioning System (GPS), and possibly up-to-date traffic data, which have been broadcast by radio or cellular phone. A number of surveys and simulations show that route guidance systems indeed decrease the overall journey time (the sum of all journey times, which can be viewed as a measure for general road usage), since inefficiencies caused by human route choice are mostly eliminated. Unfortunately, many simulations also predict that these benefits will be lost once the number of equipped vehicles exceeds a certain threshold. This is due to the ``naive'' algorithms used in current systems. These algorithms have the fundamental drawback that they do not take into account the effect of their own route recommendation. Thus, a widely used route guidance system can cause congestion all by itself if it guides many vehicles over the same road, perhaps in an attempt to avoid another congested road which --- after all --- should have been preferred. This is due to the fact that the perceivable decrease of the overall journey time under a low percentage of equipped vehicles is merely a fortunate byproduct of the system since current algorithms try to minimize the individual journey time of each driver separately. Hence methods minimizing the overall journey time need to be developped. However, when designing practically usable algorithms for this approach there are various problems to be solved.

One problem that arises when minimizing total travel time is that a minority of drivers might be sent along very long paths to allow the majority of drivers to use shorter, better paths. As routes can only be suggested to drivers, most people would actually refrain from using such a route guidance system in order to avoid being misguided onto long paths.

route example

Minimum duration routes between two nodes without geographic length constraints (left image) and with length contraints (right image). Due to road capacities the traffic is split over several paths.

To cope with this aspect of driver behavior we have introduced new additional constraints to the model. These constraints guarantee that the length of a recommended route is acceptable in the sense that it is not too far away from the shortest distance. The modification causes our route guidance problem to become NP--hard even in the simpler case of constant road travel times. Naturally, the case where arc travel times depend non-linearly on the amount of traffic flow is even harder.

In the course of our cooperation with DaimlerChrysler we have implemented algorithms for the static route guidance problem, both for the linear and non-linear case, which perform very well on real world data. These methods combine several techniques from linear and non-linear programming, as well as from combinatorial optimization. For computational speed-up the algorithms can be run in parallel on several workstations using the PVM library.

route example        route example

Screenshots of our implementation; left a solution represented by paths, right by means of road usage.

Unlike many previous approaches in this field, our algorithms do not use a simple feedback loop to incorporate the effects of the own route recommendation. Instead the feedback property is genuinely embedded into the minimization problem, which is then solved using appropriate methods. See Report 658/1999 for more information.

A subprocedure that is frequently used by all our optimization algorithms is finding a shortest path in a graph. Of course, this problem is easily solvable in polynomial time; however, since we work on very large networks and need to call this subroutine quite often, it is important to have shortest path algorithms that are also practically efficient. Therefore a main focus of the project is to study different acceleration methods for shortest path algorithms and evaluate their relevance for our instances (see Report 624/1999).

In the current model traffic is considered as static flow. This approach is quite realistic for various traffic situations, as for example rush-hour traffic in cities. However, the final goal is a purely dynamic model for traffic, where individual cars or pulks of cars travel through the network with progressing time. A major obstacle in designing a realistic dynamic model is the difficult behavior of the arc travel times, which depend on the amount of traffic on the arc at each point of time. For this reason formulating a model built on the time-expanded graph (a standard method in dealing with dynamic flows for constant arc travel times) is not easily achieved. Developing a dynamic model that allows for efficient optimization on real world data is a main topic in this project.

German-language posters about this project
  1. PDF (0.4 MB), Postscript (2.5 MB), or gzipped Postscript (0.3 MB).
  2. PDF (0.4 MB), Postscript (1.5 MB), or gzipped Postscript (0.3 MB).
  3. PDF (0.4 MB), Postscript (2.5 MB), or gzipped Postscript (0.5 MB).
top top
source last modified: Fri Oct 31 2003, last built: Fri Aug 20 2004
Andreas Fest <fest@math.tu-berlin.de>
Validate HTML