IDEAS home Printed from
   My bibliography  Save this paper

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


  • Ahuja, Ravindra
  • Goodstein, Jon
  • Mukherjee, Amit
  • Orlin, James
  • Sharma, Dushyant


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 that 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. The through assignment model is usually solved after obtaining the solution from a fleet assignment model. In this current sequential approach, the through assignment model cannot change the fleeting in order to get a better through assignment, and the fleet assignment model does not take into account the through benefits. The goal of the combined through and 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 formulation of ctFAM that is too large to be solved to optimality or near-optimality within allowable time for the data obtained by a major US 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 and 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 the neighborhood defined by us is very large; hence the suggested algorithm falls 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 which indicate that the neighborhood search approach for ctFAM provides substantial savings over the sequential approach of solving FAM and TAM

Suggested Citation

  • Ahuja, Ravindra & Goodstein, Jon & Mukherjee, Amit & Orlin, James & Sharma, Dushyant, 2003. "A Very Large-Scale Neighborhood Search Algorithm for the Combined Through and Fleet Assignment Model," Working papers 4388-01, Massachusetts Institute of Technology (MIT), Sloan School of Management.
  • Handle: RePEc:mit:sloanp:1796

    Download full text from publisher

    File URL:
    Download Restriction: no


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:mit:sloanp:1796. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Christian Zimmermann). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.