Difference: AirCrewRostering (4 vs. 5)

Revision 52008-03-01 - TWikiAdminUser

Line: 1 to 1
 
META TOPICPARENT name="SubmitCaseStudy"
<-- Under Construction -->
Line: 26 to 26
 

Operations Research Topics: IntegerProgramming

Application Areas: Rostering

Contents

Changed:
<
<

>
>
 

Problem Description

Adapted from a real-world problem

An airline is trying to roster captains for 6 flights. The flight schedules are:

flights.jpg

Only one captain is required for each sector, but a captain may be a passenger on a flight (this is called paxing). In addition to the six flights above the following flights are available for paxing and operate every 2 hours:

recurring_flights.jpg

The following rules for shifts must be observed:

  • Shifts start and finish at a captain's home base;
  • The earliest start time is on Day 1 (0001 hours) and the latest finish time is on Day 6 (2359 hours);
  • Shifts are composed of blocks of work. Each block must be no more than 13 hours;
  • Captains must have at least 12 hours break between blocks. The exception is when a block consists only of paxing flights, then a 9 hour break is all that is needed;
  • There must be a 30 min break between sector changes.

There are 6 captains available for work, 2 based in Auckland (AKL), 1 based in Christchurch (CHCH) and 3 based in Singapore (SNG). Each captain is paid $1000 for each block of work (even if it is only a 45 min pax). Each captain's contract guarantees he/she will be paid for 3 blocks of work even if they perform less.

The airline wants to know what shifts the captains should fly to minimise the cost of covering the flights.

The airline is also curious if they can reduce the cost of their roster by using fewer pilots.

Return to top

Changed:
<
<

Problem Formulation

>
>

Problem Formulation

 
Changed:
<
<
The formulation...
>
>
The formulation...
 
Changed:
<
<
Return to top

Computational Model

>
>
Return to top
 
Changed:
<
<
The computational model...
>
>

Computational Model

 
Changed:
<
<
Return to top

Results

>
>
The computational model...
 
Changed:
<
<
The results...
>
>
Return to top
 
Changed:
<
<
Return to top

Conclusions

>
>

Results

 
Changed:
<
<
In conclusion...
>
>
The results...
 
Changed:
<
<
Return to top
>
>
Return to top

Conclusions

In conclusion...

Return to top

 
Changed:
<
<
>
>
 
Changed:
<
<
>
>
 
Changed:
<
<
>
>
 
Changed:
<
<

Student Tasks

>
>
 
Changed:
<
<
  1. Write a columnwise formulation to solve the Airline Rostering Problem. Generate feasible shifts for your formulation using any method you choose, be sure that your method generates all possible shifts. The spreadsheet airline_demo.xls shows some of the possible shifts. Solve the Airline Rostering Problem and write a management summary.

    Hint Using depth-first search or power sets in AMPL is difficult for this problem. Using a different programming language to generate the shifts, or generating them by hand using a carefully thought out method may be easier.

    What to hand in Your model file. A description of your shift generation method. Your management summary.

>
>
 
Changed:
<
<
Return to top
>
>
 
META FORM name="OpsRes.CaseStudyForm"
FORM FIELD Title Title AirCrewRostering
FORM FIELD DateSubmitted DateSubmitted 20 Feb 2008
Added:
>
>
FORM FIELD CaseStudyType CaseStudyType DIYCaseStudy
 
FORM FIELD OperationsResearchTopics OperationsResearchTopics
FORM FIELD ApplicationAreas ApplicationAreas
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AIR CREW ROSTERING PROBLEM*

Adapted from a real-world problem

An airline is trying to roster captains for 6 flights. The flight schedules are:

flights.jpg

Only one captain is required for each sector, but a captain may be a passenger on a flight (this is called paxing). In addition to the six flights above the following flights are available for paxing and operate every 2 hours:

recurring_flights.jpg

The following rules for shifts must be observed:

  • Shifts start and finish at a captain’s home base;
  • The earliest start time is on Day 1 (0001 hours) and the latest finish time is on Day 6 (2359 hours);
  • Shifts are composed of blocks of work. Each block must be no more than 13 hours;
  • Captains must have at least 12 hours break between blocks. The exception is when a block consists only of paxing flights, then a 9 hour break is all that is needed;
  • There must be a 30 min break between sector changes.

There are 6 captains available for work, 2 based in Auckland (AKL), 1 based in Christchurch (CHCH) and 3 based in Singapore (SNG). Each captain is paid $1000 for each block of work (even if it is only a 45 min pax). Each captain’s contract guarantees he/she will be paid for 3 blocks of work even if they perform less.

The airline has started an AMPL model, but given up:

FLIGHT_SCHEDULE.MOD

model;

set TODS; # T(our) O(f) D(uty) set = pilot schedules
set FLYS {TODS} within FLIGHTS;

param Blocks {TODS} integer >= 1;
param Base {TODS} symbolic within BASES;

They have asked you to complete their model file and write a data file and script file to solve their rostering problem.

The airline is also curious if they can reduce the cost of their roster by using less pilots. As a second deliverable, they have asked you to investigate this option. |

 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback