Topics in airline crew scheduling and large-scale optimization.

摘要

Airline operations research is a well studied area due to its large impact on revenue. The problems of assigning equipment types, aircraft and crew itineraries to flights are crucial since a slight improvement in a solution value can yield millions of dollars in savings. The focus of this dissertation is to improve on existing solution methodologies in planning of an airline and to partially integrate the assignment problems cited above.; The main topic of the dissertation is airline crew scheduling, the problem of assigning crew itineraries to flights. We develop a new methodology for solving crew scheduling problems. The approach uses parallel computing techniques and algorithms and hence is implemented in parallel and run on a cluster of personal computers. We present a parallel random itinerary generator and a parallel solver for large scale linear programs. The results obtained are very encouraging.; We develop a parallel primal-dual simplex algorithm that is capable of solving linear programs with at least an order of magnitude more columns than the previous work. The algorithm repeatedly solves several linear programs in parallel and combines the dual solutions to obtain a new dual feasible solution. The primal part of the algorithm involves a new randomized pricing strategy. We tested the algorithm on instances with thousands of rows and tens of millions of columns.; Part of the dissertation deals with partially integrating schedule planning, aircraft assignment, and crew scheduling. We solve a crew scheduling problem with additional constraints that preserve the plane count and we assume we are allowed to slightly change the departure times. We improve on the existing crew scheduling solutions, on average, by a factor of two.; The last part of the dissertation focuses on a new methodology for solving the airline crew scheduling problem over the weekly horizon. We introduce a second objective, called regularity. Regularity measures the repetition rate of crew itineraries. New models are developed that address the cost of a crew schedule and the regularity. The models produce huge integer programs and we present a methodology for solving them. Solutions are reported with low cost and high regularity.