19 Search Results for "Funke, Stefan"

Volume

OASIcs, Volume 42

14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems

ATMOS 2014, September 11, 2014, Wrocław, Poland

Editors: Stefan Funke and Matús Mihalák

Document
DOI: 10.4230/LIPIcs.SEA.2023.20
Efficient Yao Graph Construction

Authors: Daniel Funke and Peter Sanders

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
Yao graphs are geometric spanners that connect each point of a given point set to its nearest neighbor in each of k cones drawn around it. Yao graphs were introduced to construct minimum spanning trees in d dimensional spaces. Moreover, they are used for instance in topology control in wireless networks. An optimal 𝒪(n log n)-time algorithm to construct Yao graphs for a given point set has been proposed in the literature but - to the best of our knowledge - never been implemented. Instead, algorithms with a quadratic complexity are used in popular packages to construct these graphs. In this paper we present the first implementation of the optimal Yao graph algorithm. We engineer the data structures required to achieve the 𝒪(n log n) time bound and detail algorithmic adaptations necessary to take the original algorithm from theory to practice. We propose a priority queue data structure that separates static and dynamic events and might be of independent interest for other sweepline algorithms. Additionally, we propose a new Yao graph algorithm based on a uniform grid data structure that performs well for medium-sized inputs. We evaluate our implementations on a wide variety of synthetic and real-world datasets and show that our implementation outperforms current publicly available implementations by at least an order of magnitude.
Cite as

