License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2019.2
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11414/
Go to the corresponding OASIcs Volume Portal

Lindner, Niels ; Liebchen, Christian

New Perspectives on PESP: T-Partitions and Separators

pdf-format:
OASIcs-ATMOS-2019-2.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{lindner_et_al:OASIcs:2019:11414,
  author =	{Niels Lindner and Christian Liebchen},
  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 =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Valentina Cacchiani and Alberto Marchetti-Spaccamela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11414},
  doi =		{10.4230/OASIcs.ATMOS.2019.2},
  annote =	{Keywords: Periodic Event Scheduling Problem, Periodic Timetabling, Graph Partitioning, Graph Separators, Balanced Cuts}
}

Keywords: Periodic Event Scheduling Problem, Periodic Timetabling, Graph Partitioning, Graph Separators, Balanced Cuts
Collection: 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Issue Date: 2019
Date of publication: 15.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI