28 Search Results for "Sch�bel, Anita"


Document
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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
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-dev.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}
}
Document
The Trickle-In Effect: Modeling Passenger Behavior in Delay Management

Authors: Anita Schöbel, Julius Pätzold, and Jörg P. Müller

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)


Abstract
Delay management is concerned with making decisions if a train should wait for passengers from delayed trains or if it should depart on time. Models for delay management exist and can be adapted to capacities of stations, capacities of tracks, or respect vehicle and driver schedules, passengers' routes and further constraints. Nevertheless, what has been neglected so far, is that a train cannot depart as planned if passengers from another train trickle in one after another such that the doors of the departing train cannot close. This effect is often observed in real-world, but has not yet been taken into account in delay management. We show the impact of this "trickle-in" effect to departure delays of trains under different conditions. We then modify existing delay management models to take the trickle-in effect into account. This can be done by forbidding certain intervals for departure. We present an integer programming formulation with these additional constraints resulting in a generalization of classic delay management models. We analyze the resulting model and identify parameters with which it can be best approximated by the classical delay management problem. Experimentally, we show that the trickle-in effect has a high impact on the overall delay of public transport systems. We discuss the impact of the trickle-in effect on the objective function value and on the computation time of the delay management problem. We also analyze the trickle-in effect for timetables which have been derived without taking this particular behavioral pattern of passengers into account.

Cite as

Anita Schöbel, Julius Pätzold, and Jörg P. Müller. The Trickle-In Effect: Modeling Passenger Behavior in Delay Management. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{schobel_et_al:OASIcs.ATMOS.2019.6,
  author =	{Sch\"{o}bel, Anita and P\"{a}tzold, Julius and M\"{u}ller, J\"{o}rg P.},
  title =	{{The Trickle-In Effect: Modeling Passenger Behavior in Delay Management}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{6:1--6:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.6},
  URN =		{urn:nbn:de:0030-drops-114187},
  doi =		{10.4230/OASIcs.ATMOS.2019.6},
  annote =	{Keywords: Public Transport Planning, Delay Management, Integer Programming}
}
Document
Robustness as a Third Dimension for Evaluating Public Transport Plans

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

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


Abstract
Providing attractive and efficient public transport services is of crucial importance due to higher demands for mobility and the need to reduce air pollution and to save energy. The classical planning process in public transport tries to achieve a reasonable compromise between service quality for passengers and operating costs. Service quality mostly considers quantities like average travel time and number of transfers. Since daily public transport inevitably suffers from delays caused by random disturbances and disruptions, robustness also plays a crucial role. While there are recent attempts to achieve delay-resistant timetables, comparably little work has been done to systematically assess and to compare the robustness of transport plans from a passenger point of view. We here provide a general and flexible framework for evaluating public transport plans (lines, timetables, and vehicle schedules) in various ways. It enables planners to explore several trade-offs between operating costs, service quality (average perceived travel time of passengers), and robustness against delays. For such an assessment we develop several passenger-oriented robustness tests which can be instantiated with parameterized delay scenarios. Important features of our framework include detailed passenger flow models, delay propagation schemes and disposition strategies, rerouting strategies as well as vehicle capacities. To demonstrate possible use cases, our framework has been applied to a variety of public transport plans which have been created for the same given demand for an artificial urban grid network and to instances for long-distance train networks. As one application we study the impact of different strategies to improve the robustness of timetables by insertion of supplement times. We also show that the framework can be used to optimize waiting strategies in delay management.

Cite as

Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Robustness as a Third Dimension for Evaluating Public Transport Plans. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:OASIcs.ATMOS.2018.4,
  author =	{Friedrich, Markus and M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Robustness as a Third Dimension for Evaluating Public Transport Plans}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.4},
  URN =		{urn:nbn:de:0030-drops-97097},
  doi =		{10.4230/OASIcs.ATMOS.2018.4},
  annote =	{Keywords: robustness, timetabling, vehicle schedules, delays}
}
Document
Cost-Minimal Public Transport Planning

Authors: Julius Pätzold, Alexander Schiewe, and Anita Schöbel

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


Abstract
In this paper we discuss what a cost-optimal public transport plan looks like, i.e., we determine a line plan, a timetable and a vehicle schedule which can be operated with minimal costs while, at the same time, allowing all passengers to travel between their origins and destinations. We are hereby interested in an exact solution of the integrated problem. In contrast to a passenger-optimal transport plan, in which there is a direct connection for every origin-destination pair, the structure or model for determining a cost-optimal transport plan is not obvious and has not been researched so far. We present three models which differ with respect to the structures we are looking for. If lines are directed and may contain circles, we prove that a cost-optimal schedule can (under weak assumptions) already be obtained by first distributing the passengers in a cost-optimal way. We are able to streamline the resulting integer program such that it can be applied to real-world instances. The model gives bounds for the general case. In the second model we look for lines operated in both directions, but allow only simplified vehicle schedules. This model then yields stronger bounds than the first one. Our most realistic model looks for lines operated in both directions, and allows all structures for the vehicle schedules. This model, however, is only computable for small instances. Finally, the results of the three models and their respective bounds are compared experimentally.

