Date/Time
Date(s) - 21/09/2017
10:00 am - 11:00 am
Categories
Title: Personalized Route Planning: Deducing Driving Preferences and Fast Querying
Abstract:
We study the problem of learning individual route preferences of drivers. Most current route planning services only compute shortest or quickest paths. But many other criteria might play a role for a user to prefer a certain route, as, e.g., fuel consumption, jam likeliness, road conditions, scenicness of the route, turns, allowed maximum speeds, toll costs and many more. Specifying the importance of each criterion manually is a non-trivial, unintuitive and time consuming undertaking for a user. Therefore, we develop approaches that deduce such preferences automatically based on paths previously driven by the user. We present an LP-formulation of the problem making use of a Dijkstra-based separation oracle.
The resulting algorithm runs in polynomial time and allows for the user preference computation in few seconds even if several hundred routes are taken into account. As a side product, the same LP-formulation also allows for the elegant construction of multicriteria Contraction Hierarchies.
Biography:
Stefan earned his Ph.D. in Computer Science at the Max-Planck-Institut f. Informatik and the University of the Saarland in 2001. During his PostDoc years in Saarbruecken and Urbana-Champaign he was a Visiting Assistant Professor at Stanford University in 2004/5 before becoming a professor at the University of Greifswald in 2007. Since 2010 he holds the chair for Algorithmics at the University of Stuttgart. His research interests range from problems in computational geometry and discrete optimization to algorithms in general. He has been recepient of best paper awards or honorable mentions at VLDB 2014, AAAI 2014, SIGSPATIAL GIS 2011, ACM SPM 2005, and awardee of the Otto-Hahn-Medal and the Heinz-Billing-Award of the Max-Planck-Society, as well as two Google Research Awards.