Daniel Funke and Peter Sanders. Efficient Yao Graph Construction. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 20:1-20:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:LIPIcs.SEA.2023.20,
  author =	{Funke, Daniel and Sanders, Peter},
  title =	{{Efficient Yao Graph Construction}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.20},
  URN =		{urn:nbn:de:0030-drops-183706},
  doi =		{10.4230/LIPIcs.SEA.2023.20},
  annote =	{Keywords: computational geometry, geometric spanners, Yao graphs, sweepline algorithms, optimal algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.14
An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions

Authors: Florian Barth, Stefan Funke, and Claudius Proissl

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Graphs with multiple edge costs arise naturally in the route planning domain when apart from travel time other criteria like fuel consumption or positive height difference are also objectives to be minimized. In such a scenario, this paper investigates the number of extreme shortest paths between a given source-target pair s, t. We show that for a fixed but arbitrary number of cost types d ≥ 1 the number of extreme shortest paths is in n^O(log^{d-1}n) in graphs G with n nodes. This is a generalization of known upper bounds for d = 2 and d = 3.
Cite as

Florian Barth, Stefan Funke, and Claudius Proissl. An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 14:1-14:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.ESA.2022.14,
  author =	{Barth, Florian and Funke, Stefan and Proissl, Claudius},
  title =	{{An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.14},
  URN =		{urn:nbn:de:0030-drops-169525},
  doi =		{10.4230/LIPIcs.ESA.2022.14},
  annote =	{Keywords: Parametric Shortest Paths, Extreme Shortest Paths}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.15
Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets

Authors: Florian Barth, Stefan Funke, and Claudius Proissl

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In a road network with multicriteria edge costs we consider the problem of computing a minimum number of driving preferences such that a given set of paths/trajectories is optimal under at least one of these preferences. While the exact formulation and solution of this problem appears theoretically hard, we show that in practice one can solve the problem exactly even for non-homeopathic instance sizes of several thousand trajectories in a road network of several million nodes. We also present a parameterized guaranteed-polynomial-time scheme with very good practical performance.
Cite as

Florian Barth, Stefan Funke, and Claudius Proissl. Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 15:1-15:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.ISAAC.2021.15,
  author =	{Barth, Florian and Funke, Stefan and Proissl, Claudius},
  title =	{{Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.15},
  URN =		{urn:nbn:de:0030-drops-154481},
  doi =		{10.4230/LIPIcs.ISAAC.2021.15},
  annote =	{Keywords: Route planning, personalization, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.28
Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences

Authors: Stefan Funke and Felix Weitbrecht

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Given an ordered sequence of points P = {p₁, p₂, … , p_n}, we are interested in computing T, the set of distinct triangles occurring over all Delaunay triangulations of contiguous subsequences within P. We present a deterministic algorithm for this purpose with near-optimal time complexity O(|T|log n). Additionally, we prove that for an arbitrary point set in random order, the expected number of Delaunay triangles occurring over all contiguous subsequences is Θ(nlog n).
Cite as

Stefan Funke and Felix Weitbrecht. Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 28:1-28:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:LIPIcs.ISAAC.2020.28,
  author =	{Funke, Stefan and Weitbrecht, Felix},
  title =	{{Efficiently Computing All Delaunay Triangles Occurring over All Contiguous Subsequences}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.28},
  URN =		{urn:nbn:de:0030-drops-133725},
  doi =		{10.4230/LIPIcs.ISAAC.2020.28},
  annote =	{Keywords: Computational Geometry, Delaunay Triangulation, Randomized Analysis}
}
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
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2014
OASIcs, Volume 42, ATMOS'14, Complete Volume

Authors: Stefan Funke and Matúš Mihalák

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
OASIcs, Volume 42, ATMOS'14, Complete Volume
Cite as

Stefan Funke and Matúš Mihalák. OASIcs, Volume 42, ATMOS'14, Complete Volume. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Proceedings{funke_et_al:OASIcs.ATMOS.2014,
  title =	{{OASIcs, Volume 42, ATMOS'14, Complete Volume}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014},
  URN =		{urn:nbn:de:0030-drops-47613},
  doi =		{10.4230/OASIcs.ATMOS.2014},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Combinatorics, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2014.i
Frontmatter, Table of Contents, Preface, Workshop Organization

Authors: Stefan Funke and Matús Mihalák

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
Frontmatter, Table of Contents, Preface, Workshop Organization
Cite as

Stefan Funke and Matús Mihalák. Frontmatter, Table of Contents, Preface, Workshop Organization. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. i-ix, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:OASIcs.ATMOS.2014.i,
  author =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  title =	{{Frontmatter, Table of Contents, Preface, Workshop Organization}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{i--ix},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.i},
  URN =		{urn:nbn:de:0030-drops-47470},
  doi =		{10.4230/OASIcs.ATMOS.2014.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Workshop Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.1
Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time

Authors: Julian Dibbelt, Ben Strasser, and Dorothea Wagner

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (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 be relevant. Delays are formalized using a stochastic model. We show how to compute a decision graph that minimizes the expected arrival time while bounding the latest arrival time over all sub-paths. Finally we show how the information contained within a decision graph can compactly be represented to the user. We experimentally evaluate our algorithms and show that the running times allow for interactive usage on a realistic train network.
Cite as

Julian Dibbelt, Ben Strasser, and Dorothea Wagner. Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 1-14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{dibbelt_et_al:OASIcs.ATMOS.2014.1,
  author =	{Dibbelt, Julian and Strasser, Ben and Wagner, Dorothea},
  title =	{{Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.1},
  URN =		{urn:nbn:de:0030-drops-47488},
  doi =		{10.4230/OASIcs.ATMOS.2014.1},
  annote =	{Keywords: Algorithms, Optimization, Delay-robustness, Route planning, Public transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.15
Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments

Authors: Tim Nonner and Marco Laumanns

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
The Shortest Path with Alternatives (SPA) policy differs from classical shortest path routing in the following way: instead of providing an exact list of means of transportation to follow, this policy gives such a list for each stop, and the traveler is supposed to pick the first option from this list when waiting at some stop. First, we show that an optimal policy of this type can be computed in polynomial time for uniform arrival times under reasonable assumptions. A similar result was so far only known for Poisson arrival times, which are less realistic for frequency-based public transportation systems. Second, we experimentally evaluate such policies. In this context, our main finding is that SPA policies are surprisingly competitive compared to traditional shortest paths, and moreover yield a significant reduction of waiting times, and therefore improvement of user experience, compared to similar greedy approaches. Specifically, for roughly 25% of considered cases, we could decrease the expected waiting time by at least 20%. To run our experiments, we also describe a tool-chain to derive the necessary information from the popular GTFS-format, therefore allowing the application of SPA policies to a wide range of public transportation systems.
Cite as

Tim Nonner and Marco Laumanns. Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 15-24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{nonner_et_al:OASIcs.ATMOS.2014.15,
  author =	{Nonner, Tim and Laumanns, Marco},
  title =	{{Shortest Path with Alternatives for Uniform Arrival Times: Algorithms and Experiments}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{15--24},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.15},
  URN =		{urn:nbn:de:0030-drops-47494},
  doi =		{10.4230/OASIcs.ATMOS.2014.15},
  annote =	{Keywords: Shortest Path, Stochastic Optimization, Public Transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.25
Locating Battery Charging Stations to Facilitate Almost Shortest Paths

Authors: Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, and Michael Segal

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using "t-spanning" routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t-spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.
Cite as

Esther M. Arkin, Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell, and Michael Segal. Locating Battery Charging Stations to Facilitate Almost Shortest Paths. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 25-33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{arkin_et_al:OASIcs.ATMOS.2014.25,
  author =	{Arkin, Esther M. and Carmi, Paz and Katz, Matthew J. and Mitchell, Joseph S. B. and Segal, Michael},
  title =	{{Locating Battery Charging Stations to Facilitate Almost Shortest Paths}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{25--33},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.25},
  URN =		{urn:nbn:de:0030-drops-47500},
  doi =		{10.4230/OASIcs.ATMOS.2014.25},
  annote =	{Keywords: approximation algorithms; geometric spanners; transportation networks}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.34
Online Train Shunting

Authors: Vianney Boeuf and Frédéric Meunier

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
At the occasion of ATMOS 2012, Tim Nonner and Alexander Souza defined a new train shunting problem that can roughly be described as follows. We are given a train visiting stations in a given order and cars located at some source stations. Each car has a target station. During the trip of the train, the cars are added to the train at their source stations and removed from it at their target stations. An addition or a removal of a car in the strict interior of the train incurs a cost higher than when the operation is performed at the end of the train. The problem consists in minimizing the total cost, and thus, at each source station of a car, the position the car takes in the train must be carefully decided. Among other results, Nonner and Souza showed that this problem is polynomially solvable by reducing the problem to the computation of a minimum independent set in a bipartite graph. They worked in the offline setting, i.e. the sources and the targets of all cars are known before the trip of the train starts. We study the online version of the problem, in which cars become known at their source stations. We derive a 2-competitive algorithm and prove than no better ratios are achievable. Other related questions are also addressed.
Cite as

Vianney Boeuf and Frédéric Meunier. Online Train Shunting. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 34-45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{boeuf_et_al:OASIcs.ATMOS.2014.34,
  author =	{Boeuf, Vianney and Meunier, Fr\'{e}d\'{e}ric},
  title =	{{Online Train Shunting}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{34--45},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.34},
  URN =		{urn:nbn:de:0030-drops-47512},
  doi =		{10.4230/OASIcs.ATMOS.2014.34},
  annote =	{Keywords: Bipartite graph, competitive analysis, online algorithm, train shunting problem, vertex cover}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.46
Engineering Graph-Based Models for Dynamic Timetable Information Systems

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

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
Many efforts have been done in the last years to model public transport timetables in order to find optimal routes. The proposed models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. The array-based models have been shown to be very effective in terms of query time, while the graph-based models usually answer queries by computing shortest paths, and hence they are suitable to be used in combination with speed-up techniques developed for road networks. In this paper, we focus on the dynamic behavior of graph-based models considering the case where transportation systems are subject to delays with respect to the given timetable. We make three contributions: (i) we give a simplified and optimized update routine for the well-known time-expanded model along with an engineered query algorithm; (ii) we propose a new graph-based model tailored for handling dynamic updates; (iii) we assess the effectiveness of the proposed models and algorithms by an experimental study, which shows that both models require negligible update time and a query time which is comparable to that required by some array-based models.
Cite as

Alessio Cionini, Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Kalliopi Giannakopoulou, Andreas Paraskevopoulos, and Christos Zaroliagis. Engineering Graph-Based Models for Dynamic Timetable Information Systems. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 46-61, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cionini_et_al:OASIcs.ATMOS.2014.46,
  author =	{Cionini, Alessio and D'Angelo, Gianlorenzo and D'Emidio, Mattia and Frigioni, Daniele and Giannakopoulou, Kalliopi and Paraskevopoulos, Andreas and Zaroliagis, Christos},
  title =	{{Engineering Graph-Based Models for Dynamic Timetable Information Systems}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{46--61},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.46},
  URN =		{urn:nbn:de:0030-drops-47522},
  doi =		{10.4230/OASIcs.ATMOS.2014.46},
  annote =	{Keywords: Timetabling, dynamic updates, queries, shortest paths}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.62
Local Search for the Resource Constrained Assignment Problem

Authors: Markus Reuther

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
The resource constrained assignment problem (RCAP) is to find a minimal cost cycle partition in a directed graph such that a resource constraint is fulfilled. The RCAP has its roots in an application that deals with the covering of a railway timetable by rolling stock vehicles. Here, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes several variants of vehicle routing problems. We contribute a local search algorithm for this problem that is derived from an exact algorithm which is similar to the Hungarian method for the standard assignment problem. Our algorithm can be summarized as a k-OPT heuristic, exchanging k arcs of an alternating cycle of the incumbent solution in each improvement step. The alternating cycles are found by dual arguments from linear programming. We present computational results for instances from our railway application at Deutsche Bahn Fernverkehr AG as well as for instances of the vehicle routing problem from the literature.
Cite as

Markus Reuther. Local Search for the Resource Constrained Assignment Problem. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 62-78, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{reuther:OASIcs.ATMOS.2014.62,
  author =	{Reuther, Markus},
  title =	{{Local Search for the Resource Constrained Assignment Problem}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{62--78},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.62},
  URN =		{urn:nbn:de:0030-drops-47538},
  doi =		{10.4230/OASIcs.ATMOS.2014.62},
  annote =	{Keywords: Assignment Problem, Local Search, Rolling Stock Rotation Problem, Vehicle Routing Problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.79
A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem

Authors: Ralf Borndörfer, Markus Reuther, and Thomas Schlechte

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
Cite as

Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 79-91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2014.79,
  author =	{Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas},
  title =	{{A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation  Problem}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{79--91},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.79},
  URN =		{urn:nbn:de:0030-drops-47549},
  doi =		{10.4230/OASIcs.ATMOS.2014.79},
  annote =	{Keywords: Coarse-To-Fine Linear Programming, Rolling Stock Rotation Problem}
}
  • Refine by Author
  • 6 Funke, Stefan
  • 2 Barth, Florian
  • 2 Dibbelt, Julian
  • 2 Proissl, Claudius
  • 2 Reuther, Markus
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Theory of computation → Discrete optimization
  • 1 Theory of computation → Shortest paths
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 2 Rolling Stock Rotation Problem
  • 2 Route planning
  • 2 computational geometry
  • 2 shortest paths
  • 1 Algorithms
  • Show More...

  • Refine by Type
  • 18 document
  • 1 volume

  • Refine by Publication Year
  • 14 2014
  • 1 2017
  • 1 2020
  • 1 2021
  • 1 2022
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact