Solving real-life transportation scheduling problems

Transportation by railroads and airlines contains a rich set of optimization problems with substantial potential savings in transportation costs. In the past few decades, unfortunately, optimization models were not widely used in transportation industries, because of (i) the large size and tremendous complexity of these problems, (ii) the lack of suitable algorithmic approaches for solving them, and (iii) insufficient computing power available. However, as major advances have taken place in algorithm design, analysis and implementation, complemented by enhanced computer systems, transportation scheduling problems now appear to be tractable.; The goal of this dissertation is to study several real-life transportation scheduling problems that are of great importance for railroads and airlines. The related literatures of these problems have only dealt with simplified models or small instances failing to incorporate the characteristic of real-life applications. In Chapter 2, we present an integrated model for the locomotive scheduling problem. In Chapter 3, we propose two approaches to solve the railroad blocking problem. In Chapters 4 and 5, we study extensions and generalizations of combined through and fleet assignment models. The focus of this dissertation is to model these problems with realistic constraints and solve the real-life instances of those models with modern optimization techniques. The major solution approaches developed in this dissertation are based on Very Large Scale Neighborhood (VLSN) search, which is a heuristic approach but works very well for real-life instances. The computational tests for those problems are performed on real-life data from major U.S. transportation carriers. The results reveal that the models and solution approaches developed in this dissertation are practically implementable and capable of generating significant economic impact on transportation industries.