Proposed by Özgür Akgün

(See [gronkvist2004constraint])

Tail Assignment is the problem of deciding which individual aircraft (identified by its tail number) should cover which flight. Each aircraft is thus assigned a route consisting of a sequence of flights, and possibly other activities such as maintenance, to perform. Tail Assignment deals with individual constraints, flights which are fixed in time, as well as individual rules for each tail. The planning period is typically one month. The purpose is to really create a solution that is possible to operate, satisfying all rules and regulations. The most basic rules are rules which only depend on two flights, so-called connection-based rules.

For example, there must be a certain minimum buffer time between a landing and the next take-off. Another important set of constraints are the flight restriction rules, which forbid certain aircraft to operate certain flights. There can be many reasons for the restriction - there can be a curfew for the arrival airport and some aircraft, because the aircraft violates noise or environmental restrictions. But there can also be more down-to-earth reasons, like the aircraft not having the required in-flight entertainment system or extra fuel tanks required for a long flight. Either way, the result is that an aircraft is restricted from operating a flight. Finally, there are the maintenance rules. Aviation authorities require that all aircraft undergo various types of maintenance activities regularly. There are many maintenance types, depending om aircraft type, registration country, and airline. Typically, the rules specify that aircraft must undergo maintenance every X hours, or every Y landings. Airlines often also require that their aircraft return to a maintenance base frequently, even if no maintenance is done, to increase robustness in case disruptions occur. These rules typically specify that aircraft must come back to a maintenance base every Z days.

The normal representation of the Tail Assignment problem is in terms of a flight network. In the flight network, each node represents a flight, or some other activity such as a preassigned maintenance activity for specific aircraft, and each arc represents a connection between two flights or activities. For example, if operating flight f followed by flight f is allowed according to connection rules, the connection from f to f is considered legal, and the flight network will contain an arc between nodes f and f’. Since we are solving a dated problem, where flights are fixed in time, there are carry-in activities in the beginning of the period representing the last flights operated by each aircraft in the previous planning period, and the network is acyclic. The goal is now to find paths (routes) through the network for all aircraft, starting at the carry-in activities, such that all flight nodes are covered exactly once, and all rules are satisfied.