Search Results

Documents authored by Lindner, Niels

Document
DOI: 10.4230/OASIcs.ATMOS.2024.4
Periodic Event Scheduling with Flexible Infrastructure Assignment

Authors: Enrico Bortoletto, Rolf Nelson van Lieshout, Berenike Masing, and Niels Lindner

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

Abstract
We present novel extensions of the Periodic Event Scheduling Problem (PESP) that integrate the assignment of activities to infrastructure elements. An application of this is railway timetabling, as station and platform capacities are limited and need to be taken into account. We show that an assignment of activities to platforms can always be made periodic, and that it can be beneficial to allow larger periods for the assignment than for the timetable. We present mixed-integer programming formulations for the general problem, as well as for the practically relevant case when multiple platforms can be considered equivalent, for which we present a bipartite matching approach. We finally test and compare these models on real-world instances.
Cite as

Enrico Bortoletto, Rolf Nelson van Lieshout, Berenike Masing, and Niels Lindner. Periodic Event Scheduling with Flexible Infrastructure Assignment. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2024.4,
  author =	{Bortoletto, Enrico and van Lieshout, Rolf Nelson and Masing, Berenike and Lindner, Niels},
  title =	{{Periodic Event Scheduling with Flexible Infrastructure Assignment}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{4:1--4:18},
  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.4},
  URN =		{urn:nbn:de:0030-drops-211929},
  doi =		{10.4230/OASIcs.ATMOS.2024.4},
  annote =	{Keywords: Periodic Event Scheduling, Periodic Timetabling, Railway Timetabling, Matchings, Infrastructure Assignments, Platform Assignments, Station Capacities}
}
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.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.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
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2022
OASIcs, Volume 106, ATMOS 2022, Complete Volume

Authors: Mattia D'Emidio and Niels Lindner

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

Abstract
OASIcs, Volume 106, ATMOS 2022, Complete Volume
Cite as

22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1-240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{demidio_et_al:OASIcs.ATMOS.2022,
  title =	{{OASIcs, Volume 106, ATMOS 2022, Complete Volume}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{1--240},
  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},
  URN =		{urn:nbn:de:0030-drops-171036},
  doi =		{10.4230/OASIcs.ATMOS.2022},
  annote =	{Keywords: OASIcs, Volume 106, ATMOS 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Mattia D'Emidio and Niels Lindner

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

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

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

Copy BibTex To Clipboard

@InProceedings{demidio_et_al:OASIcs.ATMOS.2022.0,
  author =	{D'Emidio, Mattia and Lindner, Niels},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{0:i--0:x},
  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.0},
  URN =		{urn:nbn:de:0030-drops-171040},
  doi =		{10.4230/OASIcs.ATMOS.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
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.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.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}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.7
Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data

Authors: Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe

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

Abstract
We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.
Cite as

Niels Lindner, Pedro Maristany de las Casas, and Philine Schiewe. Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.7,
  author =	{Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine},
  title =	{{Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{7:1--7:15},
  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.7},
  URN =		{urn:nbn:de:0030-drops-148767},
  doi =		{10.4230/OASIcs.ATMOS.2021.7},
  annote =	{Keywords: Preprocessing Shortest Path Problems, Interval Data, Graph Algorithms}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.5
Determining All Integer Vertices of the PESP Polytope by Flipping Arcs

Authors: Niels Lindner and Christian Liebchen

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

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

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

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2020.5,
  author =	{Lindner, Niels and Liebchen, Christian},
  title =	{{Determining All Integer Vertices of the PESP Polytope by Flipping Arcs}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{5:1--5:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.5},
  URN =		{urn:nbn:de:0030-drops-131411},
  doi =		{10.4230/OASIcs.ATMOS.2020.5},
  annote =	{Keywords: Periodic Event Scheduling Problem, Periodic Timetabling, Mixed Integer Programming}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2019.2
New Perspectives on PESP: T-Partitions and Separators

Authors: Niels Lindner and Christian Liebchen

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

Abstract
In the planning process of public transportation companies, designing the timetable is among the core planning steps. In particular in the case of periodic (or cyclic) services, the Periodic Event Scheduling Problem (PESP) is well-established to compute high-quality periodic timetables. We are considering algorithms for computing good solutions and dual bounds for the very basic PESP with no additional extra features as add-ons. The first of these algorithms generalizes several primal heuristics that have been proposed, such as single-node cuts and the modulo network simplex algorithm. We consider partitions of the graph, and identify so-called delay cuts as a structure that allows to generalize several previous heuristics. In particular, when no more improving delay cut can be found, we already know that the other heuristics could not improve either. This heuristic already had been proven to be useful in computational experiments [Ralf Borndörfer et al., 2019], and we locate it in the more general concept of what we denote T-partitions. With the second of these algorithms we propose to turn a strategy, that has been discussed in the past, upside-down: Instead of gluing together the network line-by-line in a bottom-up way, we develop a divide-and-conquer-like top-down approach to separate the initial problem into two easier subproblems such that the information loss along their cutset edges is as small as possible. We are aware that there may be PESP instances that do not fit well the separator setting. Yet, on the RxLy-instances of PESPlib in our experimental computations, we come up with good primal solutions and dual bounds. In particular, on the largest instance (R4L4), this new separator approach, which applies a state-of-the-art solver as subroutine, is able to come up with better dual bounds than purely applying this state-of-the-art solver in the very same time.
Cite as

Niels Lindner and Christian Liebchen. New Perspectives on PESP: T-Partitions and Separators. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lindner_et_al:OASIcs.ATMOS.2019.2,
  author =	{Lindner, Niels and Liebchen, Christian},
  title =	{{New Perspectives on PESP: T-Partitions and Separators}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{2:1--2:18},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.2},
  URN =		{urn:nbn:de:0030-drops-114144},
  doi =		{10.4230/OASIcs.ATMOS.2019.2},
  annote =	{Keywords: Periodic Event Scheduling Problem, Periodic Timetabling, Graph Partitioning, Graph Separators, Balanced Cuts}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2018.16
A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable

Authors: Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner

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

Abstract
We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it? In [Julius Paetzold et al., 2017], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem. In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.
Cite as

Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner. A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2018.16,
  author =	{Bornd\"{o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels},
  title =	{{A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{16:1--16:15},
  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.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.16},
  URN =		{urn:nbn:de:0030-drops-97214},
  doi =		{10.4230/OASIcs.ATMOS.2018.16},
  annote =	{Keywords: Vehicle Scheduling, Periodic Timetabling, Bipartite Matching}
}
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