Crew Scheduling — Worked Example

Airline crew scheduling formulated as set partitioning. Dantzig-Wolfe Decomposition generates crew pairings for each base via column generation, making a massive integer program tractable.

Problem Description

An airline must assign crews to a set of flight legs. Each crew member starts and ends their duty period at the same base airport. A pairing is a sequence of flight legs forming a round trip from a crew member’s base. Everything is self-contained: this example does not build on any other example on this site.

Notation (all symbols defined before first use):

$F$: Set of flight legs to be covered.
$B$: Number of crew bases.
$P^b$: Set of all feasible pairings originating from base $b$ .
$a_{fp}$: 1 if pairing $p$ covers flight leg $f$ , else 0.
$c_p$: Cost of pairing $p$ (e.g., duty time, hotel costs).
$x_p$: 1 if pairing $p$ is selected, else 0.

Set-Partitioning Formulation

The crew scheduling master formulation is a set-partitioning problem: every flight leg must be covered by exactly one pairing:

\begin{aligned} \min \quad & \sum_{b=1}^{B} \sum_{p \in P^b} c_p x_p \\ \text{s.t.} \quad & \sum_{b=1}^{B} \sum_{p \in P^b} a_{fp} x_p = 1 \quad \forall f \in F \quad \text{(coupling: coverage constraints)} \\ & \sum_{p \in P^b} x_p \ge 1 \quad \forall b = 1, \ldots, B \quad \text{(sub-problem: base feasibility)} \\ & x_p \in \{0,1\} \quad \forall p \end{aligned}

Dantzig-Wolfe Decomposition and Column Generation

The LP relaxation has one variable per feasible pairing. There are exponentially many pairings in $P^b$ for each base $b$ , making explicit enumeration infeasible.

Dantzig-Wolfe Decomposition decomposes along bases: relax the coupling coverage constraints with dual variables $\pi_f$ .

Dual variables: $\pi_f$ is the marginal cost saving of covering flight $f$ from the master. A pairing is attractive if its cost (duty time plus overheads) is less than the total dual value of the legs it covers.

Pricing sub-problem for base $b$ : Find the minimum reduced-cost pairing from base $b$ :

\bar{c}_p = c_p - \sum_{f \in F} \pi_f^* a_{fp}

\begin{aligned} \min \quad & c_p - \sum_{f \in F} \pi_f^* a_{fp} \\ \text{s.t.} \quad & p \in P^b \quad \text{(feasible pairing from base } b\text{)} \end{aligned}

This sub-problem is typically solved as a constrained shortest-path problem on a time-space network for base $b$ , incorporating duty-time rules, rest requirements, and airport curfews.

If $\min_p \bar{c}_p < 0$ for any base, a new improving pairing (column) is added to the restricted master problem (RMP).

Column Generation for Crew Pairings

The algorithm iterates:

Solve the RMP (LP relaxation over the current subset of pairings).
Extract duals $\pi_f^*$ from coverage constraints.
For each base $b$ : solve the pricing sub-problem to find the most attractive new pairing.
If any pairing has negative reduced cost: add it to the RMP and go to step 1.
Otherwise: the LP relaxation is optimal. Apply branch-and-price for integrality if needed.

Citation

Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs . Operations Research, 46(3), 316–329. doi:10.1287/opre.46.3.316