# Difference: AirCrewRostering (1 vs. 12)

#### Revision 122009-07-23 - CameronWalker

Line: 1 to 1

 META TOPICPARENT name="SubmitCaseStudy"
`<-- Under Construction -->`
Line: 86 to 86

 FORM FIELD CaseStudyType FORM FIELD OperationsResearchTopics CaseStudyType DIYCaseStudy OperationsResearchTopics IntegerProgramming 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 FORM FIELD ComputationalModel ProblemFormulation The formulation... ComputationalModel The computational model... Results The results...

Line: 1 to 1

 META TOPICPARENT name="SubmitCaseStudy"
`<-- Under Construction -->`
Line: 92 to 92

 FORM FIELD Results FORM FIELD Conclusions Results The results... Conclusions In conclusion... ExtraForExperts
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 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.

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

|

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

Line: 1 to 1

 META TOPICPARENT name="SubmitCaseStudy"
`<-- Under Construction -->`
Line: 80 to 80

Deleted:
<
<

 META FORM FORM FIELD Title name="OpsRes.CaseStudyForm" Title AirCrewRostering DateSubmitted 20 Feb 2008
Line: 94 to 92

 FORM FIELD Results FORM FIELD Conclusions Results The results... Conclusions In conclusion... ExtraForExperts
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. 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.

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

Line: 1 to 1

 META TOPICPARENT name="SubmitCaseStudy"
`<-- Under Construction -->`
Line: 80 to 80

>
>

 META FORM FORM FIELD Title name="OpsRes.CaseStudyForm" Title AirCrewRostering DateSubmitted 20 Feb 2008 CaseStudyType DIYCaseStudy OperationsResearchTopics IntegerProgramming
Changed:
<
<
 FORM FIELD ApplicationAreas ApplicationAreas
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AIR CREW ROSTERING 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 FORM FIELD ComputationalModel ProblemFormulation The formulation... ComputationalModel The computational model... Results The results... Conclusions In conclusion... ExtraForExperts
Changed:
<
<

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.

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:

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.

|
>
>
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. 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" 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="1210164051" name="airline_demo.xls" path="airline_demo.xls" size="24064" stream="airline_demo.xls" tmpFilename="" user="BaseUserMapping_333" version="1"

Line: 1 to 1

 META TOPICPARENT name="SubmitCaseStudy"
`<-- Under Construction -->`
Line: 84 to 84

 FORM FIELD Title FORM FIELD DateSubmitted Title AirCrewRostering DateSubmitted 20 Feb 2008 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*

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 FORM FIELD ExtraForExperts Conclusions In conclusion... ExtraForExperts

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.

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:

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

Line: 1 to 1

 META TOPICPARENT name="SubmitCaseStudy"
`<-- Under Construction -->`
Line: 40 to 40
Changed:
<
<

>
>

## Computational Model

The computational model...

Line: 48 to 48
Changed:
<
<

>
>

The results...

Line: 56 to 56
Changed:
<
<

>
>

## Conclusions

In conclusion...

Line: 1 to 1

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

Changed:
<
<
>
>

## Problem Description

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.

Line: 36 to 34

## Problem Formulation

Changed:
<
<
The formulation...
>
>
The formulation...

## Computational Model

Changed:
<
<
The computational model...
>
>
The computational model...

Changed:
<
<
The results...
>
>
The results...

## Conclusions

Changed:
<
<
In conclusion...
>
>
In conclusion...

Changed:
<
<
>
>
```<--

-->```

Changed:
<
<
>
>
```<--

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.

-->```

Line: 1 to 1

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

Changed:
<
<

>
>

## Problem Description

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.

Changed:
<
<

>
>

## Problem Formulation

Changed:
<
<
The formulation...
>
>
The formulation...

Changed:
<
<

## Computational Model

>
>

Changed:
<
<
The computational model...
>
>

Changed:
<
<

## Results

>
>
The computational model...

Changed:
<
<
The results...
>
>

Changed:
<
<

>
>

Changed:
<
<
In conclusion...
>
>
The results...

Changed:
<
<
>
>

## Conclusions

In conclusion...

Changed:
<
<
>
>

Changed:
<
<
>
>

Changed:
<
<
>
>

Changed:
<
<

>
>

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

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

 FORM FIELD OperationsResearchTopics OperationsResearchTopics ApplicationAreas
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AIR CREW ROSTERING 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"
>
>
`<-- 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
>
>
 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

## Problem Description

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.

## Problem Formulation

The formulation...

## Computational Model

The computational model...

The results...

## Conclusions

In conclusion...

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.

 META FORM FORM FIELD Title name="OpsRes.CaseStudyForm" Title AirCrewRostering DateSubmitted 20 Feb 2008 OperationsResearchTopics ApplicationAreas
|*FORM FIELD ProblemDescription*|ProblemDescription|*THE AIR CREW ROSTERING 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 FORM FIELD ComputationalModel ProblemFormulation The formulation... ComputationalModel The computational model... Results The results... Conclusions In conclusion... ExtraForExperts

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.

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:

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.