صفحه 1:
Airline Crew Scheduling
Problem
(CSP)
Ahmad Khayer Dastjerdi
256622
صفحه 2:
Review
~ Introduction
» Scheduling Process
* Airline Crew Scheduling Problem
» Model
» Solution Approaches
» Case Study
صفحه 3:
Introduction:
* Airline crew scheduling is a well-studied field in
OR.
* Second cost-relevant factor after fuel
* Misunderstanding and disharmonies among the
crew :
negative effect on the airline's customers.
* Highly competitive global market
SE ee eer ee ee een nee
صفحه 4:
Introduction
(Con’d)
Dominant driving forces for airline companies :
* Cost Minimization
* Customer Satisfaction
Other important fields:
ماك ةا"
Training of staff
- Employee satisfaction
معصهصهکنهم خصمعو جوا عوماء عطا ومتلامء : عه19۵ وصنقهما (18)2002 حهصءه/1(۳
UGE mV CCB IES Cag) ۷
صفحه 5:
:Scheduling Process
-The main business of an airline is to offer and execute
flights in such a way that profit is maximized
-Underlying scheduling tasks that need to be fulfilled:
+ Which flights are offered.
0 Wile nees MG Rel cp NECN
Da iytta weet lce cite elie ictmiy to Mero rer Cpe
+ How the schedule execution is controlled and unpredictable events
are handled.
1) Branch-and-Price Column:Generation for Solving Huge Integer Programs. Barnhart C, Cohn AM, Johnson EL, Klabjan D,
0
صفحه 6:
5 2 Block and
Dus cGy صمت یت نیت
وتات مهو
د نت
SON Str evrene ted 8
0020200000 ين
05 4
وستصمهام طتعهممع. يي
ا 2
Bares ates
Scheduling Assignment
منم همه
1 ee cee coer ENC Te eae
Pee Seo معمهلا 61 ععكناقطصءل! 881 )2003(
صفحه 7:
:Airline Crew Scheduling Problem (CSP)
+ The largest scheduling problem
+ Its task is to assign all flights of a given timetable
together with further activities to a توافت ار 0
crew members stationed
ةا
0 (BALAJI GOPALAKRISHNAN, ELLIS. L. JOHNSON 2005)
00 rae juling approach with tim een creer ent ott
صفحه 8:
:Basic definitions
A flight leg: is a non-stop air transit from a departure
airport to its corresponding destination airport.
A flight duty: is a series of flight legs that can be
serviced by one crew member within a workday (24
hours) .
A transit: occurs if the crew members' time-
dependent location does not equal to the next
scheduled location.
A pairing: which starts from and returns to the crew
member’s home base. Its maximum duration is limited
by a given upper bound, e.g..five working days.
صفحه 9:
Pre-scheduled activities. like vacation, simulation,
training; medical examinations, etc. represent
activities that a crew member has to undertake
without exception.
A roster or line-of-work (LOW): represents a
potential crew schedule for a dedicated crew member
of the planning periods of usually two or four weeks.
one eat ease Reon ne rc neem Om CCRC ctr eee Len eer ae NC COS
EL, Klabjan D, Nemhauser GL, Vance PH (2003)
Oe caer meee te ee UCL Ce MCT Nace enV TiCtcd
Routing Problem. ( Mellouli 2001)
صفحه 10:
Roster Example
dayt day2 day3 day4 dayS
2۱ [ 0 2 Roster
cays, اجه
23:59
Flight duty
17:35
emt | Flight
17:38
صفحه 11:
:The Crew Scheduling Problem
* Crew Pairing, Problem (CPP)
* Crew Assignment Problem (CAP) or
airline Crew Rostering Problem (CRP)
ا وسهای)خهمناههج0 ما وحتصصعاط همق وصتلعلعطع۹ مدع ماعته
صفحه 12:
Viodel for crew pairing problem
Airline Crew Scheduling: State-of-the-Art BALAJI GOPALAKRISHNANELLIS. L. JOHNSON(2005)
صفحه 13:
‘An example
ای ره ۱ اف کی ۰
i 8 7 6 0 A
مكب السك ا cre (ec تكو
م ل 1۹0 11:30- 10:00- roe
1230 11:00
The second plane flies between Atlanta and New York
۳ I H G
3 ۸ ee 7 1۳92
ore 14:30- 12:00- 0
The third plane goes on alAtlanta, New'¥6tk, MetiPhis |Atlanta
0 0 ان رد 8 K
Mem Ad | ۱۱ rena Mem=Ad | NY—-Mem | au—Nv
Yanserere 7 ae 11:45- ۳۳7 9
14:00 120
AB,CD,EF,GH.U,KLM,NOP for total cost 6.25
ABCDEF,GHI,KLMNOP for total cost 6.00
AB, CDU, GHEF, KLMNOP for total cost 4.75
صفحه 14:
Is there a cheaper
?combination available
In order to be certain, we
would have to check all
pairings
صفحه 15:
Model for crew assignment problem
Pter ces arc rps eon e Cer eset
Claude P. Medard Nidhi Sawhney, An integrated aircraft routing, crew scheduling and
flight retiming model (Anne Mercier, Francois Soumis 2005)
صفحه 16:
:Solution approach
* Constructive heuristics
* Mathematical Programming
Branch-and-Bound
Branch-and-Cut
۰ Network-based Models
* Meta-Heuristics
۱6/۶ ۱
Simulated Annealing
صفحه 17:
۱۱0
Hotel stays
Transit
Hotel cost
Transit cost
Total cost
ete
(%
100
100
100
100
100
Manual
)schedule
mene nace ty
3
Autom.
)Schedule
27
76.29
113.16
61.93
106.38
88.50
Serer se
Case study:
(European tourist airline)
Total
%) Saving
(
DS
13.16-
38.07
6.58-
11.50
Tee eee
ممم 5
Suhl, Markus P. Thiel 2}
price 0
erring!
and multipl
Yufeng Guo|
صفحه 18:
Thank you for your
attention