Search Results

Documents authored by Storandt, Sabine

Document
DOI: 10.4230/OASIcs.ATMOS.2024.1
Landmark Hub Labeling: Improved Bounds and Faster Query Answering

Authors: Justine Cauvi, Ruoying Li, and Sabine Storandt

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
Hub Labeling (HL) is a state-of-the-art method for answering shortest-distance queries between node pairs in weighted graphs. It provides very fast query times but also requires considerable additional space to store the label information. Recently, a generalization of HL, called Landmark Hub Labeling (LHL), has been proposed, that conceptionally allows a storage of fewer label information without compromising the optimality of the query result. However, query answering with LHL was shown to be slower than with HL, both in theory and practice. Furthermore, it was not clear whether there are graphs with a substantial space reduction when using LHL instead of HL. In this paper, we describe a new way of storing label information of an LHL such that query times are significantly reduced and then asymptotically match those of HL. Thus, we alleviate the so far greatest shortcoming of LHL compared to HL. Moreover, we show that for the practically relevant hierarchical versions (HHL and HLHL), there are graphs in which the label size of an optimal HLHL is a factor of Θ(√ n) smaller than that of an optimal HHL. We establish further novel bounds between different labeling variants. Additionally, we provide a comparative experimental study between approximation algorithms for HL and LHL. We demonstrate that label sizes in an LHL are consistently smaller than those of HL across diverse benchmark graphs, including road networks.
Cite as

