4 Search Results for "Masing, Berenike"

Document
DOI: 10.4230/OASIcs.ATMOS.2023.5
Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice

Authors: Berenike Masing, Niels Lindner, and Christian Liebchen

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

Abstract
We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances.
Cite as

Berenike Masing, Niels Lindner, and Christian Liebchen. Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{masing_et_al:OASIcs.ATMOS.2023.5,
  author =	{Masing, Berenike and Lindner, Niels and Liebchen, Christian},
  title =	{{Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{5:1--5:15},
  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.5},
  URN =		{urn:nbn:de:0030-drops-187669},
  doi =		{10.4230/OASIcs.ATMOS.2023.5},
  annote =	{Keywords: Periodic Timetabling, Line Planning, Track Choice, Mixed-Integer Programming, Construction Sites, Railway Rescheduling}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.7
Periodic Timetabling with Cyclic Order Constraints

Authors: Enrico Bortoletto, Niels Lindner, and Berenike Masing

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

Abstract
Periodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful.
Cite as

Enrico Bortoletto, Niels Lindner, and Berenike Masing. Periodic Timetabling with Cyclic Order Constraints. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2023.7,
  author =	{Bortoletto, Enrico and Lindner, Niels and Masing, Berenike},
  title =	{{Periodic Timetabling with Cyclic Order Constraints}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{7:1--7:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.7},
  URN =		{urn:nbn:de:0030-drops-187689},
  doi =		{10.4230/OASIcs.ATMOS.2023.7},
  annote =	{Keywords: Periodic Timetabling, Railway Timetabling, Periodic Event Scheduling Problem, Cyclic Orders, Mixed-Integer Programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2022.3
Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling

Authors: Enrico Bortoletto, Niels Lindner, and Berenike Masing

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

Abstract
Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [Borndörfer et al., 2020]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [Bortoletto et al., 2022]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances.
Cite as

Enrico Bortoletto, Niels Lindner, and Berenike Masing. Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2022.3,
  author =	{Bortoletto, Enrico and Lindner, Niels and Masing, Berenike},
  title =	{{Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-171075},
  doi =		{10.4230/OASIcs.ATMOS.2022.3},
  annote =	{Keywords: Periodic Timetabling, Tropical Geometry, Neighborhood Search, Mixed-Integer Programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.2
Forward Cycle Bases and Periodic Timetabling

Authors: Niels Lindner, Christian Liebchen, and Berenike Masing

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

Abstract
Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance R1L1 of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.
Cite as

Niels Lindner, Christian Liebchen, and Berenike Masing. Forward Cycle Bases and Periodic Timetabling. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.2,
  author =	{Lindner, Niels and Liebchen, Christian and Masing, Berenike},
  title =	{{Forward Cycle Bases and Periodic Timetabling}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{2:1--2:14},
  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.2},
  URN =		{urn:nbn:de:0030-drops-148719},
  doi =		{10.4230/OASIcs.ATMOS.2021.2},
  annote =	{Keywords: Periodic Timetabling, Cycle Bases, Mixed Integer Programming}
}
  • Refine by Author
  • 4 Lindner, Niels
  • 4 Masing, Berenike
  • 2 Bortoletto, Enrico
  • 2 Liebchen, Christian

  • Refine by Classification
  • 4 Applied computing → Transportation
  • 3 Mathematics of computing → Combinatorial optimization
  • 2 Mathematics of computing → Integer programming
  • 1 Computing methodologies → Concurrent algorithms
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 4 Periodic Timetabling
  • 3 Mixed-Integer Programming
  • 1 Construction Sites
  • 1 Cycle Bases
  • 1 Cyclic Orders
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2023
  • 1 2021
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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