Some properties of the fleet assignment problem

Given a flight schedule and fleets of different types of planes, the fleet assignment problem is to determine the type of plane to assign to each flight segment. The fleet assignment problem is modeled as a multicommodity flow problem on a time-space directed network. This paper studies the complexity of the problem and the behavior of the solution as a function of the number of fleets. An analytical expression is given for the minimum number of planes required by one fleet; the complexity of the feasibility problem for two fleets is unknown and for three fleets it is NP-complete. Also, the ratio of the minimum number of planes required by K fleets to the minimum number of planes required by one fleet can be at least as large as and the LP relaxation of an integer problem for the minimum number of planes required by K fleets can be quite bad since its optimal value equals the minimum number of planes required by one fleet. When a frequently used connectivity condition is imposed, the one-fleet problem is NP-complete. The authors also analyze a model in which the constraints on the size of the fleets are omitted. Here the 2-fleet model is a network flow problem, but the minimum cost problem for 3 fleets is NP-hard.