On January 21, 2014, one of my PhD students, Derya Sever, will defend her thesis:
Routing in Stochastic Networks (see here for the full version, available after 22/1/2014)
This thesis considers an interesting and challenging problem on developing routing policies at an operational level under stochastic and dynamic network conditions where travel times and/or demands fluctuate due random events, such as accidents, etc. It is exactly this kind of information, policies and algorithms which have the potential to strengthen the current generation of car navigation, like e.g. TomTom.
Dynamic routing models capture real-life dynamics more realistically. According to recent studies, dynamic decision making by considering uncertainty and real-time information lead to significant cost savings (up to 47% cost savings when compared to the routing decisions without real-time information). However, these savings are at the expense of computational complexity as the routing problem becomes combinatorial. A good routing algorithm should be accurate, fast, simple to implement and flexible enough to adapt to real life situations. Also, for practical purposes, we need fast and simple dynamic routing algorithms that provide the travelers with high-quality routing decisions.
In this thesis, balancing the trade-off between computational time and solution quality is of particular importance because fast, simple and accurate routing decisions prevent travelers wasting time for retrieving decisions with lower transportation costs and higher customer service levels for transportation companies.
In the thesis, the dynamic routing problems are modelled using an Markov Decision Process and are solved using a Dynamic Program. Sever considers dynamic travel times due to disruptions in the network and analyses in details the value of information in shortest path problems. She develops efficient stochastic lookahead strategies (with and without spill back effects, link correlations in traffic disruptions, etc.) to handle the problem. Considering stochastic and dynamically revealed demand is a last element she focuses on.
Categories: Mathematical models, Planning, Shortest Paths
Homepage of Tom Van Woensel 