Crew Scheduling

This model considers an airline crew scheduling problem. The solution strategy
uses constraint programming as a subproblem algorithm for linear programming
column generation. Each column represents the pairing of a potential set of
flights to be flown by a crew. Thus, the master problem must find a set of
pairings that covers every flight at a minimum cost. This is a particular kind
of set covering problem.

The overall algorithm is controlled by a main block in CrewScheduling.mod. The
script starts by generating an initial set of pairings. Then, the problem
alternates between solving the Linear Programming relaxation of the set covering
problem and solving a pairing generation problem that produces new columns for
the master problem. Once the columns are satisfactory, the columns are fixed and
the set covering problem is solved to find the integer optimal solution.
Finally, the script prints the pairing used for each crew.

The constraint programming subproblem is of particular interest. A crew pairing
is defined as a set of flights that start and end at a crew base and that
satisfy a set of schedule constraints. We use constraint programming to
enumerate potential crew pairings. In the initialization stage, we enumerate a
set of pairings that are guaranteed to cover every flight. In the column
generation phase, we use the constraint program twice. First, we determine the
optimal crew pairing with respect to the current set of dual multipliers. Once
we know this, we search for all pairings that have reduced cost of at least half
of the optimal pairing. This gives us a large set of entering columns and
eliminates one of the major weaknesses of column generation: the large number of
iterations needed to improve the objective value in the master problem.
The data were converted from the flight schedules of a regional airline.
Industry


Sumber : milis IPOMS