Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.01.2015 | Regular Article | Ausgabe 1/2015

OR Spectrum 1/2015

A graph partitioning strategy for solving large-scale crew scheduling problems

Zeitschrift:
OR Spectrum > Ausgabe 1/2015
Autoren:
Silke Jütte, Ulrich W. Thonemann

Abstract

Railway crew scheduling deals with generating driver duties for a given train timetable such that all work regulations are met and the resulting schedule has minimal cost. Typical problem instances in the freight railway industry require the generation of duties for thousands of drivers operating tens of thousands of trains per week. Due to short runtime requirements, common solution approaches decompose the optimization problem into smaller subproblems that are solved separately. Several studies have shown that the way of decomposing the problem significantly affects the solution quality. An overall best decomposition strategy for a freight railway crew scheduling problem, though, is not known. In this paper, we present general considerations on when to assign two scheduled train movements to separate subproblems (and when to rather assign them to the same subproblem) and deduct a graph partitioning based decomposition algorithm with several variations. Using a set of real-world problem instances from a major European railway freight carrier, we evaluate our strategy and benchmark the performance of the decomposition algorithm both against a common non-decomposition algorithm and a lower bound on the optimal solution schedule. The test runs show that our decomposition algorithm is capable of producing high-quality solution schedules while significantly cutting runtimes compared to the non-decomposition solution algorithm. We are following a ”greenfield” approach, where no information on previous schedules is needed. Hence, our approach is applicable to any railway crew scheduling setting, including network enlargement, integration of new customers, etc.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2015

OR Spectrum 1/2015 Zur Ausgabe

Premium Partner

    Bildnachweise