Integer programming approaches are applicable to crew scheduling problems in many transportation fields including train crew scheduling problems, by modeling them to set covering/partitioning problems. However, an efficient solution for a certain scheduling problem may not be applicable to another problem. The main issue is the development of an appropriate solution method with the consideration on the features of the problem. For train crew scheduling problems, we propose a crew path enumeration algorithm that extracts candidates of the crew path based on the reduced cost of each task transition obtained by solving its relaxation problem, and present efficiency of the algorithm.

Copyright (c) 2006 Railway Technical Research Institute