contents

|
|
Algorithms for Optimal Route Guidance
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.
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.
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
-
PDF (0.4 MB),
Postscript (2.5 MB), or
gzipped Postscript (0.3 MB).
-
PDF (0.4 MB),
Postscript (1.5 MB), or
gzipped Postscript (0.3 MB).
-
PDF (0.4 MB),
Postscript (2.5 MB), or
gzipped Postscript (0.5 MB).
|