Reprinted from Compass News, number 3, fall 1996 US Airways typically flies about 2,500 jet flights to over a hundred domestic, Caribbean and European markets using more than 400 aircraft of 14 different types. One of the major tasks in planning the operation of the airline is the fleet assignment process. This is the assignment of an aircraft type to each flight in the schedule.
The process is driven by the complementary objectives of maximizing revenue (by matching seat capacity to passenger demand) and reducing costs (such as fuel, maintenance and airport gating). The assignment must meet a wide variety of requirements. For example, it must respect restrictions on the operating ranges of aircraft as well as curfews and runway limitations at airports. Aircraft must stay overnight at stations where maintenance work can be performed. The assignment must distribute evenly the workload among flight crews based at different stations.There must also be enough time for passengers to deplane and enplane and for servicing the aircraft.
Today most major airlines use automated procedures based on mathematical optimization models to solve this problem. At US Airways, the Operations Research Group has been providing automated decision support for the fleeting of schedules since 1993, at an annual benefit to the airline of several million dollars.
We coded our initial one-day Fleet Assignment Model (FAM) in C and implemented it as a stand-alone system. It was extensively used in production, to fleet current schedules and to play out what-if scenarios for advance planning. Thanks to this success, we were asked in 1994 to extend the model to better capture the complex tradeoffs involved in the utilization of aircraft, crew personnel and maintenance facilities.
After considering several modeling languages, we chose to implement the new FAM in AMPL. AMPL features sets, nodes, arcs and piecewise-linear terms which can express fleet assignment structures succinctly.
The backbone of our model is the set of pairs of flights that can be operated successively by the same aircraft. We build this set by using the set of flights in the schedule and the set of possible assignments.
Each flight is represented by a triple (s1, t1, s2), where the fields stand for originating station, departure time and destination station respectively:
set FLIGHT within {STATION, TIME, STATION};
The set of possible assignments is of the form (s1, t1,
s2, e), where e designates a valid aircraft type:
set ASSIGNMENT within {FLIGHT, AIRCRAFT_TYPE};
Then we can create the set of all possible connections as
set CONNECTION := setof {(sl,tl,s2,e) in ASSIGNMENT,
(s2,t2,s3,e) in ASSIGNMENT} (sl,tl,s2,e,t2,s3);
This set is huge, as there are millions of connections. To reduce it, we apply
heuristic rules based on the underlying connection patterns of our schedule.
Since an AMPL model is structured around sets, we can express our reduction
rules quite naturally in terms of the set constructors in AMPL. For example, we
can eliminate all connections that require a stay on the ground of at least 120
minutes, in the following way. We use the flight time associated with each
assignment to calculate the arrival time,
param flight_time {ASSIGNMENT} integer >= 0;
param arrival_time {(sl,tl,s2,e) in ASSIGNMENT}:=
t1 + flight_time[sl,tl,s2,e];
and use the latter to filter the connections:
set QUICK_CONNECTION :=
{(sl,tl,s2,e,t2,s3) in CONNECTION:
arrival_time[sl,tl,s2,e] + 120 > t2};
We construct CONNECTION, a set of 6-tuples, by splicing
elements of ASSIGNMENT, a set of 4-tuples. We index the
scalar parameters flight_time and arrival_time over
ASSIGNMENT, an unordered set. This capability of
manipulating sets is a significant advantage over row and column index-based
modeling languages. We then represent each connection in the reduced set with a 0-1 variable. FAM gives rise to a mixed-integer multicommodity flow maximization problem. A space-time network for each aircraft type captures the flight connections. We add loops to the network to account for overnight stays. This is all easily done in AMPL, as the language provides node and arc descriptors, a circular ordering of a one-dimensional set (to capture the time loop) and a binary variable designator. Here is how we can express the flow balance constraints and the 0-1 connection variables for the previous example:
node flight_departure {(sl,tl,s2,e) in ASSIGNMENT};
arc flight_connect {(sl,tl,s2,e,t2,s3) in QUICK_CONNECTION} binary,
from flight_departure [sl,tl,s2,e],
to flight_departure [s2,t2,s3,e];
Here the flexibility of AMPL allows us to index the nodes over an
input set and the arcs over a derived set. A penalty scheme balances the use of aircraft, crew and maintenance resources. The planner sets a target for each resource and imposes a piecewise-linear penalty for deviations from the target. Representing these piecewise-linear functions in AMPL is straightforward, as the language provides the appropriate constructs. An added benefit is that AMPL treats both concave and non-concave piecewise-linear terms in a manner transparent to the modeler.
The solution procedure consists of three steps implemented in the AMPL script language. After the mixed-integer optimization problem is formulated, we relax the integrality constraints and pass the resulting LP to a solver. We then examine the LP solution and heuristically make certain fleet assignments by fixing variables. We also replace the aggregated version of some utilization constraints with a disaggregated one.
All this is facilitated by the relax_integrality environment option and the fix, drop and restore AMPL script commands. For example, to finalize the assignment of the MD80 fleet incoming to Boston, we write
fix {(sl,tl,s2,e,t2,s3) in QUICK_CONNECTION:
s2 = 'BOS' and e = 'MD80'}
flight_connect[sl,tl,s2,e,t2,s3];
After the heuristic step, we restore the integrality constraints and pass the
reduced MIP to the solver, which then assigns fleets to the remaining flights.
Finally, another AMPL script produces a report of the results for the schedule
planners.We make liberal use of AMPL's variety of ways to create validity checks and assertions. We impose range restrictions on parameters such as flight_time. We restrict sets of tuples such as FLIGHT to be a subset of a given cross product. We use the check statement to formulate more complex assertions. For example, to ensure that for each station the number of incoming flights equals the number of outgoing ones, we write
check {s2 in STATION}:
card {(sl,tl,s2) in FLIGHT} = card {(s2,t2,s3) in FLIGHT};
Similar checks ensure that there exists at least one connection possibility for
each flight and that for each one-stop flight there exists at least one
aircraft type that can operate both segments of it. When an assertion fails, it
is typically due to some inconsistency in the input data. An error report is
then produced with information that guides the planner to locate and fix the
problem.
We started development in February 1995. A working version was used in production by August of the same year. The final version was released to the planners in November. It is integrated in a graphical interactive system that our planners use to view, edit and evaluate schedules.
The model is about 600 lines long, including the driver script and the report-generating script. This is indicative of the expressive power of AMPL. With a production model this small, maintenance is easier and the learning curve for new members of the development team is shorter. In addition, a modeling language such as AMPL helps us focus more on the "what" rather than on the "how". The language takes care of the latter. This resulted in an improved design and allowed us to experiment with frequent changes in formulation and in aircraft connection logic.
Currently we are implementing a production model in AMPL for multi-day fleet assignment. We are reusing a good portion of the one-day model, thanks to the modularity afforded by AMPL. We have also derived rapid model prototypes from the one-day FAM to solve related problems:
In conclusion, it is pleasant to see that modeling languages and optimization packages have matured to a level that allow the OR practitioner to tackle large and complex business problems with confidence and solve them in a timely manner. This was almost impossible a few years ago. Of course, this creates demand for even further capability. Our wish list for AMPL includes warm-start features, more control over the branch-and-bound algorithm of the solver, and two-way communication with the solver. There are also essential network structures such as paths and cycles that we currently have no satisfactory way of describing in AMPL.
As Robert Fourer and David Gay announced at the May 1996 INFORMS conference in Washington, D.C., some of these new AMPL features are under construction. We are looking forward to their release. Modeling software such as AMPL not only allows us to design better production models faster, it is also a valuable learning tool and fun to experiment with.
Dan Waddelow and Russ Rushmeier did the market research and recommended AMPL to US Airways Operations Research. Russ, Renzo Vaccari and Spyros developed FAM, with contributions from Suresh Acharya and Rajiv Lochan. Jeff Comer and Atul Jain integrated FAM into the production environment For more information on the model, Spyros can be reached at 703-418-5966.
Return to the AMPL cases index.