University of Konstanz
Graduiertenkolleg / PhD Program
Computer and Information Science

Colloquium of the Department and the PhD Program

title

Route Planning: Energy-efficient, Constraint-respecting, and fast!

speaker

Prof. Stefan Funke, University of Stuttgart
Stuttgart, Germany

date & place

Wednesday, 20.06.2012, 15:15 h
Room C 252

abstract

While the classical problem of computing shortest paths in a graph is still an area of active research, the growing interest in energy-efficient transportation has created a large number of new and interesting research questions in the context of route planning. How can I find the energy-optimal path from A to B for my electric vehicle (EV)? Where are the best locations for battery switch stations such that I can get anywhere with my EV? What is the shortest path from A to B which does not exceed a total height difference of 200m? For some of these problems we exhibit their inapproximability, for others we present very efficient algorithms.