ActivitiesActivities include A Spatiotemporal Knowledge World and Transportation Networks.
Road networks and more generally transportation networks are an interesting research subject in that they represent the principal dataset for a large range of applications, including GIS, transportation systems, location-based services and Web mapping.
Currently, such datasets are provided by two global players, Navteq and TeleAtlas. More recently, community-driven efforts have begun to challenge commercial efforts, at least for the context of non-critical applications. Openstreetmaps being the most prominent example aims at creating a vector map of the world based on a Wiki approach, i.e., everybody can/should contribute. With a growing user base, this effort has resulting already in a complete coverage of Germany. One of the major costs in map-data generation is keeping the data up-to-date. Community driven efforts elegantly address this problem with its user base and dedicated local interest.
The effort in this project addresses the challenges of evolving map datasets specifically by working towards (i) automatic map-attribute generation (i) automatic map generation, and (iii) algorithms addressing change.
Dynamic Travel Times
With the availability of cheap positioning technology and the
penetration of asset tracking applications such as fleet management
applications, vehicle tracking data, as a component of floating car
data (FCD), becomes an important tool for traffic assessment and
prediction. Floating car data (FCD) refers to using data generated by
one vehicle as a sample to assess to overall traffic conditions ("cork
swimming in the river"). Having large amounts of vehicles collecting
such data for a given spatial area such as a city (e.g., taxis, public
transport, utility vehicles, private vehicles) will create an accurate
picture of the traffic condition in time and space. The whole
motivation for this work and the related research project
TRACK&TRADE it presents
is derived from this fact.
In our work, we developed technology to
- collect FCD from vehicle fleets,
- derive network-related travel times (map-matching),
- provide efficient data manipulation means and
- provide services that utilize these respective datasets.
A critical aspect when using FCD to assess traffic in general and to derive travel times for the road network in particular is the amount of data that needs to be available and consequently the number of vehicle collecting the data. Increasing the vehicle penetration is thus of critical importance and this work provides a flexible, Web-services-based architecture to simplify the connection of new FCD sources.
Map-matching the tracking data produces travel time data related to a specific edge in the road network. Collection of large amounts of tracking data and, thus, travel times produce travel time profiles for a road network. A collection of such historical data can be used to capture trends in travel time behavior according to temporal variations. Based on large amounts of travel time data, edge-based weights in the form of time-varying characteristic travel times are derived. The figure below gives example travel times in minutes for major roads in the metropolitan area of Athens, Greece. With the help of FCD, we will be able to capture these travel time variations in the road network.
To derive travel time profiles from collected travel times (dynamic travel times), efficient data manipulation methods are needed. We advocate the use of a simple data warehouse to aggregate collected travel times and to derive dynamic travel times for the road network, i.e., dynamic impedance in a road network. Such dynamic travel times can be seen in relation to static weights (link-based speed types) that are typically available as map attributes in current road network datasets.
time fluctuations for Athens,
Travel Time Maps
Travel Time Maps illustrate the traffic situation in urban areas by indicating current speeds for road links in a map. Travel times are overlayed with road network data indicating the typical travel time for roads. Categorizing and visualizing these categories results in a simple tool to assess the traffic situation for the overall area and/or specific roads in question. In turn, such a tool can be used as a simple means to verify and create traffic news. A simple coloring schema (green – orange – red) illustrates the traffic condition as derived from comparing current travel times in relation to expected travel times in the road network.
Collected FCD (vehicle tracking data - blue dots) and resulting travel times and traffic conditions
Hierarchical Routing Algorithm
Time is money becomes a very concrete and meaningful state- ment
when considering it in the context of routing and navigation
applications. A quote from the field of transportation logistics sug-
gests that saving 5% in transportation time translates to 25% added
profit! This fact should be a more than adequate motivation for the
development of methods that efficiently support the computation of
dependable routing solutions.
The essential components of a navigation system are (i) a shortest- path algorithm and (ii) a map dataset. In order to deliver high quality routing solutions to users fast, algorithms need to be efficient and road networks up-to- date. We introduce the HBA∗ algorithm, a bidirectional version of the A* algorithm that utilizes road network hierarchies to achieve faster computation times. The HBA* uses hierarchical jumping, a technique that favors the use of the higher category roads to reduce the overall search space and to significantly improve the running time of shortest-path computation.
To test the algorithm, we use dynamic travel times to assess the performance of our shortest-path algorithm (i) in relation to existing solutions (HBA* vs. A*) as well as (ii) to assess the effect of the dynamic travel times on the quality of routing solutions. Dynamic travel times are derived from vehicle tracking data also commonly referred to as floating car data (FCD) or probe vehicle data (PVD). Large collections of such data are used to derive trends in the travel time behavior for road networks. To compute shortest-path solutions, dynamic travel times allow us to find more accurate solutions when compared to static weights as provided by map data vendors. For this study, large amounts of historical FCD have been collected over a period of 2 years for the road networks of Athens, Greece and Vienna, Austria.
Through experimentation it was established that the HBA* outperforms existing routing solutions by a magnitude while at the same time providing shortest-path solutions of comparable quality.
A prototype of a Web-based multimodal routing app has been developed
using the Opentripplanner
routing engine and a custom Google Maps mashup interface.
routing prototype for Athens, Greece
- A new perspective on efficient and dependable vehicle routing - Link
- Utilizing Wireless Positioning as a Tracking Data Source - Link
- Dynamic travel time provision for road networks - Link
- Dynamic Travel Time Maps - Link
- Dynamic Travel Time Maps - Enabling Efficient Navigation - Link
- Addressing the Need for Map-Matching Speed: Localizing Global Curve-Matching Algorithms - Link
- Practical Data Management Techniques for Vehicle Tracking Data - Link
- On Map-Matching Vehicle Tracking Data - Link
- Trajectory Indexing Using Movement Constraints - Link
- Indeterminacy and Spatiotemporal Data: Basic Definitions and Case Study - Link
- Indexing of network constrained moving objects - Link
- Novel Approaches in Query Processing for Moving Object Trajectories - Link
- Capturing the Uncertainty of Moving-Object Representations - Link