Energy-optimal routes for electric vehicles

We study the problem of electric vehicle route planning, where an important aspect is computing paths that minimize energy consumption. Thereby, any method must cope with specific properties, such as recuperation, battery constraints (over- and under-charging), and frequently changing cost functions (e. g., due to weather conditions). This work presents a practical algorithm that quickly computes energy-optimal routes for networks of continental scale. Exploiting multi-level overlay graphs [25, 30], we extend the Customizable Route Planning approach [7] to our scenario in a sound manner. This includes the efficient computation of profile queries and the adaption of bidirectional search to battery constraints. Our experimental study uses detailed consumption data measured from a production vehicle (Peugeot iOn). It reveals for the network of Europe that a new cost function can be incorporated in about five seconds, after which we answer random queries within 0.3 ms on average. Additional evaluation on an artificial but realistic [21, 35] vehicle model with unlimited range demonstrates the excellent scalability of our algorithm: Even for long-range queries across Europe it achieves query times below 5 ms on average---fast enough for interactive applications. Altogether, our algorithm exhibits faster query times than previous approaches, while improving (metric-dependent) preprocessing time by three orders of magnitude.