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 schedulingproblem, in the context of North American railroads. Crew scheduling for North American railroads isvery different from that of European railroads, which has been well studied. The crew scheduling problemis to assign crew (train operators) to scheduled trains over a time horizon (generally a week) at minimalcost while honoring several operational and contractual requirements. Each North American Class Irailroad spends at least a billion dollars in crew costs annually and does not have any decision supportsystem 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. Wehave developed a network-flow based crew-optimization model that has applications in all levels ofdecision making in crew scheduling: tactical, planning, and strategy. Our network-flow model maps theassignment of crew to trains as the flow of crew on an underlying network where different crew types aremodeled as different commodities in this network. We formulate the crew assignment problem as aninteger-programming problem on this network, which allows this problem to be solved to optimality. Wealso 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. Wepresent very promising computational results of our algorithms on the data provided by a major NorthAmerican railroad. Our network flow model is likely to form a backbone for a decision-support systemfor crew scheduling.