Revision 122009-07-23 - CameronWalker

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

<-- Under Construction -->

Line: 86 to 86

FORM FIELD CaseStudyType	CaseStudyType	DIYCaseStudy
FORM FIELD OperationsResearchTopics	OperationsResearchTopics	IntegerProgramming
FORM FIELD ApplicationAreas	ApplicationAreas	Rostering

Changed:

<
<

|*FORM FIELD ProblemDescription*|ProblemDescription|*Adapted from a real-world problem*

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

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:

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 minise the cost of covering the flights.

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

>
>

|*FORM FIELD ProblemDescription*|ProblemDescription|*Adapted from a real-world problem*

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

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:

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. |

FORM FIELD ProblemFormulation	ProblemFormulation	The formulation...
FORM FIELD ComputationalModel	ComputationalModel	The computational model...
FORM FIELD Results	Results	The results...

Revision 112008-05-07 - TWikiAdminUser

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

<-- Under Construction -->

Line: 92 to 92

FORM FIELD Results	Results	The results...
FORM FIELD Conclusions	Conclusions	In conclusion...
FORM FIELD ExtraForExperts	ExtraForExperts

Changed:

<
<

|*FORM FIELD StudentTasks*|StudentTasks|

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 method. 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.

|

>
>

|*FORM FIELD StudentTasks*|StudentTasks|

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.

|

META FILEATTACHMENT	attachment="flights.jpg" attr="h" comment="" date="1203501646" name="flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" size="44700" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT	attachment="recurring_flights.jpg" attr="h" comment="" date="1203501673" name="recurring_flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" size="24381" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" tmpFilename="" user="LaurenJackson" version="1"
META FILEATTACHMENT	attachment="airline_demo.xls" attr="" comment="" date="1210165005" name="airline_demo.xls" path="airline_demo.xls" size="17920" stream="airline_demo.xls" tmpFilename="" user="BaseUserMapping_333" version="2"

Revision 102008-05-07 - TWikiAdminUser

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

<-- Under Construction -->

Line: 80 to 80

Deleted:

<
<

airline_demo.xls: airline_demo.xls

META FORM	name="OpsRes.CaseStudyForm"
FORM FIELD Title	Title	AirCrewRostering
FORM FIELD DateSubmitted	DateSubmitted	20 Feb 2008

Line: 94 to 92

FORM FIELD Results	Results	The results...
FORM FIELD Conclusions	Conclusions	In conclusion...
FORM FIELD ExtraForExperts	ExtraForExperts

Changed:

<
<

|*FORM FIELD StudentTasks*|StudentTasks|

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. Solve the Airline Rostering Problem and write a management summary.
Hint Using depth-first search or power sets in AMPL is difficult for this method. 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.

|

>
>

|*FORM FIELD StudentTasks*|StudentTasks|

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 method. 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.

|

META FILEATTACHMENT

attachment="flights.jpg" attr="h" comment="" date="1203501646" name="flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" size="44700" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

META FILEATTACHMENT

attachment="recurring_flights.jpg" attr="h" comment="" date="1203501673" name="recurring_flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" size="24381" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

Changed:

<
<

META FILEATTACHMENT	attachment="airline_demo.xls" attr="" comment="" date="1210164051" name="airline_demo.xls" path="airline_demo.xls" size="24064" stream="airline_demo.xls" tmpFilename="" user="BaseUserMapping_333" version="1"

>
>

META FILEATTACHMENT	attachment="airline_demo.xls" attr="" comment="" date="1210165005" name="airline_demo.xls" path="airline_demo.xls" size="17920" stream="airline_demo.xls" tmpFilename="" user="BaseUserMapping_333" version="2"

Revision 92008-05-07 - TWikiAdminUser

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

<-- Under Construction -->

Line: 80 to 80

Added:

>
>

airline_demo.xls: airline_demo.xls

META FORM	name="OpsRes.CaseStudyForm"
FORM FIELD Title	Title	AirCrewRostering
FORM FIELD DateSubmitted	DateSubmitted	20 Feb 2008
FORM FIELD CaseStudyType	CaseStudyType	DIYCaseStudy
FORM FIELD OperationsResearchTopics	OperationsResearchTopics	IntegerProgramming

Changed:

<
<

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:

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:

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. |

>
>

FORM FIELD ApplicationAreas	ApplicationAreas	Rostering

|*FORM FIELD ProblemDescription*|ProblemDescription|*Adapted from a real-world problem*

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

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:

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 minise the cost of covering the flights.

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

FORM FIELD ProblemFormulation	ProblemFormulation	The formulation...
FORM FIELD ComputationalModel	ComputationalModel	The computational model...
FORM FIELD Results	Results	The results...
FORM FIELD Conclusions	Conclusions	In conclusion...
FORM FIELD ExtraForExperts	ExtraForExperts

Changed:

<
<

|*FORM FIELD StudentTasks*|StudentTasks|*STUDENT TASKS*

1. Add a ??? LINK ?? columnwise formulation for finding a pilot roster flight_schedule.mod.

What to hand in Your completed flight_schedule.mod file.

2. Design a system/process for generating all possible Tours of Duty (TODs). Generate the TODs to create flight_schedule.dat.

What to hand in A brief (less than 1 page) description of your system/process. Your flight_schedule.dat file.

3. Solve The Air Crew Rostering Problem. Be sure to investigate the possibility of less pilots.

What to hand in A management summary of your solution.

Extra for Experts' Tasks

1. The airline had hired another AMPL consultant to generate TODs automatically. She had almost finished before going on parental leave. She has left a multitude of files in a zip archive:

??? LINK ??? flights.zip

All the files are complete except flight_schedule.run (there is an incomplete version in the archive). Complete flight_schedule.run and run generating_flights.run to solve The Air Crew Rostering Problem.

What to hand in Your completed flight_schedule.run file. A comment on whether your solution from generating_flights.run agrees with your solution where you generated the TODs yourself.

|

>
>

|*FORM FIELD StudentTasks*|StudentTasks|

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. Solve the Airline Rostering Problem and write a management summary.
Hint Using depth-first search or power sets in AMPL is difficult for this method. 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.

|

META FILEATTACHMENT

attachment="flights.jpg" attr="h" comment="" date="1203501646" name="flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" size="44700" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

META FILEATTACHMENT

attachment="recurring_flights.jpg" attr="h" comment="" date="1203501673" name="recurring_flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" size="24381" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

Added:

>
>

META FILEATTACHMENT	attachment="airline_demo.xls" attr="" comment="" date="1210164051" name="airline_demo.xls" path="airline_demo.xls" size="24064" stream="airline_demo.xls" tmpFilename="" user="BaseUserMapping_333" version="1"

Revision 82008-05-07 - TWikiAdminUser

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

<-- Under Construction -->

Line: 84 to 84

FORM FIELD Title	Title	AirCrewRostering
FORM FIELD DateSubmitted	DateSubmitted	20 Feb 2008
FORM FIELD CaseStudyType	CaseStudyType	DIYCaseStudy

Changed:

<
<

FORM FIELD OperationsResearchTopics	OperationsResearchTopics

>
>

FORM FIELD OperationsResearchTopics	OperationsResearchTopics	IntegerProgramming

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:

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:

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. |

FORM FIELD ProblemFormulation	ProblemFormulation	The formulation...

Line: 93 to 93

FORM FIELD Conclusions	Conclusions	In conclusion...
FORM FIELD ExtraForExperts	ExtraForExperts

|*FORM FIELD StudentTasks*|StudentTasks|*STUDENT TASKS*

1. Add a ??? LINK ?? columnwise formulation for finding a pilot roster flight_schedule.mod.

What to hand in Your completed flight_schedule.mod file.

2. Design a system/process for generating all possible Tours of Duty (TODs). Generate the TODs to create flight_schedule.dat.

What to hand in A brief (less than 1 page) description of your system/process. Your flight_schedule.dat file.

3. Solve The Air Crew Rostering Problem. Be sure to investigate the possibility of less pilots.

What to hand in A management summary of your solution.

Extra for Experts' Tasks

1. The airline had hired another AMPL consultant to generate TODs automatically. She had almost finished before going on parental leave. She has left a multitude of files in a zip archive:

??? LINK ??? flights.zip

All the files are complete except flight_schedule.run (there is an incomplete version in the archive). Complete flight_schedule.run and run generating_flights.run to solve The Air Crew Rostering Problem.

What to hand in Your completed flight_schedule.run file. A comment on whether your solution from generating_flights.run agrees with your solution where you generated the TODs yourself.

|

Changed:

<
<

META FILEATTACHMENT

attachment="flights.jpg" attr="" comment="" date="1203501646" name="flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" size="44700" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

META FILEATTACHMENT

