  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.
