eCOMPASS - WP2

Fast First-Move Queries through Run-Length Encoding

kit — Mon, 10 Nov 2014 12:05:44 +0000

Authors:

Ben Strasser, Daniel Harabor, Adi Botea

Publication Date:

July, 2014

Abstract:

We introduce a novel preprocessing-based algorithm to solve the problem of determining the first arc of a shortest path in sparse graphs. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix.

File:

ECOMPASS-TR-061.pdf

Work Packages:

WP2

Publication Details:

SOCS'14

Customizable Contraction Hierarchies

kit — Mon, 10 Nov 2014 11:58:38 +0000

Authors:

JULIAN DIBBELT, BEN STRASSER and DOROTHEA WAGNER

Publication Date:

September, 2014

Abstract:

We consider the problem of quickly computing shortest paths in weighted graphs. Often, this is achieved in two phases: 1) derive auxiliary data in an expensive preprocessing phase, 2) use this auxiliary data to speedup the query phase. Instead, by adding a fast weight-customization phase, we extend Contraction Hierarchies to support a three-phase workflow: The expensive preprocessing is split into a phase exploiting solely the unweighted topology of the graph, as well as a lightweight phase that adapts the auxiliary data to a specific weight. We achieve this by basing our Customizable Contraction Hierarchies on nested dissection orders. We provide an in-depth experimental analysis on large road and game maps that shows that Customizable Contraction Hierarchies are a very practicable solution in scenarios where edge weights often change.

File:

ECOMPASS-TR-059.pdf

Work Packages:

WP2

Bibtex Entry:

