Activities

Activities include A Spatiotemporal Knowledge World and Transportation Networks.

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.

Achievements

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

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.


Travel time fluctuations for Athens, Greece

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. 

Multimodal Routing

http://web.imis.athena-innovation.gr:10080/opentripplanner-webapp/

A prototype of a Web-based multimodal routing app has been developed using the Opentripplanner routing engine and a custom Google Maps mashup interface.


Multimodal routing prototype for Athens, Greece

Publications