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.2020.7
URN: urn:nbn:de:0030-drops-131438
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13143/
Go to the corresponding OASIcs Volume Portal

Breugem, Thomas ; Dollevoet, Twan ; Huisman, Dennis

Analyzing a Family of Formulations for Cyclic Crew Rostering

pdf-format:
OASIcs-ATMOS-2020-7.pdf (0.4 MB)

Abstract

In this paper, we analyze a family of formulations for the Cyclic Crew Rostering Problem (CCRP), in which a cyclic roster has to be constructed for a group of employees. Each formulation in the family is based on a partition of the roster. Intuitively, finer partitions give rise to a formulation with fewer variables, but possibly more constraints. Coarser partitions lead to more variables, but might allow to incorporate many of the constraints implicitly. We derive analytical results regarding the relative strength of the different formulations, which can serve as a guideline for formulating a given problem instance. Furthermore, we propose a column generation approach, and use it to compare the strength of the formulations empirically. Both the theoretical and computational results demonstrate the importance of choosing a suitable formulation. In particular, for practical instances of Netherlands Railways, stronger lower bounds are obtained, and more than 90% of the roster constraints can be modeled implicitly.

BibTeX - Entry

@InProceedings{breugem_et_al:OASIcs:2020:13143,
  author =	{Thomas Breugem and Twan Dollevoet and Dennis Huisman},
  title =	{{Analyzing a Family of Formulations for Cyclic Crew Rostering}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{7:1--7:16},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Dennis Huisman and Christos D. Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13143},
  URN =		{urn:nbn:de:0030-drops-131438},
  doi =		{10.4230/OASIcs.ATMOS.2020.7},
  annote =	{Keywords: Crew Planning, Roster Sequence, Column Generation, Railway Optimization}
}

Keywords: Crew Planning, Roster Sequence, Column Generation, Railway Optimization
Collection: 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Issue Date: 2020
Date of publication: 10.11.2020

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