27 Search Results for "Huisman, Dennis"

Volume

OASIcs, Volume 85

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

ATMOS 2020, September 7-8, 2020, Pisa, Italy (Virtual Conference)

Editors: Dennis Huisman and Christos D. Zaroliagis

Document
DOI: 10.4230/OASIcs.ATMOS.2025.1
The Fair Periodic Assignment Problem

Authors: Rolf Nelson van Lieshout and Bartholomeüs Theodorus Cornelis van Rossum

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We study the periodic assignment problem, in which a set of periodically repeating tasks must be assigned to workers within a repeating schedule. The classical efficiency objective is to minimize the number of workers required to operate the schedule. We propose a 𝒪(n log n) algorithm to solve this problem. Next, we formalize a notion of fairness among workers, and impose that each worker performs the same work over time. We analyze the resulting trade-off between efficiency and fairness, showing that the price of fairness is at most one extra worker, and that such a fair solution can always be found using the Nearest Neighbor heuristic. We characterize all instances that admit a solution that is both fair and efficient, and use this result to develop a 𝒪(n log n) exact algorithm for the fair periodic assignment problem. Finally, we show that allowing aperiodic schedules never reduces the price of fairness.
Cite as

Rolf Nelson van Lieshout and Bartholomeüs Theodorus Cornelis van Rossum. The Fair Periodic Assignment Problem. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanlieshout_et_al:OASIcs.ATMOS.2025.1,
  author =	{van Lieshout, Rolf Nelson and van Rossum, Bartholome\"{u}s Theodorus Cornelis},
  title =	{{The Fair Periodic Assignment Problem}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{1:1--1:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.1},
  URN =		{urn:nbn:de:0030-drops-247574},
  doi =		{10.4230/OASIcs.ATMOS.2025.1},
  annote =	{Keywords: Cyclic scheduling, Fairness, Traveling Salesman Problem}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.2
A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing

Authors: Fabian Löbel and Niels Lindner

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.
Cite as

Fabian Löbel and Niels Lindner. A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lobel_et_al:OASIcs.ATMOS.2025.2,
  author =	{L\"{o}bel, Fabian and Lindner, Niels},
  title =	{{A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{2:1--2:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.2},
  URN =		{urn:nbn:de:0030-drops-247580},
  doi =		{10.4230/OASIcs.ATMOS.2025.2},
  annote =	{Keywords: Periodic Timetabling, Passenger Routing, Polyhedral Complexes}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.7
Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs

Authors: David C. Kutner and Anouk Sommer

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
In train networks, carefully-chosen delays may be beneficial for certain passengers, who would otherwise miss some connection. Given a simple (directed or undirected) temporal graph and a set of passengers (each specifying a starting vertex, an ending vertex, and a desired arrival time), we ask whether it is possible to delay some of the edges of the temporal graph to realize all the passengers' demands. We call this problem DelayBetter (DB), and study it along with two variants: in δ-DelayBetter, each delay must be of at most δ; in (δ-)Path DB, passengers also fully specify the vertices they should visit on their journey. On the positive side, we give a polynomial-time algorithm for Path DB and δ-Path DB, and obtain as a corollary a polynomial-time algorithm for DB and δ-DB on trees. We also provide an fpt algorithm for both problems parameterized by the size of the graph’s Feedback Edge Set together with the number of passengers. On the negative side, we show NP-completeness of (1-)DB on bounded-degree temporal graphs even when the lifetime is 2, and of (10-)DB on bounded-degree planar temporal graphs of lifetime 19. Our results complement previous work studying reachability problems in temporal graphs with delaying operations. This is to our knowledge the first such problem in which the aim is to facilitate travel between specific points (as opposed to facilitating or impeding a broadcast from one or many sources).
Cite as

David C. Kutner and Anouk Sommer. Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kutner_et_al:LIPIcs.SAND.2025.7,
  author =	{Kutner, David C. and Sommer, Anouk},
  title =	{{Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.7},
  URN =		{urn:nbn:de:0030-drops-230604},
  doi =		{10.4230/LIPIcs.SAND.2025.7},
  annote =	{Keywords: Temporal Graphs, Computational Complexity, Delay Management, Train Networks}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.8
Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem

Authors: Pedro José Correia Duarte, Marie Schmidt, Dennis Huisman, and Lucas P. Veelenturf

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
This paper introduces the Passenger-Oriented Timetabling problem with flexible frequencies (POT-flex) in the context of railway planning problems. POT-flex aims at creating feasible railway timetables minimising total perceived passenger travel time. The contribution of the POT-flex lies in its relaxation of the generally adopted assumption that line frequencies should be a fixed part of the input. Instead, we consider flexible line frequencies, encompassing a minimum and maximum frequency per line, allowing the timetabling model to decide on optimal line frequencies to obtain better solutions using fewer train services per line. We develop a mixed-integer programming formulation for POT-flex based on the Passenger-Oriented Timetabling (POT) formulation of [Polinder et al., 2021] and compare the performance of the new formulation against the POT formulation on three instances. We find that POT-flex allows to find feasible timetables in instances containing bottlenecks, and show improvements of up to 2% on the largest instance tested. These improvements highlight the cost that fixed line frequencies can have on timetabling.
Cite as

Pedro José Correia Duarte, Marie Schmidt, Dennis Huisman, and Lucas P. Veelenturf. Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{correiaduarte_et_al:OASIcs.ATMOS.2023.8,
  author =	{Correia Duarte, Pedro Jos\'{e} and Schmidt, Marie and Huisman, Dennis and Veelenturf, Lucas P.},
  title =	{{Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{8:1--8:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.8},
  URN =		{urn:nbn:de:0030-drops-187695},
  doi =		{10.4230/OASIcs.ATMOS.2023.8},
  annote =	{Keywords: PESP, Passenger Oriented Timetabling, Perceived Travel Time}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2020
OASIcs, Volume 85, ATMOS 2020, Complete Volume

Authors: Dennis Huisman and Christos D. Zaroliagis

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

Abstract
OASIcs, Volume 85, ATMOS 2020, Complete Volume
Cite as

20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1-272, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{huisman_et_al:OASIcs.ATMOS.2020,
  title =	{{OASIcs, Volume 85, ATMOS 2020, Complete Volume}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{1--272},
  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},
  URN =		{urn:nbn:de:0030-drops-131356},
  doi =		{10.4230/OASIcs.ATMOS.2020},
  annote =	{Keywords: OASIcs, Volume 85, ATMOS 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Dennis Huisman and Christos D. Zaroliagis

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

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

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

Copy BibTex To Clipboard

@InProceedings{huisman_et_al:OASIcs.ATMOS.2020.0,
  author =	{Huisman, Dennis and Zaroliagis, Christos D.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{0:i--0:x},
  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.0},
  URN =		{urn:nbn:de:0030-drops-131363},
  doi =		{10.4230/OASIcs.ATMOS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.1
An Efficient Solution for One-To-Many Multi-Modal Journey Planning

Authors: Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

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

Abstract
We study the one-to-many journey planning problem in multi-modal transportation networks consisting of a public transit network and an additional, non-schedule-based mode of transport. Given a departure time and a single source vertex, we aim to compute optimal journeys to all vertices in a set of targets, optimizing both travel time and the number of transfers used. Solving this problem yields a crucial component in many other problems, such as efficient point-of-interest queries, computation of isochrones, or multi-modal traffic assignments. While many algorithms for multi-modal journey planning exist, none of them are applicable to one-to-many scenarios. Our solution is based on the combination of two state-of-the-art approaches: ULTRA, which enables efficient journey planning in multi-modal networks, but only for one-to-one queries, and (R)PHAST, which enables efficient one-to-many queries, but only in time-independent networks. Similarly to ULTRA, our new approach can be combined with any existing public transit algorithm that allows a search to all stops, which we demonstrate for CSA and RAPTOR. For small to moderately sized target sets, the resulting algorithms are nearly as fast as the pure public transit algorithms they are based on. For large target sets, we achieve a speedup of up to 7 compared to a naive one-to-many extension of a state-of-the-art multi-modal approach.
Cite as

Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. An Efficient Solution for One-To-Many Multi-Modal Journey Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sauer_et_al:OASIcs.ATMOS.2020.1,
  author =	{Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{An Efficient Solution for One-To-Many Multi-Modal Journey Planning}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{1:1--1:15},
  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.1},
  URN =		{urn:nbn:de:0030-drops-131371},
  doi =		{10.4230/OASIcs.ATMOS.2020.1},
  annote =	{Keywords: Algorithm Engineering, Route Planning, Public Transit, One-to-Many}
}
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/OASIcs.ATMOS.2020.3
Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm

Authors: Vassilissa Lehoux and Christelle Loiodice

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

Abstract
We propose an additional preprocessing step for the Trip-Based Public Transit Routing algorithm, an exact state-of-the art algorithm for bi-criteria min cost path problems in public transit networks. This additional step reduces significantly the preprocessing time, while preserving the correctness and the computation times of the queries. We test our approach on three large scale networks and show that the improved preprocessing is compatible with frequent real-time updates, even on the larger data set. The experiments also indicate that it is possible, if preprocessing time is an issue, to use the proposed preprocessing step on its own to obtain already a significant reduction of the query times compared to the no pruning scenario.
Cite as

Vassilissa Lehoux and Christelle Loiodice. Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lehoux_et_al:OASIcs.ATMOS.2020.3,
  author =	{Lehoux, Vassilissa and Loiodice, Christelle},
  title =	{{Faster Preprocessing for the Trip-Based Public Transit Routing Algorithm}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{3:1--3:12},
  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.3},
  URN =		{urn:nbn:de:0030-drops-131395},
  doi =		{10.4230/OASIcs.ATMOS.2020.3},
  annote =	{Keywords: Public transit, Route planning, Algorithms, Preprocessing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.4
Integrating ULTRA and Trip-Based Routing

Authors: Jonas Sauer, Dorothea Wagner, and Tobias Zündorf

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

Abstract
We study a bi-modal journey planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or cycling). Given a pair of source and target locations, the objective is to find a Pareto set of journeys optimizing arrival time and the number of required transfers. For public transit networks with a restricted, transitively closed transfer graph, one of the fastest known algorithms solving this bi-criteria problem is Trip-Based Routing [Witt, 2015]. However, this algorithm cannot be trivially extended to unrestricted transfer graphs. In this work, we combine Trip-Based Routing with ULTRA [Baum et al., 2019], a preprocessing technique that allows any public transit algorithm that requires transitive transfers to handle an unrestricted transfer graph. Since both ULTRA and Trip-Based Routing precompute transfer shortcuts in a preprocessing phase, a naive combination of the two leads to a three-phase algorithm that performs redundant work and produces superfluous shortcuts. We therefore propose a new, integrated preprocessing phase that combines the advantages of both and reduces the number of computed shortcuts by up to a factor of 9 compared to a naive combination. The resulting query algorithm, ULTRA-Trip-Based is the fastest known algorithm for the considered problem setting, achieving a speedup of up to 4 compared to the fastest previously known approach, ULTRA-RAPTOR.
Cite as

Jonas Sauer, Dorothea Wagner, and Tobias Zündorf. Integrating ULTRA and Trip-Based Routing. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sauer_et_al:OASIcs.ATMOS.2020.4,
  author =	{Sauer, Jonas and Wagner, Dorothea and Z\"{u}ndorf, Tobias},
  title =	{{Integrating ULTRA and Trip-Based Routing}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{4:1--4:15},
  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.4},
  URN =		{urn:nbn:de:0030-drops-131408},
  doi =		{10.4230/OASIcs.ATMOS.2020.4},
  annote =	{Keywords: Algorithms, Journey Planning, Multi-Modal, Public Transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.5
Determining All Integer Vertices of the PESP Polytope by Flipping Arcs

Authors: Niels Lindner and Christian Liebchen

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

Abstract
We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. We finally present better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.
Cite as

Niels Lindner and Christian Liebchen. Determining All Integer Vertices of the PESP Polytope by Flipping Arcs. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2020.5,
  author =	{Lindner, Niels and Liebchen, Christian},
  title =	{{Determining All Integer Vertices of the PESP Polytope by Flipping Arcs}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{5:1--5:18},
  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.5},
  URN =		{urn:nbn:de:0030-drops-131411},
  doi =		{10.4230/OASIcs.ATMOS.2020.5},
  annote =	{Keywords: Periodic Event Scheduling Problem, Periodic Timetabling, Mixed Integer Programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.6
A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling

Authors: Paul Bouman, Alexander Schiewe, and Philine Schiewe

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

Abstract
When evaluating the operational costs of a public transport system, the most important factor is the number of vehicles needed for operation. In contrast to the canonical sequential approach of first fixing a timetable and then adding a vehicle schedule, we consider a sequential approach where a vehicle schedule is determined for a given line plan and only afterwards a timetable is fixed. We compare this new sequential approach to a model that integrates both steps. To represent various operational requirements, we consider multiple possibilities to restrict the vehicle circulations to be short, as this can provide operational benefits. The sequential approach can efficiently determine public transport plans with a low number of vehicles. This is evaluated theoretically and empirically demonstrated for two close-to real-world instances.
Cite as

Paul Bouman, Alexander Schiewe, and Philine Schiewe. A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bouman_et_al:OASIcs.ATMOS.2020.6,
  author =	{Bouman, Paul and Schiewe, Alexander and Schiewe, Philine},
  title =	{{A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{6:1--6:16},
  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.6},
  URN =		{urn:nbn:de:0030-drops-131422},
  doi =		{10.4230/OASIcs.ATMOS.2020.6},
  annote =	{Keywords: Vehicle Scheduling, Timetabling, Integrated Planning}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.7
Analyzing a Family of Formulations for Cyclic Crew Rostering

Authors: Thomas Breugem, Twan Dollevoet, and Dennis Huisman

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

Abstract
In this paper, we analyze a family of formulations for the Cyclic Crew Rostering Problem (CCRP), in which a cyclic roster has to be constructed for a group of employees. Each formulation in the family is based on a partition of the roster. Intuitively, finer partitions give rise to a formulation with fewer variables, but possibly more constraints. Coarser partitions lead to more variables, but might allow to incorporate many of the constraints implicitly. We derive analytical results regarding the relative strength of the different formulations, which can serve as a guideline for formulating a given problem instance. Furthermore, we propose a column generation approach, and use it to compare the strength of the formulations empirically. Both the theoretical and computational results demonstrate the importance of choosing a suitable formulation. In particular, for practical instances of Netherlands Railways, stronger lower bounds are obtained, and more than 90% of the roster constraints can be modeled implicitly.
Cite as

Thomas Breugem, Twan Dollevoet, and Dennis Huisman. Analyzing a Family of Formulations for Cyclic Crew Rostering. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{breugem_et_al:OASIcs.ATMOS.2020.7,
  author =	{Breugem, Thomas and Dollevoet, Twan and Huisman, Dennis},
  title =	{{Analyzing a Family of Formulations for Cyclic Crew Rostering}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{7:1--7:16},
  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.7},
  URN =		{urn:nbn:de:0030-drops-131438},
  doi =		{10.4230/OASIcs.ATMOS.2020.7},
  annote =	{Keywords: Crew Planning, Roster Sequence, Column Generation, Railway Optimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.8
Time-Dependent Alternative Route Planning

Authors: Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis

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

Abstract
We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches. In particular, the entire alternative graph can be computed in less than 0.384sec for the road network of Germany, and in less than 1.24sec for that of Europe. Our approach provides also "quick-and-dirty" results of decent quality, in about 1/300 of the above mentioned query times for continental-size instances.
Cite as

Spyros Kontogiannis, Andreas Paraskevopoulos, and Christos D. Zaroliagis. Time-Dependent Alternative Route Planning. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kontogiannis_et_al:OASIcs.ATMOS.2020.8,
  author =	{Kontogiannis, Spyros and Paraskevopoulos, Andreas and Zaroliagis, Christos D.},
  title =	{{Time-Dependent Alternative Route Planning}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{8:1--8:14},
  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.8},
  URN =		{urn:nbn:de:0030-drops-131441},
  doi =		{10.4230/OASIcs.ATMOS.2020.8},
  annote =	{Keywords: time-dependent shortest path, alternative routes, travel-time oracle, plateau and penalty methods}
}
  • Refine by Type
  • 26 Document/PDF
  • 3 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 3 2025
  • 1 2023
  • 20 2020
  • 2 2009
  • 1 2007

  • Refine by Author
  • 7 Huisman, Dennis
  • 3 Schmidt, Marie
  • 3 Wagner, Dorothea
  • 3 Zaroliagis, Christos D.
  • 2 Dollevoet, Twan
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 24 OASIcs
  • 1 DagSemProc

  • Refine by Classification
  • 16 Applied computing → Transportation
  • 6 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Shortest paths
  • 3 Mathematics of computing → Combinatorial optimization
  • 3 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 2 Algorithms
  • 2 Delay Management
  • 2 Modeling
  • 2 Network Flow
  • 2 Periodic Timetabling
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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