Time-Optimal Route Planning for Non-linear Recharging Electric Vehicles on Road Networks
摘要
With the rise of green energy and technology, electric vehicles (EVs) are becoming a popular mode of transportation. In this paper, we investigate the route planning problem for EVs, considering factors such as driving range limits, charging station locations, and electricity levels. Unlike fuel vehicles, EV recharging exhibits significant non-linearity: it is faster at low electricity levels and slows at higher levels, requiring careful planning. To solve these challenges, we propose an efficient label assignment algorithm to construct a charging network, leveraging fast-charging capabilities. Additionally, an approximate method accelerates query processing. Experiments on real road networks show our algorithm achieves speeds 2–3 orders of magnitude faster than the baseline.