FLIGHT STRING MODELS FOR AIRCRAFT FLEETING AND ROUTING

Given a schedule of flight legs to be flown by an, airline, the fleet assignment problem is to determine the minimum cost assignment of flig hts to aircraft types, called fleets, such that each scheduled flight is assigned to exactly one fleet, and the resulting assignment is feas ible to fly given a limited number of aircraft in each fleet. Then the airline must determine a sequence of flights, or routes, to be flown by individual aircraft such that assigned lights are included in exact ly one route, and all aircraft can, be maintained as necessary. This i s referred to as the aircraft routing problem. In this paper, we prese nt a single model and solution approach to solve simultaneously the fl eet assignment and aircraft routing problems. Our approach is robust i n that it can capture costs associated with aircraft connections and c omplicating constraints such as maintenance requirements. By setting t he number of fleets to one, our approach can be used to solve the airc raft routing problem alone. We show how to extend our model and soluti on approach to solve aircraft routing problems with additional constra ints requiring equal aircraft utilization. With data provided by airli nes, we provide computational results for the combined fleet assignmen t and aircraft routing problems without equal utilization requirements and for aircraft routing problems requiring equal aircraft utilizatio n.