Two-level decomposition algorithm for crew rostering problems with fair working condition

doi:10.1016/j.ejor.2014.02.010

Return

Two-level decomposition algorithm for crew rostering problems with fair working condition

2014-09-01

PRE

Tatsushi Nishi *

Taichi Sugiyama

Masahiro Inuiguchi

DOI：10.1016/j.ejor.2014.02.010

Original

Original request for help

Save

Abstract

En 中文

A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments. (C) 2014 Elsevier B.V. All rights reserved.

Keywords:

Railway scheduling

Crew rostering

Two-level decomposition algorithm

Cut generation

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.