In a first step at integrating flee

In a first step at integrating fleet assignment and
schedule design decisions, Rexing et al. (2000) simultaneously
assign an aircraft type to each flight leg
and select each flight leg’s departure time, allowing
retimings of 5–20 minutes from the current schedule.
Departure retiming allows additional aircraft assignments
that can lead to better matches between flight
leg demand and assigned capacity. The result, according
to Rexing et al. (2000), is reduced operating costs
and improved revenue capture, with savings for one
major airline of $20–$50 million annually.
2.3. Aircraft Maintenance Routing
With schedule design and fleet assignment decisions
made, the flight network decomposes into subnetworks,
each one associated with aircraft of a single
type. The assignment of individual aircraft to flight
legs in a subnetwork occurs in the aircraft maintenance
routing step. The goal is to determine routings,
or rotations, for each aircraft in a fleet. A routing is
a sequence of flight legs, with the destination of one
flight leg the same as the origin of the next leg in
the sequence. A rotation is a routing that starts and
ends at the same location. Each aircraft’s rotation visits
maintenance stations at regular intervals. More
details on the maintenance routing problem are contained
in Feo and Bard (1989), Gopalan and Talluri
(1998), and Clarke et al. (1996b). For restricted maintenance
routings of three or four days, Gopalan and Talluri
(1998) and Talluri (1998) describe graph-theoretic
approaches to maintenance routing.
In general, the aircraft maintenance routing problem
can be modeled as a network circulation problem
with side constraints. The decision variables correspond
to sequences (strings) of flight legs, with each
sequence beginning and ending at maintenance stations
and satisfying the rules governing the maximum
time between maintenance. If a string is included in
the solution, a single aircraft flies each flight in the
sequence and then undergoes maintenance. Side constraints
include cover constraints and count constraints.
Cover constraints ensure that each flight leg is contained
in exactly one selected string, and count constraints
limit the number of assigned aircraft to the
number available. Additional details are provided in
Barnhart et al. (1998a).