Computing shortest paths is one of the most researched topics in algorithm engineering. Currently available algorithms compute shortest paths in mere fractions of a second on continental sized road networks. In the presence of unreliability, however, current algorithms fail to achieve results as impressive as for the static setting. In contrast to speed-up techniques for static route planning, current implementations for the stochastic on-time arrival problem require the computationally expensive step of solving convolution products. Running times can reach hours when considering large scale networks. We present a novel approach to reduce this immense computational effort of stochastic routing based on existing techniques for alternative routes. In an extensive experimental study, we show that the process of stochastic route planning can be speed-up immensely, without sacrificing much in terms of accuracy.

Electric Vehicle routing is often modeled as a Shortest Feasible Path Problem (SFPP), which minimizes total travel time while maintaining a non-zero State of Charge (SoC) along the route. However, the problem assumes perfect information about energy consumption and charging stations, which are difficult to even estimate in practice. Further, drivers might have varying risk tolerances for different trips. To overcome these limitations, we propose two generalizations to the SFPP; they compute the shortest feasible path for any initial SoC and, respectively, for every possible minimum SoC threshold. We present algorithmic solutions for each problem, and provide two constructs: Starting Charge Maps and Buffer Maps, which represent the tradeoffs between robustness of feasible routes and their travel times. The two constructs are useful in many ways, including presenting alternate routes or providing charging prompts to users. We evaluate the performance of our algorithms on realistic input instances.

Stochastic route planning is a hard problem, since it deals with uncertain edge weights, usually modeled as probability distributions. Stochastic shortest path queries are very expensive, as they must compute convolutions of edge weight distributions, whose representations can have a major impact on query costs. Effective speedup techniques for shortest path queries exist for deterministic edge weights, but their extensions to stochastic settings have had limited success, and real-time stochastic routing queries remain beyond reach. We introduce the tiering technique for Contraction and Edge Hierarchies (CHs and EHs) to address this challenge. We divide the hierarchy into tiers, and represent edge weights in each tier in ways that permit effective tradeoffs between accuracy, convolution costs, and space use. We show how to use Gaussians to approximate histograms, and bound errors using the KL divergence and Hellinger distance measures. We develop Uncertain Contraction Hierarchies (UCHs) and Uncertain Edge Hierarchies (UEHs) using these methods, and show that they improve both CH and EH performance for three different stochastic query types: probabilistic budget routes, non-dominated routes, and routes to minimize the mean-risk objective. We evaluate our methods using real-world data from Mapbox Traffic Data for a section of Los Angeles. Finally, our results show that query times for EHs can be competitive with CHs for stochastic edge weights, contrary to current belief.

Electric Vehicle (EV) battery capacity is limited, so EV routing must trade off travel time for energy consumption, which grows quad-ratically with speed. Current multi-parameter EV routing methods assume accurate estimates of time and energy consumed, but current models for obtaining these estimates cannot capture this time-energy tradeoff in a sufficiently flexible way. We present a new approach to EV modeling that addresses such shortcomings. Conventional wisdom holds that models operating at finer time granularities yield better energy consumption estimates. We first show that such is not necessarily the case, by defining a new structuring abstraction for vehicle speed profiles called phases, which models energy consumption accurately at lower temporal granularity. We also address the challenge of generating speed profiles for planned trips with realistic variance in travel times and energy consumed. Our method combines the phase abstraction with Markov chains and kernel density estimation to learn these variations, and construct realistic vehicle speed profiles for real-world routes. Using 52 hours of driving data collected on a Nissan Leaf, we show that our model achieves a per-trip accuracy better than even that of current microscopic models and generates speed proiles that accurately model time and energy consumption at the trip level.