Ship and Airline Scheduling - a Model, Its Application and Development

Abstract

This thesis considers airline and ship scheduling. It was initially motivated by seven years spent in the National Airways Corporate Planning Department and the subsequent realization that each industry tends to see its own craft scheduling problem as unique. The early part of the work centres around a general scheduling model and four methods for solving it. Discoveries made there led to a refined application of Benders’ Decomposition to airline scheduling and to a computer based system for multi- commodity, multi-vessel ship scheduling. Section one gives an introduction to the thesis. The second section reviews ship and airline schedule construction, dividing the latter into sequential (step wise) and direct methods. It is observed that scheduling research in each area tends to be independent of advances made in similar fields. The areas where further research is needed are identified. The third section defines a general linear model in the ‘direct’ category and uses it to explore the relationship between numbers of variables carried in a master problem and solution optimality. Four methods are considered for solving such a model. These methods are either developed to explore the above relationship or are methods that have proven useful on similar problems. These include Lagrangian Relaxation and Benders’ Decomposition. An appendix gives a constraint aggregation method for solving integer LP problems which arose as a by-product of this research. The fourth section considers airline schedule construction and shows how Bender’s Decomposition may be effectively adapted to the problem of choosing a schedule from a set provided (using the integer master problem) and having it judged by a passenger assignment subroutine. The section shows how the structure of the formulation leads to a very simple algorithm for the integer master problem. The passenger assignment model need not be a continuous LP. Section five details a ship scheduling system developed for multi-product oil distribution. The system is modular in construction, leading to a set of ship schedules. A subset of these are judged by a product distribution module until the optimum ship and product (cost) schedule is found. Notable achievements include: - a simplex pivot control method, which represents the requirement that a schedule selection decision variable must be integer by a set of linear equations; - a novel use of Lagrangian Relaxation, to determine the number of craft schedules that are needed in an arc-chain formulation of the general model to guarantee an optimal solution; - a constraint aggregation scheme for solving integer LP problems; - the Bender’s Decomposition refinements for airline scheduling, mentioned earlier; and - the first published system for multi-commodity, multi-fleet ship scheduling.