License
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2008.1588
URN: urn:nbn:de:0030-drops-15884
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1588/
Go to the corresponding OASIcs Volume Portal


Nachtigall, Karl ; Opitz, Jens

Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations

pdf-format:
Document 1.pdf (294 KB)


Abstract

In the last 15 years periodic timetable problems have found much interest in the combinatorial optimization community. We will focus on the optimisation task to minimise a weighted sum of undesirable slack times. This problem can be formulated as a mixed integer linear problem, which for real world instances is hard to solve. This is mainly caused by the integer variables, the so-called modulo parameter. At first we will discuss some results on the polyhedral structure of the periodic timetable problem. These ideas allow to define a modulo simplex basic solution by calculating the basic variables from modulo equations. This leads to a modulo network simplex method, which iteratively improves the solution by changing the simplex basis.

BibTeX - Entry

@InProceedings{nachtigall_et_al:OASIcs:2008:1588,
  author =	{Karl Nachtigall and Jens Opitz},
  title =	{{Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) },
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Matteo Fischetti and Peter Widmayer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1588},
  URN =		{urn:nbn:de:0030-drops-15884},
  doi =		{http://dx.doi.org/10.4230/OASIcs.ATMOS.2008.1588},
  annote =	{Keywords: Periodic event scheduling problem, integer programming, modulo network simplex}
}

Keywords: Periodic event scheduling problem, integer programming, modulo network simplex
Seminar: 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)
Issue Date: 2008
Date of publication: 24.09.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI