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.2015.97
URN: urn:nbn:de:0030-drops-54524
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5452/
Go to the corresponding OASIcs Volume Portal

Fischer, Frank

Ordering Constraints in Time Expanded Networks for Train Timetabling Problems

pdf-format:
3.pdf (1 MB)

Abstract

The task of the train timetabling problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. This kind of problem has proven to be very challenging and numerous solution approaches have been proposed. One of the most successful approaches is based on time discretized network models. However, one of the major weaknesses of these models is that fractional solutions tend to change the order of trains along some track, which is not allowed for integer solutions, leading to poor relaxations. In this paper, we present an extension for these kind of models, which aims at overcoming these problems. By exploiting a configuration based formulation, we propose to extend the model with additional ordering constraints. These constraints enforce compatibility of orderings along a sequence of tracks and greatly improve the quality of the relaxations. We show in some promising preliminary computational experiments that our approach indeed helps to resolve many of the invalid overtaking problems of relaxations
for the standard models.

BibTeX - Entry

@InProceedings{fischer:OASIcs:2015:5452,
  author =	{Frank Fischer},
  title =	{{Ordering Constraints in Time Expanded Networks for Train Timetabling Problems}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{97--110},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5452},
  URN =		{urn:nbn:de:0030-drops-54524},
  doi =		{10.4230/OASIcs.ATMOS.2015.97},
  annote =	{Keywords: combinatorial optimization, train timetabling, Lagrangian relaxation, ordering constraints}
}

Keywords: combinatorial optimization, train timetabling, Lagrangian relaxation, ordering constraints
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

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