The fleet assignment problem: Solving a large-scale integer program |
| |
Authors: | Christopher A. Hane Cynthia Barnhart Ellis L. Johnson Roy E. Marsten George L. Nemhauser Gabriele Sigismondi |
| |
Affiliation: | (1) School of Industrial and Systems Engineering, Georgia Institute of Technology, 30332-0205 Atlanta, GA, United States |
| |
Abstract: | Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.This work was supported by NSF and AFORS grant DDM-9115768 and NSF grant SES-9122674.Corresponding author. |
| |
Keywords: | Linear programming Mixed-integer programming Large-scale optimization Airline fleet assignment |
本文献已被 SpringerLink 等数据库收录! |
|