Optimized Crew Scheduling at Air New Zealand (Tour-of-duty Planing…
Optimized Crew Scheduling at Air
Aircraft and aircrews are the most expensive resource. Then efficient ultilization is important
Most of optimization attempts failed because the lacking of solution method and computer power
Consisting of 2 problems:
Tours-of-duty planning problem: minimize cost and cover all scheduled flight).
Rostering problem: assign tours-of-duty to individual crew member.
Tour-of-duty Planing Problem:
is a alternating sequence of duty period and rest period
consists of one or more flights and may also include
: the flight that crews get in as a passenger to another airport for a subsequence operating flight.
the first and the end duty period have to be at the same base
Length of duty periaod
the lastest time at which a flight may start within a duty period
the maximum allowanble flight time
the number of screws required to operate a flight.
effect of time-zone or the changing of weather at foreign airport.
Desirable feature: is that all the crews member perform same sequence of flight as much as possible in their duty.
Airlines prefer the cheapest solution but have a better robustness or good practice feature.
Robustness is avoiding a flight from discruption
A solution with good feature and robustness is ussually cost more than mimimum-cost solution.
--> need a solution balance between them.
consists of contructing a
line of Work
for each crew member.
LOW: is a sequence of activities and rest period (such as 14 or 28 days). Include ToDs, training, leave, days off and call duties
Process is to assign all roster activities to crews with requirement:
Legal: which mean it have to satify all the rule, contract condition.
Feasible: activities assigned must be signed by screw menmber of corect rank. no ToD should be unassigned
Maximize the roster quality: which mean assign roter for the most prefered crew member
Air New Zealand
the largest national and international airline in New Zealand
employs over 2,000 screw member
eight B737-200 and nine B373-300 on national flight
13 B767 and eight B747 aircraft on international flight
Has four majors crew types: national and international for pilot and attendant with different contract and pay scheme.
Therefore, have different scheduling rule and cause more complexity
Model and Solution method for Aircrews Scheduling
A set-partitioning problem (SPP) is structured zero-one interger program.
because the very large practical instances make conputional difficulties
Most of research use heristic method
easy to implement
no expensive resource is required
provide no bound on quality of any feasible solution
No guarantee a feasible solution even if one exist.
Tours-of-duty Planning Model
Solution of Generalized Set-Partitioning Problems
Nowaday, SPP model arising in both Tod and rostering problem are solved using linear programming.
Air New Zealand ToD and rostering can be solved a special purpose of SPP. it is ZIP which was developed by Ryan 1980.
we also apply "contraint branching" which contains a pair of contrains
normally, a braching will force a variable to zero or one. But contrain braching have 2 set. the pair will be covered together in 1st set or separately in the 2nd set.
Integer Properties of Set-Partitioning Problems
Problem: some set-partition are very difficult to solve while other are quite easy.
In LP relation, they use 3 particular classes (uinimodular, balanced and perfect) which suggest that the problem will to easier rather than harder
ToD planning SPP have a sub-sequence matrix which are similar with balanced problem
Rostering SPP created a upper-bound contraints which have perfect-block of variables.
Degeneracy and Set-Partitioning Problems
the solution of LP relaxation of SPPs is often difficult because near-interger basic feasible solution are very degenerate.
to overcome the problem, we apply steepest-edge pricing and Wolfe method.
Wolf method provides a guarantee termination by creating a tension between crew contains.
but we only use it when degeneration become large. 100-200 degenerate pivot in 10,000 iterations is acceptable.
National ToD Planning
International Flight Attendant ToD Planning
International-Pilot ToD Planning
line of work (LoW)
A tour of duty (ToD)
The set-partitioning problem (SPP)
linear programming (LP) relaxation