A neighborhood search algorithm for the combined through and fleet assignment model with time windows

The fleet assignment model (FAM) for an airline assigns fleet types to a set of flight legs that satisfies a variety of constraints and minimizes the cost of the assignment. The through assignment model matches inbound flight legs into a city with the outbound flight legs at the same city that are flown by the same plane types and creates through connections (that is, flight connections with one stopover). The combined through and fleet assignment model (ctFAM) integrates both the models into a single model and obtains optimal fleet and through assignments by varying both sets of decision variables simultaneously. In a recent article, Ahuja et al. proposed a very large-scale neighborhood (VLSN) search algorithm for the ctFAM. In this article, we generalize this approach to incorporate time windows. In the model considered in this article, each flight leg has a time window associated with its departure time. The objective is to determine fleet assignment, departure time of all flight legs, and through connections between flights to minimize the total cost of fleet assignment and through connections. We call this model ctFAM with time windows or ctFAM-TW. Allowing flexibility in the flight departure time creates greater opportunities for fleet assignment and through connections, and can reduce costs substantially. We describe the details of a VLSN search algorithm for ctFAM-TW and also present computational results of our algorithm on the data provided by a large US airline.