Skip to content

2. Hierarchical Structure & Levels

2.1 The Domain Hierarchy

Airline crew scheduling problems operate across distinct operational granularity levels. Rave formalizes these granularities into a fixed spatial-temporal hierarchy:

graph TD
    Plan["Plan / Roster Level<br>(Full roster for an individual crew member over a month)"]
    Trip["Solution / Trip Level<br>(Single Pairing / Trip - Sequence of Duties)"]
    Duty["Duty Level<br>(Single Working Day - Sequence of Flights)"]
    Leg["Leg Level<br>(Single Flight Leg - Departure to Arrival)"]

    Plan --> Trip
    Trip --> Duty
    Duty --> Leg
  1. Leg (Base Activity): An indivisible flight leg from an origin airport to a destination airport with fixed departure and arrival times.
  2. Duty (Derived Activity): A sequence of consecutive flight legs flown by a crew member within a single working day.
  3. Trip / Pairing (Derived Activity): A complete sequence of duties starting and ending at the crew member's home base airport.
  4. Roster / Plan (Derived Activity): A schedule assigned to a specific named crew member over an entire planning horizon.

2.2 Level Contexts & Scope

Every variable and rule expression in Rave belongs to an implicit or explicit Level Context. The level determines:

  • The scope of accessible keywords and attributes.
  • How frequently the expression is evaluated during search tree traversal.

Referencing leg.%departure_time% requires a Leg context. Referencing sum(leg(duty), ...) evaluates within a Duty context by aggregating over all constituent Leg instances.

2.3 New Instances vs. Continued Instances

During pairing generation, the solver incrementally constructs candidate trips leg-by-leg. This introduces two dynamic search states:

  • New Instance: When a candidate leg cannot legally or structurally belong to the current active Duty, the generator creates a new instance of the Duty level.
  • Continued Instance: When a candidate leg is appended to the existing active Duty, the current Duty instance is extended. All expressions scoped to the Duty level recalculate their values dynamically for this continued instance.