Cite as

Julius Pätzold, Alexander Schiewe, and Anita Schöbel. Cost-Minimal Public Transport Planning. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{patzold_et_al:OASIcs.ATMOS.2018.8,
  author =	{P\"{a}tzold, Julius and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Cost-Minimal Public Transport Planning}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{8:1--8:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.8},
  URN =		{urn:nbn:de:0030-drops-97138},
  doi =		{10.4230/OASIcs.ATMOS.2018.8},
  annote =	{Keywords: Public Transport Planning, Integer Optimization, Line Planning, Vehicle Scheduling}
}
Document
Integrating Passengers' Assignment in Cost-Optimal Line Planning

Authors: Markus Friedrich, Maximilian Hartl, Alexander Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)


Abstract
Finding a line plan with corresponding frequencies is an mportant stage of planning a public transport system. A line plan should permit all passengers to travel with an appropriate quality at appropriate costs for the public transport operator. Traditional line planning procedures proceed sequentially: In a first step a traffic assignment allocates passengers to routes in the network, often by means of a shortest path assignment. The resulting traffic loads are used in a second step to determine a cost-optimal line concept. It is well known that travel time of the resulting line concept depends on the traffic assignment. In this paper we investigate the impact of the assignment on the operating costs of the line concept. We show that the traffic assignment has significant influence on the costs even if all passengers are routed on shortest paths. We formulate an integrated model and analyze the error we can make by using the traditional approach and solve it sequentially. We give bounds on the error in special cases. We furthermore investigate and enhance three heuristics for finding an initial passengers’ assignment and compare the resulting line concepts in terms of operating costs and passengers’ travel time. It turns out that the costs of a line concept can be reduced significantly if passengers are not necessarily routed on shortest paths and that it is beneficial for the travel time and the costs to include knowledge on the line pool already in the assignment step.

Cite as

Markus Friedrich, Maximilian Hartl, Alexander Schiewe, and Anita Schöbel. Integrating Passengers' Assignment in Cost-Optimal Line Planning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:OASIcs.ATMOS.2017.5,
  author =	{Friedrich, Markus and Hartl, Maximilian and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Integrating Passengers' Assignment in Cost-Optimal Line Planning}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{5:1--5:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.5},
  URN =		{urn:nbn:de:0030-drops-79015},
  doi =		{10.4230/OASIcs.ATMOS.2017.5},
  annote =	{Keywords: Line Planning, Integrated Public Transport Planning, Integer Programming, Passengers' Routes}
}
Document
Robustness Tests for Public Transport Planning

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

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)


Abstract
The classical planning process in public transport planning focuses on the two criteria operating costs and quality for passengers. Quality mostly considers quantities like average travel time and number of transfers. Since public transport often suffers from delays caused by random disturbances, we are interested in adding a third dimension: robustness. We propose passenger-oriented robustness indicators for public transport networks and timetables. These robustness indicators are evaluated for several public transport plans which have been created for an artificial urban network with the same demand. The study shows that these indicators are suitable to measure the robustness of a line plan and a timetable. We explore different trade-offs between operating costs, quality (average travel time of passengers), and robustness against delays. Our results show that the proposed robustness indicators give reasonable results.

Cite as

Markus Friedrich, Matthias Müller-Hannemann, Ralf Rückert, Alexander Schiewe, and Anita Schöbel. Robustness Tests for Public Transport Planning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:OASIcs.ATMOS.2017.6,
  author =	{Friedrich, Markus and M\"{u}ller-Hannemann, Matthias and R\"{u}ckert, Ralf and Schiewe, Alexander and Sch\"{o}bel, Anita},
  title =	{{Robustness Tests for Public Transport Planning}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{6:1--6:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.6},
  URN =		{urn:nbn:de:0030-drops-78904},
  doi =		{10.4230/OASIcs.ATMOS.2017.6},
  annote =	{Keywords: robustness measure, timetabling, line planning, delays, passenger-orientation}
}
Document
Look-Ahead Approaches for Integrated Planning in Public Transportation

Authors: Julius Pätzold, Alexander Schiewe, Philine Schiewe, and Anita Schöbel

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)


