Next generation algorithms for railroad crew and locomotive scheduling

Our research concerns optimal railroad crew and locomotive management. Crew scheduling entails assigning crews to trains while complying with union rules, so that the crew costs are minimal and train delays due to crew unavailability are minimized. Locomotive scheduling ensures the correct number and type of locomotives are attached to each train such that a train has sufficient pulling power while satisfying a variety of business constraints and minimizing locomotive costs. Locomotive routing involves routing each locomotive unit on a cyclic sequence of trains so that it can be fueled and serviced as necessary. These problems are difficult to solve NP-Complete problems and the North American locomotive and crew scheduling problems have not yet been solved satisfactorily. However, solving these problems has the potential to save railroads several million dollars a year.;First, we examine the North American railroad crew scheduling problem (CSP). We develop a network-flow based crew-optimization model and design efficient algorithms using problem decomposition and relaxation techniques. Next, we extend the earlier attempts to solve the locomotive planning problem (LPP) on several dimensions by considering new constraints desired by locomotive directors. We develop additional formulations necessary to transition solutions of our models to practice and report computational tests of these models on the data provided to us by a major US railroad. Next, we study the locomotive routing problem (LRP). The LRP is a very large-scale combinatorial optimization problem and has previously been unstudied and unsolved. We formulate the LRP as an integer programming problem on a suitably constructed space-time network and develop fast aggregation-disaggregation based methods to solve this problem. Finally, we study the multicommodity flow problem (MCFP). MCFPs have found application in wide variety of domains. The LPP and the CSP are indeed special cases of the MCFP. However, the integer version of this problem is NP-Complete. We propose a novel aggregation-disaggregation framework to solve a class of large-scale integer MCFPs.