Sensible edge weight rounding for realistic path planning

Abstract

Real-world route planning problems are conventionally modeled as weighted graphs - either as grid graphs for open spaces or as path/road networks. The edge weights (e.g. Euclidean distances, travel times or energy consumption) are then derived from measurements or estimations. But the resulting weights are often overly precise and demand a lot of space to be stored. In addition, operations on these weights are computationally expensive. The common approach to avoid those problems is to round edge weights to reasonable precisions (e.g. whole meters, seconds or watt). Unfortunately, naive rounding schemes can easily distort the structure of optimal paths in the graph. In this paper, we present a novel rounding framework based on the construction of an overlay graph. We show that a carefully designed overlay graph based on so called contraction hierarchies can accelerate shortest path computations and minimize rounding errors at the same time, while demanding little space on its own.