## Fall 2014: Theory Seminar

Donald Bren Hall, Room 1425, 1:00pm

October 24, 2014:

#
Two-Phase Bicriterion Search for Finding Fast and Efficient Electric
Vehicle Routes

##
Michael T. Goodrich

The problem of finding an electric vehicle route that optimizes both
driving time and energy consumption can be modeled as a bicriterion
path problem. Unfortunately, the problem of finding optimal bicriterion
paths is NP-complete. This paper studies such problems restricted to
two-phase paths, which correspond to a common way people drive electric
vehicles, where a driver uses one driving style (say, minimizing
driving time) at the beginning of a route and another driving style
(say, minimizing energy consumption) at the end. We provide efficient
polynomial-time algorithms for finding optimal two-phase paths in
bicriterion networks, and we empirically verify the effectiveness of
these algorithms for finding good electric vehicle driving routes in
the road networks of various U.S. states. In addition, we show how to
incorporate charging stations into these algorithms, in spite of the
computational challenges introduced by the negative energy consumption
of such network vertices.

(Joint work with Paweł Pszona, to appear at ACM SIGSPATIAL 2014.)