Abstract
In this paper we deal with three consecutive planning stages in public transportation: Line planning (including line pool generation), timetabling, and vehicle scheduling. These three steps are traditionally performed one after another in a sequential way often leading to high costs in the (last) vehicle scheduling stage. In this paper we propose three different ways to "look ahead", i.e., to include aspects of vehicle scheduling already earlier in the sequential process: an adapted line pool generation algorithm, a new cost structure for line planning, and a reordering of the sequential planning stages. We analyze these enhancements experimentally and show that they can be used to decrease the costs significantly.

Cite as

Julius Pätzold, Alexander Schiewe, Philine Schiewe, and Anita Schöbel. Look-Ahead Approaches for Integrated Planning in Public Transportation. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{patzold_et_al:OASIcs.ATMOS.2017.17,
  author =	{P\"{a}tzold, Julius and Schiewe, Alexander and Schiewe, Philine and Sch\"{o}bel, Anita},
  title =	{{Look-Ahead Approaches for Integrated Planning in Public Transportation}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{17:1--17:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.17},
  URN =		{urn:nbn:de:0030-drops-78944},
  doi =		{10.4230/OASIcs.ATMOS.2017.17},
  annote =	{Keywords: line pool generation, line planning, vehicle scheduling, integrated planning, public transport}
}
Document
Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171)

Authors: Leo G. Kroon, Anita Schöbel, and Dorothea Wagner

Published in: Dagstuhl Reports, Volume 6, Issue 4 (2016)


Abstract
This report documents the talks and discussions at the Dagstuhl seminar 16171 “Algorithmic Methods for Optimization in Public Transport”. The seminar brought together researchers from algorithm, algorithm engineering, operations research, mathematical optimization and engineering, all interested in algorithms in public transportation. Also several practitioners were able to join the group and brought valuable insights on current practice and challenging problems.

Cite as

Leo G. Kroon, Anita Schöbel, and Dorothea Wagner. Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171). In Dagstuhl Reports, Volume 6, Issue 4, pp. 139-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@Article{kroon_et_al:DagRep.6.4.139,
  author =	{Kroon, Leo G. and Sch\"{o}bel, Anita and Wagner, Dorothea},
  title =	{{Algorithmic Methods for Optimization in Public Transport (Dagstuhl Seminar 16171)}},
  pages =	{139--160},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{4},
  editor =	{Kroon, Leo G. and Sch\"{o}bel, Anita and Wagner, Dorothea},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.4.139},
  URN =		{urn:nbn:de:0030-drops-66949},
  doi =		{10.4230/DagRep.6.4.139},
  annote =	{Keywords: delay and disruption management, dynamic passenger information, public transportation, resource scheduling, timetabling}
}
Document
A Matching Approach for Periodic Timetabling

Authors: Julius Pätzold and Anita Schöbel

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)


Abstract
The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard, but with important applications mainly for finding good timetables in public transportation. In this paper we consider PESP in public transportation, but in a reduced version (r-PESP) in which the driving and waiting times of the vehicles are fixed to their lower bounds. This results in a still NP-hard problem which has less variables, since only one variable determines the schedule for a whole line. We propose a formulation for r-PESP which is based on scheduling the lines. This enables us on the one hand to identify a finite candidate set and an exact solution approach. On the other hand, we use this formulation to derive a matching-based heuristic for solving PESP. Our experiments on close to real-world instances from LinTim show that our heuristic is able to compute competitive timetables in a very short runtime.

Cite as

Julius Pätzold and Anita Schöbel. A Matching Approach for Periodic Timetabling. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{patzold_et_al:OASIcs.ATMOS.2016.1,
  author =	{P\"{a}tzold, Julius and Sch\"{o}bel, Anita},
  title =	{{A Matching Approach for Periodic Timetabling}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.1},
  URN =		{urn:nbn:de:0030-drops-65251},
  doi =		{10.4230/OASIcs.ATMOS.2016.1},
  annote =	{Keywords: PESP, Timetabling, Public Transport, Matching, Finite Dominating Set}
}
  • Refine by Author
  • 28 Schöbel, Anita
  • 7 Schiewe, Alexander
  • 5 Müller-Hannemann, Matthias
  • 4 Goerigk, Marc
  • 4 Pätzold, Julius
  • Show More...

  • Refine by Classification
  • 9 Applied computing → Transportation
  • 2 Applied computing → Operations research
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Theory of computation → Network optimization
  • 1 Mathematics of computing → Combinatorial optimization
  • Show More...

  • Refine by Keyword
  • 7 Public Transport
  • 5 Timetabling
  • 4 Integer Programming
  • 4 Line Planning
  • 4 timetabling
  • Show More...

  • Refine by Type
  • 28 document

  • Refine by Publication Year
  • 3 2006
  • 3 2010
  • 3 2016
  • 3 2017
  • 3 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail