We reconsider the concept of transit nodes as introduced by Bast et al. [3] and for the first time construct instance based lower bounds on the size of transit node sets by interpreting a LP formulation of the problem and its dual. As a side product we achieve considerably smaller access node sets which directly influences the query time for non-local queries.

When heading back home from work there are often things to do on the way like grocery shopping, getting cash from an ATM, refueling at a gas station, or dropping off a parcel at a post-office. We consider the problem of planning an optimal route (quickest or shortest) that visits facilities of the respective type on the way home. The proposed solution based on the combination of a distance sensitive doubling technique and contraction hierarchies is orders of magnitudes faster than either a naive approach or previous results and produces the answers in an instant for realistic queries without compromising guaranteed optimality. With such fast query times, this type of route query becomes feasible even on mobile devices or for high-throughput web-based route planners.

We consider the problem of routing electric vehicles (EV) in the most energy-efficient way within a road network taking into account both their limited energy supply as well as their ability to recuperate energy. Employing a classical result by Johnson and an observation about Dijkstra under non-constant edge costs we obtain O(n log n +m) query time after a O(nm) preprocessing phase for any road network graph whose edge costs represent energy consumption or recuperation.If the energy recuperation is height induced in a very natural way,the preprocessing phase can even be omitted. We then adapt a technique for speeding-up (unconstrained) shortest path queries to our scenario to achieve a speed-up of another factor of around 20. Our results drastically improve upon the recent results in (Artmeier et al. 2010) and allow for route planning of EVs in an instant even on large networks.

We consider the following two problems: Map Matching: Given a sequence of (imprecise) location measurements from a mobile user moving on a road network, determine the most likely path in the network this user has travelled along. Prediction of Trajectories: Given the path of where a mobile user has moved along in a road network up to now, predict where he will travel along in the near future. Our map matching algorithm is simple and efficient even in case of very imprecise measurements like GSM-localizations and allows for the real-time tracking of a large number of mobile users on modest hardware. Our proposed path prediction algorithm is equally simple but yields extremely accurate predictions at a very low computational cost.