DROPS

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.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.ESA.2025.6

On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms

Authors: Jens Schlöter

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

In the knapsack problem under explorable uncertainty, we are given a knapsack instance with uncertain item profits. Instead of having access to the precise profits, we are only given uncertainty intervals that are guaranteed to contain the corresponding profits. The actual item profit can be obtained via a query. The goal of the problem is to adaptively query item profits until the revealed information suffices to compute an optimal (or approximate) solution to the underlying knapsack instance. Since queries are costly, the objective is to minimize the number of queries. In the offline variant of this problem, we assume knowledge of the precise profits and the task is to compute a query set of minimum cardinality that a third party without access to the profits could use to identify an optimal (or approximate) knapsack solution. We show that this offline variant is complete for the second-level of the polynomial hierarchy, i.e., Σ₂^p-complete, and cannot be approximated within a non-trivial factor unless Σ₂^p = Δ₂^p. Motivated by these strong hardness results, we consider a "resource-augmented" variant of the problem where the requirements on the query set computed by an algorithm are less strict than the requirements on the optimal solution we compare against. More precisely, a query set computed by the algorithm must reveal sufficient information to identify an approximate knapsack solution, while the optimal query set we compare against has to reveal sufficient information to identify an optimal solution. We show that this resource-augmented setting allows interesting non-trivial algorithmic results.

Cite as

Jens Schlöter. On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schloter:LIPIcs.ESA.2025.6,
  author =	{Schl\"{o}ter, Jens},
  title =	{{On the Complexity of Knapsack Under Explorable Uncertainty: Hardness and Algorithms}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.6},
  URN =		{urn:nbn:de:0030-drops-244740},
  doi =		{10.4230/LIPIcs.ESA.2025.6},
  annote =	{Keywords: Explorable uncertainty, knapsack, queries, approximation algorithms}
}

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.2024.10

Periodic Timetabling: Travel Time vs. Regenerative Energy

Authors: Sven Jäger, Sarah Roth, and Anita Schöbel

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

Abstract

While it is important to provide attractive public transportation to the passengers allowing short travel times, it should also be a major concern to reduce the amount of energy used by the public transport system. Electrical trains can regenerate energy when braking, which can be used by a nearby accelerating train. Therefore, apart from the minimization of travel times, the maximization of brake-traction overlaps of nearby trains is an important objective in periodic timetabling. Recently, this has been studied in a model allowing small modifications of a nominal timetable. We investigate the problem of finding periodic timetables that are globally good in both objective functions. We show that the general problem is NP-hard, even restricted to a single transfer station and if only travel time is to be minimized, and give an algorithm with an additive error bound for maximizing the brake-traction overlap on this small network. Moreover, we identify special cases in which the problem is solvable in polynomial time. Finally, we demonstrate the trade-off between the two objective functions in an experimental study.

Cite as

