Map Partitioning

In Kooperation mit TomTom

Rückfragen zum Thema: Natalia.Kliewer@fu-berlin.de

 

Many speedup techniques for route (a.k.a. shortest path) computation rely on a good partition of the underlying map (a.k.a. graph). Examples of such speedup techniques include arc-flag based approaches, and multi-level overlay techniques such as customizable route planning. Popular partitioning algorithms and tools include METIS (Serial Graph Partitioning and Fill-reducing Matrix Ordering), PUNCH (Partitioning Using Natural Cut Heuristics), and SCOTCH (Static Mapping, Graph, Mesh and Hypergraph Partitioning). Map partitioning can be implemented as a hierarchical process, and typical objectives include

  • minimizing the number of edges crossing the partition,
  • balancing the node count in the different elements of the partition.
  • homogeneous shape of the elements in the partition (rather squares than “bananas”)

A consortium of car manufacturers, application/compiler developers, map data providers, and service providers, is currently introducing a new format for navigation maps called Navigation Data Standard (NDS). Key feature of NDS include a hierarchical tiling of maps, and a subdivision of the map into so-called update regions.

Ideally, preprocessing of map data to speedup routing should be local to the elements of the map partition defined by NDS tiles. On the other hand, NDS tiles regularly constitute a “bad” partition in terms of the first two objectives stated above. Hence, the elements of a “good” map partition will most likely have to intersect with multiple NDS tiles. If the number of tiles intersected by an element of a map partition is typically small, we can call the partition compatible with the corresponding tiling. This leads to the following research questions:

  • How compatible with NDS tiles can “good” map partitions be?
  • How do existing map partitioning algorithms and tools rank in terms of compatibility with NDS tiles?
  • Can existing map partitioning algorithms be adapted or extended to be compatible with NDS tiles?
icon3_department_wirtschaftsinformatik
Visit www.or2017.de ...