THE FLEET ASSIGNMENT PROBLEM - SOLVING A LARGE-SCALE INTEGER-PROGRAM

Given a flight schedule and set of aircraft, the fleet assignment prob lem is to determine which type of aircraft should fly each flight segm ent. This paper describes a basic daily, domestic fleet assignment pro blem and then presents chronologically the steps taken to solve it eff iciently. Our model of the fleet assignment problem is a large multi-c ommodity 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 so lutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simple x, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computationa l results show that the algorithm finds solutions with a maximum optim ality gap of 0.02% and is more than two orders of magnitude faster tha n using default options of a standard LP-based branch-and-bound code.