eCOMPASS - WP3

Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time

kit — Mon, 10 Nov 2014 12:02:42 +0000

Authors:

Julian Dibbelt, Ben Strasser, and Dorothea Wagner

Publication Date:

June, 2014

Abstract:

We study the problem of computing delay-robust routes in timetable networks. Instead of a single path we compute a decision graph containing all stops and trains/vehicles that might berelevant. Delays are formalized using a stochastic model. We show how to compute a decisiongraph that minimizes the expected arrival time while bounding the latest arrival time over allsub-paths. Finally we show how the information contained within a decision graph can compactlybe represented to the user. We experimentally evaluate our algorithms and show that the running times allow for interactive usage on a realistic train network.

File:

ECOMPASS-TR-060.pdf

Work Packages:

WP3

Bibtex Entry:

@INPROCEEDINGS{dsw-drjtn-14, AUTHOR = {Julian Dibbelt and Ben Strasser and Dorothea Wagner}, TITLE = {{Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time}}, BOOKTITLE = {Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'14)}, KEY = {ATMOS'14}, SERIES = {OpenAccess Series in Informatics (OASIcs)}, YEAR = {2014}, PDF = {http://i11www.ira.uka.de/extra/publications/dsw-drjtn-14.pdf} }

Publication Details:

ATMOS'14

User-Constrained Multi-Modal Route Planning

kit — Mon, 10 Nov 2014 11:31:02 +0000

Authors:

Julian Dibbelt, Thomas Pajor, Dorothea Wagner

Publication Date:

June, 2014

Abstract:

In the multi-modal route planning problem we are given multiple transportation networks (e.\,g., pedestrian, road, public transit) and ask for a best \emph{integrated} journey between two points. The main challenge is that a seemingly optimal journey may have changes between networks that do not reflect the user's modal preferences. In fact, quickly computing reasonable multi-modal routes remains a challenging problem: Previous approaches either suffer from poor query performance or their available choices of modal preferences during query time is limited. % In this work we focus on computing exact multi-modal journeys that can be restricted by specifying arbitrary modal sequences at query time. For example, a user can say whether he wants to only use public transit, or also prefers to use a taxi or walking at the beginning or end of the journey; or if he has no restrictions at all. % By carefully adapting node contraction, a common ingredient to many speedup techniques on road networks, we are able to compute point-to-point queries on a continental network combined of cars, railroads and flights several orders of magnitude faster than Dijkstra's algorithm. Thereby, we require little space overhead and obtain fast preprocessing times.

File:

ECOMPASS-TR-058.pdf

Work Packages:

WP3

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 ALENEX 2012, first revision

Robust Routing in Urban Public Transportation: Evaluating Strategies that Learn From the Past

ethz — Wed, 05 Nov 2014 16:22:30 +0000

Authors:

Kateřina Böhmová, Matúš Mihalák, Peggy Neubert, Tobias Pröger

Publication Date:

November, 2014

Abstract:

Given an urban public transportation network and historic delay information, we consider the problem of computing reliable journeys. We propose new algorithms based on our recently presented solution concept (Böhmová et al., ATMOS 2013), and perform an experimental evaluation using real-world delay data from Zürich, Switzerland. We compare these methods to natural approaches as well as to our recently proposed method which can also be used to measure typicality of past observations. Moreover, we demonstrate how this measure relates to the predictive quality of the individual methods. In particular, if the past observations are typical, then the learning-based methods are able to produce solutions that perform well on typical days, even in the presence of strong delays.

File:

ECOMPASS-TR-057.pdf

Work Packages:

WP3

Computing and Listing st-Paths in Public Transportation Networks

ethz — Wed, 05 Nov 2014 15:34:08 +0000

Authors:

Kateřina Böhmová, Matúš Mihalák, Tobias Pröger, Gustavo Sacomoto, Marie-France Sagot

Publication Date:

November, 2014

Abstract:

Given a set of directed paths (called lines) L, a public transportation network is a directed graph G_L=(V_L,A_L) which contains exactly the vertices and arcs of every line l∈L. An st-route is a pair (π,γ) where γ=<l_1,...,l_h> is a line sequence and π is an st-path in G_L which is the concatenation of subpaths of the lines l_1,...,l_h, in this order. We study three related problems concerning traveling from s to t in G_L. We present an optimal algorithm for computing an st-route (π,γ) where |γ| (i.e., the number of line changes plus one) is minimum among all st-routes. We show for the problem of finding an st-route (π,γ) that minimizes the number of different lines in γ, even computing an o(log |V|)-approximation is NP-hard. Finally, given a constant integer β, we present an algorithm for listing all st-paths π for which a route (π,γ) with |γ|≤β exists, and show that the running time of this algorithm is polynomial with respect to the input and the output size.

File:

ECOMPASS-TR-056.pdf

Work Packages:

WP3

A Personalized Multimodal Tourist Tour Planner

gkortsilas — Wed, 05 Nov 2014 10:40:02 +0000

Authors:

Damianos Gavalas, Vlasios Kasapakis, Charalampos Konstantopoulos, Grammati Pantziou, Nikolaos Vathis, Christos Zaroliagis

Publication Date:

November, 2014

Abstract:

Tourists become increasingly dependent on mobile city guides to locate tourist services and retrieve information about nearby points of interest (POIs) when visiting unknown destinations. Although several city guides support the provision of personalized tour recommendations to assist tourists visiting the most interesting attractions, existing tour planners only consider walking tours. Herein, we introduce eCOMPASS, a context-aware mobile application which also considers the option of using public transit for moving around. Far beyond than just providing navigational aid, eCOMPASS incorporates multimodality (i.e. time dependency) within its routing logic aiming at deriving near-optimal sequencing of POIs along recommended tours so as to best utilize time available for sightseeing and minimize waiting time at transit stops. Further advancing the state of the art, eCOMPASS allows users to define arbitrary start/end locations (e.g. the current location of a mobile user) rather than choosing among a fixed set of locations. This paper describes the routing algorithm which comprises the core functionality of eCOMPASS and discusses the implementation details of the mobile application using the metropolitan area of Berlin (Germany) as case study.

File:

ECOMPASS-TR-055.pdf

Work Packages:

WP3

WP5

Publication Details:

MUM 2014

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

Approximation Algorithms for Arc Orienteering Problems

cti — Fri, 24 Jan 2014 10:44:24 +0000

Authors:

Damianos Gavalas, Charalampos Konstantopoulos, Konstantinos Mastakas, Grammati Pantziou and Nikolaos Vathis

Publication Date:

January, 2014

Abstract:

In this paper we study the Arc Orienteering Problem in directed and undirected graphs. To the best of our knowledge, we give the st approximation algorithms for both the undirected and the directed versions of the problem. Our main results are the following: (i) We give an O( log2(m) / log log(m))-approximation algorithm for the AOP in directed graphs, where m is the number of arcs of the graph of the problem, using the O( log^2(n) / log log(n))-approximation for the OP in directed graphs found in [13]. (ii) Using the (2+ε)-approximation algorithm for the unweighted version of the OP in [6], we obtain a (6+ε+o(1))-approximation algorithm for the AOP in undirected graphs and a (4+ε)-approximation algorithm for the unweighted version of the AOP in undirected graphs. Moreover, we prove that the Mixed Orienteering Problem (MOP) can be reduced to AOP and that any approximation algorithm for the AOP yields an approximation algorithm for the MOP.

File:

ECOMPASS-TR-047.pdf

Work Packages:

WP3

Connection Scan Accelerated

kit — Sun, 01 Dec 2013 20:49:26 +0000

Authors:

Ben Strasser and Dorothea Wagner

Publication Date:

January, 2014

Abstract:

We study the problem of efficiently computing journeys intimetable networks. Our algorithm optimally answers profilequeries, computing all journeys given a time interval. Ourstudy demonstrates that queries can be answered optimallyon large country-scale timetable networks within severalmilliseconds and fast delay integration is possible. Previouswork either had to drop optimality or only consideredcomparatively small timetable networks. Our technique isa combination of the Connection Scan Algorithm and multi-level overlay graphs.

File:

ECOMPASS-TR-034.pdf

Work Packages:

WP3

Bibtex Entry:

@INPROCEEDINGS{sw-csa-13, AUTHOR = {Ben Strasser and Dorothea Wagner}, TITLE = {{Connection Scan Accelerated}}, EDITOR = {Catherine C. McGeoch and Ulrich Meyer}, BOOKTITLE = {Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX'14)}, KEY = {ALENEX'14}, PUBLISHER = {SIAM}, YEAR = {2014} }

Publication Details:

Proceedings ALENEX'14

Algorithms for Transport Optimization – Theory and Practice

gkortsilas — Fri, 29 Nov 2013 13:12:22 +0000

Authors:

C. Zaroliagis

Publication Date:

October, 2013

Abstract:

Public or private transport gives rise to several optimization problems, which

are typically characterized by high complexity and sheer size, while some of them

pose, in addition, real-time response constraints. Ecient algorithms can make

a great dierence towards an ecient and eective solution of such problems. In

this talk, a few important algorithmic approaches are surveyed that are theo-

retically sound and practically ecient for the transport optimization problems

they solve.

File:

ECOMPASS-TR-033.pdf

Work Packages:

WP2

WP3

Publication Details:

ICAA 2014, Lecture Notes in Computer Science Vol. 8321 (Springer-Verlag, 2014), to appear

Applied Algorithms

gkortsilas — Fri, 29 Nov 2013 13:07:52 +0000

Authors:

P. Gupta and C. Zaroliagis

Publication Date:

October, 2013

Abstract:

Algorithms for Transport Optimization – Theory and Practice

File:

ECOMPASS-TR-032.pdf

Work Packages:

WP2

WP3

Publication Details:

ICAA 2014, Lecture Notes in Computer Science Vol. 8321, Springer, 2014.