Airline Crew Pairing: Transformer Deep-RL Scheduler
A ViT-style Deep Q-Network that builds a month of legal airline crew pairings one leg at a time, feasible by construction, published as an interactive replay you can scrub decision by decision.
Problem Statement
A crew pairing is a legal multi-day tour of duty: a sequence of flights that leaves a crew base, splits into workdays separated by overnight layovers, and returns to the same base, all while obeying a thick rulebook of duty-hour limits, rest rules, legs per duty, time away from base, per-base credit caps and crew availability. Covering an airline's month with a cheap set of those tours is the first and most expensive stage of crew scheduling, and the classical method (implicitly enumerating an astronomical pool of candidate pairings and solving a set-partitioning integer program by column generation) is well understood but expensive to build, specific to the instance it was built for, and optimizes cost with robustness added afterwards. This project takes the other route and learns a construction policy: the agent walks the connection network, appends legs to an open pairing and closes it back at base, trained on a distribution of perturbed schedules so a changed month does not mean re-solving from scratch. Three things had to be true for that to be worth anything. The schedule it emits must be legal, not approximately legal, which rules out learning legality from a penalty. It must hold up on a month whose seed was never trained on, not only on the month it was fitted to. And the numbers it reports must be measured against something real: the benchmark's own reference solution from a classical cost optimizer, scored with the same connection classifiers.
Results & Impact
0.658
Held-out Coverage
Cabin policy on 8 unseen instances; cockpit 0.629
0
Feasibility Violations
Independent re-checker over random rollouts
3.6× fewer
Fragile Connections
85, against the GERAD reference solution’s 310
≤ 0.05
Generalization Gap
Train vs. held-out coverage at plateau
+4 pts
Search Lift
Beam 8×4 over greedy, with no retraining
31 days
Planning Horizon
1,013 legs, 26 airports, 3 crew bases
Watch It Solve a Month
Pick a recording from the drop-down inside the frame. Each one opens on the finished month, with every connection already drawn; press Play at the bottom of the frame to rewind to the first decision and watch the policy rebuild the schedule leg by leg. Nothing here runs a model in your browser; the searches were run offline and baked into the page.
Loading the replay…
Four recordings
Two 500-episode training runs, plus a beam search and a best-first search solving a month the policy has never seen.
Scrub any decision
Play replays the construction one connection at a time; the panels show the top actions by Q-value and the reward the step earned.
Click a connection
Any edge in the network opens the flight: route, times, block time, the pairing operating it, and how it joined.
Policy Performance
Every policy is scored on the same 8 held-out instances (perturbations of the base month whose seeds were never sampled during training), and the reference solution is re-measured with this project's own connection classifiers, so the robustness columns compare like with like.
| Policy | Coverageheld-out mean | Strandedpairings | Short connsrobust | Critical connsfragile |
|---|---|---|---|---|
| multi-cabinbestViT-DQN, 40 training variants | 0.658 | 13.3 | 54.6 | 90.4 |
| multi-cockpitsame network, tighter duty limits | 0.629 | 15.9 | 52.6 | 85.0 |
| single-instancetrained on one month, transferred | 0.528 | N/A | N/A | N/A |
| random maskedlegal moves, chosen at random | 0.47 | ~55 | N/A | N/A |
| GERAD referenceclassical cost optimizer, deadheads throughout | 1.00 | N/A | 10 | 310 |
A short connection is a tight same-airport turn the crew can make because it follows the aircraft, the robust kind. A critical connection has under 15 minutes of buffer, so one late inbound cascades. Higher is better in the short column and lower in the other three.
The reference row is not a like-for-like coverage comparison: it reaches 1.00 by deadheading throughout, which the headline runs deliberately did not model. The comparison that does hold is robustness, and even per covered leg, the reference's critical-connection rate is about 2.3 times the learned policy's. The trade this project makes is coverage for resilience, and it is a trade rather than a win.
The trained Q-function is already a value estimate, so at inference it doubles as a search heuristic. No retraining, no new data, just a larger decode budget.
seed 42
greedy → beam 8×4
seed 45
greedy → beam 8×4
seed 0
tie: greedy already optimal here
About four coverage points for roughly three times the wall clock, nine seconds against three per instance. The anytime best-first variant is seeded with a full greedy dive, so whatever budget it is given, it cannot return a worse answer than greedy.
The number that matters most here is not the coverage headline but the train-versus-held-out gap of 0.00 to 0.05 at plateau. A construction policy that had memorized its training month would show a wide one. Alongside zero feasibility violations from an independent re-checker, that is what makes the rest of the table worth reading.
Approach & Methodology
Choosing the Decision, Not Just the Model
The source paper assigns crews flight by flight; three granularities were weighed here and sequential pairing construction won. The agent opens a pairing at a base, extends it, and closes it back at that base, repeating until every leg is covered or nothing legal remains. That choice does real work: it concentrates credit assignment on the tour that earned the reward, keeps episodes at roughly the number of legs plus the number of pairings rather than exploding, and maps cleanly onto a network that scores a set of candidate moves. Deadheads (crew riding as passengers to reposition) are first-class actions at half credit with a per-pairing budget and a hop-bounded reachability guard, not a post-processing fix.
Feasibility Lives in the Action Mask
Every rule is evaluated before an action is offered: the connection window and its classification into short, sit or layover, maximum flying time and legs and span per duty, duties per pairing, total time away from base, per-base credit caps, per-base daily crew availability reduced by vacations, and a backward dynamic-programming check that the crew can still reach its home base from wherever the move would leave it. A one-step viability lookahead keeps the agent out of dead ends. The consequence is that the network cannot emit an illegal schedule, so no reward budget is spent teaching it the rulebook and no repair heuristic runs afterwards; when an open pairing does run out of legal continuations, it is discarded, its resources refunded and a large strand penalty fired, rather than the episode quietly corrupting.
An Observation That Is a Set, Not a Vector
Each step presents up to 64 candidate actions as a token matrix rather than a fixed-width state vector: one 30-feature row per candidate carrying the action type, embedded departure and arrival airports, base flags, day of month, sine and cosine of time of day, block time, buffer to the previous leg, short and critical and NCC indicators, delay risk, the post-append accumulator ratios that say how full the duty and the pairing would become, remaining base credit and availability, preference score, and a can-return-to-base flag. A parallel boolean mask marks which of them are legal, and a 10-feature global vector carries episode context. Because the observation is a set, the number of legal moves can swing from about 56 at an opening step to under 4 at a continuation step without changing a tensor shape.
A Transformer That Scores the Whole Candidate Set
The Q-network is a ViT-style encoder: airport identities are embedded, the remaining numerics are projected to a 192-dimensional model width, a learned context token in the ViT CLS role carries the global features, and a four-layer pre-norm transformer encoder lets every candidate attend to every other one. That is the right inductive bias for the question actually being asked (is this the best next leg given what else is on offer and how full my duty already is), which a per-candidate MLP structurally cannot ask. A dueling head then scores each token pointer-style as a shared state value plus a mean-centered advantage, with masked actions driven to negative infinity so they can never be selected or bootstrapped from.
A Reward With Four Terms and an Off Switch on Each
Coverage pays +1.0 per leg flown and charges -4.0 for every leg still uncovered at the end. Cost charges excess time away from base, each pairing opened, and each deadhead hour. Robustness pays for short connections, where the crew follows the aircraft, and penalizes fragile critical ones, or switches to the source paper's squared non-critical-connection formulation with compensation when the delay-prediction flag is on. Preferences pay a scaled bonus for flying a leg the base's crews prefer. Every weight and every enable flag sits in one YAML file, so an ablation is a config edit rather than a code branch, and the discount is 1.0 within an episode because a pairing built on day 3 is worth exactly what it is worth on day 30.
Training for Generalization, Not for One Month
Double DQN with a target network, prioritized experience replay, Huber loss, gradient clipping and mixed precision. But the load-bearing design choice is the data, not the optimizer. Each episode samples a fresh instance from 40 seeded perturbations of the base month (departure jitter, leg subsampling, availability and credit resampling, regenerated preferences), and evaluation runs the greedy policy every 20 episodes against a disjoint split of 8 variants whose seeds are never trained on. The reported number is the held-out mean, the checkpoint kept is the best by held-out coverage, and the train-versus-held-out gap is logged as a metric in its own right so overfitting shows up as a curve rather than as a surprise at the end.
Reusing the Value Network as a Search Heuristic
A trained Q-function is already an estimate of what a state is worth, so at inference it does double duty. Beam search keeps the best partial constructions and scores frontiers by realized return plus the network's best remaining Q, batching every frontier evaluation per depth. An anytime best-first variant runs a priority queue on realized-plus-estimated return, seeded with a full greedy dive so its answer is never worse than greedy and the search budget is pure upside. Beam 8x4 lifted held-out coverage from 0.612 to 0.651 and from 0.613 to 0.647 on two seeds and tied on a third, for about 9 seconds against 3 per instance and no retraining. Textbook-optimal A* was considered and rejected in writing: the only admissible bound available here is loose enough that the search collapses into breadth-first.
Diagnosing the Ceiling, and Proving the Rules
Coverage plateaus near 0.63 to 0.66, so the terminal states were dissected rather than explained away. About 52% of the uncovered legs depart non-base airports and were orphaned once their feeder legs got routed elsewhere, about 20% depart a base whose availability has been exhausted, about 25% are blocked by the stranding guard on a thinned-out network, and credit caps never bind at all, which ranks the levers as deadheads first, availability slack second, inference-time search third and a longer exploration schedule fourth. Underneath all of it sits an 84-test suite whose load-bearing member is the feasibility invariant: because all legality lives in the mask, any rule bug surfaces as a random rollout constructing an illegal pairing, which the independent verifier catches.
Architecture
── DATA ────────────────────────────────────────────────────────────
┌──────────────────────────────────────────────────────────────────┐
│ GERAD / Quesnel the monthly benchmark instances │
│ instance1: 31 days, 1,013 legs, 26 airports, 3 crew bases │
│ plus a reference solution from a classical cost optimizer │
│ synth_perturb.py: jitter, subsample, resample, all seeded │
│ 40 training variants . 8 held-out, seeds never trained on │
└────────────────────────────────┬─────────────────────────────────┘
│ one episode samples one variant
↓
── ENVIRONMENT - FEASIBLE BY CONSTRUCTION ────────────────────────
┌──────────────────────────────────────────────────────────────────┐
│ env/crew_pairing_env one month, one crew class │
│ START(leg) -> APPEND(leg)* -> CLOSE, then open the next │
│ DEADHEAD(leg) to reposition: half credit, 4 per pairing │
│ no legal continuation -> discard, refund, -8.0, carry on │
└────────────────────────────────┬─────────────────────────────────┘
│ every candidate leg, before it is offered
↓
┌──────────────────────────────────────────────────────────────────┐
│ env/masking.py an illegal move never exists │
│ connection window . duty flying time . legs per duty │
│ duty span . duties per pairing . time away from base │
│ per-base credit cap . per-base daily crew availability │
│ backward-DP "can I still get home?" reachability guard │
└────────────────────────────────┬─────────────────────────────────┘
│ tokens [K,30] . mask [K] . global [10]
↓
┌──────────────────────────────────────────────────────────────────┐
│ models/vit_dqn.py set encoder over the candidates │
│ airport embeddings + numeric projection -> d_model 192 │
│ learned context token (the ViT CLS) holds global state │
│ TransformerEncoder: depth 4, heads 4, d_ff 384, pre-norm │
│ dueling pointer head -> one Q per action, masked to -inf │
└────────────────────────────────┬─────────────────────────────────┘
│ argmax Q at eval, epsilon-greedy while training
↓
┌──────────────────────────────────────────────────────────────────┐
│ env/reward.py multi-objective, gamma = 1 │
│ coverage +1.0 per leg covered, -4.0 per leg left open │
│ cost -0.15 / excess TAFB h, -0.5 / pairing opened │
│ robustness +0.5 short connection, -0.5 critical one │
│ preference +0.3 scaled by the leg score for that base │
└────────────────────────────────┬─────────────────────────────────┘
│ (s, a, r, s') transitions
↓
── LEARNING ────────────────────────────────────────────────────────
┌──────────────────────────────────────────────────────────────────┐
│ train.py Double DQN over 500 episodes │
│ prioritized replay . Huber loss . grad clip 10 . AMP │
│ hard target sync every 2,500 env steps . 8.3 s / episode │
│ greedy eval on the held-out split every 20 episodes │
│ keep the best-by-eval-coverage checkpoint as best.pt │
└────────────────────────────────┬─────────────────────────────────┘
│
↓
── INFERENCE - THE SAME NETWORK AS A SEARCH HEURISTIC ────────────
best.pt
|-- greedy argmax Q, about 3 s per instance
|-- beam W x M keep the W best partial constructions, expand
| the top-M actions, score by g + max Q of the child
'-- anytime A* priority queue on f = g + h, seeded with a greedy
dive, so the answer is never worse than greedy
│
↓
demo.py -> events.jsonl -> viz/build_site.py -> GitHub Pages replay