Advanced Search
MyIDEAS: Login to save this paper or follow this series

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

Contents:

Author Info

  • Ahuja, Ravindra
  • Goodstein, Jon
  • Mukherjee, Amit
  • Orlin, James
  • Sharma, Dushyant
Registered author(s):

    Abstract

    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

    Download Info

    If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
    File URL: http://hdl.handle.net/1721.1/1796
    Download Restriction: no

    Bibliographic Info

    Paper provided by Massachusetts Institute of Technology (MIT), Sloan School of Management in its series Working papers with number 4388-01.

    as in new window
    Length:
    Date of creation: 27 Jan 2003
    Date of revision:
    Handle: RePEc:mit:sloanp:1796

    Contact details of provider:
    Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA
    Phone: 617-253-2659
    Web page: http://mitsloan.mit.edu/
    More information through EDIRC

    Order Information:
    Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA

    Related research

    Keywords: Large-scale neighborhoods; Algorithm; Fleet assignment model (FAM);

    References

    No references listed on IDEAS
    You can help add them by filling out this form.

    Citations

    Lists

    This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

    Statistics

    Access and download statistics

    Corrections

    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).

    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.

    If references are entirely missing, you can add them using this form.

    If the full references list an item that is present in RePEc, but the system did not link to it, you can help with 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 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.