New combinatorial approaches for solving railroad planning and scheduling problems

Railroads play an important role in freight transportation sector by providing efficient cost-effective service. Their planning processes pose challenging optimization problems involving strategic, tactical, and operational level decisions. Railroad optimization problems have been studied for more than forty years. The last decade has witnessed a significant progress in this area as railroads have started using operations research in their planning processes and experienced a substantial amount of cost savings as a result of their efforts.;We study the train dispatching problem and the yard operations problem from operational and tactical planning perspectives. For the train dispatching problem, we develop a novel network-flow representation of the problem. The associated integer programming formulation generalizes all previous works in addition to considering new practical constraints that have not been studied earlier. The approaches used for this problem are extended to study the railroad service design problems. These problems include the following tactical counterparts of the train dispatching problem: (i) train dispatching with variable train-speeds, (ii) addition of new train services to dispatching plans, and (iii) coordinated maintenance planning.;The yard operations problem includes several scheduling and resource allocation decisions. This study focuses on the hump sequencing problem, which is the most critical component of this problem. In studying the hump sequencing problem, we also introduce the stepwise tardiness scheduling criterion as a new scheduling criterion. We develop integer programming formulations of the corresponding single-machine scheduling problem, and propose approximation algorithms for this NP-complete problem. By managing their yard operations effectively, railroads aim to increase their yard capacities. Increasing yard capacities allows railroads to reduce their core transportation costs. We study the effects of yard capacities on the blocking plan by developing strong lower bounds. The techniques we propose also give strong lower bounds for the degree-constrained network design problem.;Main focus of this work is on railroad planning and scheduling; we develop solution methods for a set of railroad problems to find optimal and near-optimal solutions which are also implementable. Nonetheless, we also contribute to machine scheduling literature by introducing a new practically relevant scheduling criterion and to network design literature by developing strong lower bounds for the degree-constrained problems.