Crew and vehicle rescheduling based on a network flow model and its application to a railway train operation

Tatsuhiro Sato*, Shuichiro Sakikawa, Toyohisa Morita, Nobutaka Ueki, Tomohiro Muratay

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


For the crew rescheduling problem (CRP) and the vehicle rescheduling problem (VRP), we propose a 0-1 integer programming formulation based on a network flow model and a solution method that uses a heuristic flow modification and a local search technique. The proposed formulation is able to represent the "differences between the new and original schedules", which is a significant criterion for the CRP/VRP, though taking these differences into account is difficult for other related formulations based on the set partitioning/covering models. Implementation of a prototype system for vehicle rescheduling showed that the model is also effective for designing interactive operations between users and the computer system. The results of numerical experiments with real-world vehicle rescheduling data showed that the proposed method generated feasible solutions within a practical amount of time, and on the basis of a two-phase solution approach, the proposed method improved the evaluation values of the solution. This work could lead to practical computer systems which would effectively support train recovery operations under strict time limitations.

Original languageEnglish
JournalIAENG International Journal of Applied Mathematics
Issue number3
Publication statusPublished - 2009 Aug 1


  • Crew/vehicle rescheduling
  • Heuristics
  • Local search
  • Network flow model
  • Railway
  • Train operation

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Crew and vehicle rescheduling based on a network flow model and its application to a railway train operation'. Together they form a unique fingerprint.

Cite this