UC Riverside

Electric Vehicle (EV) route planning is an important but hard problem, since battery capacity is limited, charging times are long, and charging stations are sparsely distributed. It is nonetheless critical to improving the time and energy efficiency of future transportation systems, and to promoting EV adoption, by reducing driver range anxiety. EV routing is usually modeled as a Shortest Feasible Path (SFP) problem, which ensures a non-negative State of Charge along the route, taking both travel time and energy consumption to be deterministic and known in advance. In practice, however, travel time and energy consumption are both stochastic variables, which can be hard to estimate accurately.

This dissertation presents a set of techniques to advance our abilities to address such stochasticity. First, we show how to accurately predict energy consumption and travel times along routes using phases, a new structuring abstraction for vehicle speed profiles. Contrary to conventional wisdom, using phases outperforms even microscopic energy estimation models. We show that using phases to generate synthetic trips preserves the real-world variance in travel times and energy consumptions of real-world trips.

Next, we show how to efficiently encapsulate the tradeoffs between travel times and robustness of feasible routes against deviations in energy consumptions using the Starting Charge Map and Buffer Map constructs. Further, we generalize the SFP problem to permit stochastic travel times and energy consumptions using two different probabilistic definitions of route feasibility. These definitions allow drivers to maintain route feasibility either in expectation, or by setting explicit lower bounds on stranding probability.

We also study how to effectively apply well-known speedup techniques, such as Contraction and Edge Hierarchies, for route planning with stochastic edge weights. We show that the choice of weight representations has a significant impact on the routing query runtimes, and introduce the tiering technique, which significantly improves query times for three different stochastic routing objectives. We evaluate all presented methods on realistic routing instances.

Lastly, we generalize the problem of identifying dwell regions for trajectory sets to that of finding shared dwell regions, and present two novel approaches to the problem. We show that our solutions outperform the state-of-the-art by nearly a factor of three.