34 Search Results for "Sauer, Jonas"

Volume

OASIcs, Volume 137

25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

ATMOS 2025, September 18-19, 2025, Warsaw, Poland

Editors: Jonas Sauer and Marie Schmidt

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.37
The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends

Authors: Lotte Blank, Sergio Cabello, Mohammad Taghi Hajiaghayi, Robert Krauthgamer, Sepideh Mahabadi, André Nusser, Jeff M. Phillips, and Jonas Sauer

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting. Our second and main set of results for the expiration model designs algorithms for the diameter and k-center problems, where items are points in a metric space. Our results significantly extend those known for the special case of sliding-window streams by Cohen-Addad, Schwiegelshohn, and Sohler [ICALP 2016], and obtain a strictly better approximation factor for the diameter in the important special case of high-dimensional Euclidean metrics. We develop new decomposition and coordination techniques along with a geometric dominance framework to filter out redundant points based on both temporal and spatial proximity.
Cite as

Lotte Blank, Sergio Cabello, Mohammad Taghi Hajiaghayi, Robert Krauthgamer, Sepideh Mahabadi, André Nusser, Jeff M. Phillips, and Jonas Sauer. The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 37:1-37:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.ICALP.2026.37,
  author =	{Blank, Lotte and Cabello, Sergio and Hajiaghayi, Mohammad Taghi and Krauthgamer, Robert and Mahabadi, Sepideh and Nusser, Andr\'{e} and Phillips, Jeff M. and Sauer, Jonas},
  title =	{{The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{37:1--37:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.37},
  URN =		{urn:nbn:de:0030-drops-264269},
  doi =		{10.4230/LIPIcs.ICALP.2026.37},
  annote =	{Keywords: clustering, diameter, streaming, sliding window, sampling}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.54
Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution

Authors: Geri Gokaj, Marvin Künnemann, Sabine Storandt, and Carina Truschel

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The Pareto sum of two-dimensional point sets P and Q in ℝ² is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the Pareto sum arises frequently in bi-criteria optimization algorithms. Prior work establishes that computing the Pareto sum of sets P and Q of size n suffers from conditional lower bounds that rule out strongly subquadratic O(n^{2-ε})-time algorithms, even when the output size is Θ(n). Naturally, we ask: How efficiently can we approximate Pareto sums, both in theory and practice? Can we beat the near-quadratic-time state of the art for exact algorithms? On the theoretical side, we formulate a notion of additively approximate Pareto sets and show that computing an approximate Pareto set is fine-grained equivalent to Bounded Monotone Min-Plus Convolution. Leveraging a remarkable Õ(n^{1.5})-time algorithm for the latter problem (Chi, Duan, Xie, Zhang; STOC '22), we thus obtain a strongly subquadratic (and conditionally optimal) approximation algorithm for computing Pareto sums. On the practical side, we engineer different algorithmic approaches for approximating Pareto sets on realistic instances. Our implementations enable a granular trade-off between approximation quality and running time/output size compared to the state of the art for exact algorithms established in (Funke, Hespe, Sanders, Storandt, Truschel; Algorithmica '25). Perhaps surprisingly, the (theoretical) connection to Bounded Monotone Min-Plus Convolution remains beneficial even for our implementations: in particular, we implement a simplified, yet still subquadratic version of an algorithm due to Chi, Duan, Xie and Zhang, which on some sufficiently large instances outperforms the competing quadratic-time approaches.
Cite as

Geri Gokaj, Marvin Künnemann, Sabine Storandt, and Carina Truschel. Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 54:1-54:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gokaj_et_al:LIPIcs.SoCG.2026.54,
  author =	{Gokaj, Geri and K\"{u}nnemann, Marvin and Storandt, Sabine and Truschel, Carina},
  title =	{{Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{54:1--54:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.54},
  URN =		{urn:nbn:de:0030-drops-258602},
  doi =		{10.4230/LIPIcs.SoCG.2026.54},
  annote =	{Keywords: computational geometry, fine-grained complexity, algorithm engineering}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2026.106
Engineering Greedy Heuristics and Simulated Annealing Methods for the Median Triangulation Under the Parallel Flip Distance (CG Challenge)

Authors: Jacobus Conradi, Benedikt Kolbe, Philip Mayer, Jonas Sauer, and Jack Spalding-Jamieson

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We present our approach for the CG:SHOP 2026 challenge. In this international challenge, the goal was to find a median triangulation for a set of triangulations in the parallel flip reconfiguration graph of all triangulations of an underlying point set. Our simulated-annealing-based approach makes use of two ingredients: a heuristic edge selection for approximating the parallel flip distance of two given triangulations, and a heuristic procedure to generate good initial triangulations.
Cite as

Jacobus Conradi, Benedikt Kolbe, Philip Mayer, Jonas Sauer, and Jack Spalding-Jamieson. Engineering Greedy Heuristics and Simulated Annealing Methods for the Median Triangulation Under the Parallel Flip Distance (CG Challenge). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 106:1-106:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.SoCG.2026.106,
  author =	{Conradi, Jacobus and Kolbe, Benedikt and Mayer, Philip and Sauer, Jonas and Spalding-Jamieson, Jack},
  title =	{{Engineering Greedy Heuristics and Simulated Annealing Methods for the Median Triangulation Under the Parallel Flip Distance}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{106:1--106:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.106},
  URN =		{urn:nbn:de:0030-drops-259125},
  doi =		{10.4230/LIPIcs.SoCG.2026.106},
  annote =	{Keywords: triangulation, flip distance, parallel flip distance, heuristic, competition}
}
Document
CG Challenge
DOI: 10.4230/LIPIcs.SoCG.2026.107
Shadoks Approach to Parallel Reconfiguration of Triangulations (CG Challenge)

Authors: Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We describe the methods used by Team Shadoks to win the CG:SHOP 2026 Challenge on parallel reconfiguration of planar triangulations. Our approach combines exact methods based on SAT with several greedy heuristics, and also makes use of SAT and MaxSAT for solution improvement.
Cite as

Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard. Shadoks Approach to Parallel Reconfiguration of Triangulations (CG Challenge). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 107:1-107:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dafonseca_et_al:LIPIcs.SoCG.2026.107,
  author =	{da Fonseca, Guilherme D. and Feschet, Fabien and Gerard, Yan},
  title =	{{Shadoks Approach to Parallel Reconfiguration of Triangulations}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{107:1--107:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.107},
  URN =		{urn:nbn:de:0030-drops-259130},
  doi =		{10.4230/LIPIcs.SoCG.2026.107},
  annote =	{Keywords: Exact algorithm, SAT, MaxSAT, heuristic, computational geometry}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.15
Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques

Authors: Johannes Breitling and Moritz Laupichler

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

Abstract
We introduce a first-of-its-kind efficient, exact algorithm for the dynamic taxi-sharing problem with single-transfer journeys, i.e., a dispatcher that assigns traveler requests to a fleet of shared taxi-like vehicles allowing transfers between vehicles. We extend an existing no-transfer solution by collecting all viable pickup and dropoff vehicles for a request and computing the optimal transfer point for every pair of vehicles. We analyze underlying shortest-path problems and employ state-of-the-art routing algorithms to compute distances on-the-fly, which serves as the basis of dispatching requests with exact and up-to-date travel time information. We utilize constraints on existing routes, pruning techniques for transfer points, and both instruction- and thread-level parallelism to speed up the computation of the best assignment for every traveler. In addition to the exact variant, we propose a tunable heuristic approach that sacrifices solution quality in favor of improved running time. We evaluate our algorithm on a large road network with realistic input sets (up to 150000 requests). We demonstrate the effectiveness of our speedup techniques and the heuristic. We show first results on the benefits of transfers for taxi sharing on dense request sets, proving that our algorithm is well suited for the analysis of taxi sharing with transfers on large input instances.
Cite as

Johannes Breitling and Moritz Laupichler. Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:OASIcs.ATMOS.2025.15,
  author =	{Breitling, Johannes and Laupichler, Moritz},
  title =	{{Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{15:1--15:22},
  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.15},
  URN =		{urn:nbn:de:0030-drops-247718},
  doi =		{10.4230/OASIcs.ATMOS.2025.15},
  annote =	{Keywords: Dynamic taxi sharing, ride pooling, dial-a-ride problem, transfers, route planning}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.17
The Line-Based Dial-a-Ride Problem with Transfers

Authors: Jonas Barth, Kendra Reiter, and Marie Schmidt

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

Abstract
We introduce the line-based dial-a-ride problem with transfers (liDARPT), a variation of the well-studied dial-a-ride problem (DARP), where vehicles transport requests on-demand but are constrained to operate along a set of lines, and passengers are allowed to transfer between lines on their journey. We develop an event-based solution approach for the liDARPT that relies on the construction of an event-based graph and uses a MILP to find optimal circulations in the event-based graph. To make this solution approach effective, we devise a pre-processing routine to limit the size of the event-based graph. We extensively test our approach on novel benchmark instances, inspired by real-life long-distance bus networks. In our experiments, problem instances with up to 80 requests can be solved to optimality within 15 minutes, and an average of 99.69% of requests are accepted in all instances solved to optimality.
Cite as

Jonas Barth, Kendra Reiter, and Marie Schmidt. The Line-Based Dial-a-Ride Problem with Transfers. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:OASIcs.ATMOS.2025.17,
  author =	{Barth, Jonas and Reiter, Kendra and Schmidt, Marie},
  title =	{{The Line-Based Dial-a-Ride Problem with Transfers}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{17:1--17:20},
  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.17},
  URN =		{urn:nbn:de:0030-drops-247736},
  doi =		{10.4230/OASIcs.ATMOS.2025.17},
  annote =	{Keywords: dial-a-ride, line-based, transfers, on-demand, ridepooling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.16
A Model for Strategic Ridepooling and Its Integration with Line Planning

Authors: Lena Dittrich, Michael Rihlmann, Sarah Roth, and Anita Schöbel

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

Abstract
Ridepooling becomes more and more popular and providing comfortable and easy-to-use transportation (nearly as taxi rides) is known to motivate passengers to use public transport. In this paper we develop a model for strategic planning of ridepooling. Here we decide in which regions ridepooling should be offered and what capacities are needed, neglecting the operational details of dial-a-ride planning. We use this model for integrating ridepooling and line planning, and analyze the integrated model theoretically and numerically. Our experiments show the potential of the approach.
Cite as

Lena Dittrich, Michael Rihlmann, Sarah Roth, and Anita Schöbel. A Model for Strategic Ridepooling and Its Integration with Line Planning. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dittrich_et_al:OASIcs.ATMOS.2025.16,
  author =	{Dittrich, Lena and Rihlmann, Michael and Roth, Sarah and Sch\"{o}bel, Anita},
  title =	{{A Model for Strategic Ridepooling and Its Integration with Line Planning}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{16:1--16:20},
  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.16},
  URN =		{urn:nbn:de:0030-drops-247720},
  doi =		{10.4230/OASIcs.ATMOS.2025.16},
  annote =	{Keywords: Multi-modal planning, Line plan, Ridepooling, Integrated models}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.18
Energy-Efficient Line Planning by Implementing Express Lines

Authors: Sarah Roth and Anita Schöbel

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

Abstract
While a shift from individual transport to public transport reduces greenhouse gas emissions, public transport itself also consumes a non-negligible amount of energy. Acceleration processes have a high part in that, especially in urban transportation networks where stops are not far from each other. Express lines which skip stops hence use less energy than a vehicle on a normal line on the same route. Additionally, they increase the attractiveness of public transport by reducing travel times. In this paper, we introduce the express line planning problem ELP which extends the well-known line planning problem by the additional planning of express lines and which stops they skip. The problem is stated in a bicriteria setting minimizing the passengers travel time and the energy consumption of the public transport system. We investigate the problem’s complexity and develop two different MIP formulations and show their equivalence. The models are tested numerically on medium sized instances.
Cite as

Sarah Roth and Anita Schöbel. Energy-Efficient Line Planning by Implementing Express Lines. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{roth_et_al:OASIcs.ATMOS.2025.18,
  author =	{Roth, Sarah and Sch\"{o}bel, Anita},
  title =	{{Energy-Efficient Line Planning by Implementing Express Lines}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{18:1--18:21},
  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.18},
  URN =		{urn:nbn:de:0030-drops-247746},
  doi =		{10.4230/OASIcs.ATMOS.2025.18},
  annote =	{Keywords: Line Planning, Express Lines, Sustainable Public Transport}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.11
Design of Distance Tariffs in Public Transport

Authors: Philine Schiewe, Anita Schöbel, and Reena Urban

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

Abstract
Setting the ticket prices is a crucial decision in public transport. Its basis, relevant for all related questions, such as dynamic prices or prices for different passenger groups, is the underlying fare strategy. Popular fare strategies are based on zones or on distances. Transitions from one fare strategy to another occur frequently, e.g., if public transport operators are joined to a larger association, or if structural decisions in a region have taken place. In this paper we report practically relevant issues when a fare structure should be changed to a distance tariff, a problem frequently arising when a ticket system based on mobile devices is introduced. We present mixed-integer linear programs for finding the parameters of a distance tariff, analyze rounding properties, and reflect how the change in revenue for the operator and the number of highly affected passengers can be controlled. Additionally, we evaluate the developed models experimentally.
Cite as

Philine Schiewe, Anita Schöbel, and Reena Urban. Design of Distance Tariffs in Public Transport. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schiewe_et_al:OASIcs.ATMOS.2025.11,
  author =	{Schiewe, Philine and Sch\"{o}bel, Anita and Urban, Reena},
  title =	{{Design of Distance Tariffs in Public Transport}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{11:1--11:20},
  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.11},
  URN =		{urn:nbn:de:0030-drops-247670},
  doi =		{10.4230/OASIcs.ATMOS.2025.11},
  annote =	{Keywords: public transport, fare strategy, distance tariff}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.14
Using A* for Optimal Train Routing on Moving Block Systems

Authors: Stefan Engels and Robert Wille

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

Abstract
Modern control systems based on Moving Block allow for shorter headways and higher capacity on existing railway infrastructure. At the same time, few algorithms for optimal routing on networks equipped with such modern control systems exist. Previous methods rely on Mixed Integer Linear Programming (MILP) and face a trade-off between model size and accuracy, especially considering comparably complex and nonlinear headway constraints as well as train dynamics. With this work, we propose a complementary approach based on A*. Under a reasonable and easy assumption on train driver behavior, we propose a solution encoding and state space that is flexible concerning the choice of search algorithm and the modeling detail. The applicability is showcased on a small benchmark set. The implementation is available open-source as part of the Munich Train Control Toolkit (MTCT) on GitHub at https://github.com/cda-tum/mtct.
Cite as

Stefan Engels and Robert Wille. Using A* for Optimal Train Routing on Moving Block Systems. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{engels_et_al:OASIcs.ATMOS.2025.14,
  author =	{Engels, Stefan and Wille, Robert},
  title =	{{Using A* for Optimal Train Routing on Moving Block Systems}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{14:1--14:18},
  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.14},
  URN =		{urn:nbn:de:0030-drops-247701},
  doi =		{10.4230/OASIcs.ATMOS.2025.14},
  annote =	{Keywords: ETCS, Train Routing, Moving Block, A*, Munich Train Control Toolkit}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.12
Separator-Based Alternative Paths in Customizable Contraction Hierarchies

Authors: Scott Bacherle, Thomas Bläsius, and Michael Zündorf

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

Abstract
We propose an algorithm for computing alternatives to the shortest path in a road network, based on the speed-up technique CCH (customizable contraction hierarchy). Computing alternative paths is a well-studied problem, motivated by the fact that route-planning applications benefit from presenting different high-quality options the user can choose from. Another crucial feature of modern routing applications is the inclusion of live traffic, which requires speed-up techniques that allow efficient metric updates. Besides CCH, the other speed-up technique supporting metric updates is CRP (customizable route planning). Of the two, CCH is the more modern solution with the advantages of providing faster queries and being substantially simpler to implement efficiently. However, so far, CCH has been lacking a way of computing alternative paths. While for CRP, the commonly used plateau method for computing alternatives can be applied, this is not so straightforward for CCH. With this paper, we make CCH a viable option for alternative paths, by proposing a new separator-based approach to computing alternative paths that works hand-in-hand with the CCH data structure. With our experiments, we demonstrate that CCH can indeed be used to compute alternative paths efficiently. With this, we provide an alternative to CRP that is simpler and has lower query times.
Cite as

Scott Bacherle, Thomas Bläsius, and Michael Zündorf. Separator-Based Alternative Paths in Customizable Contraction Hierarchies. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bacherle_et_al:OASIcs.ATMOS.2025.12,
  author =	{Bacherle, Scott and Bl\"{a}sius, Thomas and Z\"{u}ndorf, Michael},
  title =	{{Separator-Based Alternative Paths in Customizable Contraction Hierarchies}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-247685},
  doi =		{10.4230/OASIcs.ATMOS.2025.12},
  annote =	{Keywords: Alternative routes, realistic road networks, customizable contraction hierarchies, route planning, shortest paths}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.8
Refined Integer Programs and Polyhedral Results for the Target Visitation Problem

Authors: Sven Mallach

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

Abstract
The Target Visitation Problem (TVP) combines the Traveling Salesman Problem and the Linear Ordering Problem, and thus serves as a natural model for route planning applications where both the travel costs and the order of the sites to visit matter. More precisely, in addition to the costs that apply for the selected links connecting two subsequently visited sites, the relative urgency of visiting one site before another is quantified and taken into account. In this article, we present refined integer linear programming formulations for the TVP, along with clarifications and extensions regarding the description of the polytopes associated with their feasible solution sets by a minimal set of linear equations and facet-defining inequalities. The practical effectiveness of exploiting the proposed improvements by means of a branch-and-cut algorithm is demonstrated in a computational study. In addition, we report the optimal values for some previously unsolved instances.
Cite as

Sven Mallach. Refined Integer Programs and Polyhedral Results for the Target Visitation Problem. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mallach:OASIcs.ATMOS.2025.8,
  author =	{Mallach, Sven},
  title =	{{Refined Integer Programs and Polyhedral Results for the Target Visitation Problem}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{8:1--8:17},
  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.8},
  URN =		{urn:nbn:de:0030-drops-247647},
  doi =		{10.4230/OASIcs.ATMOS.2025.8},
  annote =	{Keywords: Route planning, Transportation, Logistics, Traveling salesman problem, Linear ordering problem, Polyhedral Combinatorics, Branch-and-cut, Integer Programming, Linear programming}
}
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}
}
  • Refine by Type
  • 33 Document/PDF
  • 21 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 4 2026
  • 21 2025
  • 1 2023
  • 3 2022
  • 3 2020
  • Show More...

  • Refine by Author
  • 11 Sauer, Jonas
  • 5 Wagner, Dorothea
  • 5 Zündorf, Tobias
  • 4 Schmidt, Marie
  • 3 Schöbel, Anita
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs
  • 23 OASIcs

  • Refine by Classification
  • 22 Applied computing → Transportation
  • 11 Theory of computation → Shortest paths
  • 10 Mathematics of computing → Graph algorithms
  • 5 Theory of computation → Computational geometry
  • 3 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 4 Algorithms
  • 4 route planning
  • 4 shortest paths
  • 3 Public Transportation
  • 3 Route Planning
  • 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