Integer Programming Based Approaches for the Railroad Line Scheduling and Capacity Planning Problems

by

Guvenc Sahin
University of Florida

We study a group of line and terminal planning problems for railroads. Our research focuses on a set of complex scheduling and sequencing problems as well as their counterparts at the strategic level. In this talk, the train dispatching problem and its strategic counterpart known as the line-capacity planning problem are discussed in detail. The solution methods are based on the network representation of the problem and its integer programming formulation. We provide an integer programming formulation that generalizes all special cases of the problem studied earlier and handles realistic constraints that have not been previously considered. Based on the integer programming formulation, we develop heuristic methods that find high-quality solutions for real-life problems. Our modeling approach is also applicable to a wide range of job scheduling problems with ready times and due dates.