TPAC Pairing Optimiser is a component that automatically generates crew pairings to cover legs or other required duties in a transport schedule.
TPAC Pairing Optimiser utilizes advanced constraint programming and optimization techniques in order to minimize solution cost subject to statutory, crew and company rules, crew availability constraints and penalties for undesirable solutions. Rules and penalties are described using the TPAC Rules rule management system.
TPAC Pairing Optimiser can be used both during the planning phase to generate pairings from scratch, and during the crew operations phase to perform crew pattern repair, ie. dynamically adjust pairings in response to operational changes.
The optimizer is a back-end component with a well-defined interface, and can readily be integrated into larger crew planning, tracking or management systems.
Crew pairing is the process of grouping the small parcels of work that make up a transport schedule into larger chunks, called crew pairings (also known as patterns), which can later be allocated to actual crew members during the crew rostering stage.
Pairings have the useful property that they start and end at locations that are served by a single crew base, which allows them to be allocated without further recombination.
The key challenges in generating crew pairings are:
-
To create legal pairings that are likely to be rosterable
-
To produce quality solutions
-
To be scalable with problem size
-
To produce solutions quickly
Systems can be characterized by their input, output, and what processing they perform. TPAC Pairing Optimiser can be described as such:
- Input
-
-
A transport schedule, describing the legs that need to be crewed and any other required duties
-
Legality and penalty rules to constrain the solution
-
Cost information, eg. pay, hotels, allowances and penalties for non-robust solutions.
-
Resource availability, eg. number of crew available at each base
-
- Processing
-
-
A set of crew pairings is constructed which minimizes the costs subject to the rules and resource availability
-
- Output
-
-
A set of crew pairings (also known as crew patterns)
-
The following documents may also be of interest:
| Document | Description |
|---|---|
| Crewing Rules Overview | A description of how crewing rules are specified for use by products such as TPAC Pairing Optimiser and TPAC Rostering Optimiser. |
| Crewing Rule Repository Template | A Common Rules repository set up in the form required for crewing, containing example rule implementations that can be customized for a particular client. |
| TPAC Rostering Optimizer Description | An overview of the TPAC rostering optimizer component. |
| Common Rules Editor User Guide | User guide for the editor that is used to view the Crewing Rule Repository Template and implement rules. The user guide also includes an introduction to Common Rules. |
TPAC Pairing Optimiser provides:
-
Flight crew pattern generation (the pilot problem)
-
Handling of relief crew
-
-
Cabin crew pattern generation (the flight attendant problem)
-
Handling of variable crewing for each leg
-
-
Selectable solution construction process
-
Ability to maximize daily or weekly pairing regularity
-
-
Configurable legality and penalty rules
-
New types of rules can be added with no code change
-
Accountability for rule changes
-
What-if scenario modelling for rule changes
See Crewing Rules Overview document for further information.
-
-
Tunable penalty costs, allowing solutions to trade off between
-
Robustness
-
Pay cost
-
Number of hotels
-
Number of deadhead/paxing sectors
-
Rosterability
-
-
Handling of multiple crew bases and categories
-
Generation of pairings that include non-flying activities away from base such as training, simulator sessions and standby
-
Global and local optimization steps, which can be applied separately if required
-
Scalability
-
Capable of handling large (tier-one airline) pairing problems
-
-
Reporting tools to summarise solutions
-
Costs, descriptions and other items used within reports are defined using the TPAC Rules rule management system
-
-
Run management capability, to start, stop and keep track of runs
TPAC Pairing Optimiser allows rules to be specified using the TPAC Rules rule management system.
TPAC Pairing Optimiser solves different kinds of problems using different approaches, in order to take advantage of problem-specific techniques and optimizations. There are three modes of operation:
-
Single crew size
This mode is used for cabin or flight crew problems where the required crew complement is the same on all legs and is the most straightforward problem to solve.
-
Flight crew with relief
Where relief crew is required for some legs in a transport schedule, extra handling is required. The optimiser can automatically determine where relief crew is required to obey legality rules.
There are two alternative solution generation strategies available within this mode. For maximum robustness, relief crew pairings can be generated which match those of the main crew but incorporate deadheading/paxing legs where relief crew are not required. For minimum cost, relief crew duties can only be generated where relief is required, and this relief problem can then be optimized separately.
-
Variable crew requirements
Where different crew complements are required for different legs, extra processing is required to generate suitable pairing, taking into account factors like:
-
The need to minimize the number of different pairings generated to maximize robustness
-
Different constraints for different crew ranks or categories in different bases.
-
The optimiser solves problems in stages. The stages applied and their order varies for different modes of operation, but such stages include:
-
Problem definition
Problem definition is the first stage for most modes of operation. During this stage, the problem is extracted from the input data, and constraints are generated to aid the optimizers in subsequent stages.
As an example, this stage typically produces a constraint that limits the set of legs that are candidates for deadheading. While any leg can theoretically be used to deadhead crew, there are many legs that in practice are unlikely to be used. Applying this constraint reduces the problem size for the later stages.
-
Global optimization
During global optimization stages, the problem is considered as a whole and a broad-brush solution is found.
Techniques based in operations research such as linear programming, mixed integer programming and stochastic techniques are employed to produce legal solutions that maximize the given objectives.
-
Local improvement
During local improvement stages, smaller parts of the initial solution are selected and optimized separately. By selecting sub-problems of a suitable size, more rigorous optimization approaches can be applied, leading to further cost reduction.
Specifically, constraint programming techniques are used for column generation and mixed integer programming techniques are then used to find solutions to the sub-problem.
-
Follow the leader
For some cabin-crew modes of operation, the first solution found is a nominal solution for a particular crew member (for example a flight service director, the most senior cabin crew category). During follow-the-leader stages, activities (patterns) are built for other crew categories that attempt to follow the patterns in the nominal solution to maximize solution robustness.
-
Relief crew patterns
For some flight-crew modes of operation, patterns for relief crew are determined separately to the non-relief crew. This allows the trade-off between robustness and cost to be specified separately for relief crew, as well as for different legality and penalty rules to apply if appropriate.
- Activity
-
Within the optimiser, a sequence of Duties that start and end at a crew base. An activity within the optimiser is more commonly known as a crew pairing (also pattern).
More generally (such as in TPAC Rostering Optimiser), an Activity is a block of work that can be allocated to a crew member (or to multiple crew members).
- Carry-in
-
Pairing is performed for a particular roster period. Carry-in information is one of the inputs to the pairing process, and describes pairings from the last roster period that overlapped into this roster period. The carry-in pairings effectively reduce the crewing requirements for activities in the roster period of interest.
The reason a pairing might overlap roster periods is that all pairings must end at a crew base, so in order to crew legs that fall near the end of the roster period that don't end at a crew base, legs from the next roster period need to be used in constructing legal pairings.
- Crew base
-
The place that a given crew will start Activities from and return to.
This may be different to the start and end locations of the Duty Activities in the Activity, but will normally be accessible using ground transport. For example, a London base might be used to crew Duty Activities starting at Heathrow, Gatwick and Stanstead airports.
- Duty
-
An ordered sequence of Duty Activities that don't contain any layovers.
- Duty Activity
-
A general term describing a unit of work which may become part of a duty, plus some information describing who is required and what role they have for that work.
Within the optimiser, examples of Duty Activities include:
-
A leg, with a particular crew complement and a specification of whether the work is in a deadheading/paxing or an operating capacity.
-
A standby period, for a particular crew complement away from base.
-
Emergency procedure training conducted away from base.
-
- Layover
-
A rest of some duration (as determined by rules) at a location other than the crew's base.
- Leg
-
The fundamental unit of travel in a transport schedule where a vehicle travels from a start location to and end location. The start and end locations are normally different, but may be the same.
- Pairing
-
Pairing can be used as a noun, in which case it refers to an Activity. Additionally, the process of generating pairings is known as crew pairing.
- Pattern
-
See Activity.
- Paxing/deadheading
-
Where a crew member travels on a leg in a non-operating capacity.
- Roster period
-
Transport companies often break time down into roster periods in order to simplify their business processes. Crew pairing and rostering are performed for whole roster periods in advance. Roster periods are typically four to eight weeks long.
Further Information
You may wish to look at the PDF version (18K 
) of this document.