attachment="recurring_flights.jpg" attr="" comment="" date="1203501673" name="recurring_flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" size="24381" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

>
>

META FILEATTACHMENT

attachment="flights.jpg" attr="h" comment="" date="1203501646" name="flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" size="44700" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

META FILEATTACHMENT

attachment="recurring_flights.jpg" attr="h" comment="" date="1203501673" name="recurring_flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" size="24381" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

Revision 72008-04-02 - TWikiAdminUser

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

<-- Under Construction -->

Line: 40 to 40

Return to top

Changed:

<
<

Computational Model

>
>

Computational Model

The computational model...

Line: 48 to 48

Return to top

Changed:

<
<

Results

>
>

Results

The results...

Line: 56 to 56

Return to top

Changed:

<
<

Conclusions

>
>

Conclusions

In conclusion...

Revision 62008-03-01 - TWikiAdminUser

  META TOPICPARENT 
 name="SubmitCaseStudy" 

<-- Under Construction -->
- META TOPICPARENT
+ name="SubmitCaseStudy"
  Operations Research Topics: IntegerProgramming 
 Application Areas: Rostering 
 Contents
-<
<
+ Problem Description
 Problem Formulation
 Computational Model
 Results
 Conclusions
->
>
+ Problem Description
 Problem Formulation
 Computational Model
 Results
 Conclusions
   Problem Description 

Adapted from a real-world problem

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



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:



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 
  Problem Formulation
-<
<
+The formulation...
->
>
+The formulation...
 Return to top

  Computational Model
-<
<
+The computational model...
->
>
+The computational model...
 Return to top

  Results
-<
<
+The results...
->
>
+The results...
 Return to top

  Conclusions
-<
<
+In conclusion...
->
>
+In conclusion...
 Return to top
-<
<
->
>
+<--

-->
-<
<
->
>
+<--

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.

-->

Revision 52008-03-01 - TWikiAdminUser

  META TOPICPARENT 
 name="SubmitCaseStudy" 

<-- Under Construction -->
- META TOPICPARENT
+ name="SubmitCaseStudy"
  Operations Research Topics: IntegerProgramming 
 Application Areas: Rostering 
 Contents
-<
<
+ Problem Description 
  Problem Formulation 
  Computational Model 
  Results 
  Conclusions 
 
 

 StudentTasks
->
>
+ Problem Description
 Problem Formulation
 Computational Model
 Results
 Conclusions
   Problem Description 

Adapted from a real-world problem

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



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:



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
-<
<
+  Problem Formulation
->
>
+  Problem Formulation
-<
<
+The formulation...
->
>
+The formulation...
-<
<
+Return to top
  Computational Model
->
>
+Return to top
-<
<
+The computational model...
->
>
+  Computational Model
-<
<
+Return to top
  Results
->
>
+The computational model...
-<
<
+The results...
->
>
+Return to top
-<
<
+Return to top
  Conclusions
->
>
+  Results
-<
<
+In conclusion...
->
>
+The results...
-<
<
+Return to top
->
>
+Return to top

  Conclusions 

In conclusion...

Return to top
-<
<
->
>
-<
<
->
>
-<
<
->
>
-<
<
+  Student Tasks
->
>
-<
<
+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.
->
>
-<
<
+Return to top
->
>
  META FORM 
 name="OpsRes.CaseStudyForm" 


 FORM FIELD Title 
 Title 
 AirCrewRostering 


 FORM FIELD DateSubmitted 
 DateSubmitted 
 20 Feb 2008
- META FORM
+ name="OpsRes.CaseStudyForm"
- FORM FIELD Title
+ AirCrewRostering
- FORM FIELD DateSubmitted
+Feb 2008
->
>
+ FORM FIELD CaseStudyType 
 CaseStudyType 
 DIYCaseStudy
- FORM FIELD 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:



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:



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.
|

Revision 42008-02-23 - MichaelOSullivan

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

Added:

>
>

<-- Under Construction -->

Revision 32008-02-20 - LaurenJackson

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

Revision 22008-02-20 - LaurenJackson

Line: 1 to 1

META TOPICPARENT	name="SubmitCaseStudy"

Revision 12008-02-20 - LaurenJackson

Line: 1 to 1

Added:

>
>

META TOPICPARENT	name="SubmitCaseStudy"

<-- This template controls both the look and functionality of case study topics. You should not need to alter the layout, only edit the data using the form above.

Set the view and edit templates: Comment out the next line to use the TWiki default view

