The fleet assignment problem: Solving a large-scale integer program

The fleet assignment problem: Solving a large-scale integer program

0.00 Avg rating0 Votes
Article ID: iaor1997904
Country: Netherlands
Volume: 70
Issue: 2
Start Page Number: 211
End Page Number: 232
Publication Date: Oct 1995
Journal: Mathematical Programming (Series A)
Authors: , , , , ,
Keywords: programming: integer, programming: linear
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. The present 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.

Reviews

Required fields are marked *. Your email address will not be published.