Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14469
For citation please use:
Main Title: Strong formulations for the Multi-module PESP and a quadratic algorithm for Graphical Diophantine Equation Systems
Author(s): Galli, Laura
Stiller, Sebastian
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15696
http://dx.doi.org/10.14279/depositonce-14469
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: The Periodic Event Scheduling Problem (PESP) is the method of choice for real-world periodic timetabling in public transport. Its MIP formulation has been studied intensely for the case of uniform modules, i.e., when all events have the same period. In practice, multiple modules are equally important. The strength of current methods for uniform modules rests on three ingredients: Every feasible instance allows for an optimal solution with a certain structure. Therefore, it can be reformulated with the use of an integral cycle basis. Finally, a certain type of rounding cuts arising from cycles has proven very powerful. All of this fails in the multi-module case. Therefore, applications with multiple periods were hardly solvable so far. We analyze a certain type of Diophantine equation systems closely related to the multi-module PESP. Thereby, we identify a structure, so-called sharp trees, that allows to solve the system in O (n^2) time. We show, a sharp tree is guaranteed to exist and found by a similar algorithm, if the modules form a linear lattice. Based on this we develop the machinery to solve multi-module PESPs on real-world scale. In particular, we recover all three ingredients for the multi-module case. In our computational results the new MIP-formulations drastically improve the solvability of multi-module PESPs. We also demonstrate that without sharp trees no similar approach can be hoped for.
Subject(s): integer programming
periodic event scheduling
diophantine equation systems
public transport
timetabling
Issue Date: 2010
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2010, 09
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-009-2010.pdf
Format: Adobe PDF | Size: 119.87 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.