@INPROCEEDINGS{dsw-cch-sea-14, AUTHOR = {Julian Dibbelt and Ben Strasser and Dorothea Wagner}, TITLE = {{Customizable Contraction Hierarchies}}, EDITOR = {Joachim Gudmundsson and Jyrki Katajainen}, BOOKTITLE = {Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14)}, KEY = {SEA'14}, PUBLISHER = {Springer}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {8504}, YEAR = {2014}, PAGES = {271--282}, PDF = {http://i11www.ira.uka.de/extra/publications/dsw-cch-sea-14.pdf} }

Publication Details:

This is the extended paper, submitted to the special issue of the ACM Journal of Experimental Algorithmics (JEA) dedicated to selected papers from SEA 2014

Eco-friendly Vehicle Routing via Balanced and Compact Clustering

gkortsilas — Tue, 04 Nov 2014 15:45:51 +0000

Authors:

Dimitrios Gkortsilas, Christos Zaroliagis

Publication Date:

September, 2014

Abstract:

We investigate the Vehicle Routing Problem with Time Windows (VRPTW)

under an eco-friendly framework that demands the delivery of balanced and compact

customer clusters. We present a new approach consisting of three major phases:

(i) a first clustering of customers with compatible time windows;

(ii) a second clustering of customers with close geographic

proximity based on various methods (natural cuts, KaHIP, quad trees);

(iii) a refinement phase that either splits a cluster into smaller

ones, or merges clusters to form a bigger compact cluster.

Our approach turns out to be beneficial when used in an on-line

environment, where changes to the initial tour are requested (add a

new customer to the tour or drop some customers). The new method

serves as a warm starting point for re-evaluating and further

optimizing the solution of VRPTW. Experiments with real data sets

demonstrate that our approach compares favorably with

standard approaches that start from a basic (cold) solution.

File:

ECOMPASS-TR-053.pdf

Work Packages:

WP2

ANALYSIS AND EXPERIMENTAL EVALUATION OF TIME-DEPENDENT DISTANCE ORACLES

cti — Thu, 09 Oct 2014 13:53:42 +0000

Authors:

SPYROS KONTOGIANNIS, GEORGE MICHALOPOULOS, GEORGIA PAPASTAVROU, ANDREAS PARASKEVOPOULOS, DOROTHEA WAGNER, CHRISTOS ZAROLIAGIS

Publication Date:

September, 2014

Abstract:

Urban road networks are typically represented as directed graphs equipped with some metric which assigns distance functions (rather than scalars) to the arcs, e.g., representing the traversal times as functions of the departure time from their tails. Such a metric is usually created by sampling the distance values of all the arcs at certain points in time, and then considering the interpolants of these sampled values as the corresponding (periodic, continuous, piecewise linear) distance functions of the arcs. Distance oracles and speedup techniques aim to create appropriate traffic metadata (distance summaries, or search profiles) during a preprocessing phase, in order to be able to respond to shortest-path queries significantly faster than a typical Dijkstra run. Distance oracles focus mainly on provable worst/average case guarantees on preprocessing time/space complexities, query time complexity and approximation ratio. Speedup techniques emphasize on the thorough experimental evaluation of their performance on real large-scale road network instances.In this work, we experimentally evaluate the only time-dependent distance oracles existing so far on a truly real-world time-dependent data set (city of Berlin). In particular: (i) We present a new time-dependent distance oracle whose preprocessing phase is based on a new approximation technique for creating approximate distance summaries, that is a quite simple and fast one-to-all approximation method. (ii) We conduct an extensive experimental study with three query algorithms and six different landmark sets, achieving remarkable speedups over the time-dependent variant of Dijkstra'a algorithm.We describe here all the implementation details concerning the digestion of the raw traffic data, along with several heuristic improvements of both the preprocessing phase and the query algorithms, which are crucial for their experimental analysis. Our results are quite encouraging, achieving speedups by two orders of magnitude versus a typical time-dependent Dijkstra run, while in the vast majority of the queries the exact solution is discovered.

File:

ECOMPASS-TR-050.pdf

Work Packages:

WP2

Publication Details:

Submitted for publication

Engineering a New Model for Dynamic Timetable Information Systems

coordinator — Sat, 01 Mar 2014 18:43:36 +0000

Authors:

Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis

Publication Date:

February, 2014

Abstract:

Many efforts have been done in the last decade to model public transport timetables
in a graph theoretical framework. The aim is to represent
a timetable as a graph so that an optimal route or itinerary
is found by computing afterwards a shortest path in such a graph. One of the most used models is the so called time-expanded graph model. Its main
drawback is that if the timetable changes (e.g., due to a delay
occurring in the network), the graph needs to be topologically updated.

In this paper we propose a new model to represent the timetable
of a public transportation system as a graph. Its main advantage is that it
can be efficiently updated after a change in the timetable. In fact, it is
based on a compact representation that allows us to update the graph by changing
only few arc weights and does not require any topological modification.
We also conduct a comparative experimental study on real-world timetables
to assess the efficiency and practical applicability of the new model against
the classical and the reduced time-expanded models. The experiments show that the new model outperforms the other two models in query
and update times and also in space requirements.

File:

ECOMPASS-TR-049.pdf

Work Packages:

WP2

WP3

Recent Research Results on Traffic Prediction (an overview)

certh — Mon, 27 Jan 2014 10:39:50 +0000

Authors:

Dionisis Kehagias

Publication Date:

January, 2014

Abstract:

This report outlines the most representative research results on Traffic Prediction at the Information Technologies Institute of CERTH that were developed within the scope of the eCOMPASS project during the last year.

File:

ECOMPASS-TR-048.pdf

Work Packages:

WP2

Rectilinear Shortest Path and Rectilinear Minimum Spanning Tree with Neighborhoods

ethz — Wed, 22 Jan 2014 17:48:59 +0000

Authors:

Yann Disser, Matus Mihalak, and Sandro Montanari

Publication Date:

January, 2014

Abstract:

We study the geometric shortest path and the minimum spanning treeproblem with neighborhoods in the L 1 metric. In this setting, we are given agraph G = (R, E), where R = {R 1 , . . . , R n } is a set of polygonal regions inthe plane. Placing a point p i inside each region R i turns G into an edge-weightedgraph G p , p = {p 1 , . . . , p n }, where the cost of an edge is the distance betweenthe points. The Shortest Path Problem with Neighborhoods asks, for given R s andR t , to find a placement p such that the resulting shortest s-t path in G p is smallestamong all graphs G p . The Minimum Spanning Tree Problem with Neighborhoodsasks for a placement p such that the resulting minimum spanning tree of G p hasthe smallest cost among all minimum spanning trees of all graphs G p . We studythese problems in the L 1 metric, and show that the shortest path problem withneighborhoods is solvable in polynomial time, whereas the minimum spanningtree problem with neighborhoods is NP-hard, even if the neighborhood regionsare segments.

File:

ECOMPASS-TR-046.pdf

Work Packages:

WP2

Checking the Stationarity of the Datasets

certh — Mon, 02 Dec 2013 16:08:01 +0000

Authors:

T. Diamantopoulos, D. Kehagias

Publication Date:

October, 2013

Abstract:

This document provides stationarity checks for the Berlin and Warsaw datasets.

File:

ECOMPASS-TR-045.pdf

Work Packages:

WP2

Time Series Segmentation

certh — Mon, 02 Dec 2013 16:06:50 +0000

Authors:

T. Diamantopoulos, D. Kehagias

Publication Date:

September, 2013

Abstract:

This document provides information about the idea of segmenting a time seriesto identify segments that have constant trend.

File:

ECOMPASS-TR-044.pdf

Work Packages:

WP2

Use of Density-based Cluster Analysis and Classification Techniques for Traffic Congestion Prediction and Visualization

certh — Mon, 02 Dec 2013 16:05:00 +0000

Authors:

T. Diamantopoulos, D. Kehagias, F. Konig, D. Tzovaras

Publication Date:

September, 2013

Abstract:

The field of Intelligent Transportation Systems has lately raised increasing interest due to it high socio-economic impact. This work aims on developing efficient techniques for traffic congestion prediction and visualisation. We have designed a simple, yet effective and scalable model to handle sparse data from GPS observations and reduce the problem of congestion prediction to a binary classification problem (jam, non-jam). An attempt to generalise the problem is performed by exploring the impact of discriminative versus generative classifiers when employed to produce results in a 30-minute interval ahead of present time. In addition, we present a novel congestion prediction algorithm based on using correlation metrics to improve feature selection. Concerning the visualisation of traffic jams, we present a traffic jam visualisation approach based on cluster analysis that identifies dense congestion areas.

File:

ECOMPASS-TR-043.pdf

Work Packages:

WP2