Justine Cauvi, Ruoying Li, and Sabine Storandt. Landmark Hub Labeling: Improved Bounds and Faster Query Answering. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cauvi_et_al:OASIcs.ATMOS.2024.1,
  author =	{Cauvi, Justine and Li, Ruoying and Storandt, Sabine},
  title =	{{Landmark Hub Labeling: Improved Bounds and Faster Query Answering}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{1:1--1:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.1},
  URN =		{urn:nbn:de:0030-drops-211892},
  doi =		{10.4230/OASIcs.ATMOS.2024.1},
  annote =	{Keywords: Route Planning, Shortest Path, Hub Labeling}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.19
Algorithms for Gradual Polyline Simplification

Authors: Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
Displaying line data is important in many visualization applications, and especially in the context of interactive geographical and cartographic visualization. When rendering linear features as roads, rivers or movement data on zoomable maps, the challenge is to display the data in an appropriate level of detail. A too detailed representation results in slow rendering and cluttered maps, while a too coarse representation might miss important data aspects. In this paper, we propose the gradual line simplification (GLS) problem, which aims to compute a fine-grained succession of consistent simplifications of a given input polyline with certain quality guarantees. The core concept of gradual simplification is to iteratively remove points from the polyline to obtain increasingly coarser representations. We devise two objective functions to guide this simplification process and present dynamic programs that compute the optimal solutions in 𝒪(n³) for an input line with n points. For practical application to large inputs, we also devise significantly faster greedy algorithms that provide constant factor guarantees for both problem variants at once. In an extensive experimental study on real-world data, we demonstrate that our algorithms are capable of producing simplification sequences of high quality within milliseconds on polylines consisting of over half a million points.
Cite as

Nick Krumbholz, Stefan Funke, Peter Schäfer, and Sabine Storandt. Algorithms for Gradual Polyline Simplification. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{krumbholz_et_al:LIPIcs.SEA.2024.19,
  author =	{Krumbholz, Nick and Funke, Stefan and Sch\"{a}fer, Peter and Storandt, Sabine},
  title =	{{Algorithms for Gradual Polyline Simplification}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.19},
  URN =		{urn:nbn:de:0030-drops-203847},
  doi =		{10.4230/LIPIcs.SEA.2024.19},
  annote =	{Keywords: Polyline simplification, Progressive simplification, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.60
Pareto Sums of Pareto Sets

Authors: Demian Hespe, Peter Sanders, Sabine Storandt, and Carina Truschel

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
In bi-criteria optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on efficient merging or combining of partial solutions and filtering of dominated solutions in the resulting sets. In this paper, we consider the task of computing the Pareto sum of two given Pareto sets A, B of size n. The Pareto sum contains all non-dominated points of the Minkowski sum M = {a+b|a ∈ A, b ∈ B}. Since the Minkowski sum has a size of n², but the Pareto sum C can be much smaller, the goal is to compute C without having to compute and store all of M. We present several new algorithms for efficient Pareto sum computation, including an output-sensitive one with a running time of 𝒪(n log n + nk) and a space consumption of 𝒪(n+k) for k = |C|. We also describe suitable engineering techniques to improve the practical running times of our algorithms and provide a comparative experimental study. As one showcase application, we consider preprocessing-based methods for bi-criteria route planning in road networks. Pareto sum computation is a frequent task in the preprocessing phase. We show that using our algorithms with an output-sensitive space consumption allows to tackle larger instances and reduces the preprocessing time compared to algorithms that fully store M.
Cite as

Demian Hespe, Peter Sanders, Sabine Storandt, and Carina Truschel. Pareto Sums of Pareto Sets. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hespe_et_al:LIPIcs.ESA.2023.60,
  author =	{Hespe, Demian and Sanders, Peter and Storandt, Sabine and Truschel, Carina},
  title =	{{Pareto Sums of Pareto Sets}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.60},
  URN =		{urn:nbn:de:0030-drops-187132},
  doi =		{10.4230/LIPIcs.ESA.2023.60},
  annote =	{Keywords: Minkowski sum, Skyline, Successive Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.5
Algorithms for Landmark Hub Labeling

Authors: Sabine Storandt

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Landmark-based routing and Hub Labeling (HL) are shortest path planning techniques, both of which rely on storing shortest path distances between selected pairs of nodes in a preprocessing phase to accelerate query answering. In Landmark-based routing, stored distances to landmark nodes are used to obtain distance lower bounds that guide A* search from node s to node t. With HL, tight upper bounds for shortest path distances between any s-t-pair can be interfered from their stored node labels, making HL an efficient distance oracle. However, for shortest path retrieval, the oracle has to be called once per edge in said path. Furthermore, HL often suffers from a large space consumption as many node pair distances have to be stored in the labels to allow for correct query answering. In this paper, we propose a novel technique, called Landmark Hub Labeling (LHL), which integrates the landmark concept into HL. We prove better worst-case path retrieval times for LHL in case it is path-consistent (a new labeling property we introduce). Moreover, we design efficient (approximation) algorithms that produce path-consistent LHL with small label size and provide parametrized upper bounds, depending on the highway dimension h or the geodesic transversal number gt of the graph. Finally, we show that the space consumption of LHL is smaller than that of (hierarchical) HL, both in theory and in experiments on real-world road networks.
Cite as

Sabine Storandt. Algorithms for Landmark Hub Labeling. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{storandt:LIPIcs.ISAAC.2022.5,
  author =	{Storandt, Sabine},
  title =	{{Algorithms for Landmark Hub Labeling}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.5},
  URN =		{urn:nbn:de:0030-drops-172901},
  doi =		{10.4230/LIPIcs.ISAAC.2022.5},
  annote =	{Keywords: Hub Labeling, Landmark, Geodesic, Hitting Set, Highway Dimension}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.12
Map Matching for Semi-Restricted Trajectories

Authors: Timon Behr, Thomas C. van Dijk, Axel Forsch, Jan-Henrik Haunert, and Sabine Storandt

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
We consider the problem of matching trajectories to a road map, giving particular consideration to trajectories that do not exclusively follow the underlying network. Such trajectories arise, for example, when a person walks through the inner part of a city, crossing market squares or parking lots. We call such trajectories semi-restricted. Sensible map matching of semi-restricted trajectories requires the ability to differentiate between restricted and unrestricted movement. We develop in this paper an approach that efficiently and reliably computes concise representations of such trajectories that maintain their semantic characteristics. Our approach utilizes OpenStreetMap data to not only extract the network but also areas that allow for free movement (as e.g. parks) as well as obstacles (as e.g. buildings). We discuss in detail how to incorporate this information in the map matching process, and demonstrate the applicability of our method in an experimental evaluation on real pedestrian and bicycle trajectories.
Cite as

Timon Behr, Thomas C. van Dijk, Axel Forsch, Jan-Henrik Haunert, and Sabine Storandt. Map Matching for Semi-Restricted Trajectories. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{behr_et_al:LIPIcs.GIScience.2021.II.12,
  author =	{Behr, Timon and van Dijk, Thomas C. and Forsch, Axel and Haunert, Jan-Henrik and Storandt, Sabine},
  title =	{{Map Matching for Semi-Restricted Trajectories}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.12},
  URN =		{urn:nbn:de:0030-drops-147717},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.12},
  annote =	{Keywords: map matching, OpenStreetMap, GPS, trajectory, road network}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.2
On the Multi-Kind BahnCard Problem

Authors: Mike Timm and Sabine Storandt

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
The BahnCard problem is an important problem in the realm of online decision making. In its original form, there is one kind of BahnCard associated with a certain price, which upon purchase reduces the ticket price of train journeys for a certain factor over a certain period of time. The problem consists of deciding on which dates BahnCards should be purchased such that the overall cost, that is, BahnCard prices plus (reduced) ticket prices, is minimized without having knowledge about the number and prices of future journeys. In this paper, we extend the problem such that multiple kinds of BahnCards are available for purchase. We provide an optimal offline algorithm, as well as online strategies with provable competitiveness factors. Furthermore, we describe and implement several heuristic online strategies and compare their competitiveness in realistic scenarios.
Cite as

Mike Timm and Sabine Storandt. On the Multi-Kind BahnCard Problem. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{timm_et_al:OASIcs.ATMOS.2020.2,
  author =	{Timm, Mike and Storandt, Sabine},
  title =	{{On the Multi-Kind BahnCard Problem}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{2:1--2:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.2},
  URN =		{urn:nbn:de:0030-drops-131382},
  doi =		{10.4230/OASIcs.ATMOS.2020.2},
  annote =	{Keywords: offline solution, competitiveness, traveller profiles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.20
Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies

Authors: Johannes Blum and Sabine Storandt

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing the search space size of a bidirectional Dijkstra run. To explain the practical success of CH, several theoretical upper bounds for the maximum search space size were derived in previous work. For example, it was shown that in minor-closed graph families search space sizes in 𝒪(√n) can be achieved (with n denoting the number of nodes in the graph), and search space sizes in 𝒪(h log D) in graphs of highway dimension h and diameter D. In this paper, we primarily focus on lower bounds. We prove that the average search space size in a so called weak CH is in Ω(b_α) for α ≥ 2/3 where b_α is the size of a smallest α-balanced node separator. This discovery allows us to describe the first approximation algorithm for the average search space size. Our new lower bound also shows that the 𝒪(√n) bound for minor-closed graph families is tight. Furthermore, we deeper investigate the relationship of CH and the highway dimension and skeleton dimension of the graph, and prove new lower bound and incomparability results. Finally, we discuss how lower bounds for strong CH can be obtained from solving a HittingSet problem defined on a set of carefully chosen subgraphs of the input network.
Cite as

Johannes Blum and Sabine Storandt. Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blum_et_al:LIPIcs.ESA.2020.20,
  author =	{Blum, Johannes and Storandt, Sabine},
  title =	{{Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.20},
  URN =		{urn:nbn:de:0030-drops-128861},
  doi =		{10.4230/LIPIcs.ESA.2020.20},
  annote =	{Keywords: contraction hierarchies, search space size, balanced separator, tree decomposition}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.35
Simplification of Polyline Bundles

Authors: Joachim Spoerhase, Sabine Storandt, and Johannes Zink

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We propose and study a generalization to the well-known problem of polyline simplification. Instead of a single polyline, we are given a set of l polylines possibly sharing some line segments and bend points. Our goal is to minimize the number of bend points in the simplified bundle with respect to some error tolerance δ (measuring Fréchet distance) but under the additional constraint that shared parts have to be simplified consistently. We show that polyline bundle simplification is NP-hard to approximate within a factor n^(1/3 - ε) for any ε > 0 where n is the number of bend points in the polyline bundle. This inapproximability even applies to instances with only l=2 polylines. However, we identify the sensitivity of the solution to the choice of δ as a reason for this strong inapproximability. In particular, we prove that if we allow δ to be exceeded by a factor of 2 in our solution, we can find a simplified polyline bundle with no more than 𝒪(log (l + n)) ⋅ OPT bend points in polytime, providing us with an efficient bi-criteria approximation. As a further result, we show fixed-parameter tractability in the number of shared bend points.
Cite as

Joachim Spoerhase, Sabine Storandt, and Johannes Zink. Simplification of Polyline Bundles. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{spoerhase_et_al:LIPIcs.SWAT.2020.35,
  author =	{Spoerhase, Joachim and Storandt, Sabine and Zink, Johannes},
  title =	{{Simplification of Polyline Bundles}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.35},
  URN =		{urn:nbn:de:0030-drops-122821},
  doi =		{10.4230/LIPIcs.SWAT.2020.35},
  annote =	{Keywords: Polyline Simplification, Bi-criteria Approximation, Hardness of Approximation, Geometric Set Cover}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2018
OASIcs, Volume 65, ATMOS'18, Complete Volume

Authors: Ralf Borndörfer and Sabine Storandt

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
OASIcs, Volume 65, ATMOS'18, Complete Volume
Cite as

18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{borndorfer_et_al:OASIcs.ATMOS.2018,
  title =	{{OASIcs, Volume 65, ATMOS'18, Complete Volume}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018},
  URN =		{urn:nbn:de:0030-drops-97272},
  doi =		{10.4230/OASIcs.ATMOS.2018},
  annote =	{Keywords: Theory of computation, Design and analysis of algorithms, Mathematics of computing, Discrete mathematics, Mathematics of computing, Combinatorics}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2018.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Ralf Borndörfer and Sabine Storandt

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2018.0,
  author =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.0},
  URN =		{urn:nbn:de:0030-drops-97050},
  doi =		{10.4230/OASIcs.ATMOS.2018.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.18
Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Authors: Stefan Funke, Sören Laue, and Sabine Storandt

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
In a personalized route planning query, a user can specify how relevant different criteria as travel time, gas consumption, scenicness, etc. are for his individual definition of an optimal route. Recently developed acceleration schemes for personalized route planning, which rely on preprocessing, achieve a significant speed-up over the Dijkstra baseline for a small number of criteria. But for more than five criteria, either the preprocessing becomes too complicated or the query answering is slow. In this paper, we first present a new LP-based preprocessing technique which allows to deal with many criteria efficiently. In addition, we show how to further reduce query times for all known personalized route planning acceleration schemes by considering approximate queries. We design a data structure which allows not only to have personalized costs but also individual approximation guarantees per query, allowing to trade solution quality against query time at the user's discretion. This data structure is the first to enable a speed-up of more than 100 for ten criteria while accepting only 0.01% increased costs.
Cite as

Stefan Funke, Sören Laue, and Sabine Storandt. Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:LIPIcs.SEA.2017.18,
  author =	{Funke, Stefan and Laue, S\"{o}ren and Storandt, Sabine},
  title =	{{Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.18},
  URN =		{urn:nbn:de:0030-drops-76255},
  doi =		{10.4230/LIPIcs.SEA.2017.18},
  annote =	{Keywords: personalized route planning, contraction hierarchies, linear program, separation oracle, approximate queries}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2013.42
Delay-Robustness of Transfer Patterns in Public Transportation Route Planning

Authors: Hannah Bast, Jonas Sternisko, and Sabine Storandt

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract
Transfer pattern routing is a state-of-the-art speed-up technique for finding optimal paths which minimize multiple cost criteria in public transportation networks. It precomputes sequences of transfer stations along optimal paths. At query time, the optimal paths are searched among the stored transfer patterns, which allows for very fast response times even on very large networks. On the other hand, even a minor change to the timetables may affect many optimal paths, so that, in principle, a new computation of all optimal transfer patterns becomes necessary. In this paper, we examine the robustness of transfer pattern routing towards delay, which is the most common source of such updates. The intuition is that the deviating paths caused by typical updates are already covered by original transfer patterns. We perform experiments which show that the transfer patterns are remarkably robust even to large and many delays, which underlines the applicability and reliability of transfer pattern routing in realistic routing applications.
Cite as

Hannah Bast, Jonas Sternisko, and Sabine Storandt. Delay-Robustness of Transfer Patterns in Public Transportation Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 42-54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bast_et_al:OASIcs.ATMOS.2013.42,
  author =	{Bast, Hannah and Sternisko, Jonas and Storandt, Sabine},
  title =	{{Delay-Robustness of Transfer Patterns in Public Transportation Route Planning}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{42--54},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.42},
  URN =		{urn:nbn:de:0030-drops-42434},
  doi =		{10.4230/OASIcs.ATMOS.2013.42},
  annote =	{Keywords: Route planning, public transportation, transfer patterns, delay, robustness}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2013.123
Result Diversity for Multi-Modal Route Planning

Authors: Hannah Bast, Mirko Brodesser, and Sabine Storandt

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract
We study multi-modal route planning allowing arbitrary (meaningful) combinations of public transportation, walking, and taking a car / taxi. In the straightforward model, the number of Pareto-optimal solutions explodes. It turns out that many of them are similar to each other or unreasonable. We introduce a new filtering procedure, Types aNd Thresholds (TNT), which leads to a small yet representative subset of the reasonable paths. We consider metropolitan areas like New York, where a fast computation of the paths is difficult. To reduce the high computation times, optimality-preserving and heuristic approaches are introduced. We experimentally evaluate our approach with respect to result quality and query time. The experiments confirm that our result sets are indeed small (around 5 results per query) and representative (among the reasonable Pareto-optimal paths), and with average query times of about one second or less.
Cite as

Hannah Bast, Mirko Brodesser, and Sabine Storandt. Result Diversity for Multi-Modal Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 123-136, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bast_et_al:OASIcs.ATMOS.2013.123,
  author =	{Bast, Hannah and Brodesser, Mirko and Storandt, Sabine},
  title =	{{Result Diversity for Multi-Modal Route Planning}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{123--136},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.123},
  URN =		{urn:nbn:de:0030-drops-42494},
  doi =		{10.4230/OASIcs.ATMOS.2013.123},
  annote =	{Keywords: Route Planning, Multi-Modal, Result Diversity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact