SOME PROPERTIES OF THE FLEET ASSIGNMENT PROBLEM

Given a flight schedule and fleets of different types of planes, the f leet assignment problem is to determine the type of plane to assign to each flight segment. The fleet assignment problem is modeled as a mul ticommodity 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 gi ven for the minimum number of planes required by one fleet; the comple xity of the feasibility problem for two fleets is unknown and for thre e fleets it is NP-complete. Also, the ratio of the minimum number of p lanes required by K fleets to the minimum number of planes required by one fleet can be at least as large as 3/8 log2 K and the LP relaxatio n 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 nu mber of planes required by one fleet. When a frequently used connectiv ity condition is imposed, the one-fleet problem is NP-complete. We als o analyze a model in which the constraints on the size of the fleets a re omitted. Here the 2-fleet model is a network flow problem, but the minimum cost problem for 3 fleets is NP-hard.