# Colloquium of the Department and the PhD Program

## title

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

## speaker

## 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.