Application of column generation for train-set scheduling problems with regular maintenance constraints

Akiyoshi Ohno, Tatsushi Nishi, Masahiro Inuiguchi, Satoru Takahashi, Kenji Ueda

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


In this paper, we propose a column generation for the train-set scheduling problem with regular maintenance constraints. The problem is to allocate the minimum train-set to the train operations required to operate a given train timetable. In the proposed method, a tight lower bound can be obtained from the continuous relaxation for Dantzig-Wolfe reformulation by column generation. The subproblem for the column generation is an elementary shortest path problem with resource constraints. A labeling algorithm is applied to solve the subproblem. In order to reduce the computational effort for solving subproblems, a new state space relaxation of the subproblem is developed in the labeling algorithm. An upper bound is computed by a heuristic algorithm. Computational results demonstrate the effectiveness of the proposed method.

Original languageEnglish
Pages (from-to)151-159+17
JournalIEEJ Transactions on Electronics, Information and Systems
Issue number1
Publication statusPublished - 2012
Externally publishedYes


  • Column generation
  • Combinatorial optimization
  • Labeling Algorithm
  • Set partitioning problem
  • Train-set scheduling

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Application of column generation for train-set scheduling problems with regular maintenance constraints'. Together they form a unique fingerprint.

Cite this