Nannicini, Giacomo (2009) Point-to-point shortest paths on dynamic time-dependent road networks. PhD thesis, Laboratoire d'Informatique de l'X, EP/X p.189.

Full text available as: - final-thesis.pdf ( 1749 Kb )

Licence: Copyright

Abstract

The computation of point-to-point shortest paths on time-dependent

road networks has many practical applications which are interesting

from an industrial point of view. Typically, users are interested in

the path leading to their destination which has the smallest travel

time among all possible paths; it is natural to model the shortest

paths problem on a time-dependent graph, where the arc weights are

travel times that depend on the time of day at which the arc is

traversed. We study both fully combinatorial methods and mathematical

formulation based methods. From a combinatorial point of view, if we

impose some restrictions on the arc weights, the problem can be solved

in polynomial time with the well known Dijkstra's algorithm. However,

applying Dijkstra's algorithm on a graph with several millions of

vertices and arcs, such as a continental road network, may require

several seconds of CPU time. This is not acceptable for real-time

industrial applications; therefore, the need for speedup techniques

arises. Bidirectional search is a standard technique to speed up

computations on static (i.e. non time-dependent) graphs; however, as

the arrival time at the destination is unknown, the cost of

time-dependent arcs around the target node cannot be evaluated, thus

bidirectional search cannot be directly applied on time-dependent

networks. We propose an algorithm based on an asymmetric bidirectional

search, which allows the extension to the time-dependent case of

hierarchical speedup techniques, well known for static graphs. Our

method deals efficiently with dynamic scenarios where arcs weights can

change, so that we can take into account real-time and forecast

traffic information as soon as it becomes available. We achieve

average query times for time-dependent shortest paths

computations that were previously only possible on dynamic graphs with

static arc costs. We discuss the integration of our algorithm

with an existing real-world industrial application.

For general arc weight functions, the problem is not polynomially

solvable; we propose a mathematical programming formulation which is a

Mixed-Integer Linear Program (MILP) if the time-dependent arc weights

are linear or piecewise linear functions, whereas it is a

Mixed-Integer Nonlinear Program (MINLP) if the arc weights are

nonlinear functions. We study efficient algorithms for both classes of

problems, and test them on benchmark instances taken from the

literature, as well as shortest paths instances. We propose new

branching strategies within the context of a Branch-and-Bound

algorithm for MILPs. Computational experiments show that, by

generating good branching decisions, we enumerate on average half the

nodes enumerated by traditional strategies. Our approach is also

competitive in terms of total computational time. Finally, we present

a general-purpose heuristic for MINLPs based on Variable Neighbourhood

Search, Local Branching, Sequential Quadratic Programming and

Branch-and-Bound. Experiments show the reliability of our heuristic

with respect to methods proposed in the literature.

Statistiques de consultation

Repository Staff Only: edit this item