  We study the problem of minimizing overall trip time for battery electric
vehicles in road networks. As battery capacity is limited, stops at charging
stations may be inevitable. Careful route planning is crucial, since charging
stations are scarce and recharging is time-consuming. We extend the Constrained
Shortest Path problem for electric vehicles with realistic models of charging
stops, including varying charging power and battery swapping stations. While
the resulting problem is NP-hard, we propose a combination of algorithmic
techniques to achieve good performance in practice. Extensive experimental
evaluation shows that our approach (CHArge) enables computation of optimal
solutions on realistic inputs, even of continental scale. Finally, we
investigate heuristic variants of CHArge that derive high-quality routes in
well below a second on sensible instances.
