Crew and Vehicle Rescheduling Based on a Network Flow Model and Its Application to a Railway Train Operation

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 "dierences between the new and original schedules", which is a significant criterion for the CRP/VRP, though taking these dierences into account is dicult for other related formula- tions based on the set partitioning/covering mod- els. Implementation of a prototype system for ve- hicle rescheduling showed that the model is also ef- fective for designing interactive operations between users and the computer system. The results of numer- ical experiments with real-world vehicle rescheduling data showed that the proposed method generated fea- sible 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 com- puter systems which would eectively support train recovery operations under strict time limitations.