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.

We study the problem of graph partitioning for evolving road networks. While the road network of the world is mostly stable, small updates happen on a relatively frequent basis, as can been observed with the OpenStreetMap project (http://www.openstreetmap.org). For various reasons, professional applications demand the graph partition to stay roughly the same over time, and that changes are limited to areas where graph updates occur. In this work, we define the problem, present algorithms to satisfy the stability needs, and evaluate our techniques on continental-sized road networks. Besides the stability gains, we show that, when the changes are low and local, running our novel techniques is an order of magnitude faster than running graph partitioning from scratch.

We study how to compute routes that avoid traffic in road networks. Imperfections in real-time traffic feeds may yield routes with undesirable detours through parking lots or residential areas. The main challenge we address in this work is that of defining and computing paths that incorporate a volatile secondary cost function. We define the problem, study its complexity, and present algorithms that compute routes without undesirable detours. Experiments on continental-sized road networks demonstrate the feasibility of our approach.

A novel algorithm is proposed for the distributed and location-free detection of boundaries in sensor networks. The approach allows a node to decide autonomously, based solely on connectivity information of a small 2-hop neighborhood, whether it is in the interior of the network or on its fringes. This makes the presented algorithm well suited for scenarios that include mobility or dynamic changes to the network topology. The algorithm is compared qualitatively and quantitatively to multiple previous approaches. Various models and network settings are considered in extensive simulations. Even though the algorithm uses less information than most other approaches, it yields significantly better results. It is very robust against variations in node degree and does not rely on simplified assumptions of the communication model. Moreover, the approach is easy to implement on real sensor nodes, as it requires little computational power.

Computing meaningful alternative routes in a road network is a complex problem -- already giving a clear definition of a best alternative seems to be impossible. Still, multiple methods describe how to compute reasonable alternative routes, each according to their own quality criteria. Among these methods, the penalty method has received much less attention than the via-node or plateaux based approaches. A mayor cause for the lack of interest might be the unavailability of an efficient implementation. In this paper, we take a closer look at the penalty method and extend upon its ideas. We provide the first viable implementation --suitable for interactive use-- using dynamic runtime adjustments to perform up to multiple orders of magnitude faster queries than previous implementations. Using our new implementation, we thoroughly evaluate the penalty method for its flaws and benefits.

We present a fast algorithm with preprocessing for computing multiple good alternative routes in road networks. Our approach is based on single via node routing on top of Contraction Hierarchies and achieves superior quality and efficiency compared to previous methods. The algorithm has neglectable memory overhead.

We present a new heuristic point-to-point shortest path algorithm based on contraction hierarchies (CH). Given an epsilon >= 0, we can prove that the length of the path computed by our algorithm is at most (1 + ε) times the length of the optimal (shortest) path. Exact CH is based on node contraction: removing nodes from a network and adding shortcuts to preserve shortest path distances. Our heuristic CH tries to avoid adding shortcuts even when a replacement path is (1+epsilon) times longer. However, we cannot avoid all such shortcuts, as we need to ensure that errors do not stack. Combinations with goal-directed techniques bring further speed-ups.