[Chair]  [Computer Science Department (FBI)]  [University Dortmund] 

Project Group Application


Intermediate Report

Final Report


Route-Planning Group

Map-Generation Group

Simulation Group


GPS-ROUTE: A Domain-Independent Trajectory Planner

Route planning is one of the most important application areas of computer science in general and graph search in particular. Current technology like hand-held computers, car navigation and GPS positioning systems ask for a suitable combination of mobile computing and course selection for moving objects, but
  1. most maps come on external storage devices and are by far larger than main memory capacity. This is especially true for on-board and hand-held computer systems.
  2. most available digital maps are expensive, since exhibiting and processing road information e.g. by surveying methods or by digitizing satellite images is very costly.
  3. maps are likely to be inaccurate and to contain systematic errors in the input sources or inference procedures.
  4. it is costly to keep map information up-to-date, since road geometry continuously changes over time.
  5. maps only contain information on road classes and travel distances, which is often not sufficient to infer travel time. In rush hours or on bank holidays, the time needed for driving deviates significantly from the one assuming usual travel speed.
  6. in some regions of the world digital maps are not available at all.
Therefore, we develop a domain-independent route planning system that takes a set of traces as an input precomputes an according graph structure and quickly answers different on-line queries.


Stefan Edelkamp

GPS-Route is being developed by Stefan Edlekamp and Shahid Jabbar and by PG 452.
Thanks to Thomas Willhalm for code that improve shortest path queries on geometric domains

This project group activity is not connected to Peter Roosen's tour planner to GPS routes converted, also named GPS-Route.