Turn Costs in Energy-Optimal Route Planning for Electric Vehicles

The problem of finding energy-optimal routes for electric vehicles through a road network has recently gained interest. In the network, recuperation and consumption with respect to battery limitations is represented by non-static edge costs, which are computed considering energy loss and height differences between vertices, in previous work. The problem gives rise to the wish to consider costs on the basis of kinetic energy differences.

These costs differ for different pairs of edges, i.e. different turns, which is why they cannot be simply attached to edges of the road network. Common ways to incorporate turn costs are presented and judged in the first chapter. The growth in complexity compared to simple, edge-weighted graphs is bounded by the average degree of vertices.

When modeling changes in velocity in a turn or over a segment, the need to check the battery level multiple times arises which complicates the computation of costs. By considering the continuous, physical perspective of energy consumption, we observe that it suffices to check the battery level at certain spots. Namely, at local extrema of the energy consumption function. On the premise, that extrema are easily determined, the problem will be restated as having for every edge a sequence of intervals, in which the consumption function is monotone. In between two weightings, the battery constraint is applied. The results on turn costs and continuous energy costs will be used to give a modified Dijkstra solving the problem of turn costs and continuous weightings. If energy consumption in an interval is computable in constant time and the intervals per edge are known or easily computable,the length of weighting sequences, the average degree of vertices, and the size of the road network give an upper bound on the runtime complexity of the algorithm.