Invited Session Wed.1.H 0111

Wednesday, 10:30 - 12:00 h, Room: H 0111

Cluster 13: Logistics, traffic, and transportation [...]

Stochastic routing


Chair: Pieter Audenaert



Wednesday, 10:30 - 10:55 h, Room: H 0111, Talk 1

Sofie Demeyer
Time-dependent stochastic routing: A practical implementation

Coauthors: Pieter Audenaert, Mario Pickavet


By tracking cell phones and GPS systems on road networks, vast amounts of accurate travel time data can be collected. From this data we can derive time-dependent travel time probability distributions for each of the roads and by making use of these distributions, the travel time distribution of whole routes can be calculated. Here, we present a case study of an industrial-strength time-dependent and stochastic routing system, with the main focus on its practical implementation. Distributions are represented by a number of percentiles, since we use actual measured data and we do not want to impose a single common probability distribution. As determining the exact correlations between each pair of links is quite cumbersome, two extreme cases were investigated, namely assuming that all links are completely correlated and assuming they are not. A stochastic routing algorithm was developed that determines the travel time distribution in both cases. Experiments show that the resulting routes indeed are faster than those in a deterministic routing system. It should be noted that results of this work are deployed by the industrial partners involved in this research.



Wednesday, 11:00 - 11:25 h, Room: H 0111, Talk 2

Moritz Kobitzsch
Alternative routes and route corridors


We present an overview over two static route planning techniques, alternative routes and corridor graphs, and discuss how to compute them efficiently. An alternative route is considered a valid alternative to a shortest path, whenever it fulfils three simple criteria: local optimality, limited overlap, limited stretch. The second technique, corridor graphs, is a method to iteratively grow a subgraph around an initial set of paths to a single target. This technique bases on allowing deviations along the route and can account for minor detours. We expect a combination of these techniques to manifest itself in an immense reduction of the input size for
stochastic route planning.



Wednesday, 11:30 - 11:55 h, Room: H 0111, Talk 3

Sebastien Blandin
Fast computation of solution to stochastic on-time arrival problem

Coauthors: Alexandre Bayen, Samitha Samaranayake


We consider the stochastic on-time arrival (SOTA) problem which consists in finding a policy that maximizes the probability of reaching a destination within a given budget. We propose novel algorithmic methods for the fast computation of its solution in general graphs with stochastic and strictly positive minimal network-wide edge weights, with application to transportation networks in particular. Our first contribution is based on the proof of existence of an optimal order for minimizing the computation time of the optimal policy for the SOTA problem in a dynamic programming framework. The second contribution of this work is based on the integration of a zero-delay convolution method, which allows for further reduction of the algorithm complexity by a factor log n /n. We illustrate the comparative run-times of the different algorithms on selected synthetic networks and on actual road networks from Northern California, using real travel-time estimates from the Mobile Millennium traffic information system.


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Buy Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.