Quick and energy-efficient routes : computing constrained shortest paths for electric vehicles

Abstract

In this paper we study multi-criteria routing problems related to Electric Vehicles (EVs). Because EVs still suffer from a rather small cruising range restricted by the battery's capacity, and loading stations are sparse and reloading is time intensive, previous work focused on computing the most energy-efficient routes efficiently. Unfortunately these approaches do not guarantee anything in terms of distance or travel time. But even a very eco-friendly driver might not be willing to accept a tour three times as long as the quickest one to save some energy. Therefore we present new types of queries considering energy-consumption and distance or travel time and reloading effort, e.g. computing the shortest or quickest path on which the EV does not run out of energy while requiring at most k recharging events (with k being an input parameter). The respective optimization problems are instances of the constrained shortest path problem, which is NP-hard. Nevertheless we will provide preprocessing techniques that allow for fast query answering even in large street graphs.