Advances in the Optimization of Airline Fleet Assignment

Rushmeier, Russell A.; Kontogiorgis, Spyridon A.
May 1997
Transportation Science;May97, Vol. 31 Issue 2, p159
Academic Journal
We present an advanced model for the formulation and solution of large scale fleet assignment problems that arise in the scheduling of air transportation. Fleet assignment determines the type of aircraft to operate each flight in a given schedule, subject to a variety of side constraints, due to marketing, operational, maintenance and crew restrictions. We model the problem as mixed-integer multicommodity flow on networks encoding activities linking flight departures. We focus on fully representing flight connection possibilities, while accurately capturing complex operational rules. We also provide a unified framework for the expression of resource constraints via piecewise linear penalties, which permits a profitability-based tradeoff between operational goals and revenue. Computational results on actual schedules show that high quality assignments for one-day problems can be obtained within an hour of computation. The use of the model at USAir results in an annual benefit of at least $15 million.


Related Articles

  • An Efficient Airline Re-Fleeting Model for the Incremental Modification of Planned Fleet Assignments. Jarrah, Ahmad I.; Goodstein, Jon; Narasimhan, Ram // Transportation Science;Nov2000, Vol. 34 Issue 4, p349 

    Airlines typically manage their annual business cycle by subdividing the year into a sequence of scheduling periods that span about a month each. Fleet assignment represents an important step in the planning process for each new scheduling period and is usually undertaken using computer-based...

  • Wardrop Equilibria with Risk-Averse Users. Ordóñez, Fernando; Stier-Moses, Nicolás E. // Transportation Science;Feb2010, Vol. 44 Issue 1, p63 

    Network games can be used to model competitive situations in which agents select routes to minimize their cost. Common applications include traffic, telecommunication, and distribution networks. Although traditional network models have assumed that realized costs only depend on congestion, in...

  • Two-Stage Fleet Assignment Model Considering Stochastic Passenger Demands. Sherali, Hanif D.; Xiaomei Zhu // Operations Research;Mar/Apr2008, Vol. 56 Issue 2, p383 

    An airline's fleet typically contains multiple aircraft families, each having a specific cockpit design and crew requirement. Each aircraft family contains multiple aircraft types having different capacities. Given a flight schedule network, the fleet assignment model is concerned with assigning...

  • Zone Scheduling of Bus Routes to Improve Service Reliability. Jordan, William C.; Turnquist, Mark A. // Transportation Science;Aug79, Vol. 13 Issue 3, p242 

    A model of an urban bus route incorporating measures of both reliability and average trip time is developed. The impact of zone scheduling on these measures is determined by selecting optimal zone structures using a dynamic programming model, Application of the model to a specific bus route...

  • THE AUCTION ALGORITHM FOR THE TRANSPORTATION PROBLEM. Bertsekas, Dimitri P.; Castanon, David A. // Annals of Operations Research;1989, Vol. 20 Issue 1-4, p67 

    The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids arc in, objects are awarded to the highest bidder....

  • Asymptotic Properties of Random Multidimensional Assignment Problems. Grundel, D. A.; Oliveira, C. A.S.; Pardalos, P. M. // Journal of Optimization Theory & Applications;Sep2004, Vol. 122 Issue 3, p487 

    The multidimensional assignment problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association. In this paper, we prove two conjectures made in Ref. 1 and based on data from computational experiments on MAPs. We show that the mean optimal...

  • A Polynomial Simplex Method for the Assignment Problem. Hung, Ming S. // Operations Research;May/Jun83, Vol. 31 Issue 3, p595 

    We present a polynomial primal simplex algorithm for the assignment problem. For an n x n assignment problem with integer cost coefficients, the algorithm generates at most n[sup 3]ln change bases prior to reach the optimal basis, where change is the difference in objective value between an...

  • Optimal Traffic Assignment with Elastic Demands: A Review Part II. Algorithmic Approaches. Gartner, Nathan H. // Transportation Science;May80, Vol. 14 Issue 2, p192 

    Part I of this study reviewed the formulation of the traffic assignment problem (TAP) in a network and identified its underlying rationale. This part examines algorithmic approaches for calculating the flow patterns resulting from the different modes of assignment. An efficient methodology for...

  • AN IMPROVED DUAL BASED ALGORITHM FOR THE GENERALIZED ASSIGNMENT PROBLEM. Guignard, Monique; Rosenwein, Moshe B. // Operations Research;Jul/Aug89, Vol. 37 Issue 4, p658 

    The generalized assignment problem (GAP) determines the minimum cost assignment of n jobs to m agents such that each job is assigned to exactly one agent, subject to an agent's capacity. Existing solution algorithms have not solved problems with more than 100 decision variables. This paper...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics