Optimized Crew Scheduling at Air
New Zealand

Introduction

Tour-of-duty Planing Problem:

Rostering Problem:

Air New Zealand

Model and Solution method for Aircrews Scheduling

Tours-of-duty Planning Model

Rostering Model

Solution of Generalized Set-Partitioning Problems

Integer Properties of Set-Partitioning Problems

Degeneracy and Set-Partitioning Problems

National ToD Planning

National Rostering

International Flight Attendant ToD Planning

International-Flight-Attendant Rostering

International-Pilot ToD Planning

International-Pilot Rostering

Implementation

Impacts

References

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.

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

is a alternating sequence of duty period and rest period

each duty period consists of one or more flights and may also include passengering flight

Passengering flight: 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

Requirement:

Length of duty periaod

Desirable feature: is that all the crews member perform same sequence of flight as much as possible in their duty.

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.

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.

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

the largest national and international airline in New Zealand

employs over 2,000 screw member

Operating

  • 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

click to edit

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

Weakness:

  • provide no bound on quality of any feasible solution
  • No guarantee a feasible solution even if one exist.

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.

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.

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.

click to edit

  • line of work (LoW)
  • A tour of duty (ToD)
  • The set-partitioning problem (SPP)
  • linear programming (LP) relaxation

Done

Done

Done