Set Partitioning for Airline Crew Scheduling (SPP)
- Category
- Scheduling
- Formulation
- Combinatorial
- Objective
- Minimize
- Time limit
- 60 s per instance
- Paper
- Solving Airline Crew Scheduling Problems by Branch-and-CutKarla L. Hoffman, Manfred Padberg · Management Science, 1993
Description
An airline operates a set of flight legs during a scheduling period and must assign crew rotations to cover every flight leg. A rotation is a pre-generated sequence of flight segments that begins and ends at a crew base, conforms to all applicable work rules, and spans a multi-day duty period. The airline provides a collection of flight legs and candidate rotations. For each rotation, the airline specifies which flight legs it covers and an associated cost representing all incremental expenses of that rotation, including time away from base, per diem and lodging, flying time, and any deadheading (transporting a crew on a flight without serving passengers). The coverage relationship is encoded as a table with one row for each flight leg and one column for each rotation, where each entry is one if the flight leg in that row is included in the rotation in that column, and zero otherwise.
The airline must select a subset of the candidate rotations so that every flight leg is covered by exactly one chosen rotation. This exact coverage requirement means that no flight leg may be left unassigned and no flight leg may appear in two or more selected rotations simultaneously.
In addition to the exact coverage requirement, the problem may include a set of base constraints that enforce contractual and regulatory labor rules governing crew utilization at each crew base. Each base constraint involves a subset of the rotations and stipulates that a weighted combination of the selected rotations from that subset must fall between a specified lower bound and a specified upper bound. The weight assigned to each rotation in the subset is a strictly positive rational number, and both the lower and upper bounds are strictly positive rational numbers with the lower bound strictly less than the upper bound. These weights and bounds are provided by the airline and encode rules such as requiring that the aggregate hours crews stationed at a particular base spend away from home during a duty period lies within prescribed minimum and maximum limits. A problem instance may have zero or more such base constraints.
The goal is to choose the set of rotations that satisfies the exact coverage requirement for every flight leg and simultaneously respects all base constraints, while minimizing the total cost, defined as the sum of the costs of the selected rotations.
Instance schema
{
"dimensions": {
"num_rows": "<int> Number of flight legs that must be covered during the scheduling period.",
"num_cols": "<int> Number of candidate crew rotations available for selection."
},
"cost_vector": "<list[int], length num_cols> Incremental cost of each candidate rotation, including time away from base, per diem, lodging, flying time, and deadheading expenses.",
"constraint_matrix_A": {
"columns": "<list[list[int]], length num_cols> For each candidate rotation, the sorted list of flight leg indices that the rotation covers."
},
"has_base_constraints": "<bool> Whether the instance includes crew base constraints enforcing labor utilization rules.",
"base_constraints": {
"num_bases": "<int> Number of crew bases subject to labor utilization rules.",
"num_constraints": "<int> Number of base constraints enforcing crew utilization limits.",
"D_matrix": {
"rows": "<list[list[float]], shape [num_bases][num_cols]> Hours away from base that each rotation contributes to each crew base."
},
"lower_bounds_d1": "<list[float], length num_bases> Minimum required weighted hours for crew utilization at each base.",
"upper_bounds_d2": "<list[float], length num_bases> Maximum allowed weighted hours for crew utilization at each base."
}
}Solution schema
{
"objective_value": "<float> Total cost of all selected crew rotations.",
"selected_rotations": "<list[int]> Indices of the crew rotations chosen to cover every flight leg.",
"variable_values": "<dict, key: '{rotation_index}'> Whether each candidate rotation is selected (1.0) or not (0.0)."
}Public instances
For development. Scoring uses private instances, which are never published. Sign in to download them.
- tiny_instance.json60 s
Checker
The checker our evaluation runs, from the FrontierOR benchmark (CC BY 4.0) with the recomputed objective added to its result. How to run it. Sign in to download it.
- feasibility_check.py