This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ahuja, R. K. Articles by Sharma, D. Search for Related Content

A Very Large-Scale Neighborhood Search Algorithm for the Combined Through-Fleet-Assignment Model

Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611
Information Services Division, United Airlines World Headquarters–WHQKB, Chicago, Illinois 60666
Automatic Data Processing, Roseland, New Jersey 07068
Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109
ahuja{at}ufl.edu
amit_r_mukherjee{at}adp.com
jorlin{at}mit.edu
dushyant{at}umich.edu

The fleet-assignment model (FAM) for an airline assigns fleet types to the set of flight legs that satisfies a variety of constraints and minimizes the cost of the assignment. A through connection at a station is a connection between an arrival flight and a departure flight at the station, both of which have the same fleet type assigned to them, which ensures that the same plane flies both legs. Typically, passengers are willing to pay a premium for through connections. The through-assignment model (TAM) identifies a set of profitable throughs between arrival and departure flights flown by the same fleet type at each station to maximize the through benefits. TAM is usually solved after obtaining the solution from FAM. In this sequential approach, TAM cannot change the fleeting to get a better through assignment, and FAM does not take into account the through benefits. The goal of the combined through-fleet-assignment model (ctFAM) is to come up with a fleeting and through assignment that achieves the maximum combined benefit of the integrated model. We give a mixed integer-programming (MIP) formulation of ctFAM that is too large to be solved to even near optimality within allowable time for the data obtained by a major U.S. airline. We thus focus on neighborhood search algorithms for solving ctFAM, in which we start with the solution obtained by the previous sequential approach (that is, solving FAM first, followed by TAM) and improve it successively. Our approach is based on generalizing the swap-based neighborhood search approach of Talluri (1996) for FAM, which proceeds by swapping the fleet assignment of two flight paths flown by two different plane types that originate and terminate at the same stations and the same times. An important feature of our approach is that the size of our neighborhood is very large; hence the suggested algorithm is in the category of very large-scale neighborhood (VLSN) search algorithms. Another important feature of our approach is that we use integer programming to identify improved neighbors. We provide computational results that indicate that the neighborhood search approach for ctFAM provides substantial savings over the sequential approach of solving FAM and TAM.

Key words: transportation, air; heuristics; integer programming; neighborhood search; networks
History: received July 2002; revised March 2005; accepted March 2006.

This article has been cited by other articles:

				R. K. Ahuja, K. C. Jha, J. B. Orlin, and D. Sharma Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem INFORMS Journal on Computing, January 1, 2007; 19(4): 646 - 657. [Abstract] [PDF]