Set VIEW_TEMPLATE = CaseStudyView

Comment out the next line to use the TWiki default edit

Set EDIT_TEMPLATE = CaseStudyEdit

-->

<--
This topic can only be changed by: 
 Set ALLOWTOPICCHANGE = TWikiAdminGroup, MaintenanceGroup, ContributorGroup
 
-->

Case Study: AirCrewRostering

Submitted: 20 Feb 2008

Operations Research Topics: IntegerProgramming

Application Areas: Rostering

Problem Description

Adapted from a real-world problem

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

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:

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

Problem Formulation

The formulation...

Return to top

Computational Model

The computational model...

Return to top

Results

The results...

Return to top

Conclusions

In conclusion...

Return to top

Student Tasks

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.

Return to top

META FORM	name="OpsRes.CaseStudyForm"
FORM FIELD Title	Title	AirCrewRostering
FORM FIELD DateSubmitted	DateSubmitted	20 Feb 2008
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:

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:

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. |

FORM FIELD ProblemFormulation	ProblemFormulation	The formulation...
FORM FIELD ComputationalModel	ComputationalModel	The computational model...
FORM FIELD Results	Results	The results...
FORM FIELD Conclusions	Conclusions	In conclusion...
FORM FIELD ExtraForExperts	ExtraForExperts

|*FORM FIELD StudentTasks*|StudentTasks|*STUDENT TASKS*

1. Add a ??? LINK ?? columnwise formulation for finding a pilot roster flight_schedule.mod.

What to hand in Your completed flight_schedule.mod file.

2. Design a system/process for generating all possible Tours of Duty (TODs). Generate the TODs to create flight_schedule.dat.

What to hand in A brief (less than 1 page) description of your system/process. Your flight_schedule.dat file.

3. Solve The Air Crew Rostering Problem. Be sure to investigate the possibility of less pilots.

What to hand in A management summary of your solution.

Extra for Experts' Tasks

1. The airline had hired another AMPL consultant to generate TODs automatically. She had almost finished before going on parental leave. She has left a multitude of files in a zip archive:

??? LINK ??? flights.zip

All the files are complete except flight_schedule.run (there is an incomplete version in the archive). Complete flight_schedule.run and run generating_flights.run to solve The Air Crew Rostering Problem.

What to hand in Your completed flight_schedule.run file. A comment on whether your solution from generating_flights.run agrees with your solution where you generated the TODs yourself.

|

META FILEATTACHMENT

attachment="flights.jpg" attr="" comment="" date="1203501646" name="flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" size="44700" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

META FILEATTACHMENT

attachment="recurring_flights.jpg" attr="" comment="" date="1203501673" name="recurring_flights.jpg" path="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" size="24381" stream="C:\Users\Lauren Jackson\Documents\Desktop\Desktop stuff\Twiki\Twiki images\AirCrewRostering\recurring_flights.jpg" tmpFilename="" user="LaurenJackson" version="1"

View topic | History: r12 < r11 < r10 < r9 | More topic actions...

Difference: AirCrewRostering (1 vs. 12)

Revision 122009-07-23 - CameronWalker

Revision 112008-05-07 - TWikiAdminUser

Revision 102008-05-07 - TWikiAdminUser

Revision 92008-05-07 - TWikiAdminUser

Revision 82008-05-07 - TWikiAdminUser

Revision 72008-04-02 - TWikiAdminUser

Computational Model

Computational Model

Results

Results

Conclusions

Conclusions

Revision 62008-03-01 - TWikiAdminUser

Operations Research Topics: IntegerProgramming

Application Areas: Rostering

Contents

Problem Description

Problem Formulation

Computational Model

Results

Conclusions

Revision 52008-03-01 - TWikiAdminUser

Operations Research Topics: IntegerProgramming

Application Areas: Rostering

Contents

Problem Description

Problem Formulation

Problem Formulation

Computational Model

Computational Model

Results

Conclusions

Results

Conclusions

Student Tasks

Revision 42008-02-23 - MichaelOSullivan

Revision 32008-02-20 - LaurenJackson

Revision 22008-02-20 - LaurenJackson

Revision 12008-02-20 - LaurenJackson

Case Study: AirCrewRostering

Submitted: 20 Feb 2008

Operations Research Topics: IntegerProgramming

Application Areas: Rostering

Contents

Problem Description

Problem Formulation

Computational Model

Results

Conclusions

Student Tasks