Airline operations recovery: An optimization approach.

摘要

In the real world, an airline schedule does not operate as planned. It is often disrupted by maintenance problems or severe weather conditions. In a typical day several flights may be delayed or cancelled, and aircraft and crews may miss the rest of their assigned flights. Most of the work for this dissertation work focussed on the problem of crew recovery. However, it is apparent that crew rescheduling is only part of the big and complex picture that an airline coordinator is faced with. The crew problem cannot be solved satisfactorily if dealt with in isolation from the problem of reassigning aircraft. To address this issue we also present a new framework for integrated recovery.; We first formulate the Airline Integrated Recovery problem. Initial formulations had three large parts corresponding to crew assignment, aircraft routing, and passenger flow. Linking these parts seems to lend to very large problems that would be intractable even for small disruptions. A new decomposition scheme is proposed. Its novel feature is its master problem the Schedule Recovery Model. It provides a cancellation and delay plan that satisfies imposed landing restrictions and assigns equipment type. Once this master problem is solved, the three problems for crew, aircraft, and passengers decouple. The operational plan for each equipment type is formulated in two separate subproblems, an Aircraft Recovery Model and a Crew Recovery Model. Either an aircraft and a crew are found for each flight leg or the flight is cancelled. A Passenger Flow subproblem then finds new itineraries for disrupted passengers. The solution algorithm is derived by applying Benders' decomposition algorithm to a mixed-integer linear programming formulation for the problem.; In the second part of this dissertation, we present our work on crew recovery. We develop a computational framework for solving the Crew Recovery Model, the hardest subproblem of the Airline Integrated Recovery problem due to complex crew pairing legality rules that govern generation of new pairings and the huge number of potential pairings. Preprocessing techniques are applied to extract a subset of the schedule for rescheduling. A fast crew pairing generator is built that enumerates feasible continuations of partially flown crew trips. The primal-dual subproblem simplex method is used to solve a linear relaxation of a huge set covering problem. Several branching strategies are presented that allow fast generation of integer solutions. Computational results using a schedule from a major air carrier are presented.