|
Network flow-based approaches to the railroad crew–scheduling problem B. Vaidyanathan, K.C. Jha, and R.K. Ahuja, IBM Journal of Research & Development 51, 325-344. 2007 We study the crew–scheduling problem of North American railroads (which is very different from that of European railroads, which has been well studied). The problem is to assign train operators to scheduled trains over a time horizon (generally a week) at minimal cost, while honoring several operational and contractual requirements. We have developed a network-flow-based crew-optimization model that has applications at all levels of decision making in crew scheduling. Our network-flow model maps the assignment of crew to trains as the flow of crew on an underlying network where different crew types are modeled as different commodities in this network. We formulate the crew assignment problem as an integer-programming problem on this network, which allows the problem to be solved to optimality. We also develop several highly efficient algorithms using problem decomposition and relaxation techniques, where we use the special structure of the underlying network model to obtain significant speed-ups. We present very promising computational results of our algorithms on the data provided by a major North American railroad. |