Sven Jäger, Sarah Roth, and Anita Schöbel. Periodic Timetabling: Travel Time vs. Regenerative Energy. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jager_et_al:OASIcs.ATMOS.2024.10,
  author =	{J\"{a}ger, Sven and Roth, Sarah and Sch\"{o}bel, Anita},
  title =	{{Periodic Timetabling: Travel Time vs. Regenerative Energy}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{10:1--10:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.10},
  URN =		{urn:nbn:de:0030-drops-211983},
  doi =		{10.4230/OASIcs.ATMOS.2024.10},
  annote =	{Keywords: periodic timetabling, regenerative braking}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2024.15

A Bi-Objective Optimization Model for Fare Structure Design in Public Transport

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

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

Abstract

Fare planning in public transport is important from the view of passengers as well as of operators. In this paper, we propose a bi-objective model that maximizes the revenue as well as the number of attracted passengers. The potential demand per origin-destination pair is divided into demand groups that have their own willingness how much to pay for using public transport, i.e., a demand group is only attracted as public transport passengers if the fare does not exceed their willingness to pay. We study the bi-objective problem for flat and distance tariffs and develop specialized algorithms to compute the Pareto front in quasilinear or cubic time, respectively. Through computational experiments on structured data sets we evaluate the running time of the developed algorithms in practice and analyze the number of non-dominated points and their respective efficient solutions.

Cite as

Philine Schiewe, Anita Schöbel, and Reena Urban. A Bi-Objective Optimization Model for Fare Structure Design in Public Transport. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schiewe_et_al:OASIcs.ATMOS.2024.15,
  author =	{Schiewe, Philine and Sch\"{o}bel, Anita and Urban, Reena},
  title =	{{A Bi-Objective Optimization Model for Fare Structure Design in Public Transport}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{15:1--15:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.15},
  URN =		{urn:nbn:de:0030-drops-212034},
  doi =		{10.4230/OASIcs.ATMOS.2024.15},
  annote =	{Keywords: Public transport, fare structure design, modeling, bi-objective, algorithm}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2023.9

Recoverable Robust Periodic Timetabling

Authors: Vera Grafe and Anita Schöbel

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

Abstract

We apply the concept of recoverable robustness to periodic timetabling, resulting in the Recoverable Robust Periodic Timetabling Problem (RRPT), which integrates periodic timetabling and delay management. Although the computed timetable is periodic, the model is able to take the aperiodicity of the delays into account. This is an important step in finding a good trade-off between short travel times and delay resistance. We present three equivalent formulations for this problem, differing in the way the timetabling subproblem is handled, and compare them in a first experimental study. We also show that our model yields solutions of high quality.

Cite as

Vera Grafe and Anita Schöbel. Recoverable Robust Periodic Timetabling. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grafe_et_al:OASIcs.ATMOS.2023.9,
  author =	{Grafe, Vera and Sch\"{o}bel, Anita},
  title =	{{Recoverable Robust Periodic Timetabling}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{9:1--9:16},
  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.9},
  URN =		{urn:nbn:de:0030-drops-187708},
  doi =		{10.4230/OASIcs.ATMOS.2023.9},
  annote =	{Keywords: Public Transport, Recoverable Robustness, Periodic Timetabling, Delay Management, Mixed Integer Programming}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2022.7

Delay Management with Integrated Decisions on the Vehicle Circulations

Authors: Vera Grafe, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract

The task of delay management in public transport is to decide whether a vehicle should wait for a delayed vehicle in order to maintain the connection for transferring passengers. So far, the vehicle circulations are often ignored in the optimization process, although they have an influence on the propagation of the delay through the network. In this paper we consider different ways from literature to incorporate vehicle circulations in the delay management stage of public transport planning. Since the IP formulation for the integrated problem is hard to solve, we investigate bounds and develop several heuristics for the integrated problem. Our experiments on close-to real-world instances show that integrating delay management and decisions on vehicle circulations may reduce the overall delay by up to 39 percent. We also compare the runtimes and objective function values of the different heuristics. We conclude that we can find competitive solutions in a reasonable amount of time.

Cite as

Vera Grafe, Alexander Schiewe, and Anita Schöbel. Delay Management with Integrated Decisions on the Vehicle Circulations. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{grafe_et_al:OASIcs.ATMOS.2022.7,
  author =	{Grafe, Vera and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Delay Management with Integrated Decisions on the Vehicle Circulations}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{7:1--7:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.7},
  URN =		{urn:nbn:de:0030-drops-171119},
  doi =		{10.4230/OASIcs.ATMOS.2022.7},
  annote =	{Keywords: Public Transport, Delay Management, Vehicle Circulations, Integer Programming}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2022.9

The Edge Investment Problem: Upgrading Transit Line Segments with Multiple Investing Parties

Authors: Rowan Hoogervorst, Evelien van der Hurk, Philine Schiewe, Anita Schöbel, and Reena Urban

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract

Bus Rapid Transit (BRT) systems can provide a fast and reliable service to passengers at lower costs compared to tram, metro and train systems. Therefore, they can be of great value to attract more passengers to use public transport, which is vital in reaching the Paris Agreement Targets. However, the main advantage of BRT systems, namely their flexible implementation, also leads to the risk that the system is only implemented partially to save costs. This paper focuses therefore on the Edge Investment Problem: Which edges (segments) of a bus line should be upgraded to full-level BRT? Motivated by the construction of a new BRT line around Copenhagen, we consider a setting in which multiple parties are responsible for different segments of the line. Each party has a limited budget and can adjust its investments according to the benefits provided to its passengers. We suggest two ways to determine the number of newly attracted passengers, prove that the corresponding problems are NP-hard and identify special cases that can be solved in polynomial time. In addition, problem relaxations are presented that yield dual bounds. Moreover, we perform an extensive numerical comparison in which we evaluate the extent to which these two ways of modeling demand impact the computational performance and the choice of edges to be upgraded.

Cite as

Rowan Hoogervorst, Evelien van der Hurk, Philine Schiewe, Anita Schöbel, and Reena Urban. The Edge Investment Problem: Upgrading Transit Line Segments with Multiple Investing Parties. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hoogervorst_et_al:OASIcs.ATMOS.2022.9,
  author =	{Hoogervorst, Rowan and van der Hurk, Evelien and Schiewe, Philine and Sch\"{o}bel, Anita and Urban, Reena},
  title =	{{The Edge Investment Problem: Upgrading Transit Line Segments with Multiple Investing Parties}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{9:1--9:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.9},
  URN =		{urn:nbn:de:0030-drops-171137},
  doi =		{10.4230/OASIcs.ATMOS.2022.9},
  annote =	{Keywords: Network Design, Public Transport, Bus Rapid Transit, Modeling}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2021.3

Towards Improved Robustness of Public Transport by a Machine-Learned Oracle

Authors: Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

The design and optimization of public transport systems is a highly complex and challenging process. Here, we focus on the trade-off between two criteria which shall make the transport system attractive for passengers: their travel time and the robustness of the system. The latter is time-consuming to evaluate. A passenger-based evaluation of robustness requires a performance simulation with respect to a large number of possible delay scenarios, making this step computationally very expensive. For optimizing the robustness, we hence apply a machine-learned oracle from previous work which approximates the robustness of a public transport system. We apply this oracle to bi-criteria optimization of integrated public transport planning (timetabling and vehicle scheduling) in two ways: First, we explore a local search based framework studying several variants of neighborhoods. Second, we evaluate a genetic algorithm. Computational experiments with artificial and close to real-word benchmark datasets yield promising results. In all cases, an existing pool of solutions (i.e., public transport plans) can be significantly improved by finding a number of new non-dominated solutions, providing better and different trade-offs between robustness and travel time.

Cite as

Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Towards Improved Robustness of Public Transport by a Machine-Learned Oracle. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mullerhannemann_et_al:OASIcs.ATMOS.2021.3,
  author =	{M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Towards Improved Robustness of Public Transport by a Machine-Learned Oracle}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{3:1--3:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.3},
  URN =		{urn:nbn:de:0030-drops-148721},
  doi =		{10.4230/OASIcs.ATMOS.2021.3},
  annote =	{Keywords: Public Transportation, Timetabling, Machine Learning, Robustness}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2021.6

A Phase I Simplex Method for Finding Feasible Periodic Timetables

Authors: Marc Goerigk, Anita Schöbel, and Felix Spühler

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

The periodic event scheduling problem (PESP) with various applications in timetabling or traffic light scheduling is known to be challenging to solve. In general, it is already NP-hard to find a feasible solution. However, depending on the structure of the underlying network and the values of lower and upper bounds on activities, this might also be an easy task. In this paper we make use of this property and suggest phase I approaches (similar to the well-known phase I of the simplex algorithm) to find a feasible solution to PESP. Given an instance of PESP, we define an auxiliary instance for which a feasible solution can easily be constructed, and whose solution determines a feasible solution of the original instance or proves that the original instance is not feasible. We investigate different possibilities on how such an auxiliary instance can be defined theoretically and experimentally. Furthermore, in our experiments we compare different solution approaches for PESP and their behavior in the phase I approach. The results show that this approach can be especially helpful if the instance admits a feasible solution, while it is generally outperformed by classic mixed-integer programming formulations when the instance is infeasible.

Cite as

Marc Goerigk, Anita Schöbel, and Felix Spühler. A Phase I Simplex Method for Finding Feasible Periodic Timetables. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2021.6,
  author =	{Goerigk, Marc and Sch\"{o}bel, Anita and Sp\"{u}hler, Felix},
  title =	{{A Phase I Simplex Method for Finding Feasible Periodic Timetables}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{6:1--6:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.6},
  URN =		{urn:nbn:de:0030-drops-148753},
  doi =		{10.4230/OASIcs.ATMOS.2021.6},
  annote =	{Keywords: train timetable optimization, periodic event scheduling problem, modulo simplex}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2021.9

Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks

Authors: Vera Grafe and Anita Schöbel

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

The periodic event scheduling problem (PESP) is a well researched problem used for finding good periodic timetables in public transport. While it is based on a periodic network consisting of events and activities which are repeated every period, we propose a new periodic timetabling model using a non-periodic network. This is a first step towards the goal of integrating periodic timetabling with other planning steps taking place in the aperiodic network, e.g. passenger assignment or delay management. In this paper, we develop the new model, show how we can reduce its size and prove its equivalence to PESP. We also conduct computational experiments on close-to real-world data from Lower Saxony, a region in northern Germany, and see that the model can be solved in a reasonable amount of time.

Cite as

Vera Grafe and Anita Schöbel. Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{grafe_et_al:OASIcs.ATMOS.2021.9,
  author =	{Grafe, Vera and Sch\"{o}bel, Anita},
  title =	{{Solving the Periodic Scheduling Problem: An Assignment Approach in Non-Periodic Networks}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{9:1--9:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.9},
  URN =		{urn:nbn:de:0030-drops-148780},
  doi =		{10.4230/OASIcs.ATMOS.2021.9},
  annote =	{Keywords: Public Transport, Periodic Timetabling, PESP, Integer Programming}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2020.13

Cheapest Paths in Public Transport: Properties and Algorithms

Authors: Anita Schöbel and Reena Urban

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

Abstract

When determining the paths of the passengers in public transport, the travel time is usually the main criterion. However, also the ticket price a passenger has to pay is a relevant factor for choosing the path. The ticket price is also relevant for simulating the minimum income a public transport company can expect. However, finding the correct price depends on the fare system used (e.g., distance tariff, zone tariff with different particularities, application of a short-distance tariff, etc.) and may be rather complicated even if the path is already fixed. An algorithm which finds a cheapest path in a very general case has been provided in [R. Euler and R. Borndörfer, 2019], but its running time is exponential. In this paper, we model and analyze different fare systems, identify important properties they may have and provide polynomial algorithms for computing a cheapest path.

Cite as

Anita Schöbel and Reena Urban. Cheapest Paths in Public Transport: Properties and Algorithms. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{schobel_et_al:OASIcs.ATMOS.2020.13,
  author =	{Sch\"{o}bel, Anita and Urban, Reena},
  title =	{{Cheapest Paths in Public Transport: Properties and Algorithms}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{13:1--13: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.13},
  URN =		{urn:nbn:de:0030-drops-131499},
  doi =		{10.4230/OASIcs.ATMOS.2020.13},
  annote =	{Keywords: Public Transport, Fare Systems, Modeling, Cheapest Paths}
}

36 Search Results for "Schöbel, Anita"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message