Multi-Commodity Network Flow Based Approaches for the Railroad Crew Scheduling Problem

In this paper, we study one of the most important railroad optimization problems, the crew scheduling problem, in the context of North American railroads. Crew scheduling for North American railroads is very different from that of European railroads, which has been well studied. The crew scheduling problem is to assign crew (train operators) to scheduled trains over a time horizon (generally a week) at minimal cost while honoring several operational and contractual requirements. Each North American Class I railroad spends at least a billion dollars in crew costs annually and does not have any decision support system available that can assist it in all levels of decision making: tactical, planning, and strategy. Indeed, all decisions related to crew are made manually, thereby leaving sufficient room for improvement. We have developed a network-flow based crew-optimization model that has applications in all levels of decision making in crew scheduling: tactical, planning, and strategy. 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 this 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. Our network flow model is likely to form a backbone for a decision-support system for crew scheduling.