Airline fleet assignment and schedule design : integrated models and algorithms

In scheduled passenger air transportation, airline profitability is critically influenced by the airline's ability to construct flight schedules containing flights at desirable times in profitable markets. In this dissertation, we study two elements of the schedule generation process, namely, schedule design and fleet assignment. The schedule design problem involves selecting an optimal set of flight legs to be included in the schedule, while the fleet assignment problem involves assigning aircraft types (or fleets) to flight legs to maximize revenues and minimize operating costs simultaneously. With the fleet assignment problem, we investigate the issues of network effects, spill, and recapture. On a constrained flight leg in which demand exceeds capacity, some passengers are not accommodated, or spilled. When passengers travel on two or more constrained legs, flight leg interdependencies or network effects arise because spill can occur on any of these legs. In most basic fleet assignment models, simplistic modeling of network effects and recapture leads to sometimes severe, miscalculations of revenues. Recapture occurs when some of the spilled passengers are re-accommodated on alternate itineraries in the system. In this dissertation, we develop new fleet assignment models that capture network effects, spill, and recapture. Another benefit of one of our models is its tractability and potential for further integration with other schedule planning steps.