Universiteit Gent Faculteit Economie en Bedrijfskunde. Personeelsplanning in de luchtvaartsector: Case Brussels Airlines. Bruce Fecheyr-Lippens

Universiteit Gent Faculteit Economie en Bedrijfskunde Academiejaar 2006-2007

Personeelsplanning in de luchtvaartsector: Case Brussels Airlines

Scriptie voorgedragen tot het bekomen van de graad van licentiaat in de toegepaste economische wetenschappen

Bruce Fecheyr-Lippens onder leiding van Prof. dr. Mario Vanhoucke

“Permission”


B. Fecheyr - Lippens

Woord vooraf Het schrijven van een scriptie vergt discipline, kennis en motivatie, maar vooral passie en liefde voor het gekozen onderwerp. Je hebt deze kenmerken zelf in de hand. Doch, je staat er niet alleen voor. In de eerste plaats wil ik doctoraatstudent Broos Maenhout feliciteren met zijn krachtig algoritme voor het oplossen van de case en wil ik hem bedanken voor het delen van zijn kennis en onze uitstekende samenwerking. SN Brussels Airlines en in het bijzonder de heer Dobbelstein ben ik zeer dankbaar, voor de verkregen informatie en de openheid die de man siert. Zonder hen zou de case niet tot stand gekomen zijn. Een speciale attentie voor Julie die me de afgelopen jaren altijd heeft gesteund, mijn kennis heeft verruimd en altijd klaarstaat met een helpend hand. In het bijzonder wil ik ze bedanken voor het nalezen van de scriptie. Verder wil ik benadrukken hoe belangrijk een sterk thuisfront is als eerste ingrediënt voor een succesvolle studieperiode. Mijn moeder, Andrew, Daphne, Brecht en Alec wil ik bedanken voor de verkregen hulp. Mijn vader verdient een dankwoord voor het delen van zijn ervaringen en enthousiasme in de luchtvaart.

April 2007, Bruce Fecheyr-Lippens

I



Inhoudsopgave 1

INLEIDING ............................................................................................................................................... 1

2

PLANNING EN OPTIMALISATIE IN DE LUCHTVAARTSECTOR .................................................................... 4 2.1 2.2 2.3 2.4 2.5 2.6 2.7

3

PERSONEELSPLANNING IN DE LUCHTVAARTSECTOR: HET “AIRLINE CREW SCHEDULING PROBLEM” .... 13 3.1 3.2 3.3 3.4 3.5

4

DEFINIËRING EN SITUERING ............................................................................................................................ 13 HET BELANG VAN PERSONEELSPLANNING .......................................................................................................... 14 TERMINOLOGIE ............................................................................................................................................ 16 COMPONENTEN EN OBJECTIEVEN VAN HET CREW SCHEDULING PROCES ................................................................... 22 RELEVANTE LITERATUUR ................................................................................................................................ 28

OPTIMALISATIESTRATEGIE: SEQUENTIE VERSUS INTEGRATIE ............................................................... 29 4.1 4.2

5

VLUCHTPLANNING .......................................................................................................................................... 5 VLIEGTUIGPLANNING....................................................................................................................................... 6 HERPLANNING VAN VERSTORINGEN.................................................................................................................... 7 PLANNING VAN DE LANDINGEN ......................................................................................................................... 7 HET PLANNEN VAN DE GATE’S ........................................................................................................................... 9 STRATEGIE VOOR MAXIMALE TICKETINKOMSTEN ................................................................................................. 10 KLEINERE PLANNINGSDOMEINEN ..................................................................................................................... 11

PLANNINGSPROCEDURE ................................................................................................................................. 30 UITGEWERKT VOORBEELD .............................................................................................................................. 32

GEDETAILLEERDE ANALYSE VAN HET CREW ROSTERING PROBLEEM ..................................................... 36 5.1 CREW INFORMATIE ....................................................................................................................................... 38 5.2 TOE TE WIJZEN ACTIVITEITEN........................................................................................................................... 39 5.3 REGELS & WETGEVING .................................................................................................................................. 40 5.3.1 Voorbeelden van horizontale regels .............................................................................................. 43 5.3.2 Voorbeelden van verticale regels ................................................................................................... 47 5.4 DOELSTELLINGEN.......................................................................................................................................... 49

6

OPTIMALISATIETECHNIEKEN VOOR HET OPLOSSEN VAN HET CREW SCHEDULING PROBLEEM ............. 51 6.1 KENMERKEN VAN HET CREW SCHEDULING PROBLEEM .......................................................................................... 52 6.2 GENETISCH ALGORITME ................................................................................................................................. 54 6.3 SIMULATED ANNEALING ................................................................................................................................. 57 6.4 TABU SEARCH .............................................................................................................................................. 61 6.4.1 Algemene werking van het tabu serach algoritme ........................................................................ 61 6.4.2 Illustratief voorbeeld ...................................................................................................................... 62 6.4.3 Frequentie gebaseerd geheugen voor diversificatie en intensivering ............................................ 66 6.5 HYBRIDE COMBINATIES VOOR OPTIMALISATIE ..................................................................................................... 67

7

CASE SN BRUSSELS AIRLINES ................................................................................................................. 69 7.1 DE MAATSCHAPPIJ SN BRUSSELS AIRLINES ........................................................................................................ 70 7.1.1 Kort overzicht ................................................................................................................................. 70 7.1.2 Het crew scheduling departement ................................................................................................. 70

II



7.2 PROBLEEMSTELLING EN OPLOSSINGSMETHODIEK ................................................................................................ 73 7.3 HET HYBRIDE SCATTER SEARCH ALGORITME ........................................................................................................ 74 7.3.1 Objectieven .................................................................................................................................... 74 7.3.2 Probleemformulering ..................................................................................................................... 75 7.3.2.1 7.3.2.2

7.3.3

Hoofd rostering probleem ................................................................................................................... 75 Sub probleem ...................................................................................................................................... 78

Oplossingsmethodiek ..................................................................................................................... 80

7.3.3.1 7.3.3.2 7.3.3.3 7.3.3.4 7.3.3.5 7.3.3.6

Datarepresentatie en doelfunctie ....................................................................................................... 81 De “Diversification Generation” methode........................................................................................... 82 De “Subset Generation” methode ....................................................................................................... 83 De “Solution Combination” methode .................................................................................................. 84 De “Improvement” methode............................................................................................................... 85 De “Reference Set Update” methode ................................................................................................. 87

7.4 INPUT: DATACOLLECTIE EN DATABEWERKING...................................................................................................... 88 7.4.1 Datacollectie .................................................................................................................................. 88 7.4.2 Databewerking .............................................................................................................................. 90 7.5 VERWERKING: INPUTFILES, STRAFKOSTEN EN PARAMETERS ................................................................................... 92 7.5.1 Verwerking van de inputfiles ......................................................................................................... 92 7.5.2 Strafkosten en parameters ............................................................................................................ 93 7.6 OUTPUT, VERGELIJKENDE STUDIE EN BEPERKINGEN.............................................................................................. 94 7.6.1 Output en vergelijkende studie ...................................................................................................... 94 7.6.1.1 7.6.1.2 7.6.1.3 7.6.1.4

Doelstelling 1: gelijkverdeelde werkdruk ........................................................................................... 94 Doelstelling 2: minimale kosten ......................................................................................................... 95 Verdere analyse van de mogelijke besparingen .................................................................................. 96 Doelstelling 3 en 4: Individuele preferenties en robuustheid ............................................................ 99

7.6.2 Overzicht van de beperkingen...................................................................................................... 100 7.7 CONCLUSIES EN AANBEVELINGEN ................................................................................................................... 100 8

ALGEMEEN BESLUIT ............................................................................................................................ 102

9

LIJST VAN DE GERAADPLEEGDE WERKEN ............................................................................................... VI

10

BIJLAGE ................................................................................................................................................. XII 10.1 10.2 10.3 10.4

BIJLAGE A .............................................................................................................................................. XII BIJLAGE B .............................................................................................................................................XVI BIJLAGE C .............................................................................................................................................. XX BIJLAGE D ........................................................................................................................................... XXIII

III



Lijst van de tabellen TABEL 4.1. RESULTATEN SEQUENTIËLE AANPAK .............................................................................................................. 33 TABEL 4.2. RESULTATEN GEÏNTEGREERDE AANPAK .......................................................................................................... 34 TABEL 7.1. SUB ROSTERING PROBLEEM......................................................................................................................... 71 TABEL 7.2. MOTIVATIE CATEGORIEËN .......................................................................................................................... 91 TABEL 7.3. INGESTELDE STRAFKOSTEN .......................................................................................................................... 93 TABEL 7.4. INGESTELDE PARAMETERS........................................................................................................................... 93 TABEL 7.5. VERGELIJKING GELIJKVERDEELDE WERKDRUK .................................................................................................. 95 TABEL 7.6. VERGELIJKING VAN DE BETAALDE SOM AAN OVERUREN ..................................................................................... 96 TABEL 7.7. ASSUMPTIES ............................................................................................................................................ 97 TABEL 7.8. TOTALE POTENTIËLE BESPARINGEN ............................................................................................................... 98 TABEL 7.9. INVLOED VAN 4 % ANNULERINGEN PER MAAND .............................................................................................. 99 TABEL 7.10. OVERZICHT VAN DE BEPERKINGEN OP DE CASE .............................................................................................. 100

Lijst van de figuren FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR

2.1. 2.2. 2.3. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 3.9. 4.1. 4.2. 4.3. 4.4. 5.1. 5.2. 5.3. 5.4. 5.5. 5.6. 5.7. 6.1. 6.2.

PLANNINGSDOMEINEN IN DE LUCHTVAARTSECTOR EN AFBAKENING SCRIPTIE......................................................... 5 VARIATIE IN KOSTEN BINNEN DE TIME WINDOW .............................................................................................. 8 SEGMENTERING VAN DE REIZIGERS ............................................................................................................. 10 SITUERING PERSONEELSPLANNING.............................................................................................................. 13 COMPONENTEN TER BEPALING VAN DE WINST VAN EEN LUCHTVAARTMAATSCHAPPIJ ............................................ 15 VOORBEELD: BEGINSITUATIE .................................................................................................................... 17 MOGELIJKE PAIRING SAMENSTELLING.......................................................................................................... 18 PERSONEELSBESTAND VAN EEN LUCHTVAARTMAATSCHAPPIJ............................................................................ 19 MOGELIJKE INHOUDSCOMPONENTEN VAN EEN WERKROOSTER ........................................................................ 21 VOORBEELD VAN EEN WERKROOSTER.......................................................................................................... 22 VERGOEDING OP BASIS VAN EEN STAPSGEWIJZE LINEAIRE FUNCTIE .................................................................... 26 COMPONENTEN EN OBJECTIEVEN VAN HET CREW SCHEDULING PROCES .............................................................. 27 OVERZICHT PLANNINGSDOMEINEN DIE ELKAAR STERK BEÏNVLOEDEN ................................................................. 30 PLANNINGSSEQUENTIE VOOR LUCHTVAARTMAATSCHAPPIJEN .......................................................................... 31 SEQUENTIE VERSUS INTEGRATIE BEGINSITUATIE UITGEWERKT VOORBEELD .......................................................... 32 VERGELIJKING RESULTATEN ....................................................................................................................... 35 SITUERING CREW ROSTERING .................................................................................................................... 37 INPUTBLOKKEN VOOR HET CREW ROSTERING PROBLEEM ................................................................................. 38 INDELING VAN DE REGELS ......................................................................................................................... 42 OVERZICHT VAN DE HORIZONTALE REGELS ................................................................................................... 43 VOORBEELD LEGAAL WEEKROOSTER ........................................................................................................... 44 OVERZICHT VAN DE VERTICALE REGELS ........................................................................................................ 47 VOORBEELDEN VAN VERTICALE REGELS........................................................................................................ 48 FLOWCHART VAN EEN GENETISCH ALGORITME .............................................................................................. 55 WERKING VAN EEN LOKAAL ZOEKALGORITME ............................................................................................... 58

IV


FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR FIGUUR

6.3. 6.4. 6.5. 6.6. 6.7. 6.8. 6.9. 7.1. 7.2. 7.3. 7.4. 7.5. 7.6. 7.7. 7.8. 7.9.


FLOWCHART SIMULATED ANNEALING ......................................................................................................... 59 VOORBEELD TABU SEARCH: INITIËLE OPLOSSING ........................................................................................... 63 VOORBEELD TABU SEARCH: ITERATIE 0 ....................................................................................................... 64 VOORBEELD TABU SEARCH: ITERATIE 1 ...................................................................................................... 64 VOORBEELD TABU SEARCH: ITERATIE 2 ....................................................................................................... 65 VOORBEELD TABU SEARCH: ITERATIE 3 ....................................................................................................... 65 VOORBEELD TABU SEARCH: ITERATIE 4 ....................................................................................................... 66 DE VIER FACTOREN VOOR GELIJK VERDEELDE WERKDRUK BIJ SN BRUSSELS AIRLINES............................................. 72 LOONBAREMA'S BIJ SN BRUSSELS AIRLINES ................................................................................................. 73 VOORBEELD PROBLEEM............................................................................................................................ 79 NETWERKSTRUCTUUR VOOR EEN PERSONEELSLID .......................................................................................... 80 FLOWCHART SCATTER SEARCH ALGORITME .................................................................................................. 81 DATAREPRESENTATIE............................................................................................................................... 82 STRUCTUUR VAN DE CASE ......................................................................................................................... 88 INFORMATIEBRONNEN ............................................................................................................................. 89 KANALEN DIE LEIDEN TOT ONRECHTSTREEKS BESPARINGEN .............................................................................. 97

V



1 Inleiding De luchtvaartsector is uiterst complex en bestaat uit talloze deelgebieden die zo goed mogelijk op elkaar moeten worden afgestemd. Door het groeiend luchtverkeer, de hevige competitie en de hoge graad van complexiteit die de luchtvaartsector domineren is de vraag naar

beslissingsondersteunende

instrumenten

groter

dan

ooit.

Voor

luchtvaartmaatschappijen is het dezer dagen moeilijk om te overleven door de hevige concurrentiestrijd. Daarom is het onontbeerlijk dat een luchtvaartmaatschappij streeft naar efficiëntie en kostenreductie. De tweede grootste kost, na de brandstofkosten, zijn de personeelskosten. Daarenboven kan een efficiënte personeelsplanning de kosten drastisch verlagen. Een optimale planning van het personeel is dus een belangrijke taak voor de luchtvaartmaatschappijen. Personeelsplanning

in

de

luchtvaartsector

is

slechts

één

van

de

vele

planningsproblemen die de luchtvaartsector moet oplossen. Operationele onderzoekers noemen dit optimalisatieprobleem het “Airline Crew Scheduling” probleem. De probleemstelling die zo optimaal mogelijk moet worden opgelost bestaat uit twee stappen. Eerst moeten strategisch gekozen vluchtsequenties, pairings genaamd, worden gegenereerd. Daarna volgt de toewijzingsprocedure. In het bijzonder moet het personeel toegewezen worden aan deze pairings en aan andere activiteiten die de maatschappij doet, en moeten individuele werkroosters worden opgesteld. De twee stappen worden respectievelijk crew pairing en crew rostering genoemd. Het belangrijkste doel dat crew scheduling nastreeft, vormt het genereren van een efficiënte personeelsplanning die de kosten minimaliseert, terwijl de set van beperkingen wordt gerespecteerd. In het kader van deze scriptie worden eerst de voornaamste planningsdomeinen kort uiteengezet. Daarna begint een verticale analyse van de personeelsplanning. De focus zal gericht zijn op het crew rostering probleem omdat dit probleem in operationeel onderzoek minder aandacht geniet dan het crew pairing probleem. Naast minimale kosten streeft crew rostering daarenboven ook naar een gelijkverdeelde werkdruk tussen de roosters. Deze redenen hebben de doorslag gegeven voor het onderzoeken van crew rostering en niet crew pairing.

1



Het doel van de scriptie is tweevoudig. Ten eerste, streeft de scriptie naar het schetsen van een globaal beeld van de luchtvaartsector in zijn geheel van complexe plannings- en optimalisatieproblemen. Dit deel is heel uitgebreid omwille van de complexiteit die heerst in de sector, maar is onontbeerlijk om de nodige kennis op te bouw voor de case gebaseerd op gegevens van SN Brussels Airlines. De literatuurstudie streeft ook expliciet naar het aanwakkeren van interesse in deze zo complexe maar boeiende sector. Ten tweede, wordt het crew rostering algoritme van Maenhout and Vanhoucke (2007) getest aan de hand van werkelijke cijfers van SN Brussels Airlines. Hun algoritme streeft naar het genereren van persoonlijke roosters met gelijkverdeelde werkdruk en zal kritisch worden geëvalueerd door middel van een vergelijkende studie tussen de automatisch gegenereerde werkroosters van het algoritme en de manueel opgestelde werkroosters door SN Brussels Airlines. Het doel van dit onderzoek vormt het aantonen dat het algoritme het crew rostering probleem perfect aankan, terwijl een oplossingen van goede kwaliteit wordt gegenereerd. Een aantal belangrijke beperkingen moeten in acht genomen worden. Ten eerste, kan onmogelijk grondig worden ingegaan op elk planningsdomein. Toch is het opportuun om een korte beschrijving van elk afzonderlijk planningsdomein te geven zodat een globaal beeld van de sector gevormd kan worden. Het planningsdomein waar wel grondig onderzoek op wordt verricht is de personeelsplanning. Helaas is ook dit domein te uitgebreid. In het bijzonder zal crew pairing als gegeven beschouwd worden en gebruikt worden als input voor het crew rostering probleem. De tweede beperking betreft dus de pairings die niet zelf worden gegenereerd. Een derde beperking betreft het crew rostering algoritme van Maenhout and Vanhoucke (2007). Hun algoritme genereert maandroosters aan de hand van wekelijkse inputdata in plaats van één maandelijkse inputfile omdat de combinatorische mogelijkheden te uitgebreid zijn en teveel computergeheugen vergen. Dit komt de oplossingskwaliteit niet ten goede. Evenwel moet opgemerkt worden dat het algoritme performante resultaten behaalt en dat een verdere verfijning van het algoritme zeker mogelijk is.

2



Alvorens de scriptie aan te vatten is een belangrijke opmerking aan de orde inzake het taalaspect. Omwille van het sterk internationaal karakter van deze sector en omdat het Engels de voertaal bij uitstek is in de luchtvaartsector, zijn bepaalde begrippen onmogelijk fatsoenlijk te vertalen naar het Nederlands. Deze begrippen zullen worden verduidelijkt en verder gebruikt in hun oorspronkelijke taal. In hoofdstuk 2, zal door middel van een horizontale benadering worden ingegaan op de belangrijkste planningsdomeinen in de luchtvaartsector. Het hoofdstuk heeft als doel een globaal beeld te schetsen van de verschillende aspecten die deel uitmaken van de complexe luchtvaartsector. In hoofdstuk 3, vatten we de verticale benadering aan. De volledige focus gaat naar het domein van de personeelsplanning die uitgebreid wordt geanalyseerd en beschreven. Hoofdstuk 4, vat de individuele domeinen kort samen en bestudeert het verschil

tussen

een

sequentiële

optimalisatiestrategie

en

een

geïntegreerde

optimalisatiestrategie aan de hand van een uitgewerkt voorbeeld. In hoofdstuk 5, wordt de verticale benadering terug hernomen met een gedetailleerd onderzoek van het airline crew rostering probleem. Alvorens de case SN Brussels Airlines aan te vatten wordt een meer technisch domein behandeld in hoofdstuk 6 dat ingaat op de meest gehanteerde optimalisatietechnieken voor het oplossen van het crew scheduling probleem. Tenslotte wordt in hoofdstuk 7 een volledige case gebaseerd op werkelijke gegevens van SN Brussels Airlines gepresenteerd.

3



2 Planning en optimalisatie in de luchtvaartsector De groei van het luchtverkeer, ruwweg verdubbeld sinds 1980, de sterke competitie tussen luchtvaartmaatschappijen en de vraag naar meer comfort vanwege de passagiers hebben de complexiteit en het belang van optimalisatie in alle planningsonderdelen sterk doen toenemen (Dorndorf et al, 2007). De graad van complexiteit ligt in de luchtvaartsector heel hoog doordat verschillende soorten middelen zoals vluchten, terminals, vliegtuigen, personeel en bagage moeten worden beschouwd. Daarenboven beïnvloeden beslissingen omtrent het gebruik van deze middelen elkaar. Luchtvaartmaatschappijen moeten hun optimalisatieprogramma’s continu verbeteren om te kunnen overleven in deze sterke competitieve sector en om eventueel een competitief voordeel te creëren. De voornaamste optimalisatietechnieken worden in hoofdstuk 6 besproken. In dit hoofdstuk worden de belangrijkste planningsdomeinen beschreven die geoptimaliseerd moeten worden. Personeelsplanning

is

slechts

één

van

de

vele

planningsdomeinen

die

luchtvaartmaatschappijen pogen te optimaliseren. In het bijzonder kan de planning in de luchtvaartsector opgesplitst worden in een aantal hoofddomeinen. Deze zijn de vluchtplanning, de vliegtuigplanning, de personeelsplanning, het herplannen van verstoringen, het plannen van de landingen, het toewijzen van de standplaatsen of gate’s en het bepalen van een adequate strategie met het oog op maximale ticketinkomsten. Daarnaast bestaan nog kleinere planningsdomeinen zoals het optimaliseren van de wachttijden, de bagageplanning, het laden van de cargo, het schoonmaken van de vliegtuigen,

enzovoort. De

belangrijkste

planningsdomeinen

dat

luchthavens en

luchtvaartmaatschappijen moeten optimaliseren worden in figuur 2.1 geïllustreerd. Ook bakent deze figuur het bereik van de scriptie af. De zwart omlijnde kaders zijn de zwaartepunten van de scriptie. Zoals hierboven vermeld, wordt in dit hoofdstuk een horizontale benadering gehanteerd om de verschillende planningsdomeinen, aangeduid met blauw, te definiëren. Voor de geïnteresseerde lezer worden relevante literatuurreferenties vermeld.

4



Figuur 2.1. Planningsdomeinen in de luchtvaartsector en afbakening scriptie

De opbouw van dit hoofdstuk is als volgt. In deel 2.1, wordt het plannen van de vluchten beschreven. In deel 2.2, wordt ingegaan op de vliegtuigplanning en wordt dit planningsdomein verder opgesplitst. De personeelsplanning wordt in een afzonderlijk hoofdstuk gepresenteerd. In deel 2.3, worden de implicaties van het herplannen van verstoringen aangehaald. In deel 2.4, wordt de planning van de landingen behandeld. Het betreft een planningsdomein die door de luchthavens moet worden geoptimaliseerd, maar die belangrijke gevolgen met zich meebrengen voor de luchtvaartmaatschappijen. De planning van de gate’s of standplaatsen vormt het onderwerp van deel 2.5. Luchtvaartmaatschappijen streven naar maximale winst, daarom worden de verschillende strategieën om maximale ticketinkomsten te genereren, behandeld in deel 2.6. Tenslotte volgt in deel 2.7 een korte bespreking van een aantal kleinere planningsdomeinen.

2.1 Vluchtplanning Het plannen van de vluchten kan gedefinieerd worden als het opstellen van een vluchtrooster of timetable aan de hand van de geraamde marktaandelen dat de meest optimale vluchten, inclusief vertrek- en aankomstuur, bevat met als doel zoveel mogelijk passagiers aan te trekken. De moeilijkheid voor de luchtvaartmaatschappijen zit hem in het inschatten van hun toekomstig marktaandeel. Het heeft namelijk geen zin drie vluchten per dag naar London te voorzien als die vluchten niet gevuld geraken. Modellen die het

5



toekomstig marktaandeel zo optimaal mogelijk kunnen inschatten vormen het studieobject van dit domein. In de literatuur worden meestal modellen op basis van vaste marktaandelen aangeboden. Yan et al., (2007) benadrukken de positieve impact van een goed vluchtrooster op het marktaandeel, maar wijzen ook op het feit dat marktaandelen in een competitieve omgeving variabel zijn. In hun werk beschrijven ze hun model op basis van variabele marktaandelen van toepassing op vier Taiwanese luchtvaartmaatschappijen. In het werk van Lee et al. (2007) wordt een model voorgesteld om een robuuster vluchtrooster te construeren en wordt een literatuuroverzicht gepresenteerd van werken waarin robuuste planningen centraal staan. In dat verband vormt het werk van Cao en Kanafani (2000) een significante meerwaarde. Zij ontwikkelden een model dat de robuustheid waardeert.

2.2 Vliegtuigplanning Vliegtuigplanning of aircraft scheduling kan gedefinieerd worden als de toewijzing van de vloot aan de individuele vluchten en het plannen van de onderhoudsbeurten die vliegtuigen moeten ondergaan. Dit planningsdomein kan opgesplitst worden in twee sub problemen. Fleet assignment vormt het eerste sub probleem en behandelt de toewijzing van de vloot aan de individuele vluchten met als doel maximale inkomsten en minimale operationele kosten, rekening houdend met het vluchtrooster en de vloot van de maatschappij in kwestie. Het selecteren van het vliegtuigtype wordt voornamelijk gedetermineerd door de benodigde capaciteit. Het toewijzen van een te klein vliegtuig leidt tot een opportuniteitskost door het verlies aan klanten. Een te groot vliegtuig toewijzen, leidt daarentegen tot hogere operationele kosten (Sherali et al., 2006).

6



Aircraft maintenance routing vormt het tweede sub probleem en behandelt de planning van het onderhoud van de vliegtuigen met als doel het verzekeren van voldoende onderhoudssessies zodat het vliegtuig conform de normen vliegveilig is (Sherali et al., 2006). Tal van werken beschrijven modellen om deze optimalisatieproblemen op te lossen. In Sherali et al. (2006) wordt een handleiding gepresenteerd van methoden voor het oplossen van het fleet assignment probleem. Ook Bélanger et al. (2006) en Grönkvist (2006) zijn relevante werken omtrent aircraft scheduling.

2.3 Herplanning van verstoringen Dit planningsdomein behandelt in feite het day of operations scheduling (DAYOPS) probleem, waarbij het herplannen van vliegtuigen of personeel omwille van verstoringen zoals ziekte, technische defecten, vertragingen en afgelaste vluchten centraal staat. Dit planningsdomein heft de verstoringen op met als doel de operationele kosten, het klantongemak en de afwijking tussen de nieuwe planning en de oorspronkelijke planning te minimaliseren (Stojkovic´ et al, 2002). Nauw verbonden met dit domein vormt de robuustheid van de planning. Hoe robuuster de planning, hoe beter deze is bestand tegen verstoringen en hoe minder planningswijzigingen nodig zullen zijn. In het werk van Stojkovic´ et al (2002) is men niet gierig met literatuurreferenties en wordt een model voorgesteld die een nieuwe vluchtplanning genereert met respect voor de personeelsplanning, de regels, de passagiersconnecties en het onderhoud van vliegtuigen.

2.4 Planning van de landingen Het plannen van de landingen moet worden geoptimaliseerd door een luchthaven en kan gedefinieerd worden als de beslissing wanneer een vliegtuig moet landen zodat deze landt tussen een bepaald tijdsinterval (of time window), met respect voor de scheidingstijd tussen de landing van twee vliegtuigen omwille van turbulenties. Het landingsprobleem begint wanneer een vliegtuig het radarbereik van een luchthaven binnenkomt, waarbij zijn

7



vluchtnummer, hoogte en snelheid wordt doorstuurt naar de controleur. Op dat moment moet de controleur het vliegtuig een landingstijd toewijzen en een landingsbaan als er meerdere zouden zijn. Op basis van de binnengekomen informatie gaan de controleurs instructies geven aan de vliegtuigen over de te gebruiken hoogte en snelheid, waardoor deze onrechtstreeks een landingstijd toegewezen krijgen. Tijdens piekmomenten moeten beslissingen snel en efficiënt worden genomen zodat een continue landingsstroom kan worden

gehandhaafd.

Om

de

controleurs

hierbij

te

helpen

worden

beslissingsondersteunende programma’s ter beschikking gesteld. Een zo kleine mogelijke afwijking tussen toegewezen landingstijd en doeltijd, gedetermineerd door de meest economische snelheid of de cruise snelheid van een vliegtuig,

vormt

het

optimalisatieprobleem

vanuit

het

standpunt

van

de

luchtvaartmaatschappijen. Hoe groter die afwijking, hoe groter de extra operationele kosten voortvloeiend uit extra brandstofverbruik. De toegewezen landingstijd heeft een minimum en een maximum. De vroegste landingstijd wordt bekomen door te vliegen aan maximale snelheid. De laatste landingstijd wordt bekomen wanneer een vliegtuig aan cruise snelheid vliegt, terwijl deze blijft cirkelen totdat de brandstof is opgebruikt. Het interval waarbinnen de toegewezen landingstijd valt wordt de time window genoemd. Figuur 2.2 illustreert de variatie in de extra operationele kosten (Beasley et al, 2000).

Figuur 2.2. Variatie in kosten binnen de time window

Het optimalisatieprobleem vanuit het standpunt van de luchtvaartoperatoren is verschillend. Zij pogen de landingen optimaal te plannen met als doel een zo optimaal

8



mogelijke benutting van de luchthavencapaciteit te bekomen met respect voor de geografische en door de politiek opgelegde beperkingen en de minimale scheidingstijd tussen twee landingen (Beasley et al, 2000; Pinol and Beasley, 2006).

2.5 Het plannen van de gate’s Flight gate scheduling of het plannen van de standplaatsen is een van de belangrijkste en meest complexe taken die het luchthavenmanagement moet vervullen. De objectieven die dit domein voor ogen heeft zijn het minimaliseren van de totale wandelafstand van passagiers, het maximaliseren van de preferenties van luchtvaartmaatschappijen, het minimaliseren van het aantal ongebruikte standplaatsen, het minimaliseren van de afstand die de bagage moet afleggen en het minimaliseren van de afwijking tussen de referentieplanning

en

de

uiteindelijke

planning

zodoende

passagierscomfort

en

planningsaantrekkelijkheid te behouden. Deze doelstellingen moeten geoptimaliseerd worden onder bepaalde beperkingen. Zo kan slecht één vliegtuig op een standplaats staan en zijn bepaalde standplaatsen beperkt in materiaal en afmetingen. Ook moet een minimale grondtijd en een minimaal tijdsinterval tussen twee opeenvolgende vliegtuigen worden gewaarborgd. De talrijke objectieven en beperkingen maken het probleem heel complex waardoor een compromis zal moeten worden gesloten. In de meeste gevallen leidt een compromis tot het opstellen van prioriteiten, waarbij het minimaliseren van de wandelafstand van passagiers de voorkeur geniet (Dorndorf et al, 2007; Lim et al, 2005). Voor de geïnteresseerde lezer raad ik het werk van Dorndorf et al (2007) aan. Het werk vormt een ideaal startpunt, bevat uitgebreide literatuurreferenties en bespreekt een grote variëteit aan mathematische modellen en up-to-date oplossingstechnieken ontwikkeld voor het oplossen van het flight gate scheduling probleem. Het werk van Lim et al (2005) gaat een stap verder. Deze auteurs beschouwen de meer realistische situatie waarbij aankomst- en vertrekuren kunnen wijzigen binnen een bepaald tijdsinterval. Hierdoor wordt rekening gehouden met het dynamische karakter van het probleem.

9



2.6 Strategie voor maximale ticketinkomsten Ticketinkomsten nemen bijna de gehele inkomstenzijde van een luchtvaartmaatschappij voor hun rekening en vormen dan ook een prioritaire taak voor het management. Het doel is een adequate strategie op te stellen met het oog op het behalen van maximale inkomsten uit de ticketverkoop. Sinds de deregulering van 1979 heeft het inkomstenmanagement nog aan belang gewonnen, omdat luchtvaartmaatschappijen begonnen zijn met het aanbieden van variabele prijzen voor hetzelfde product. De klanten kunnen worden gesegmenteerd in twee groepen. De business reizigers vragen flexibiliteit en annuleringsopties, boeken laattijdig en zijn dan ook bereid meer te betalen voor hun ticket. De vrije tijd reizigers verkiezen goedkope tickets, boeken vroegtijdig en hechten minder belang aan annuleringsvoorwaarden. Figuur 2.5 illustreert beide segmenten.

Figuur 2.3. Segmentering van de reizigers

Luchtvaartmaatschappijen moeten dan ook keuzes maken. Ofwel focussen ze zich op één doelgroep en positioneren ze zich volledig naar deze doelgroep. Ofwel wordt gekozen voor een combinatiestrategie, waarbij prijsdifferentiatie centraal staat. Hoe dan ook staan de drie strategieën voor hetzelfde probleem. Hoeveel procent van de zitjes heel vroeg verkopen aan een lagere prijs, wetend dat een aantal reizigers laattijdig zullen boeken aan

10



een hogere prijs. De prijszetting vormt dus een cruciaal aspect en daarom is het interessant om te weten dat de prijs functie is van het aantal dagen voor vertrek, het huidige boekingspercentage, de voorspelling van de totale vraag, de dag van de week en het uur van de dag (Gosavi et al., 2007). Een volledig overzicht van de literatuur wordt gegeven door McGill and van Ryzin (1999). Een overzicht over de geschiedenis van inkomstenmanagement wordt in Boyd and Bilegan (2003) gepresenteerd. Andere relevante papers over dit domein zijn te vinden in (Bertsimas and de Boer, 2005; Chen et al., 2003; Karaesmen and van Ryzin, 2004; van Ryzin and McGill, 2000).

2.7 Kleinere planningsdomeinen Naast de hierboven beschreven planningsdomeinen zijn er nog tal van kleinere planningsdomeinen die moeten worden geoptimaliseerd. Eén van die domeinen is de optimalisatie van de wachttijden. In de ruimste zin verstaan we hieronder de minimalisatie van alle wachttijden die passagiers ondergaan vanaf het moment dat ze de woonst verlaten totdat ze in het vliegtuigen zitten. Op het eerste zicht lijkt dit een luchthavengebonden probleem. Dit is ook zo, maar luchtvaartmaatschappijen beslissen zelf op welke luchthavens ze opereren. Elke luchtvaartmaatschappij poogt de wachttijden te minimaliseren om in de gunst

van

de

passagiers

te

staan.

Een

niet

onbelangrijk

aspect

omdat

luchtvaartmaatschappijen veel klanten zien switchen naar concurrenten als ze niet tevreden zijn. Air Canada bijvoorbeeld hecht veel belang aan dit domein. Zo hebben ze IBM ingehuurd om het ganse proces te simuleren met als doel de wachttijd te verkleinen en simultaan grotere economische efficiëntie te behalen met nieuwe technologieën zoals selfservice kiosken en elektronische tickettering (IBM, Deep Computing Institute, 2007). De bagageplanning wordt meestal door de luchtvaartmaatschappijen uitbesteed. Het doel van dit domein is er voor zorgen dat de bagage op tijd en onbeschadigd toekomt. Als dat

mislukt

zal

dat

een

negatieve

impact

hebben

op

het

imago

van

de

luchtvaartmaatschappij. Verder moeten ook het in- en uitladen van de cargo en het

11



schoonmaken van de vliegtuigen gepland worden. Anno 2007 zijn strakke planningen kenmerkend voor deze domeinen, omdat de vliegtuigen minder lang aan de grond blijven. De beschrijving van de voornaamste domeinen die moeten worden gepland en geoptimaliseerd had tot doel de lezer een eerste kennismaking en een globaal beeld van de luchtvaartsector te verschaffen. In het volgende hoofdstuk wordt de kern van de scriptie aangevat. De planning van het personeel1 zal uitvoerig beschreven worden.

1

Met personeel wordt vanaf hier bedoeld de crew of de personeelsleden die werken in het vliegtuig.

12



3 Personeelsplanning in de luchtvaartsector: het “Airline Crew Scheduling Problem” Personeelsplanning in de luchtvaartsector wordt door operationele onderzoekers het “Airline Crew Scheduling Problem (ACSP)” genoemd en vormt de kern van de scriptie. Vanaf nu gaat de volledige focus naar dit domein. In deel 3.1, wordt dit domein gedefinieerd en gesitueerd binnen de complexe planningsvelden van de luchtvaartsector. In deel 3.2, wordt het belang van personeelsplanning aangekaart. In deel 3.3, wordt de specifieke luchtvaartterminologie zowel theoretisch als met voorbeelden verduidelijkt. Deel 3.4, bespreekt uitvoerig de componenten en de objectieven van het crew scheduling proces. Tenslotte wordt de relevante literatuur specifiek voor crew scheduling samengevat in deel 3.5.

3.1 Definiëring en situering De situering van de personeelsplanning binnen het complexe domein van de planning en optimalisatie in de luchtvaartsector kan het best worden weergegeven in figuur 3.1. De figuur moet van boven naar onder worden geïnterpreteerd. Zoals hierboven vermeld illustreren de zwarte kaders in de figuur het pad dat de scriptie bewandelt. In dit hoofdstuk wordt de personeelsplanning beschreven.

Figuur 3.1. Situering personeelsplanning

13



Zoals hierboven uitvoerig besproken bestaat planning en optimalisatie in de luchtvaartsector

uit

een

aantal

planningsdomeinen

die

in

de

meeste

luchtvaartmaatschappijen sequentieel worden opgelost. Alvorens men echter start met een sequentiële oplossingmethodiek moet men eerst kennis hebben van de individuele planningsdomeinen. Een van de meest interessante en belangrijkste planningsdomeinen is de personeelsplanning die kan worden gedefinieerd als volgt. Personeelsplanning of crew scheduling is, gegeven de vluchtplanning en de vliegtuigplanning, het proces waarbij anonieme vluchtsequenties of pairings worden gegenereerd. Daarenboven worden alle individuele personeelsleden toegewezen aan de gegenereerde pairings en aan andere activiteiten op een zodanige manier dat alle beperkingen opgelegd door overheidsregels, collectieve arbeidsovereenkomsten en bedrijfspecifieke regels worden gerespecteerd, dat alle individuele vluchten adequaat bestaft zijn door personeel en waarbij individuele werkroosters worden opgesteld voor alle personeelsleden met als tweeledig doel het minimaliseren van de kosten en het maximaliseren van de levenskwaliteit van het personeel, eventueel rekening houdend met andere aspecten zoals flexibiliteit en robuustheid. Zoals uit de definitie af te leiden en in bovenstaande figuur 3.1 te zien valt personeelsplanning uiteen in twee subdomeinen. Gegeven de individuele vluchten of flight legs worden eerst bepaalde pairings gegenereerd in het crew pairing probleem. Daarna worden individuele werkroosters voor de personeelsleden opgesteld in het crew rostering probleem. Beide subdomeinen worden toegelicht, maar in het kader van de case SN Brussels Airlines in hoofdstuk 7 zal de nadruk liggen op het crew rostering probleem.

3.2 Het Belang van personeelsplanning Het airline crew scheduling probleem is uitgebreid onderzocht in de literatuur. Ook zijn onderzoekers al in een vroeg stadium operationele onderzoekstechnieken gaan toepassen. De hoofdreden ligt in de belangrijke impact die een efficiënte personeelsplanning heeft op de kostenzijde en bijgevolg op de winst van een luchtvaartmaatschappij. Net zoals de

14



meeste bedrijven streeft een luchtvaartmaatschappij winstmaximalisatie na. Winst is gelijk aan de opbrengsten minus de kosten. De opbrengsten worden bijna uitsluitend gegenereerd uit de verkoop van tickets. In het bijzonder is deze opbrengst gelijk aan de gemiddelde prijs per ticket vermenigvuldigd met het aantal verkochte tickets. De kostenzijde wordt gedetermineerd door de aankoop van brandstof, personeelskosten, vliegtuigkosten, luchthavenkosten

en

andere

kosten

zoals

kantoorkosten,

distributiekosten,

IT–

ondersteuningsdiensten, catering, schoonmaak, bagage, training, etc. Op dezelfde manier als bij de berekening van de ticketinkomsten kan de aankoop van brandstof ontbonden worden in de gemiddelde aankoopprijs per liter vermenigvuldigd met het aantal gekochte liters. De personeelskosten betreft hoofdzakelijk de uitbetaling van de lonen en bepaalde operationele kosten zoals hotelovernachtingen en de huur van simulatorsessies. De vliegtuigkosten worden typisch ingedeeld in aankoop, onderhoud en verzekering. De luchthavenkosten tenslotte bestaan uit landingstaxen en het betalen voor een standplaats. Figuur 3.2 schematiseert de componenten die bijdragen tot het bepalen van de winst.

Figuur 3.2. Componenten ter bepaling van de winst van een luchtvaartmaatschappij

15



Zoals te zien in bovenstaand schema zijn de personeelskosten, na de aankoop van brandstof, de tweede grootste kost met een aandeel van typisch 15 a 20 % van de totale operationele kosten van een luchtvaartmaatschappij (El Moudani et al., 2001; Maenhout and Vanhoucke, 2007). Omwille van hun relatief groot belang hebben de personeelskosten een belangrijke invloed op de winst van een luchtvaartmaatschappij. Daarom is een optimale toewijzing van het personeel en in het bijzonder een efficiënte personeelsplanning van cruciaal belang om te overleven in deze sterk competitieve sector. Het voornaamste streefdoel van crew scheduling is dan ook het personeel te gebruiken op een zodanige manier dat hun kost geminimaliseerd wordt, terwijl de implementatie van het gegeven vluchtrooster wordt verzekerd (Thiel, 2004). Voor grote luchtvaartmaatschappijen kan een kostenreductie van enkele procenten leiden tot jaarlijkse besparingen van tientallen miljoenen dollars (Jarrah and Diamond, 1997; Kohl and Karisch, 2004). Het belang van een efficiënte personeelsplanning ligt dus zoals gezegd in zijn grote impact op de winstgevendheid van een luchtvaartmaatschappij. Bij American Airlines (AA) bijvoorbeeld wordt een stijging van het gebruikte personeel met 1 % vertaald in 13 miljoen dollar besparingen op jaarbasis (Anbil et al., 1991).

3.3 Terminologie Alvorens het domein van de personeelsplanning meer in detail te bekijken is het opportuun om alle begrippen theoretisch en waar mogelijk aan de hand van een voorbeeld te verduidelijken. Enkele begrippen zijn al kort verduidelijkt geweest in de hierboven besproken onderdelen. In dit deel worden deze begrippen en de nieuwe begrippen uitvoerig verduidelijkt omdat een goede kennis van de begrippen onontbeerlijk is voor het vervolg van de scriptie. Het airline crew scheduling probleem is een complex gebeuren en wordt zoals eerder aangehaald typisch opgesplitst in enerzijds het crew pairing probleem en anderzijds het crew rostering probleem. Deze twee hoofdproblemen worden sequentieel opgelost, te beginnen met crew pairing. Crew pairing betreft het genereren van pairings uit flight legs. Flight legs

16



zijn, zoals hierboven vermeld, individuele vluchten van plaats A naar plaats B zonder tussenstop, zoals bijvoorbeeld een rechtstreekse vlucht van Brussel naar London. De terugvlucht van London naar Brussel wordt dus gezien als een nieuwe flight leg. Alle flight legs staan in de flight timetable of het vluchtrooster. Gegeven deze flight legs worden sequenties van flight legs samen gebundeld tot zogenaamde pairings. Pairings zijn dus sequenties van flight legs die daarenboven starten en eindigen op dezelfde luchthaven. Bij

leg 1 0

leg 9

wijze van voorbeeld beschouw onderstaande beginsituatie geïllustreerd in figuur 3.3.

g le 8 g le 5 le g

le g

6

7

Figuur 3.3. Voorbeeld: beginsituatie

Het betreft een gedeelde van de flight legs die een luchtvaartmaatschappij aan potentiële passagiers aanbiedt. Zoals te zien in de figuur zijn er 10 flight legs. De aankomsturen staan aan de uiteinden van de pijlen, de vertrekuren aan het begin van de pijlen. Flight leg 9 bijvoorbeeld landt in Helsinki om 18 uur. De terugvlucht naar Brussel vertrekt de volgende morgen om kwart over zeven. Bijgevolg moet de crew in Helsinki overnachten. Dit wordt een nightstop genoemd. De 10 individuele flight legs moeten

17



sequentieel samengebundeld worden tot pairings. Een van de mogelijkheden wordt in figuur 3.4 weergegeven. Pairing 1 bestaat uit 6 individuele flight legs. Eerst de heen– en terugvlucht naar München, dan de heen– en terugvlucht naar Helsinki met overnachting in Helsinki. Tenslotte moet dezelfde crew nog een heen– en terugvlucht naar Straatsburg doen. Pairing 2 wordt op dezelfde manier geïnterpreteerd. Pairing 1 Helsinki 18:00

07:15

Pairing 2 London 08:00

08:30 14:00

g le

Munchen

8

16:15

le

1 leg

09:00

g 7 09:15

14:30

leg

12:45

2

07:15 15:45

Brussel

9:30

13:15

6

09:45

11:30

leg

g

3

4

10:15

le

g

5

le

leg

10:45 11:45

Straatsburg

11:15

Toulouse

Figuur 3.4. Mogelijke pairing samenstelling

Toegepast op dit voorbeeld zou ik de aandacht willen vestigen op het begrip rotatietijd in de luchtvaartsector. De rotatietijd is namelijk de tijd dat een vliegtuig aan de grond blijft tussen 2 flight legs. Door de hevige concurrentiestrijd is het noodzakelijk deze tijd te minimaliseren. Hierdoor kan een vliegtuig meer vluchten per dag verrichten. Vooral bij lagekosten maatschappijen is dit heel belangrijk omdat hun marges heel klein zijn. Vergelijk het met een fastfoodketen. Ook zij hanteren een strategie van kleine marges, maar veel rotatie. Dit in tegenstelling tot sterrenrestaurants waar een tafel bezet blijft voor de

18



volledige avond, maar waar de marges veel hoger liggen. Anno 2007 bedraagt de rotatietijd typisch 30 minuten in grote luchthavens voor continentale vluchten. Na het genereren van de pairings worden de crewmembers toegewezen aan deze pairings. Onder crewmembers verstaat men het personeel dat deel uitmaakt van de crew en de crew is in feite het personeel dat in het vliegtuig werkt. Zoals te zien in figuur 3.5 wordt dit type personeel verder opgesplitst in cockpit crew of flight crewmembers (FCM) en in cabin crew of cabin crewmembers (CCM). De Captains (CPT), de copiloten of de First officers (F/O) en de instructeurs of Type rating instructors (TRI) behoren tot het cockpit personeel en worden voor het vervolg piloten genoemd. De stewardessen en de stewards behoren tot het cabine personeel en worden voor het vervolg cabine personeelsleden genoemd. Daartegenover staat een ander type personeel, namelijk het grondpersoneel. Deze groep bestaat uit alle personeelsleden die niet in het vliegtuig werken en worden dus niet aan pairings toegewezen. De groep bestaat onder andere uit managers, administratief personeel, planners, verkopers, informatici en technisch geschoolde werknemers. De verhouding grondpersoneel versus crew is typisch 60/40. Personeelsbestand van een luchtvaartmaatschappij

Grondpersoneel

Crew

- managers - administratief personeel - planners - verkopers - informatici - technisch personeel - ...

Cockpit crew - captains - copiloten - instructeurs

Piloten

Cabin crew - stewardessen - stewards

Cabine personeelsleden

Figuur 3.5. Personeelsbestand van een luchtvaartmaatschappij

19



In deze scriptie wordt het grondpersoneel buiten beschouwing gelaten. De volledige focus gaat dus naar de crew en in het bijzonder naar het cockpit personeel zoals in het blauw in figuur 3.5 aangeduid. Voor het vervolg van de scriptie wordt de Engelse term crewmember zoveel mogelijk vermeden en vervangen door personeelslid met de achterliggende gedachte dat een personeelslid, zoals in voetnoot vermeld, ofwel een piloot is ofwel een cabine personeelslid. In tegenstelling tot het grondpersoneel worden de crewmembers wel toegewezen aan de pairings. Elke pairing wordt dus bestaft door een aantal crewmembers met bepaalde functies of posities. Deze crewsamenstelling is eigen aan de pairing en wordt het crew complement genoemd. Pairing 2 uit het voorbeeld in figuur 3.4 zal bijvoorbeeld een crew complement vereisen van één captain, één copiloot en drie cabine personeelsleden. In dat verband kan ook de term crew worden gebruikt. De zojuist beschreven toewijzingsprocedure, samen met het opstellen van de individuele werkroosters voor elke personeelslid wordt het crew rostering probleem of het crew assignment probleem genoemd. De individuele werkroosters worden typisch opgesteld voor één maand en dit twee à zes weken op voorhand. De werkroosters bevatten naast pairings ook reserve duties, pre-assigned activities en off-duty blocks. Een reserve duty of gewoonweg een reserve is eigenlijk niets anders dan een piloot die van wacht is. Afhankelijk van het soort reserve moet de piloot zich dan in een bepaald aantal minuten kunnen melden om een collega te vervangen die werkonbekwaam is. Bij SN Brussels Airlines bijvoorbeeld wordt voor de piloten een onderscheid gemaakt tussen drie types reserves. Ofwel moet de piloot in 120 minuten aanwezig kunnen zijn, ofwel in 50 minuten, ofwel in 5 minuten. Voor het laatste type zal de piloot verplicht op de luchthaven moeten wachten, daarom wordt deze enkel geprogrammeerd nadat de piloot terugkomt van een vlucht. Met pre-assigned activities bedoeld men alle activiteiten die op voorhand toegewezen zijn. Voor het vervolg wordt dan ook de Nederlandse benaming vooraf toegewezen activiteiten

gebruikt.

Het

betreft

jaarlijkse

20

verloven,

zwangerschapsverloven

en


ouderschapsverloven,

loopbaanverminderingen


en

loopbaanonderbrekingen,

simulatorsessies en andere trainingen, en allerhande grondactiviteiten zoals kantoorwerk, vergaderingen en medische controle. Tenslotte bestaan de werkroosters ook uit off-duty blocks. Dit zijn volledige rustdagen. Voor veiligheidsredenen wordt de samenstelling van de werkroosters sterk gereglementeerd door overheidsregels, vakbondsregels en bedrijfspecifieke regels, waarover meer in volgend hoofdstuk. Figuur 3.6 vat de mogelijke inhoudscomponenten van een werkrooster samen.

Figuur 3.6. Mogelijke inhoudscomponenten van een werkrooster

De theoretische verklaringen van deze gespecialiseerde luchtvaartterminologie zijn gebaseerd op het werk van El moudani et al. (2001), Gamache et al. (1999), Hoffman and Padberg (1993), Kohl and Karisch (2004), Maenhout and Vanhoucke (2007), Medard and Sawhney (2004), Thiel (2004) en Vance et al. (1997). Een fictief voorbeeld van een werkrooster wordt in onderstaande figuur 3.7 gegeven. Het betreft een weekrooster voor een piloot. De positie of rang van de piloot is captain. De piloot zal op maandag en dinsdag pairing 1 moeten doen. De pairing wordt bestaft door een crew complement van één captain, één copiloot en vier cabine personeelsleden. De inhoud van een pairing bestaat uit een flight leg naar Nice, waar de volledige crew overnacht. Op dinsdagmorgen doet de crew de ochtendvlucht terug naar Brussel, waarna ze onmiddellijk

21



nog een heen- en terugvlucht naar London moeten vervullen. Na deze pairing krijgen de crew verplichte rust. Woensdag staat voor de piloot een fire drill geprogrammeerd. Dit is een tweejaarlijkse training die een brandsituatie simuleert. De fire drill stond al enkele maanden vooraf geprogrammeerd. Het betreft hier dus een vooraf toegewezen activiteit. Donderdag staat een nieuwe pairing voor de boeg met een nieuwe crew. Het crew complement voor deze pairing bestaat uit één captain, één copiloot en drie cabine personeelsleden. Eerst staat een heen- en terugvlucht naar Manchester geprogrammeerd en vervolgens een heen- en terugvlucht naar Toulouse. Vrijdag staat voor de piloot een reserve geprogrammeerd van het type 50 minuten. In het weekend tenslotte geniet de piloot van een tweedaagse off-duty block. Nogmaals dit is een fictief voorbeeld daar in werkelijkheid een werkrooster gegeneerd wordt voor een typische periode van 1 maand.

Figuur 3.7. Voorbeeld van een werkrooster

3.4 Componenten en objectieven van het crew scheduling proces Het crew scheduling probleem is heel moeilijk op te lossen omwille van de grote combinatorische complexiteit en in mindere mate door de tegenstrijdige objectieven. Daarom wordt het opgesplitst in enkele sub problemen en substappen. Eerst wordt het cockpit personeel en het cabine personeel gesplitst, in de meeste gevallen zelfs tot hun

22



functie. Bijgevolg ontstaat er, voor het cockpit personeel, één toegewijd crew scheduling probleem voor de captains en één voor de copiloten (instructeurs worden namelijk beschouwd als captains). Vervolgens worden deze sub problemen nog verder gesplitst per vliegtuigtype. Elke sub crew scheduling probleem wordt dan verdeeld in het crew pairing probleem en het crew rostering of crew assignment probleem (Thiel, 2004). Zoals gezegd worden deze twee substappen sequentieel opgelost. Onderstaande figuur 3.9 illustreert de componenten en de objectieven van het crew scheduling probleem. In het crew pairing probleem streeft men alleen minimale kosten na. Uiteraard moeten ook alle vluchten gedekt worden en alle beperkingen gerespecteerd worden. De reden voor het nastreven van één enkel doel ligt aan de aard van het probleem. Ten eerste worden pairings anoniem gegenereerd, waardoor er onmogelijk rekening kan worden gehouden met persoonlijke preferenties, i.e., voorkeuren, die bijdragen tot de levenskwaliteit. Ten tweede kan een groter kostenvoordeel bereikt worden via productieve pairings die kosten minimaliseren (Kohl and Karisch, 2004; Maenhout and Vanhoucke, 2007). Omwille van dit feit hebben de meeste gepubliceerde werken betrekking op het crew pairing probleem. In tegenstelling tot het crew pairing probleem, wordt het crew rostering probleem wel opgelost voor de individuele personeelsleden. Hierdoor is het wel mogelijk om rekening te houden met hun individuele behoeftes en preferenties. Normaliter streven de luchtvaartmaatschappijen dan ook beide, weliswaar tegenstrijdige, doelstellingen na in het crew rostering probleem. Enerzijds kosten minimalisatie voor de maatschappij en anderzijds maximalisatie van de levenskwaliteit voor de crew. De implementatie van de levenskwaliteitcriteria kunnen verschillen naargelang luchtvaartmaatschappij. In het bijzonder zijn er 3 concepten om levenskwaliteit-criteria zoals individuele behoeftes, preferenties en bepaalde aanvragen te incorporeren in de werkroosters. Het eerste concept, the bidlines approach, wordt voornamelijk toegepast door Amerikaanse luchtvaartmaatschappijen. Eerst worden anonieme werkroosters, zogenaamde bidlines, gegenereerd. Daarna kunnen de personeelsleden bieden op deze anonieme werkroosters. Het bieden gebeurd op basis van strikte anciënniteit. Sequentieel kiest eerst de meest oudgediende en als laatste de laatst in dienst genomen personeelslid. De

23



personeelsleden kunnen dus enkel een globale preferentie uiten, maar hebben wel het voordeel dat ze exact weten wat ze zullen krijgen als hun bod aanvaard wordt. Dit concept heeft echter ook nadelen. Ten eerst worden de jongere personeelsleden sterk benadeeld omwille

van

het

anciënniteitprincipe.

Ten

tweede

bezorgd

dit

concept

de

luchtvaartmaatschappij hogere kosten omdat sommige anonieme werkroosters conflicteren met vooraf toegewezen activiteiten, vakantie dagen en met het werkrooster van de maand voordien. Bijgevolg is het mogelijk dat bepaalde pairings niet kunnen worden uitgevoerd door het personeelslid in kwestie. Sommige anonieme werkroosters kunnen dus niet volledig worden toegewezen aan één personeelslid en dit impliceert hogere kosten. Bovendien vergoeden de luchtvaartmaatschappijen op basis van de origineel geplande werkroosters waardoor de personeelsleden extra worden gestimuleerd om te bieden op conflicterende werkroosters. Bijvoorbeeld kan een piloot die weet dat hij op 31 januari landt om 23 uur bieden op een werkrooster voor de maand februari die start op 1 februari met een pairing die begint om 5 uur in de ochtend. De rustperiode van 6 uur is niet reglementair waardoor de werkroosters conflicteren. De piloot zal de eerste pairing van de maand niet moeten uitvoeren, maar er toch voor worden betaald. In de praktijk poogt men deze conflicterende situaties te vermijden door meerdere stappen in het planningproces in te bouwen. Hiermee worden conflicterende situaties (gedeeltelijk) verholpen, maar de kosten zullen evenwel stijgen door de implementatie van de vele stappen in het proces. Europese

luchtvaartmaatschappijen

gebruiken

voornamelijk

het

concept

van

personalized rostering. Dit concept is gebaseerd op het fair-and-equal share principe. De luchtvaartmaatschappijen streven een gelijkmatige verdeling van de werkdruk tussen de personeelsleden na. Het anciënniteitprincipe wordt dus zoveel mogelijk vervangen door het fair-and-equal share principe. In de praktijk wordt het concept geïmplementeerd als volgt. De personeelsleden drukken hun persoonlijke behoeftes, preferenties en aanvragen uit. Deze levenskwaliteit-criteria worden dan geaccepteerd of verworpen. De output zijn zo optimaal mogelijke persoonlijke werkroosters die in de mate van het mogelijke rekening houden met de uitgedrukte behoeftes, preferenties en aanvragen. Het voordeel van een dergelijk concept is dat de personeelsleden hun preferenties kunnen uitdrukken en dat de

24



jongere personeelsleden niet worden benadeeld. Maar, in tegenstelling tot het bidlines concept, kennen ze hun exact werkrooster niet a priori. Gedurende het laatste decennium wordt een derde concept, preferential bidding genaamd, populairder omdat het de nadelen van de twee vorige concepten (gedeeltelijk) wegwerkt. Het betreft dus een soort hybride tussen het bidline concept en personalized rostering. De techniek houdt rekening met crew preferenties tot een zekere graad zoals bijvoorbeeld regelmatig vooraf geplande vrije weekends of werken met bepaalde collega’s. Echter, in het geval van conflicten tussen de personeelsleden geldt het anciënniteitprincipe, waardoor jongere personeelsleden terug worden benadeeld (Jarrah and Diamond, 1997; Kohl and Karisch, 2004; Maenhout and Vanhoucke, 2007; Medard and Sawhney, 2004; Thiel, 2004). De objectieven van het crew scheduling probleem zijn dus ten eerste het minimaliseren van kosten en ten tweede het maximaliseren van de levenskwaliteit van de crew. De eerste stap van crew scheduling, crew pairing, heeft enkel tot doel het minimaliseren van de kosten. Crew rostering streeft beide objectieven na. Laten we nu de objectieven van naderbij bekijken te beginnen met het minimaliseren van de kosten. De kosten worden gedetermineerd door enerzijds de loonmassa en anderzijds de specifieke operationele kosten. In de meeste Europese luchtvaartmaatschappijen worden de lonen behandeld als een stapsgewijze lineaire functie en worden ze maandelijks uitbetaald. De piloten genieten van een vaste loon tot een bepaald aantal vlieguren of blok uren. Het gearceerde deel in figuur 3.8 illustreert de vaste loon. Overschrijden ze dit aantal (B1) dan worden ze per uur dat ze extra gevlogen hebben extra vergoed. Het betreft overuren dus die extra vergoeding zal per uur hoger liggen. De uurvergoeding springt dus naar een hoger niveau (L2) en blijft dan weer constant tot er eventueel weer een grens (B2) wordt overschreden met een nieuwe sprong van de uurvergoeding (L3) tot gevolg. Verder moeten ook de operationele kosten worden geminimaliseerd, zoals hotelkosten bij nightstops en deadhead kosten om een piloot naar een andere locatie te verplaatsen of te laten terugkeren zonder dat deze zelf vliegt.

25



Figuur 3.8. Vergoeding op basis van een stapsgewijze lineaire functie

Het tweede objectief, namelijk het maximaliseren van de levenskwaliteit vloeit voort uit de positieve correlatie met de werknemerstevredenheid of crew satisfactie die op zijn beurt tot twee belangrijke implicaties leidt. Enerzijds leidt een hoge crew satisfactie tot een hogere graad van aanwezigheid en die heeft op zijn beurt een positieve invloed op de graad van robuustheid omdat er minder crew moet worden vervangen. Anderzijds leidt een hogere crew satisfactie tot een hogere servicekwaliteit. Personeelsleden die tevreden zijn zullen dit met grote waarschijnlijkheid ook weerspiegelen in hun werk. Maximalisatie van levenskwaliteit mag dus niet onderschat worden door luchtvaartmaatschappijen omdat het sterk gecorreleerd is met crew satisfactie (Thiel, 2004). Het werk van Thiel (2004) focust op crew satisfactie. Crew satisfactie is een levenskwaliteit-criterium en is sterk afhankelijk van de collega’s met wie men samenwerkt. In zijn team–oriented rostering probleem poogt hij frequente teamwijzigingen te minimaliseren omdat deze een negatieve impact hebben op de crew satisfactie. Teamoriented rostering moet gezien worden als een verbetering van het personalized rostering concept doordat er rekening wordt gehouden met aspecten van personeelsbeleid of human ressource management. Luchtvaartmaatschappijen kunnen dus best meer doen dan alleen rekening houden met de individuele behoeftes, preferenties en aanvragen. Ook moeten ze zelf proactief de graad van crew satisfactie zo hoog mogelijk proberen te houden door bijvoorbeeld het team-oriented rostering concept te incorporeren in hun crew scheduling proces. Uiteraard impliceert deze extra vereiste een verhoging van de kosten. Er zal een trade-off tussen minimalisatie van de operationele kosten en minimalisatie van team

26



wijzigingen plaatsvinden. Met andere woorden de twee hoofdobjectieven, minimale kosten en maximale levenskwaliteit zijn tegenstrijdig. Luchtvaartmaatschappijen moeten streven naar een evenwicht die uiteindelijk moet leiden tot winstmaximalisatie. Figuur 3.9 illustreert de componenten en objectieven van het crew scheduling proces.

Figuur 3.9. Componenten en objectieven van het crew scheduling proces

Vanaf het moment dat het crew scheduling proces is afgerond met als resultaat de werkroosters kunnen wijzigingen optreden. Deze wijzigingen die onder andere voortvloeien uit ziekte, technische defecten, vertragingen en afgelaste vluchten moeten worden opgevangen. De manier waarop deze wijzigingen worden opgevangen beïnvloeden zowel het economisch resultaat van de luchtvaartmaatschappij als de crew satisfactie. Toch worden in de meeste luchtvaartmaatschappijen deze wijzigingen manueel opgevangen. In het pionierswerk van Stojkovic et al. (1998) rijst de vraag naar de kwaliteit van de manueel aangebrachte roosterwijziging. Rekening houdend met de combinatorische aard van het probleem ontwikkelden ze een optimalisatiemodel die in staat was om alle wijzigingen in zo kort mogelijke tijd op te vangen. Het proces die de wijzigingen opvangt wordt het operationeel airline crew scheduling probleem genoemd. Het doel van dit probleem is, waar nodig, het wijzigen van de maandelijkse werkroosters gedurende de dag tot dag operaties.

27



Het operationeel airline crew scheduling probleem moet er dus voor zorgen dat alle vluchten terug gedekt zijn aan minimale kosten en met minimale wijzigingen in de werkroosters. In tegenstelling tot het (gewoon) crew scheduling proces die geen rekening houdt met verstoringen, worden in het operationeel crew scheduling proces pairings gegenereerd specifiek voor de personeelsleden omdat onmiddellijke productie van pairings voor specifieke personeelsleden vereist zijn. Dit komt doordat de set van oude pairings die niet meer uitvoerbaar zijn omwille van verstoringen moeten worden vervangen door een set nieuwe pairings en deze moeten worden geïncorporeerd in de al bestaande maandelijkse werkroosters. Hierdoor ontstaan personalized pairings die aan de beperkingen van crew pairing, personalized crew rostering en additionele specifieke operationele beperkingen moeten voldoen (Stojkovic et al., 1998). Het operationeel crew scheduling proces herplant dus alle verstoringen die betrekking hebben op de personeelsleden en behoort dus tot het domein van het herplannen van verstoringen zoals te zien in figuur 2.1 en uiteengezet in deel 2.4.

3.5 Relevante literatuur De literatuur over het crew scheduling probleem is erg volumineus. Vooral het werk van El moudani et al. (2001), Gamache et al. (1999), Hoffman and Padberg (1993), Kohl and Karisch (2004), Maenhout and Vanhoucke (2007), Medard and Sawhney (2004), Stojkovic et al. (1998), Thiel (2004) en Vance et al. (1997), hebben bijgedragen tot het vormgeven van de bespreking over de componenten en de objectieven van het crew scheduling proces. Gepubliceerde werken over het crew pairing probleem zijn onder andere te vinden in Anbil et al., 1991; Barnhart et al., 1995; Desaulniers et al., 1997; Graves et al., 1993; Hoffman and Padberg, 1993; Housos and Elmroth, 1997; Vance et al., 1997. Rostering door middel van het bidlines concept is beschreven geweest in het werk van Campbell et al. (1997) en in het werk van Jarrah and Diamond (1997). In Jarrah and Diamond (1997) wordt tijdens het genereren van bidlines rekening gehouden met een aantal kwaliteitsparameters zoals het

streven

naar

28

constante

slaappatronen,

minimale



vermoeidheid, nightstops in dezelfde steden en lange werkblokken gevolgd door veel vrije dagen. Campbell et al. (1997) beschrijven in hun paper een bidline generator, inclusief wat– als analyse, opgesteld voor Federal Express (FedEx). Rostering door middel van het personalized rostering concept is beschreven geweest in Gamache et al. (1998, 1999). In Gamache et al. (1998) worden persoonlijke werkroosters gegenereerd voor Air Canada rekening houdend met individuele preferenties. In Gamache et al. (1999) wordt een optimalisatietechniek gepresenteerd voor het oplossen van grootschalige crew rostering problemen. Deze techniek is getest geweest op Air France. Pionierswerk over het operationeel crew scheduling probleem is te vinden in Stojkovic et al. (1998). Ondanks het feit dat alle luchtvaartmaatschappijen te kampen hebben met de dagelijkse operationele problemen waren zij de eerste die er een paper over publiceerden. Andere literatuur over het herplannen van verstoringen die betrekking hebben op de crew is onder andere te vinden in Medard and Sawhney (2004) en Schaefer et al. (2005). Deze laatste behandeld crew scheduling onder onzekerheid. Met andere woorden gaat hun model ervan uit dat de oorspronkelijk opgestelde planning in de toekomst met grote waarschijnlijkheid zal moeten worden gewijzigd omwille van de hierboven opgesomde wijzigingen die kunnen optreden. Door hiermee vooraf rekening te houden kunnen belangrijke kosten voor het herplannen worden bespaard. Indirect wordt in dit werk de nood voor robuuste roosters aangehaald.

4 Optimalisatiestrategie: sequentie versus integratie In het voorgaande zijn de zeven planningsdomeinen uiteengezet. Luchthavens en luchtvaartmaatschappijen moeten dus elk planningsdomein zo optimaal mogelijk plannen. De moeilijkheid ligt in het feit dat bepaalde planningsdomeinen elkaar sterk beïnvloeden. De gegenereerde output van het ene planningsdomein dient als input voor het volgende planningsdomein. Het complexe domein van planning en optimalisatie kan door middel van twee strategieën opgelost worden. De eerste strategie betreft de sequentiële aanpak. De tweede strategie is de geïntegreerde aanpak.

29



Beide strategieën worden hieronder beschreven en aan de hand van een voorbeeld geïllustreerd. Enkel de planningsdomeinen die elkaar sterk beïnvloeden worden beschouwd voor deze uiteenzetting. Het betreft de vluchtplanning, de vliegtuigplanning en uiteraard de personeelsplanning zoals aangeduid in het blauw in figuur 4.1.

Figuur 4.1. Overzicht planningsdomeinen die elkaar sterk beïnvloeden

In deel 4.1, wordt op basis van de planningsprocedure die luchtvaartmaatschappijen meestal hanteren om hun operaties te plannen een samenvatting gegeven van de drie planningsdomeinen. Het verschil tussen een sequentiële aanpak en een geïntegreerde aanpak wordt in deel 4.2 geïllustreerd aan de hand van een uitgewerkt voorbeeld.

4.1 Planningsprocedure Luchtvaartmaatschappijen hanteren meestal een sequentiële procedure om hun operaties te plannen. Eerst worden de flight legs gepland. Dat wil zeggen het bepalen van de periode, de vertrekuren en aankomsturen van alle individuele vluchten. Hierdoor ontstaat het vluchtrooster of de timetable. Daarna wordt het fleet assignment probleem opgelost. Zoals hierboven uiteengezet is dit het toewijzen van de vliegtuigtypes aan elke flight leg met als doel het maximaliseren van de geanticipeerde winst, rekening houdend met het aantal beschikbare vliegtuigen. Vervolgens wordt voor elk vliegtuigtype het aircraft routing probleem opgelost. Hier worden de individuele vliegtuigen toegewezen aan de flight legs zodat alle flight legs exact eenmaal worden gedekt door een vliegtuig, terwijl voldoende onderhoud voor elk vliegtuig wordt verzekerd. Naargelang het vluchtrooster worden dan

30



bepaalde sequenties van flight legs samengebundeld tot crew pairings. Dan worden de gekwalificeerde personeelsleden toegewezen aan de gegenereerde pairings. Dit in tegenstelling met de vliegtuigen die worden toegewezen aan flight legs en niet aan pairings. Cruciaal is hier ook dat alle pairings samen alle flight legs exact eenmaal moeten coveren met de nodige crew. Op dat moment is een flight leg gedekt door exact één vliegtuigen en de nodige crew. Crew rostering, de laatste stap van dit sequentieel proces, is het vormen van maandelijkse werkroosters voor elk individueel personeelslid. Figuur 4.2 illustreert de planningssequentie voor luchtvaartmaatschappijen.

Flight legs Timetable

Vluchtplanning

Fleet Assignment

Aircraft routing

Vliegtuigplanning

Crew pairing

Personeelsplanning

Figuur 4.2. Planningssequentie voor luchtvaartmaatschappijen

31

Crew rostering



4.2 Uitgewerkt voorbeeld Het verschil tussen een sequentiële of een geïntegreerde oplossingsstrategie wordt aan de hand van een fictief voorbeeld geïllustreerd. Een startende luchtvaartmaatschappij bevindt zich in de volgende beginsituatie. Ze vliegt naar vier verschillende bestemmingen heen en terug, dat wil zeggen acht flight legs. Verder bezit de startende luchtvaartmaatschappij twee vliegtuigen. Eentje van het type Airbus A-319 en eentje van het type Airbus A-330. De vliegtuigcodes staan tussen haakjes. Enkel het cockpit personeel wordt beschouwd. De maatschappij heeft vier captains en vier copiloten in dienst die gekwalificeerd zijn voor zowel de Airbus A-319 en Airbus A-330. Deze dubbele kwalificatie komt frequent voor, ook bij SN Brussels Airlines, omdat het dezelfde vliegtuigfamilie is. Figuur 4.3 illustreert de beginsituatie.

leg

7

8 leg

leg 5

leg 6

Figuur 4.3. Sequentie versus integratie beginsituatie uitgewerkt voorbeeld

De startende luchtvaartmaatschappij moet nu alles operationeel maken. Een belangrijk onderdeel van dit proces is het opstellen van de planning. Hiervoor heeft de

32



luchtvaartmaatschappij diverse programma’s aangekocht. Alhoewel ze nu nog heel klein is, mikt de maatschappij op een jaarlijkse verdubbeling van haar middelen. Dat is ook de reden van de aankoop van de diverse programma’s. Deze programma’s werken sequentieel zoals hierboven beschreven. De planner laat de programma’s sequentieel runnen en bekomt het resultaat dat in tabel 4.1 is weergegeven.

Tabel 4.1.

Timetable

Resultaten sequentiële aanpak

Flight leg

Type vliegt.

Code vliegt.

Pairing

Crew

Nummer 1

08:10 – 09:20

Brussel - Berlijn

A-319

OOWDA

1

1 CPT, 1 F/O

2

09:50 – 11:00

Berlijn - Brussel

A-319

OOWDA

1

1 CPT, 1 F/O

3

08:00 – 09:45

Brussel - Milaan

A-330

OOWDB

2

1 CPT, 1 F/O

4

10:15 – 12:00

Milaan - Brussel

A-330

OOWDB

2

1 CPT, 1 F/O

5

13:00 – 14:30

Brussel - Nice

A-319

OOWDA

2

1 CPT, 1 F/O

6

15:00 – 16:30

Nice - Brussel

A-319

OOWDA

2

1 CPT, 1 F/O

7

20:00 – 01:00

Brussel – Casablanca

A-330

OOWDB

3

1 CPT, 1 F/O

8 01:45 – 06:45 Casablanca - Brussel Bron: Fictieve gegevens, alleen ter illustratie

A-330

OOWDB

3

1 CPT, 1 F/O

De tabel moet geïnterpreteerd worden als volgt. Flight leg 1, de vlucht van Brussel naar Berlijn, vertrekt om 8:10 en komt aan om 09:20. Deze vlucht wordt voltooid met de Airbus A-319 en heeft één captain (CPT) en één copiloot (F/O) nodig. De terugvlucht van Berlijn naar Brussel staat genoteerd als flight leg 2, deze wordt met hetzelfde vliegtuig en dezelfde bemanning voltooid, en vertrekt in Berlijn om 09:50. Hieruit leidt men af dat de rotatietijd in Berlijn 30 minuten bedraagt. Overigens is 30 minuten, operationeel gezien, de minimale maar ook meest optimale rotatietijd. De andere flight legs moeten op dezelfde manier geïnterpreteerd worden. Twee opmerkingen zijn aan de orde. Ten eerste moet erop gewezen worden dat één captain en één copiloot geen pairing moeten doen. Deze twee piloten zijn wel reserve als er iets zou gebeuren met de andere piloten waardoor deze hun pairing niet zouden kunnen doen. Ten tweede behoeft pairing 2 grondige aandacht. Dezelfde piloten vliegen eerst heen en terug naar Milaan en vervolgens heen en terug naar Nice. Maar deze twee heen en terug vluchten doen ze wel met verschillende vliegtuigen. Dit is een nadeel daar de optimale rotatietijd van 30 minuten in Brussel onhaalbaar wordt omdat

33



de piloten van vliegtuig moeten wisselen. Deze suboptimale oplossing vloeit voort uit het feit dat de planning sequentieel en niet geïntegreerd gebeurd. Mercier and Soumis (2007) pogen in hun model de planning geïntegreerd aan te pakken. Deze auteurs baseren zich op andere werken die aantonen dat door de integratie van aircraft routing en crew scheduling significant betere oplossingen worden gegenereerd. Op basis van deze bevindingen hebben ook zij een model opgesteld die aircraft routing, crew scheduling en flight retiming (herplannen van de verstoringen) integreert in één model. Ook hun model genereerde meer optimale oplossingen. De reden dat een geïntegreerde aanpak meer optimale oplossingen genereert dan een sequentiële aanpak, ligt in het feit dat de minimale rotatietijd tussen twee opeenvolgende vluchten bestaft door dezelfde crew afhankelijk is van het feit of het zelfde vliegtuig wordt gebruikt voor beide vluchten (Mercier and Soumis, 2007). Zoals in het voorbeeld ook duidelijk te zien is, is de rotatietijd in Brussel voor pairing 2 geen 30 minuten, maar 1 uur. De gevolgen zijn hogere operationele kosten, daar de crew en de vliegtuigen langer aan de grond blijven. Voor grote luchtvaartmaatschappijen kunnen die extra kosten aanzienlijk oplopen. Anbil et al. (1991) berekenden dat een wijziging van de rotatietijd van 35 minuten naar 50 minuten dit de luchtvaartmaatschappij American Airlines 35 miljoen dollar extra operationele kosten zou opleveren op jaarbasis. Tabel 4.2 toont de geïntegreerde planning van dezelfde beginsituatie.

Tabel 4.2.

Timetable

Resultaten geïntegreerde aanpak

Flight leg

Type vliegt.

Code vliegt.

Pairing

Crew

1

1 CPT, 1 F/O

Nummer 1

08:10 – 09:20

Brussel - Berlijn

A-330

OOWDA

2

09:50 – 11:00

Berlijn - Brussel

A-330

OOWDA

1

1 CPT, 1 F/O

3

08:00 – 09:45

Brussel - Milaan

A-319

OOWDB

2

1 CPT, 1 F/O

4

10:15 – 12:00

Milaan - Brussel

A-319

OOWDB

2

1 CPT, 1 F/O

5

12:30 – 14:00

Brussel - Nice

A-319

OOWDA

2

1 CPT, 1 F/O

6

14:30 – 16:00

Nice - Brussel

A-319

OOWDA

2

1 CPT, 1 F/O

7

20:00 – 01:00

Brussel – Casablanca

A-330

OOWDB

3

1 CPT, 1 F/O

8

01:45 – 06:45

Casablanca - Brussel

A-330

OOWDB

3

1 CPT, 1 F/O

Bron: Fictieve gegevens, alleen ter illustratie

34



De wijzigingen staan in het blauw. De piloten die pairing 2 voldoen, moeten in deze nieuwe planning niet van vliegtuig wisselen in Brussel. Hierdoor verkort de rotatietijd met 30 minuten. Bijgevolg moeten de piloten die pairing 2 doen 30 minuten minder lang werken, komt de Airbus A-330 1 uur vroeger vrij en komt de Airbus A-319 30 minuten vroeger vrij. De Airbus A-319 vertrekt wel 10 minuten vroeger. Figuur 4.4 vergelijkt de resultaten. De verschillen staan in het blauw.

Figuur 4.4. Vergelijking resultaten

Via een geïntegreerd planningsmodel ligt de totale operationele tijd 1 uur en 50 minuten lager dan met een sequentieel planningsmodel. Bijgevolg genereert een sequentiële planning suboptimale oplossingen (Mercier and Soumis, 2007). Het voorbeeld is fictief en bezit daarom ook geen enkele bewijskracht. De literatuur daarentegen levert wel bewijzen. Een aantal gepubliceerde werken beschrijven hun geïntegreerde aanpak, maar wijzen ook op het feit dan een volledig geïntegreerde aanpak nog niet is gerealiseerd. Voorbeelden van dergelijke werken zijn onder andere het werk van Mercier and Soumis (2007) en Sherali et al. (2006). De reden dat een volledig geïntegreerde oplossing nog niet is gerealiseerd, ligt in de hierboven aangehaalde hoge graad van complexiteit die eigen is aan de luchtvaartsector. Toch leeft de overtuiging dat mits verder onderzoek hieromtrent een volledig geïntegreerde aanpak realiseerbaar moet zijn.

35



5 Gedetailleerde analyse van het crew rostering probleem De planningsdomeinen van het complexe domein van planning en optimalisatie in de luchtvaartsector zijn uiteengezet. Eén planningsdomein, namelijk crew scheduling, is grondiger geanalyseerd en beschreven. De verticale benadering die gestart is vanaf de uiteenzetting van het crew scheduling probleem wordt hier verder gezet met een gedetailleerde analyse van het crew rostering probleem. Aan de basis van de keuze om crew rostering en niet crew pairing gedetailleerder te onderzoeken liggen een aantal factoren. Ten eerste is het crew pairing probleem al veelvuldig beschreven in operationeel onderzoek. Crew rostering komt daarentegen veel minder aan bod. De reden hiervoor is de sterke kostenreductie die kan worden bereikt met crew pairing. In crew rostering ligt een sterke daling van de kosten niet voor de hand omdat een tweede doel, levenskwaliteit, evenveel aandacht zou moeten krijgen. De implicaties van een hoge levenskwaliteit en in het bijzonder van een hoge crew satisfactie zijn hierboven beschreven. In een wetenschappelijk werk is het eenvoudiger dan in een commercieel werk om minder aandacht te besteden aan kostenreductie. Daarenboven ben ik van mening dat een crew rostering algoritme dat in staat is om een gelijkverdeelde werkdruk tussen de roosters te creëren misschien wel een grotere positieve impact kan hebben op de winst dan het puur streven naar kostenreductie. Een andere factor is dat SN Brussels Airlines zijn werkroosters nog manueel opstelt. Door het crew rostering algoritme van Maenhout and Vanhoucke (2007) te testen op hun gegevens willen wij aantonen dat crew rostering ook geautomatiseerd kan worden en zelfs met een hogere graad van gelijkheid in de werkroosters. Al deze factoren samen vormen een mooie opportuniteit om het crew rostering probleem verder te onderzoeken. Figuur 5.1 situeert crew rostering te midden de planningsdomeinen in de luchtvaartsector.

36



Planning en optimalisatie in de luchtvaartsector

Vluchtplanning (Flight scheduling)

Vliegtuig planning (Aircraft scheduling)

Crew Pairing

Personeels – planning (Crew scheduling)

Herplanning verstoringen (Disruption management)

Planning van de landingen (Aircraft landing problem)

Gate planning (Flight gate scheduling)

Strategie voor ticketinkomsten (Revenue management)

Crew Rostering

Figuur 5.1. Situering crew rostering

Het crew rostering probleem heeft zoals eerder aangehaald een tweevoudig doel. Ten eerste moeten de kosten worden geminimaliseerd en ten tweede moet de levenskwaliteit en in het bijzonder de crew satisfactie worden gemaximaliseerd. Dit optimalisatieprobleem is onderhevig aan 2 types beperkingen. Ten eerste moeten alle overheidsregels, collectieve arbeidsovereenkomsten en bedrijfspecifieke regels worden gerespecteerd en ten tweede moeten alle pairings exact eenmaal worden bestaft door crew. Zoals elk optimalisatieprobleem heeft het crew rostering probleem een aantal inputgegeven nodig heeft. Als we bij wijze van spreken met een vergrootglas gaan kijken naar deze inputgegevens dan zien we dat het personalized rostering probleem vier grote inputblokken heeft zoals te zien in figuur 5.2, gebaseerd op Kohl and Karisch (2004). Zowel de crew informatie, de mogelijke activiteiten, alle regels en wetgevingen als de beoogde doelstellingen zijn allen belangrijke inputblokken voor het crew rostering proces op basis van het personalized rostering concept. Een minimale wijziging in deze inputfactoren kan leiden tot volledig verschillende werkroosters. Rostering aan de hand van het bidlines concept houdt geen rekening met individuele crew informatie omdat bidlines anonieme werkroosters zijn. In het vervolg van de scriptie wordt gekozen voor het personalized rostering concept omwille van twee redenen. In Europa en ook bij SN Brussels Airlines wordt dat concept gehanteerd en het algoritme dat gebruikt wordt in de case is een crew rostering algoritme specifiek ontwikkeld voor het personalized rostering concept.

37



Figuur 5.2. Inputblokken voor het crew rostering probleem

In wat volgt worden de inputblokken van het personalized rostering concept zorgvuldig geanalyseerd en beschreven. Deel 5.1 behandelt het eerste inputblok, namelijk de crew informatie. In deel 5.2 worden de mogelijke activiteiten kort herhaald. De uitgebreide regels en wetgevingen worden in deel 5.3 besproken en geïllustreerd aan de hand van voorbeelden. Deel 5.4 overloopt de mogelijke doelstellingen.

5.1 Crew informatie De individuele crew informatie vormt het eerste inputblok voor het personalized rostering probleem. Elke luchtvaartmaatschappij die persoonlijke werkroosters opstelt voor zijn personeel zal een goed werkend database systeem nodig hebben. De database moet namelijk voor elke individueel personeelslid zijn of haar historiek, kwalificaties, vooraf toegewezen activiteiten en toegestane vakantiedagen opslaan en updaten bij elke wijziging. De historiek en de kwalificaties van een personeelslid zijn belangrijk voor het respecteren van de opgelegde regels & wetgeving. Daarenboven is de historiek belangrijk

38



om te voldoen aan het fair-and-equal share principe dat eigen is aan personalized rostering. Het aantal blok uren, het aantal nachtvluchten, de totale service time, het aantal trainingen, de medische controles en het aantal vakantiedagen gedurende het huidige kalenderjaar zijn heel belangrijke informatie. Een piloot moet bijvoorbeeld onder een maximaal aantal blok uren per maand, per drie maand en per jaar blijven. Zo niet wordt een regel overtreden. Maar de planners streven ook naar roosters met gelijkverdeelde werkdruk. Daarom pogen ze op maandbasis en vooral op jaarbasis hetzelfde aantal blok uren voor elke piloot te bekomen. Voor de andere factoren geldt eenzelfde redenering. De kwalificaties die een personeelslid bezit zijn zoals gezegd belangrijk voor het respecteren van de regels, maar ook voor het opsplitsen van het crew rostering probleem. Zoals in deel 3.4 aangehaald is het scheduling proces heel ingewikkeld en wordt het daarom onderverdeeld in kleinere sub problemen. Niet alleen wordt het opgespitst in crew pairing en crew rostering, ook worden deze substappen verder opgesplitst per positie en per vliegtuigtype. Een piloot kan bijvoorbeeld gekwalificeerd zijn als captain voor het vliegtuigtype Airbus A-319. Op die manier maakt de piloot in kwestie deel uit van een bepaald sub probleem. Een kwalificatie die belangrijk is voor het respecteren van de regels zou bijvoorbeeld een lijst kunnen zijn van de bestemmingen waar de piloot niet mag naar toe vliegen omdat hij er niet voor is gekwalificeerd. De vooraf toegewezen activiteiten en de toegestane vakantiedagen zijn belangrijk om conflicterende roosters te vermijden. Zo kan een personeelslid die vakantie heeft gekregen de eerste week van de maand geen andere activiteiten verrichten in deze week.

5.2 Toe te wijzen activiteiten Elke luchtvaartmaatschappij heeft een set activiteiten die het moet verrichten om operationeel te blijven. Al deze activiteiten moeten dus worden toegewezen aan de personeelsleden tijdens het opstellen van de individuele werkroosters. Bijgevolg moet de set activiteiten, in het bijzonder de pairings, de reserves en de vooraf toegewezen activiteiten, een aantal weken op voorhand worden vastgelegd. Een overzicht van deze activiteiten werd gegeven in deel 3.3 en is te zien in figuur 3.6.

39



Op te merken valt dat de vooraf toegewezen activiteiten onder twee categorieën vallen. Dit komt doordat het activiteiten betreft die aan specifieke personeelsleden worden toegewezen. Het betreft dus zowel individuele crew informatie als een toe te wijzen activiteit. Maar evengoed had men ze slechts in één categorie kunnen onderbrengen zoals in Kohl and Karisch (2004).

5.3 Regels & wetgeving De regels & de wetgeving worden opgelegd door de overheid, de collectieve arbeidsovereenkomsten (cao) en door de luchtvaartmaatschappijen zelf. Deze regels stellen belangrijke beperkingen voor in het optimalisatieprobleem. Overheidsregels verschillen hoofdzakelijk naargelang het werelddeel, maar kunnen eventueel ook verschillen naargelang het land waarin de luchtvaartmaatschappij is gevestigd. De overkoepelende regels geldig in de Verenigde Staten worden opgesteld door de Federal Administration Autorithies (FAA) en worden samengevat in de Federal Administration Regulations (FAR’s). In Europa daarentegen zijn de overkoepelende Europese regels enkel geldig in de landen die toegestemd hebben. De regels worden opgesteld door de Joint Aviations Authorities (JAA) en worden samengevat in de Joint Aviations Requirements

(JAR’s).

Specifieke

overheidsregels

geldig

voor

Belgische

luchtvaartmaatschappijen worden opgesteld door de Federale Overheidsdienst Mobiliteit en Vervoer en worden samengevat in de CIR/OPS. De regels die voortvloeien uit de collectieve arbeidsovereenkomsten

kunnen

grote

verschillen

vertonen

tussen

luchtvaartmaatschappijen. Meestal hebben deze regels betrekking op de sociale kwaliteiten van de werkroosters, zoals bijvoorbeeld een minimaal aantal dagen vrijaf per maand. Luchtvaartmaatschappijen zelf stellen dan nog eens extra regels op. Deze regels vallen onder de noemer bedrijfspecifieke regels. Deze extra regels worden opgesteld om de kwaliteit van de werkroosters te doen stijgen. In de praktijk wordt echter geen onderscheid gemaakt tussen de drie types regels. Luchtvaartmaatschappijen stellen een globaal pakket aan regels op die aan alle vereisten

40



voldoen en vatten deze samen in de operations manuel (OM). Dit globale pakket wordt bij SN Brussels Airlines samengevat in de JAR-OPS OM refererend naar de Europese en Belgische overheidsregels die moeten worden voldaan. In bijlage staat een samenvatting van de regels uit de JAR-OPS OM van SN Brussels Airlines en in de elektronische bijlage staat de volledige elektronische versie van de JAR-OPS OM. In operationeel onderzoek daarentegen wordt er wel onderscheid gemaakt tussen de verschillende types regels. Ten eerste wordt een onderscheid gemaakt tussen horizontale, verticale en artificiële regels. Horizontale regels zijn regels die gelden voor één personeelslid en die dus betrekking hebben op één individueel werkrooster. Bij grote Europese luchtvaartmaatschappijen kan het aantal horizontale regels makkelijk oplopen tot meer dan 100 regels. In tegenstelling tot horizontale regels, hebben verticale regels wel betrekking op meerdere roosters en meerdere personeelsleden (Kohl and Karisch, 2004; Maenhout and Vanhoucke, 2007). De artificiële regels komen overeen met de bedrijfspecifieke regels. Ze worden dus niet vereist door de wetgeving of door de collectieve arbeidsovereenkomsten, maar ze worden toch opgelegd door de luchtvaartmaatschappijen zelf omdat ze de kwaliteit van de werkroosters positief beïnvloeden. Daarom worden artificiële regels ook wel kwaliteitsregels genoemd. Deze regels voorzien de werkroosters van extra beperkingen waardoor onaantrekkelijke roosters worden geëlimineerd. Vooral het aspect robuustheid wordt in rekening gebracht door deze regels (Kohl and Karisch, 2004). In de bespreken van het laatste inputblok wordt dieper ingegaan op de implicaties van robuuste planningen. Een tweede onderscheid kan gemaakt worden tussen sterke en zwakke beperkingen. Sterke beperkingen zijn beperkingen die bij overtreding de veiligheid van de vlucht schaden. Deze beperkingen dienen dan ook prioritair te worden gerespecteerd. Voorbeelden van dergelijke beperkingen zijn crew kwalificaties, wetgeving in verband met maximale werkuren en minimaal aantal verplichte rustperioden, medisch gezonde personeelsleden en training. Zwakke beperkingen zoals bedrijfspecifieke regels, collectieve arbeidsovereenkomsten in verband met werk en betaling, rekening houden met individuele preferenties van de personeelsleden en vakantieregelingen, garanderen de sociale kwaliteit van de werkroosters (El Moudani et al., 2001; Maenhout and Vanhoucke, 2007). Deze zwakke beperkingen zijn

41



relevant voor de opbouw van roosters omdat ze leiden tot crew satisfactie. Echter, als men ze gedeeltelijk kwijtscheldt kan dit leiden tot lagere kost oplossingen. In de meeste luchtvaartmaatschappijen evenwel zijn de kwalitatieve indicatoren opgenomen in de collectieve arbeidsovereenkomsten waardoor zij worden behandeld als (zachte) beperkingen in de oplossingsmodellen (Gamache et al., 1999; Maenhout and Vanhoucke, 2007; Medard and Sawhney, 2004). Een schematisch overzicht over de verschillende indelingen van de regels staat in figuur 5.3.

Figuur 5.3. Indeling van de regels

Eerst bouwen de luchtvaartmaatschappijen dus het globale pakket aan regels op uit de op

hen

toepasselijke

overheidsregels,

collectieve

arbeidsovereenkomsten

en

bedrijfspecifieke regels. Vervolgens wordt dit globaal pakket aan regels onderverdeeld in enerzijds horizontale, verticale en artificiële regels en anderzijds sterke en zwakke beperkingen. Voorbeelden van sterke en zwakke beperkingen zijn hierboven gegeven. Voorbeelden van horizontale en verticale regels worden respectievelijk gegeven in subdeel 5.3.1 en 5.3.2. Het betreft algemene voorbeelden gebaseerd op Gamache et al., 1999; Kohl and Karisch, 2004; Maenhout and Vanhoucke, 2007 en specifieke voorbeelden toegepast op gegevens van SN Brussels Airlines gebaseerd op hun JAR-OPS OM (2006).

42



5.3.1 Voorbeelden van horizontale regels Zoals hierboven beschreven hebben horizontale regels enkel betrekking op één personeelslid en dus op één werkrooster. Een exhaustief overzicht kan onmogelijk worden gegeven. Als vervanging worden een aantal horizontale regels geïllustreerd die frequent toegepast worden door luchtvaartmaatschappijen. Een overzicht van de horizontale regels die hieronder zullen worden geïllustreerd staan in figuur 5.4.

Figuur 5.4. Overzicht van de horizontale regels

Een eerste type horizontale regels betreft bepaalde voorwaarden van de collectieve arbeidsovereenkomsten. Deze overeenkomsten beïnvloeden welke pairings kunnen worden toegewezen aan een personeelslid, want personeelsleden kunnen enkel worden toegewezen aan activiteiten die compatibel zijn met hun kwalificatie en vooraf toegewezen activiteiten. Een piloot zal bijvoorbeeld eerst de nodige veiligheidscertificaten voor een bepaalde type vliegtuig moeten bezitten alvorens voor dat type vliegtuig gekwalificeerd te zijn. In afwachting kan deze piloot niet worden toegewezen aan de pairings die worden gevlogen met het type vliegtuig in kwestie. Ook moeten de personeelsleden over de nodige visa beschikken om bijvoorbeeld een pairing naar de Verenigde Staten te doen. Beschikken ze niet over de nodige visa dan kunnen ze dus niet worden toegewezen aan de pairings die vluchten naar de Verenigde Staten bevatten. Algemeen kan men stellen dat alleen

43



activiteiten in aanmerking komen voor een bepaald personeelslid als deze de nodige kwalificaties bezit en als de activiteiten niet conflicteren met de vooraf toegewezen activiteiten (Maenhout and Vanhoucke, 2007). Een voorbeeld ter illustratie. Beschouw onderstaand legaal werkrooster in figuur 5.5. Het weekrooster is opgesteld voor een copiloot. Zijn eerste pairing van de week begint maandagmorgen om 8:55, eindigt woensdagmorgen om 6:25 en wordt gedaan met een Airbus A-330. De heenvlucht is een vlucht naar Kinshasa met een tussenlanding in Duala. De crew overnacht in Kinshasa en krijgt er minimaal 22 uur rust zoals de regels bij SN Brussels Airlines het voorschrijven. Na de rustperiode wordt de terugvlucht naar Brussel met tussenlanding in Duala gedaan. Omstreeks 6:25 op woensdagmorgen landt deze terugvlucht. Daarna geniet de copiloot van een nieuwe verplichte rustperiode. Donderdag en vrijdag staan respectievelijk een training en een reserve geprogrammeerd. Zaterdag moet de copiloot zijn tweede pairing van de week vervullen. Dit is een heen– en terugvlucht naar Wenen te doen met een kleiner type, een Airbus A-319. Zondag tenslotte geniet de copiloot van een volledige rustdag. Tot hier toe is het werkrooster perfect legaal, maar stel nu dat de copiloot enkel gekwalificeerd is voor het type Airbus A-330. De copiloot kan pairing 2 dan niet doen omdat er wordt gevlogen met een Airbus A-319. Of stel dat de copiloot drie maand eerder aangevraagd had om van maandag tot woensdag drie vrije dagen te krijgen omwille van zijn trouw en dat de planners dit hadden aanvaard. In beide gevallen is dit werkrooster niet compatibel met zijn kwalificaties en met de vooraf toegewezen activiteiten.

Figuur 5.5. Voorbeeld legaal weekrooster

44



Een ander type horizontale regels behandelt de verplichte rustperioden. In de meeste luchtvaartmaatschappijen gelden ongeveer dezelfde regels. Voorbeelden van dergelijke regels zijn onder andere het minimaal aantal uren verplichte rust na een vlucht of tussen twee activiteiten en het minimaal aantal verplichte dagen vrijaf na een opeenvolging werkdagen. Het aantal verplichte uren rust tussen twee activiteiten is bijvoorbeeld afhankelijk van een aantal factoren van de vorige activiteit (aantal uren, duty time, aantal blok uren, nacht- of dagactiviteit, aantal overschreden tijdzones) en van een aantal factoren van de volgende activiteit (type activiteit, periode van de dag dat de activiteit begint en eindigt). Uitzonderlijk kan de verplichte rusttijd zelf afhankelijk zijn van nog eerder gedane activiteiten. (Gamache et al., 1999; Kohl and Karisch, 2004; Maenhout and Vanhoucke, 2007). Een concreet voorbeeld toegepast op SN Brussels Airlines wordt gegeven ter illustratie. Bij deze luchtvaartmaatschappij geldt dat voor een lange afstandsvlucht, gedefinieerd als een vlucht buiten bepaalde geografische limieten, het minimaal aantal uren verplichte rust na een vlucht wordt berekend als volgt (OM SN Brussels Airlines, 2006). De berekening is toegepast op de terugvlucht van Kinshasa naar Brussel in bovenstaande figuur 5.5. -

Aanmeldingstijd (Reporting time) buiten Zaventem = uur van opstijgen – 60 min.

-

Eindtijd van de vlucht (Closing time) in Zaventem = Landingsuur + 30min.

-

Vluchttijd (FDT = flight duty time) = Closing time – Reporting time = (06:25 + 30min.) – (20:55 – 60min.) = 11:30

-

Minimaal verplichte rusttijd = 1,5 * FDT (+ 5 uur na nachtvlucht) ≥ 16 uur = 21:30

In bovenstaand werkrooster krijgt de copiloot 27:05 rust. Namelijk de aanmeldingstijd van de training (10:00) minus de eindtijd van de laatste vlucht (06:55). De redenen dat hier gekozen wordt voor een ruimere marge kunnen te maken hebben met zo optimaal mogelijke vertrek- en aankomsturen, maar evenzeer met het inbouwen van robuustheid. Een vliegtuig dat in Afrika een technisch defect heeft zal moeizamer en dus langzamer

45



worden hersteld dan in Europa omdat de middelen in de westerse wereld deze van het Afrikaans continent overstijgen. Een derde type horizontale regels heeft betrekking op geaccumuleerde waarden en is daarom nauw verbonden met de historiek van de crew. De regels schrijven bepaalde beperkingen voor op maandbasis, driemaandelijkse basis, jaarbasis en andere tijdsgebonden intervallen zoals beperkingen op 30 opeenvolgende dagen of 90 opeenvolgende dagen. Voorbeelden van dergelijke beperkingen zijn maximaal aantal blok uren, maximaal aantal nachtactiviteiten, maximale tijd weg van de thuisbasis (time away from base), maximaal aantal zware activiteiten, maar ook minimaal en maximaal aantal vrije dagen. De meeste horizontale regels van dit type worden gebonden langs één zijde, maar uitzonderingen komen voor. Bij Air Canada bijvoorbeeld moet het aantal blok uren op maandbasis tussen de 70 en 78 uur liggen. Bij Brussels Airlines daarentegen worden de blok uren enkel gebonden tot bepaalde maximale waarden op 30 opeenvolgende dagen, 90 opeenvolgende dagen en op 12 opeenvolgende maanden. De maxima zijn respectievelijk 110 uur, 300 uur en 900 uur (Gamache et al., 1999; Kohl and Karisch, 2004; Maenhout and Vanhoucke, 2007; OM SN Brussels Airlines, 2006). Luchtvaartmaatschappijen moeten nog met tal van andere horizontale regels rekening houden, zoals bijvoorbeeld het overschrijden van verschillende tijdzones. Dit probleem wordt heel specifiek omschreven in de luchtvaartmaatschappijen daar het van primordiaal belang is naar veiligheid toe. Een crew die bijvoorbeeld eerst naar het Westen vliegt en dan naar het Oosten of vice versa zal een aantal verplichte rustdagen moeten krijgen omdat het risico op oververmoeidheid en bijgevolg onveiligheid te groot is (Kohl and Karisch, 2004). Voor een cabine personeelslid van SN Brussels Airlines geldt de regel dat tussen een vlucht naar de Verenigde Staten gevolgd door een vlucht naar Azië er minimaal vier verplichte rustdagen, inclusief drie lokale nachten, moeten worden voorzien (OM SN Brussels Airlines, 2006)

46



5.3.2 Voorbeelden van verticale regels Verticale regels hebben betrekking op meerdere roosters. In bepaalde gevallen zelfs op de volledige set van roosters. De verticale regels zijn minder talrijk dan de horizontale. Toch is het naar analogie met de horizontale regels onmogelijk om een exhaustief overzicht te geven van alle verticale regels. Enkel de voornaamste verticale regels worden toegelicht. Figuur 5.6 schetst een overzicht van de voornaamste types verticale regels die zullen worden toegelicht.

Figuur 5.6. Overzicht van de verticale regels

Het belangrijkste type verticale regel is zonder twijfel de regel inzake het crew complement. Zelfs al wordt het crew rostering probleem opgesplitst naar functie, vereisen verschillende activiteiten verschillende crew complements. Typisch zullen pairings die bestaan uit korte vluchten toegewezen worden aan één captain, één copiloot en twee cabine personeelsleden (Kohl and Karisch, 2007). Een voorbeeld van een dergelijke crewsamenstelling staat in figuur 5.7. Deze figuur illustreert de dagroosters van zeven personeelsleden. Hun functie staat links in de figuur. De heen- en terugvlucht naar Zurich is bijvoorbeeld toegewezen aan personeelsleden 2, 3, 4 en 5. Voor de simulatorsessie startend om 4 uur ‘s morgens bestaat de nodige crew uit een instructeur, een captain en een copiloot, respectievelijk personeelsleden 1, 2 en 3 worden hiervoor ingezet.

47



Figuur 5.7. Voorbeelden van verticale regels

Zoals het geval bij horizontale regels gelden ook voor verticale regels beperkingen inzake kwalificaties. Deze regels zijn voornamelijk van toepassing het cabine personeel, maar kunnen ook van toepassing zijn op het cockpit personeel. Een eerste geval is de beperking inzake onervaren piloten. Deze beperking is gebonden in aantal. Zo mag maximum één van de piloten onervaren zijn. In bovenstaande figuur 5.7 is personeelslid 3 de enige onervaren piloot voor de heen- en terugvlucht naar Zurich. Een tweede geval dat frequent voorkomt bij grote luchtvaartmaatschappijen zijn twee personeelsleden die een aantal keer per maand moeten samen vliegen. Dit kan bijvoorbeeld het geval zijn voor getrouwde koppels. Deze regel is eigenlijk een speciaal geval van het team-oriented rostering concept. Zoals hierboven beschreven streeft dit concept naar maximale crew satisfactie. Personeelsleden 6 en 7 illustreren deze regel in bovenstaande figuur 5.7. Een derde geval die frequent voorkomt bij piloten die samen een lange afstandsvlucht doen, zijn incompatibele situaties. Een incompatibele situatie zou zich bijvoorbeeld kunnen voordoen als de captain en de copiloot conflicterende persoonlijkheden hebben. Hun samenwerking zou hieronder kunnen lijden waardoor de vluchtveiligheid in het gedrang zou kunnen komen. Een laatste geval dat

48



beschouwd wordt zijn taalkwalificaties. Deze beperking is enkel toepasselijk op het cabine personeel. Een vlucht van Parijs naar Bangkok bijvoorbeeld bevat veel Thais sprekende passagiers, daarom moeten minstens vijf van de vereiste vijftien cabine personeelsleden Thai sprekend zijn (Kohl and Karisch, 2004). De meeste verticale regels hebben betrekking op een gedeelte van de roosters. In bepaalde gevallen kunnen de regels ook gelden voor de volledige oplossing. We spreken dan van globale beperkingen. Een luchtvaartmaatschappij kan bijvoorbeeld de doelstelling nastreven van maximale crew satisfactie en vertaalt ze naar een regel dat minimaal 80 % van de aangevraagde vrije dagen moeten worden aanvaard (Kohl and Karisch, 2004). Talrijke voorbeelden van andere verticale regels zijn voorhanden. Een daarvan, “fly below rank” of vliegen onder zijn rang, wordt frequent toegepast. Luchtvaartmaatschappijen die bijvoorbeeld streven naar robuuste werkroosters zouden meer piloten kunnen opleiden tot captains dan nodig, omdat captains onder hun rang mogen vliegen. Captains kunnen dus opereren als copiloten (Kohl and Karisch, 2004). Als bijvoorbeeld een groot aantal copiloten ziek zijn, kunnen ze worden vervangen door captains zonder dat de planning teveel moet wijzigen. Het nadeel, dat eigen is aan robuustere oplossingen, zijn hogere operationele kosten. Een captain verdiend namelijk meer dan een copiloot.

5.4 Doelstellingen De eerste twee objectieven, minimale kosten en maximale levenskwaliteit, zijn al een aantal keer aan bod gekomen en behoeven geen verdere uitleg meer. De derde doelstelling daarentegen behoeft wel nog grondige aandacht omdat robuustheid heden ten dage en zeker in de toekomst aan belang zal winnen. De reden ligt in het feit dat de luchtvaartsector zich zorgen maakt over het groeiend luchtverkeer. Volgende cijfers bevestigen deze trend. De Federal Aviation Administration rapporteerde in 1999 dat het aantal vertragingen van 1995 tot 1999 met 58 % gestegen zijn en dat het aantal afgelaste vluchten over dezelfde periode met 68 % gestegen zijn (FAA, 1999). In juni 2000 is het aantal vertragingen met 16 % gestegen ten opzichte van juni 1999 (Phillips and Irwin, 2000).

49



Bovendien wordt verwacht dat het luchtverkeer in de Verenigde Staten en in Europa zal verdubbelen in de volgende 10 à 15 jaar. Rekening houdend met deze verwachting wijzen voorspellingen uit dat als de luchthavencapaciteit gelijk blijft elke stijging van het luchtverkeer met 1 %, het aantal vertragingen met 5 % zal doen toenemen (Economist, 2000). In een rapport van het “Bureau of Transportation Statistics” staat dat in 2001 slechts 73,4 % van de vluchten op tijd aankwam en dat 3,87 % van de vluchten afgelast werden (Bureau of Transportation Statistics, 2002). Uit deze cijfers kunnen we dus concluderen dat verstoringen frequenter worden (Lee et al., 2007; Schaefer et al., 2005). De luchtvaartsector kan onmogelijk om deze cijfers heenkijken. Niet alleen moet de luchthavencapaciteit worden uitgebreid, ook moeten luchtvaartmaatschappijen rekening houden met het stijgend aantal verstoringen in hun planning. Met andere woorden de nood voor robuuste planningen dringt zich op. Door actief robuustheid in de roosters in te bouwen zijn deze roosters sterker bestand tegen wijzigingen zoals ziekte, technische defecten, vertragingen en afgelaste vluchten. Hierdoor moeten de roosters minder frequent worden aangepast waardoor de kosten van het herplannen van verstoringen drastisch kunnen dalen. Uiteraard zullen robuuste roosters hogere operationele kosten impliceren doordat grotere marges worden ingebouwd, maar deze kostenverhoging weegt niet op tegen de kostenverlaging die kan worden gerealiseerd. Hoe meer verstoringen, hoe effectiever een robuust rooster is. En zoals de hierboven aangehaalde trends bewijzen, lijkt het erop dat de luchtvaartsector meer en meer te kampen zal krijgen met verstoringen. Alle zojuist aangehaalde implicaties van robuuste roosters worden natuurlijk versterkt als men robuustheid in de volledige planning inbouwt. Er bestaat een aantal types van robuuste oplossingen. Een eerste type handelt over het plannen met extra marge. Stel dat de verplichte rusttijd na een vlucht minimaal 12 uur moet zijn. Een robuust rooster zal dan bijvoorbeeld minimaal 13 uur rust plannen. Zo bekomt men een buffer van 1 uur om vertragingen op te vangen. Een andere mogelijkheid is extra reserves te plannen. Een ander type laat oplossingen die problemen zouden kunnen opleveren toe, maar bestraft deze wel. De toewijzing van de reserves moet bijvoorbeeld compatibel zijn met de pairings uit praktische overwegingen.

50



6 Optimalisatietechnieken voor het oplossen van het crew scheduling probleem De vorige hoofdstukken beschreven het crew scheduling probleem zonder in te gaan op de technieken en methoden die gebruikt worden om dit probleem ook daadwerkelijk op te lossen. Bewust werden de technieken vermeden omdat een duidelijke beschrijving van de planningsdomeinen in de luchtvaartsector al behoorlijk complex is. Het doel was een globaal beeld te schetsen en een uitgebreide analyse van crew scheduling en in het bijzonder crew rostering te presenteren. In dit hoofdstuk wordt een overzicht gegeven van de frequent gehanteerde technieken voor optimalisatie omdat het enerzijds interessant is te weten welke technieken operationele onderzoekers hanteren en anderzijds omdat het algoritme, gebruikt voor het oplossen van de case, elementen incorporeert van alle hieronder beschreven technieken. Een onderscheid tussen technieken gehanteerd voor crew pairing en deze voor crew rostering is niet aan de orde omdat dezelfde technieken gebruikt worden om beide problemen op te lossen. Op te merken valt dat de nadruk ligt op de technieken en niet op de concrete implementatie van de technieken in het scheduling proces. In het volgend hoofdstuk daarentegen ligt de nadruk wel op de implementatie. Het crew rostering algoritme van Maenhout and Vanhoucke (2007) wordt dan volledig doorgrond en getest op werkelijke gegevens van SN Brussels Airlines. De opbouw van dit hoofdstuk is als volgt. In deel 6.1, worden de kenmerken van het crew scheduling probleem opgesomd die een impact hebben op de keuze van te gebruiken oplossingstechnieken. In deel 6.2, wordt een eerste heuristische techniek, genetische algoritmen, beschreven. Een volgende heuristische techniek, simulated annealing wordt gepresenteerd in deel 6.3. Tenslotte, wordt in deel 6.4 tabu search, een recente metaheuristische techniek die gebruikt maakt van flexibel geheugen, voorgesteld en geïllustreerd aan de hand van een voorbeeld.

51



6.1 Kenmerken van het crew scheduling probleem Het

crew

scheduling

probleem

bezit,

naast

het

feit

dat

het

om

een

optimalisatieprobleem gaat, een aantal andere belangrijke kenmerken waar rekening mee gehouden moet worden. De kenmerken bepalen namelijk welke oplossingsmethoden geschikt zijn en welke niet. Een eerste kenmerk betreft de combinatorische aard van crew scheduling. Bij grote luchtvaartmaatschappijen verplicht de combinatorische complexiteit, die in beide optimalisatieproblemen overheerst, de operationele onderzoekers te streven naar zo optimaal mogelijke oplossingen eerder dan naar de exacte optimale oplossing. Grote luchtvaartmaatschappijen bijvoorbeeld doen rond de duizend vluchten per dag, waardoor de mogelijkheden aan pairings gemakkelijk kan oplopen tot in de miljarden (Hoffman and Padberg, 1993). Voor kleine tot middelgrote problemen zijn exacte oplossingen realistischer. Hoffman and Padberg (1993) rapporteerden bijvoorbeeld hun optimale oplossing voor een probleem met 150 vluchten en 1 miljoen pairings. Het realiseren van exacte optimalisatie voor grotere, real-world, crew scheduling problemen is anno 2007 nog ontoereikend. Daarom hanteren operationele onderzoekers meestal heuristische en metaheuristische technieken zoals het genetisch algoritme, simulated annealing, tabu search en scatter search omdat deze wel in staat zijn grotere problemen op te lossen. Heuristische technieken doorzoeken de oplossingsruimte vanuit een bepaalde begintoestand op een intelligente manier waardoor de optimale of benaderend optimale oplossing wordt gevonden op korte tijd. Daarenboven zijn ze heel flexibel te modelleren en kunnen ze alle vormen van verfijning aan. Ze vormen dus een werkbaar alternatief voor exacte technieken met dat risico dat ze geen garantie bieden voor het vinden van de optimale oplossing. Om deze redenen en in het kader van de case worden enkel heuristische technieken besproken. Voor exacte methoden zoals branch-and-bound worden verwezen naar de literatuur. Een tweede kenmerk van crew scheduling is dat het een statisch probleem betreft. (El Moudani et al., 2001). Op het moment dat de werkroosters worden opgesteld, worden alle

52



hierboven beschreven inputcomponenten als vaste gegevens beschouwd. Nadat de werkroosters zijn opgesteld en aan de crew bezorgd treden er nog tal van wijzigingen op. De werkroosters worden echter niet automatisch gewijzigd tot nieuwe optimale werkroosters. De personeelsleden hebben hun werkrooster namelijk al gekregen. De opgetreden wijzigingen die in de luchtvaartsector frequent voorkomen moeten natuurlijk wel worden aangepakt. Dit wordt door het operationeel crew scheduling probleem gedaan en niet door het (gewone) crew scheduling probleem. Bijgevolg is crew scheduling een statisch en geen dynamisch probleem. Een derde kenmerk betreft het type probleem. Crew scheduling wordt door operationele onderzoekers vaak behandeld als een set partitioning probleem. Toegepast op crew pairing kan men het probleem formuleren als volgt. Gegeven een set legale pairings zoekt men de beste collectie pairings zodat alle vluchten exact eenmaal gedekt zijn door een pairing. Het set partitioning probleem ziet er dan uit als volgt (Hoffman and Padberg, 1993):

Min.

Onder voorwaarde:

,

0, 1 1, … , ,

Het probleem streeft dus zoals gezegd naar de best mogelijke collectie pairings. Het resultaat wordt in matrix gepresenteerd. Elke rij van matrix stelt een flight leg voor, elke

kolom een pairing. De werking van het set partitioning probleem zou duidelijk moeten zijn na analyse van de onderstaande symbool verklaringen.

: de vector die 1’en bezit

: het aantal beschouwde pairings : het aantal flight legs

53



: de matrix

: kost geassocieerd met de j-de pairing

1 als pairing j geselecteerd is' 0 anders

Matrix wordt kolom per kolom geconstrueerd, waarbij ()

1 als *light leg i gedekt is door pairing j' 0 anders

Beschouw onderstaand matrix ter illustratie. Flight leg 1 wordt gedekt door pairing 1, flight

leg 2 door pairing 3 en flight leg 3 ook door pairing 1. 1 0 0 .0 0 1 / 1 0 0

Het resultaat dat door matrix wordt gegeven bestaat uit één kolom en rijen. In elke rij staat een 1 of een 0. Een 1 als de pairing geselecteerd is, een 0 als de pairing niet geselecteerd is. Aan de hand van voorbeeldmatrix zou matrix moeten bestaan uit 1, 0, 1.

Vermenigvuldigd men beide matrices dan bekomt men inderdaad de vector bestaande uit 1-en.

1 0 .0 0 1 0

0 1 1 1/ .0/ .1/ 0 1 1

6.2 Genetisch algoritme Een genetisch algoritme is een vaak gehanteerde heuristische techniek voor het oplossen van het crew scheduling probleem. De eerste ontwikkelingen door John Holland namen plaats 40 jaar geleden. Het algoritme is een zoektechniek uit de kunstmatige intelligentie en het vormt een klasse binnen de evolutionaire algoritmen. Het achterliggend idee van een genetisch algoritme is een intelligente exploitatie van een willekeurige zoekbewerking (Reeves , 1993).

54



De gebruikte terminologie is sterk beïnvloed door de evolutietheorie. Een parameter die moet worden geoptimaliseerd noemt men een genoom. De waarde van een genoom wordt een allele genoemd. De som van alle genomen vormt een chromosoom en die vormt de abstracte representatie van een oplossing. De oplossing zelf wordt een individu genoemd en alle individuen samen vormen een populatie. Het algoritme zal bij iedere nieuwe iteratie de populatie vernieuwen, waarbij de populatie van een bepaalde iteratie een generatie wordt genoemd (Reeves , 1993). De werking van een genetisch algoritme bestaat uit een aantal stappen. Figuur 6.1 presenteert een flowchart van een genetisch algoritme. start

Initialisatie

willekeurig, intelligent

Selectie

fitness waarde

Reproductie

nee

crossover, mutatie

ja ° Oplossing

Stop ? einde Figuur 6.1. Flowchart van een genetisch algoritme

Initieel worden, meestal willekeurig, individuele oplossingen gegenereerd. Occasioneel kunnen de initiële oplossingen op een intelligente manier worden toegevoegd. In crew scheduling wordt dit laatste frequent toegepast omdat het sneller tot meer optimale oplossingen leidt. Voor elke oplossing in de populatie wordt een fitheid waarde bepaald. Deze waarde geeft aan hoe goed de oplossing is in vergelijking met de andere oplossingen en is gerelateerd met de waarde van de doelfunctie (Reeves , 1993).

55



De tweede stap vormt de selectie. Zoals in de evolutietheorie is de idee dat enkel de betere oplossingen overblijven. De grootte van de populatie wordt namelijk verkleint op basis van de fitheid waarde. Meerdere methoden zijn voorhanden. Ten eerste, kunnen simpelweg de beste 25 of 50 % overblijven. Ten tweede, kunnen twee oplossingen met elkaar worden vergeleken, waarbij de beste oplossing overblijft. Een derde methode bestaat erin om naast de selectie van de betere oplossingen toch een klein gedeelte van minder fitte oplossingen te behouden zodat de diversiteit van de populatie wordt behouden. Hierdoor wordt vroegtijdige convergentie naar zwakke oplossingen vermeden (Reeves, 1993). In een derde stap dienen de oplossingen zich te reproduceren totdat de initiële populatiegrootte hersteld wordt. De reproductie wordt meestal bewerkstelligd door middel van crossover en mutatie. Bij crossover ontstaan door het onderling uitwisselen van bepaalde stukken van twee oplossingen (ouders), twee nieuwe oplossingen (kinderen). In operationeel onderzoek wordt een oplossing meestal gerepresenteerd door een serie van bits. Onderstaand voorbeeld (links) illustreert een crossover operatie vanaf het crossover punt 3. Crossover Ouders:

01 0

1 1 1

Mutatie 0 0

11

00 0

1 0 1

0 1

11

Kinderen: 01 0

1 0 1

0 1

11

00 0

1 1 1

0 0

01 0 00

0 1 0

01 0

11

1 1 1

00 0

0 0

1 0 1

1 0 1

1 1 1

11

11

0 0 11

0 1 11

Bij mutatie worden bij een aantal oplossingen in de populatie één of meerdere getallen gemuteerd. Dit impliceert het programmeren van een random variabele voor elke bit dat bepaalt of de bit al dan niet moet worden gemuteerd. Bovenstaand voorbeeld (rechts) illustreert. Het doel van mutatie is behoud van diversiteit van de populatie, waardoor lokale

56



minima worden vermeden. Het resultaat van deze reproductie is het behoud van populatiegrootte met een nieuwe generatie oplossingen verschillend van de vorige generatie (Reeves , 1993). Selectie en reproductie worden herhaald totdat een stopconditie wordt bereikt. De stopconditie kan bijvoorbeeld bereikt worden na een vooraf vastgesteld aantal generaties, na een bepaalde toegewezen computertijd, na het langdurig gelijk blijven van de beste fitheid waarde en/of na het convergeren naar een bepaalde waarde (Reeves , 1993). Het voordeel van genetische algoritmen is dat ze snel tot goede oplossingen kunnen komen, zelfs voor moeilijke oplossingsruimten. Doch, vinden ze niet gegarandeerd de optimale oplossing, omdat ze de neiging hebben om te convergeren naar lokale in plaats van globale optima. Dit euvel kan gedeeltelijk verholpen worden door diversificatie in te bouwen, zoals hierboven beschreven. Een tweede nadeel ontstaat wanneer een genetisch algoritme op een dynamische dataset wordt toegepast. Crew scheduling is echter een statisch probleem met een uitgebreide oplossingsruimte. Een genetisch algoritme is dus een krachtig wapen om crew scheduling aan te pakken (Reeves , 1993).

6.3 Simulated annealing Simulated annealing is een probabilistisch heuristisch optimalisatietechniek die gebruikt wordt om een benadering van het globaal optimum van een bepaalde functie te vinden in een grote zoekruimte. Het gebruik van simulated annealing als techniek voor optimalisatie dateert van de tachtiger jaren. De naam en inspiratie komen van het uitgloeien (‘annealing’) binnen de metaalbewerking (Reeves, 1993). Het simulated annealing concept kan gezien worden als een verbetering van de lokale zoekalgoritmen, één van de bekendste heuristische algoritmen (Reeves, 1993). De werking van een lokaal zoekalgoritme kan het best geïllustreerd worden aan de hand van onderstaande figuur 7.2 en aan de hand van een flowchart van een lokaal zoekalgoritme voor het oplossen van een minimalisatie probleem dat in figuur 7.3 wordt gerepresenteerd. De uiteenzetting die hieronder volgt geldt voor een minimalisatie probleem. Voor een

57



maximalisatie probleem geldt een analoge redenering. De theoretische uiteenzetting wordt, waar nodig, bijgestaan door een concrete toepassing van het lokale zoekalgoritme op het crew rostering probleem dat streeft naar minimale kosten. Uiteraard geldt ook een analoge redenering voor een crew rostering probleem dat streeft naar maximale levenskwaliteit.

Figuur 6.2. Werking van een lokaal zoekalgoritme

Lokale zoekalgoritmen beginnen bij een gegeven toestand i, element van de

oplossingsruimte S, en bekijken dan de buurtoestanden van i (Reeves, 1993). Toegepast op

crew rostering zou de oplossingsruimte S alle mogelijke legale roostercombinaties

weergeven. De toestand i zou dan één bepaalde legale roostercombinatie voorstellen.

De buurtoestanden van i zijn elementen van de oplossingsruimte die “dicht in de buurt”

liggen van i en worden genoteerd door symbool j (Reeves, 1993). Een voorbeeld van “dicht in de buurt” zou kunnen gevonden worden door twee pairings uit twee roosters om te

wisselen, waardoor een nieuwe legale roostercombinatie wordt gecreëerd. De buurtoestanden j zijn dus ook toestanden van de oplossingsruimte en stellen dus ook een bepaalde legale roostercombinatie voor.

Daarna kiest het lokaale zoekalgoritme de beste buurtoestand op basis van een waarde die elke toestand krijgt. Bij crew rostering is de waarde afhankelijk van de kost. De waarde

58



van toestand i wordt door 3456 voorgesteld en voor toestand j door 346 waarbij 3 de

functie voorstelt die de waarde van een toestand berekent. Voor crew rostering berekent 3

dus de kost van een bepaalde roostercombinatie. De beste buurtoestand is dan de toestand met de laagste kost. Als de gekozen buurtoestand een gelijke of betere waardering heeft dan

toestand i wordt deze buurtoestand de volgende toestand i en loopt het algoritme verder

(Reeves, 1993).

Figuur 6.3. Flowchart Simulated annealing

Het lokaal zoekalgoritme herhaalt deze procedure totdat er geen betere buurtoestanden meer zijn. Het lokaal optimum en mogelijk ook het globaal optimum is dan gevonden. Hiermee wordt evenwel ook het grote nadeel van lokale zoekalgoritmen aangehaald. De bekomen oplossing is namelijk volledig afhankelijk van de begintoestand (Reeves, 1993). Het is duidelijk dat een betrouwbare heuristische techniek minder afhankelijk zou moeten zijn van de begintoestand. Uit figuur 6.2 is het duidelijk dat bepaalde opwaartse bewegingen moet worden betrokken in het zoekalgoritme om verder te kunnen kijken dan alleen het lokaal dal, maar dat een convergentie naar een minimum het finaal doel moet blijven. In simulated annealing worden dergelijke opwaartse bewegingen toegelaten, maar hun frequentie wordt gecontroleerd door een waarschijnlijkheidfunctie die wijzigt naarmate het algoritme vordert (Reeves, 1993).

59



Het simulated annealing algoritme werkt zoals het hierboven beschreven lokaal zoekalgoritme met dat verschil dat de keuze van de beste buurtoestand afhankelijk is van volgend acceptatieregel, geldig voor minimalisatie problemen. 78 4accepteer4j66 9

3456 : 346

3456 ; 346

e

1

<4=6><4?6 @

'

Als de buurtoestand j een zelfde of een betere waardering heeft, i.e., een gelijke of lagere

kost, dan wordt deze geaccepteerd. Als daarentegen de buurtoestand een slechtere

waardering heeft, i.e., een hogere kost, dan wordt deze geaccepteerd met een bepaalde waarschijnlijkheid zoals te zien in bovenstaand acceptatieregel. Het symbool c representeert

een controleparameter. Initieel bezit c een grote waarde, waardoor de waarde van de

waarschijnlijkheidfunctie 1 benaderd. Echter, na elke iteratie wordt de waarde van c

verlaagd. Dat wil zeggen dat na elke iteratie de waarschijnlijkheid op acceptatie van een slechtere buurtoestand, i.e., een opwaartse beweging, vermindert, waardoor meer lokaal zal worden gezocht naar het optimum. Naast de controleparameter wordt de waarschijnlijkheid ook bepaald door het, altijd negatieve, verschil 3456 A 346. Hoe groter dat verschil is, hoe

slechter de waardering van j of hoe hoger de kost van j, en hoe kleiner de kans dat de

slechtere buurtoestand j wordt geaccepteerd. Het simulated annealing algoritme laat dus opwaartse bewegingen toe, maar wel met dalende frequentie naarmate het algoritme vordert (Reeves, 1993). Simulated annealing omzeilt dus, door de incorporatie van opwaartse bewegingen, het grote nadeel van lokale zoekalgoritmen. Echter, een globaal optimum kan niet worden gegarandeerd. Wel heeft deze techniek bewezen goede oplossingen te verschaffen, zelfs voor heel complexe problemen. De techniek is dus geschikt voor crew rostering, maar wordt er niet heel vaak voor gehanteerd. De reden hiervoor ligt ten eerste in de lange benodigde computertijd en ten tweede in het feit dat de opwaartse bewegingen slechts gecontroleerd worden op een willekeurige manier in plaats van op meer intelligente wijze. De volgende techniek die wordt besproken, tabu search, controleert de opwaartse beweging wel op een intelligente manier.

60



6.4 Tabu search Tabu search is een recent metaheuristische optimalisatietechniek ontwikkeld door Fred Glover. Het kernidee achter tabu search is de introductie van flexibele geheugen structuren samen met strategische restricties en aspiratie niveaus als middelen voor de exploitatie van zoekruimten. Tabu search is gebaseerd op de lokale zoekalgoritmen met dat verschil dat ook slechtere oplossingen, i.e., opwaartse bewegingen, op intelligente wijze kunnen worden gekozen. Daarenboven worden bepaalde eerder bezochte oplossingen taboe, i.e., niet toegelaten, verklaart (Glover et al , 1995; Reeves, 1993). De meerderheid van de applicaties worden pas aangetroffen sinds 1989. Desondanks heeft tabu search al vele successen gekend in een verscheidenheid aan problemen. Vooral scheduling problemen zijn een rijke toepassingsbron voor moderne heuristische technieken en in het bijzonder voor tabu search. Voor kleinere probleemstellingen genereert tabu search oplossingen die optimaal zijn of die de optimale oplossing met een fractie van een percent benadert, terwijl veel minder inspanningen vereist zijn. Voor grotere probleemstellingen, zoals het airline crew scheduling probleem, behaalt tabu search oplossingen die vaak de beste oplossingen, eerder gevonden door andere benaderingen, overtreft. Voor moeilijke applicaties in onder andere scheduling heeft tabu search een nieuw record gevestigd in de literatuur voor best gekende oplossing (Glover et al., 1995; Reeves, 1993). In wat volgt wordt eerst de algemene werking van tabu search beschreven. Daarna wordt de werking geïllustreerd aan de hand van een uitgewerkt voorbeeld gebaseerd op Glover et al. (1995) en Reeves (1993).

6.4.1 Algemene werking van het tabu serach algoritme De algemene werking van tabu search is als volgt. Eerst moet een initiële oplossing worden gekozen. Deze kan willekeurig worden gegenereerd of specifiek gekozen door bijvoorbeeld de best verkregen oplossing van simulated annealing of een genetisch

61



algoritme. Dan moet bepaald worden hoe goed die oplossing is, met andere woorden zijn waarde moet worden berekend (Glover et al., 1995; Reeves, 1993). Na de keuze en de waardering van de initiële oplossing worden alle naburige oplossingen bepaald, samen met de berekening van hun waardering. Op dezelfde manier als simulated annealing wordt de beste naburige oplossing geselecteerd, met dat verschil dat de geselecteerde oplossing niet taboe mag zijn. Een belangrijke uitzonderlijk op de tabu restricties is evenwel mogelijk. Als een taboe verklaarde oplossing voldoende aantrekkelijk is, bijvoorbeeld als de oplossing zou leiden tot een betere oplossing dan tot nog toe is bereikt, dan mag de tabu regel worden overschreden. Een dergelijke conditie wordt een aspiration criteria genoemd (Glover et al , 1995; Reeves, 1993). De vorige oplossing wordt dan vervangen door de uiteindelijk geselecteerde oplossing en het algoritme herbegint een nieuwe iteratie. Deze werkwijze gaat voort totdat een bepaalde stopconditie vervult is. Zo kan het algoritme stoppen nadat alle naburige oplossingen taboe verklaart zijn, na een vast aantal iteraties, een toegewezen computertijd en/of een oplossing die al lang niet meer verbeterd is geweest (Glover et al., 1995; Reeves, 1993).

6.4.2 Illustratief voorbeeld De manier waarop oplossingen taboe worden verklaard, samen met een minder theoretische uiteenzetting van het tabu search algoritme, wordt gepresenteerd in volgend voorbeeld. Zoals hierboven vermeld, is dit illustratief voorbeeld gebaseerd op Glover et al. (1995) en Reeves (1993). Beschouw het probleem voor het opstellen van één werkrooster bestaande uit zeven pairings. Het probleem bestaat uit het ordenen van de zeven pairings zodat de crew satisfactie van het personeelslid in kwestie wordt gemaximaliseerd. Ook willen we de optimale of benaderd optimale oplossing vinden door alleen een klein deel van de 5040, i.e., 7!, mogelijke permutaties te doorzoeken.

62



Eerst moet een initiële oplossing op intelligente wijze worden geconstrueerd, door bijvoorbeeld de oplossing van een genetisch algoritme te gebruiken. De initiële oplossing wordt in figuur 6.4 getoond.

Figuur 6.4. Voorbeeld Tabu search: initiële oplossing

Verder veronderstellen we een paarsgewijze uitwisseling (of swap) als methode om naburige oplossingen te bepalen. Figuur 6.4 illustreert. Bij elke iteratie bestaan aldus 21, namelijk

B4BC6 D

, naburige oplossingen. Het vorderen van een oplossing naar een volgende

oplossing wordt een move genoemd. Bij elke swap wordt een move waarde geassocieerd die de verandering in de doelfunctie representeert. Meestal zijn de move waarden een fundamentele basis voor het bepalen van de kwaliteit van een move. Ook in dit voorbeeld zal een bepaalde move worden geselecteerd op basis van zijn move waarde. De kracht van tabu search ligt in zijn intelligente manier met het omspringen van geheugen. In het bijzonder wordt een subset van moves geclassificeerd als verboden of taboe. De classificatie is afhankelijk van de historiek van het zoekalgoritme en in het bijzonder van de recentheid en/of de frequentie van move componenten, attributen genaamd, die geparticipeerd hebben in het genereren van vorige oplossingen. Een attribuut van een move is bijvoorbeeld de swap van twee pairings. In dit voorbeeld classificeren we de meest recent geselecteerde swap als taboe voor een duur (of tenure) van drie iteraties. De reden hiervoor is het vermijden dat het zoekalgoritme juist ondernomen swaps zou herhalen, waardoor de effecten van de vorige move worden tenietgedaan. Andere tabu restricties, zoals een afzonderlijke pairing in plaats van een pairing paar, zijn uiteraard ook mogelijk, maar worden in dit voorbeeld niet beschouwd. Tenslotte is de hierboven beschreven aspiration conditie ook geldig op dit voorbeeld. De datastructuur als deze in figuur 6.5 wordt gebruikt.

63


Iteratie 0

Tabu structuur

Huidige oplossing 2

5

7


3

4

2 6

1

3

4

5

6

Top 5 kandidaten 7

1 2 3

Satisfactie waarde = 10

4 Overblijvend tabu tenure voor pairing paar (2,5)

5

Swap

waarde

5

4

6

7

4

4

3

6

2

2

3

0

4

1

-1

6

Figuur 6.5. Voorbeeld Tabu search: iteratie 0

In de tabu structuur wordt bijgehouden welke swaps taboe verklaard zijn en voor welke tabu tenure. In deze initiële oplossing met satisfactie waarde 10 is de tabu structuur leeg, i.e., geen enkele move is taboe. Nadat de kandidaat swap moves geëvalueerd zijn, wordt een top 5 samen met hun move waarde gepresenteerd rechts op de figuur. Zoals aangegeven met een pijltje in bovenstaande figuur 6.5 worden pairings 5 en 4 van plaats verwisseld. De gevolgen van die swap is een stijging van de satisfactie waarde met 6 eenheden tot een totaal van 16 eenheden. De nieuwe huidige oplossing wordt in figuur 6.6 getoond. Iteratie 1

Tabu structuur

Huidige oplossing 2

4

7

3

5

2 6

1

3

4

5

6

1 2

Satisfactie waarde = 16

3 4 3 5

Top 5 kandidaten 7

Swap

waarde

3

1

2

2

3

1

3

6

-1

7

1

-2

6

1

-4

6


De tabu structuur is niet meer leeg. Het pairing paar (5,4) is namelijk voor een tenure van drie iteraties taboe verklaard. In deze iteratie is de move die de grootste verbetering oplevert de swap (3,1). Ze doet de satisfactie waarde met twee eenheden stijgen. Figuur 6.7 toont de nieuwe huidige oplossing,i.e., iteratie twee.

64




De satisfactie waarde bedraagt nu 18 eenheden en de tabu structuur bezit een extra pairing paar die taboe verklaard is. Wel moet worden opgemerkt dat de tenure van paar (5,4) gedaald is tot twee, aangevend dat het paar voor slechts twee iteraties taboe is. Geen enkel van de kandidaten heeft een positieve move waarde. Daarom moet een niet verbeterende move worden gedaan. De aantrekkelijkste niet verbeterende move, namelijk swap (1,3), is niet toegelaten. Bijgevolg wordt de move met swap (2,4) geselecteerd. Figuur 6.8 presenteert de nieuwe oplossing.


De satisfactiewaarde is gedaald tot 14 eenheden en de tabu structuur is weer een pairing paar rijker geworden. Onder de kandidaten blijkt de move met swap (4,5) de grootste verbetering te genereren. Helaas is deze move niet toegelaten omwille van tabu restricties. Echter, het aspiration criteria is geldig omdat een superieure satisfactie waarde van 20 eenheden kan worden behaald. We hanteren deze regel en verwisselen pairings 4 en

65



5 van plaats. De bekomen nieuwe oplossing wordt getoond in figuur 6.9. Het algoritme gaat door totdat een stopconditie wordt vervuld.


Merk op dat slechts drie mogelijke swaps tegelijk taboe verklaard kunnen worden. De reden ligt in de gekozen tabu restrictie en tabu tenure van drie iteraties. In andere situaties kan het wenselijk zijn om meer swaps taboe te verklaren, door bijvoorbeeld de tabu tenure de verhogen of door een pairing in plaats van een pairing paar taboe te verklaren. In deze laatste situatie zullen, rekening houdend met een tabu tenure van drie, na twee iteraties slechts 6 van de mogelijk 21 swaps worden toegelaten, namelijk

6.4.3

E4EC6 D

.

Frequentie gebaseerd geheugen voor diversificatie en intensivering

Het tabu search algoritme kan worden uitgebreid door het inbouwen van een aantal complementaire tabu geheugen structuren. Een eerste klasse uitbreidingen worden de diversificatie benaderingen genoemd en betreft het diversifiëren van de zoekopdracht. Een opportuniteit om de zoekopdracht meer te drijven naar andere regionen betreft de complementariteit tussen recentheid en frequentie. Het hierboven beschreven voorbeeld is een typisch voorbeeld van geheugen gebaseerd op recentheid. Namelijk, de recentste drie swaps werden taboe verklaart. Door de parameter frequentie te incorporeren wordt een extra component in het geheugen ingebouwd die opereert over een langere horizon. Toegepast op bovenstaand voorbeeld kan de tabu structuur ook de frequentie van de geselecteerde swaps tellen. Een swap met een hoge frequentie wordt bestraft. Bijgevolg zal

66



ook zijn move waarde dalen, waardoor de move in kwestie minder kans maakt om geselecteerd te worden. Het geheugen gebaseerd op frequentie is dus vooral nuttig voor lange termijn applicaties omdat ze de zoekopdracht drijft naar andere regionen (Glover et al., 1995; Reeves, 1993). Een tweede klasse uitbreidingen betreft de intensivering benaderingen. De idee achter deze benaderingen is dat oplossingen met een hoge frequentie goede oplossingen zijn. Deze lijn doortrekkend, kan een set van elite oplossingen, bestaande uit hoogkwalitatieve lokale optima, worden gevormd. De strategie bestaat dan uit het exploiteren van informatie van deze elite oplossingen (Glover et al., 1995; Reeves, 1993). De

wisselwerking

tussen

intensivering

en

diversificatie

strategieën

vormen

fundamentele hoekstenen voor lange termijn geheugen in tabu search. Ze worden daarom frequent aangewend door operationele onderzoekers in hun zoektocht naar continue verbetering en efficiëntie (Glover et al., 1995).

6.5 Hybride combinaties voor optimalisatie Zoals eerder vermeld, ligt de kracht van tabu search in zijn exploitatie van geheugen. Zowel simulated annealing als genetische algoritmen kunnen voordeel halen uit het inbouwen van een geheugen functie gebaseerd op de principes van tabu search. Op deze manier is het mogelijk om hybride combinaties te creëren die betere oplossingen kunnen genereren. Een eerst hybride kan gevormd worden door simulated annealing te combineren met tabu search. Deze technieken hebben een aantal verschilpunten, waardoor een hybride combinatie betere oplossingen kan genereren. Ten eerste, tabu search selecteert op intelligente wijze een move, in tegenstelling tot simulated annealing die een move op basis van een waarschijnlijkheidsfunctie, i.e. op random wijze, selecteert. Ten tweede, de gehanteerde parameters zoals de tabu tenure kunnen in tabu search variëren in meerdere richtingen en zijn dus niet monotoon. Bij simulated annealing verandert de controleparameter in de waarschijnlijkheidsfunctie wel op monotone wijze (Reeves, 1993).

67



Vooral dat laatste is een belangrijke bron geweest voor een hybride combinatie van simulated annealing en tabu search die toelaat de controleparameter strategisch te manipuleren doormiddel van het exploiteren van geheugen. De literatuur bewijst dat deze hybride betere resultaten oplevert ten opzichte van standaard simulated annealing benaderingen (Reeves, 1993). Een tweede mogelijke hybride ontstaat uit een huwelijk tussen genetische algoritmen en tabu search. Het betreft een krachtige hybride die soms ook wel scatter search wordt genoemd. In het bijzonder wordt geheugen geïntroduceerd in genetische algoritmen voor het traceren van de historiek van genen en allelen over de sub populaties heen. Hierdoor wordt een natuurlijke methode gecreëerd voor een hybride met tabu search. De principes en de werking van een dergelijke scatter search worden uitvoerig behandeld in volgend hoofdstuk. Het algoritme van Maenhout and Vanhoucke (2007) maakt immers gebruik van deze krachtige hybride. Het is dan ook opportuun om de werking van een scatter search algoritme concreter te illustreren aan de hand van het algoritme. De beschrijving van de planningsdomeinen met in het bijzonder de personeelsplanning en de beschrijving van de heuristische optimalisatietechnieken wordt hier afgesloten. Het betrof een uitgebreide studie, maar in mijn ogen noodzakelijk met betrekking tot de case in volgend deel. Het feit dat de luchtvaartsector zo boeiend is heeft hier natuurlijk ook een belangrijk aandeel in. Het doel was een beeld te schetsen van de luchtvaartsector in zijn geheel van complexe plannings- en optimalisatieproblemen, maar ook om voldoende achtergrondinformatie te verschaffen met betrekking tot de case.

68



7 Case SN Brussels Airlines Aan de hand van de uitgebreide beschrijving over crew rostering en de metaheuristische optimalisatietechnieken, die van toepassing zijn voor het ontwikkelen van een oplossingsmodel voor het crew rostering probleem, moet het mogelijk zijn om een concrete case hieromtrent op te stellen. De keuze om de vergaarde kennis om te zetten in een case over SN Brussels Airlines lag voor de hand. België is namelijk niet rijk aan grote luchtvaartmaatschappij en een case over SN Brussels Airlines brengt toch een zekere graad van prestige met zich mee. Daarenboven werd de overtuiging dat een case rond SN Brussels Airlines mogelijk moest zijn, bevestigd na een eerste gesprek met de heer Dobbelstein, Crew Scheduling Manager van SN Brussels Airlines. De man was onmiddellijk te vinden voor het idee en bezorgde me de nodige informatie. De doelstellingen die de case voor ogen heeft zijn ambitieus. Ten eerste wordt gestreefd naar het opstellen van een praktische case, met de nadruk op case. Het is de bedoeling om SN Brussels Airlines kort voor te stellen en hun oplossingsaanpak voor crew scheduling en in het bijzonder crew rostering te schetsen. Daarna wordt de probleemstelling gepresenteerd samen met de gehanteerde oplossingsmethodiek. Het doel van de case is aantonen dat crew rostering ook op automatische wijze kan gebeuren, met eventueel betere resultaten tot gevolg. De werkroosters bekomen met het algoritme van Maenhout and Vanhoucke (2007) zullen daarom worden vergeleken met deze van SN Brussels Airlines. De indeling van de case bewandelt het volgende pad. In deel 7.1, wordt SN Brussels Airlines voorgesteld. Eerst wordt een kort overzicht gepresenteerd aan de hand van enkele cijfers. Daarna wordt dieper ingegaan op hun scheduling departement en in het bijzonder op hun oplossingsaanpak met betrekking tot het opstellen van de individuele werkroosters. In deel 7.2, worden probleemstelling en oplossingsmethodiek benadrukt. Het scatter search algoritme van Maenhout and Vanhoucke wordt uiteengezet in deel 7.3. De strategie van datacollectie en databewerking worden beschreven in deel 7.4. De verwerking van de gegevens tot maandelijkse werkroosters wordt bekomen met behulp van het algoritme. In deel 7.5, worden de ingestelde strafkosten en parameters specifiek voor de case besproken.

69



In deel 7.6, wordt de bekomen output onderworpen aan een vergelijkende studie en wordt een overzicht van de beperkingen aangeboden. Tenslotte, worden in deel 7.7 conclusies getrokken en instructies voor toekomstig onderzoek gegeven.

7.1 De maatschappij SN Brussels Airlines 7.1.1 Kort overzicht Brussels Airlines is geboren op 7 november 2006 uit een fusie tussen SN Brussels Airlines en Virgin Express. Tot vorige maand functioneerden SN Brussels Airlines en Virgin Express als aparte entiteiten. Data over Brussels Airlines was dan ook nog niet voorhanden en om die reden is besloten om de case te richten op gegevens van SN Brussels Airlines eerder dan op de fusiemaatschappij. SN Brussels Airlines mag dan geen mondiale luchtvaartmaatschappij zijn, toch vertegenwoordigde de maatschappij een omzet van 656 miljoen euro en telde het ongeveer 2100 personeelsleden in 2004. Hun vloot bestond uit 38 vliegtuigen, waarmee ze meer dan 50 bestemmingen aanbood.

7.1.2 Het crew scheduling departement De case behandelt de crew scheduling en in het bijzonder crew rostering bij SN Brussels Airlines. Zoals hierboven uiteengezet, wordt dit probleem meestal opgesplitst naar functie en vliegtuigtype. Ook bij SN Brussels Airlines volgen ze deze strategie. In het bijzonder, wordt in deze case het crew rostering probleem voor de 142 captains gekwalificeerd voor de vliegtuigfamilie AVRO beschouwd. Het doel is maandroosters opstellen voor de maand juni 2006. In onderstaande tabel 7.1 wordt cijfermateriaal gepresenteerd betreffende het specifieke rostering probleem (gesprek met de heer Dobbelstein F., 12 maart 2007, Zaventem). De cijfers bevestigen dat de case een vrij uitgebreid optimalisatieprobleem behandelt die heel representatief is.

70


Tabel 7.1.


Sub rostering probleem Aantal

Maandcijfers captains - AVRO Captains

142

Pairings

1.218

Reserves

73

Vooraf toegewezen activiteiten

265

Verloven

164

Vluchten/dag

150

Vliegtuigen

32

- AVRO RJ-85

14

- AVRO RJ-100

12

- BAE 146

6

Crew scheduling wordt bij SN Brussels Airlines gedaan met behulp van het systeem Blue One, oorspronkelijk ontwikkeld door een piloot. Dit systeem houdt rekening met alle regels en wetgevingen die moeten worden gerespecteerd. Tot op heden is Blue One uitgebreid met een pairing generator aangekocht bij Ortec, een grote speler op het gebied van consultancy en ontwikkeling van geavanceerde systemen voor onder andere personeelsplanning. Crew pairing gebeurt dus op automatische wijze (gesprek met de heer Dobbelstein F., 12 maart 2007, Zaventem). De strategie die SN Brussels Airlines volgt voor het opstellen van de werkroosters is de volgende. Drie planners stellen met behulp van Blue One een aantal weken op voorhand de maandroosters op. In het bijzonder moeten de planners alle pairings en andere activiteiten toewijzen aan de 142 captains door middel van een sleepfunctie in het systeem. Zoals gezegd, houdt het systeem rekening met alle beperkingen. De sleepfunctie wordt daarom ook beperkt zodat aan alle regels wordt voldaan. Een rostering generator gebruiken ze dus niet, terwijl de cijfers in tabel 7.1 aantonen dat miljoenen combinaties mogelijk zijn. De reden waarom de maatschappij de werkroosters manueel opstelt, ligt in hun streven naar een gelijke verdeling van de werkdruk tussen de roosters. Met andere woorden, SN Brussels Airlines hanteert het personalized rostering concept. De twee hoofddoelstellingen die ze hierbij nastreeft zijn, in dalend belang, gelijkverdeelde werkdruk en minimale kosten.

71



Daarnaast poogt ze robuustheid in te bouwen en rekening te houden met individuele preferenties (gesprek met de heer Dobbelstein F., 12 maart 2007, Zaventem). Hun prioriteit ligt dus in het fair-and-equal share principe die op basis van de volgende vier factoren wordt nagestreefd; de blok uren of de flight time (FT), de service tijd of de duty time (DT), het aantal nightstops (NS) en de time away from base (TAFB), (gesprek met de heer Dobbelstein F., 12 maart 2007, Zaventem). Figuur 7.1 illustreert die criteria voor een vlucht heen en terug naar Sevilla. Met STD (STA) bedoeld met het standaard vertrekuur (aankomstuur). De tijdspanne tussen reporting time en STD enerzijds en closing time en STA

tim e Clo sin g

ST A

ST D

tim e Re po rtin g

tim e Clo sin g

ST A

ST D

Re po rtin gt im e

anderzijds worden allemaal gereglementeerd en staan in bijlage D.

Figuur 7.1. De vier factoren voor gelijk verdeelde werkdruk bij SN Brussels Airlines

Voor het behalen van minimale kosten moeten enkel de gepresteerde blok uren in rekening worden genomen. De captains worden uitbetaald op basis van de stapsgewijze lineaire functie, zoals hierboven beschreven. De concrete waarden alsook een illustratieve berekening staan in figuur 7.2. Op te merken valt dat de overuren om fiscale redenen naar een persoonlijke korf gaan, waarmee de captains zich materiaal zoals een gsm, een computer en dergelijke mee kunnen aanschaffen of waarmee ze zelfs een verzekering kunnen financieren (gesprek met de heer Dobbelstein F., 12 maart 2007, Zaventem).

72



Figuur 7.2. Loonbarema's bij SN Brussels Airlines

7.2 Probleemstelling en oplossingsmethodiek Zoals hierboven vermeld, streeft de case naar het aantonen dat er ook een andere manier bestaat dan het manueel opstellen van de werkroosters. In het bijzonder is het de bedoeling om automatische werkroosters te genereren specifiek voor SN Brussels Airlines en aan de hand van een vergelijkende studie beide methoden te evalueren. Voor het bereiken van de doelstelling wordt de volgende oplossingsmethodiek bewandeld. Eerst wordt een uiteenzetting van het algoritme van Maenhout and Vanhoucke (2007) gepresenteerd. Hun hybride scatter search is in staat hoogkwalitatieve persoonlijke werkroosters te genereren en vormt om die reden de steunpilaar van de case. Daarna wordt beschreven welke informatie nodig is en hoe deze informatie wordt herwerkt tot intelligente, bruikbare inputfiles voor het algoritme. Vervolgens wordt de gegenereerde output geëvalueerd. Tenslotte worden de economische implicaties van een automatische rooster generator berekend en worden conclusies getrokken.

73



7.3 Het hybride scatter search algoritme De automatische generatie van werkroosters wordt aan de hand van het algoritme ontwikkeld door Maenhout and Vanhoucke (2007) bewerkstelligd. In wat volgt worden eerst hun objectieven overlopen. Daarna wordt het probleem geformuleerd en vervolgens wordt de werking van het algoritme uiteengezet. Op te merken valt dat de werking geldig is voor het globale rostering probleem en niet enkel voor een bepaalde subcategorie piloten en vliegtuigen. Expliciet moet ook nog vermeld worden dat de uiteenzetting gebaseerd is op het werk van Maenhout and Vanhoucke (2007).

7.3.1 Objectieven De doelfunctie bestaat uit drie hoofdcomponenten. Als eerste objectief streeft het algoritme de minimalisatie na van open tijd, i.e., niet toegewezen activiteiten. Bovendien bestaat het objectief uit het maximaliseren van het aantal pairings bestaft door vast personeel. Als niet alle pairings adequaat kunnen worden bestaft door vast personeel worden ze eerst toegewezen aan crew die reserves of overuren werken. Als ook dan nog onderbemande pairings overblijven, zullen freelancers moeten worden gehuurd aan een vaste kost per vlieguur. Het tweede objectief streeft naar roosters met gelijkverdeelde werkdruk. Het implementeren van dit objectief gebeurt door een aantal representatieve factoren, die beperkt worden door regels en wetgeving, gelijk te verdelen over de roosters. In het bijzonder worden de afwijkingen van de gemiddelde of standaard waarde van die factoren bestraft. De factoren die SN Brussels Airlines hanteert zijn de hierboven vermelde service tijd, blok uren, aantal nightstops en TAFB. Als het gemiddeld aantal blok uren per maand bijvoorbeeld 60 bedraagt, zal een werkrooster die 70 blok uren bevat worden bestraft. Een werkrooster met meer dan 110 blok uren is volgens de regels van toepassing op SN Brussels Airlines, zelfs niet legaal. In deze context kunnen we de factoren ook beschouwen als middelen die worden geconsumeerd totdat de gemiddelde of standaard waarde wordt bereikt en hoogstens tot een bepaalde maximale waarde.

74



Als derde objectief tenslotte kunnen de personeelsleden hun individuele preferenties voor bepaalde roosterattributen uitdrukken. Ze kunnen niet alleen hun preferentie voor specifieke pairings en reserves uidrukken, ook kunnen ze dat doen voor meer algemene roosterattributen zoals de dag van de maand of het uur van de dag dat ze wel of niet willen werken.

7.3.2 Probleemformulering De formulering van het crew rostering probleem is gebaseerd op de Dantzig-Wolfe decompositie die het oorspronkelijk probleem opsplitst in een hoofd rostering probleem en een sub probleem dat mogelijke legale werkroosters genereert door alle horizontale regels te respecteren.

7.3.2.1 Hoofd rostering probleem Het hoofd rostering probleem wordt gemodelleerd als een set partitioning probleem en genereert op basis van de verkregen legale werkroosters exact één werkrooster voor elk vast personeelslid en maximaal één werkrooster voor elke freelancer en extra personeelslid zodat alle activiteiten bestaft zijn, de beperkingen tussen personeelsleden worden gerespecteerd en de doelfunctie wordt geoptimaliseerd. Eerst worden de notaties verduidelijkt dan wordt het hoofd rostering probleem geformuleerd.

Personeelsleden: F G / F I / FJ

set van vast/extra/freelance personeel die moeten worden gepland (index 5,

K

set van vaardigheidscategorieën (index L, L K), bijvoorbeeld captain.

5 F G / 5 F I /5 F J ).

J

G I M)N / M)N / M)N

1 als vast/extra/freelance personeelslid 5 vaardigheidscategorie L bezit, anders 0.

Individuele werkroosters:

75


J

O)G / O)I / O)


set van legale werkroosters voor vast/extra/freelance personeelslid 5, met respect voor alle sterke horizontale regels (index P, P O)G / P O)I / P J

O) ).

Activiteiten: Q

te plannen set van pairings (index , Q).

S

te plannen set van vooraf toegewezen activiteiten (index T, T S).

R

te plannen set van reserves (index , R).

te plannen set van activiteiten (index , met Q U R U S).

RN

vereist aantal personeelsleden van vaardigheidcategorie L voor activiteit

V

service tijd voor activiteit

Andere parameters: J

I G ()W / ()W / ()W

1 als werkrooster P voor vast/extra/freelance personeelslid 5 de activiteit bestaft, anders 0.

)WG

strafkost van werkrooster P voor vast personeelslid 5 voor de complete

NI

strafkost voor het huren van extra personeel met vaardigheidscategorie L

N

J

strafkost voor het huren van freelance personeel met vaardigheidscategorie

X N

strafkost voor het onderbemannen van activiteit in vaardigheidscategorie L.

periode.

voor de complete periode.

L per uur.

Y N

strafkost voor het overbemannen van activiteit in vaardigheidscategorie L.

Beslissingsvariabelen: J

Z)WG / Z)WI / Z)W

1 als vast/extra/freelance personeelslid 5 toegewezen is aan werkrooster P, anders 0.

76



Op te merken valt het subtiele verschil tussen extra personeel en freelance personeel. Extra personeel wordt aangeworven en vergoed voor de complete periode, terwijl freelancers op uurbasis worden vergoed. De formulering van het hoofd rostering probleem is de volgende.

416

Minimaliseer:

I I X Y )WG Z)WG ^ NI M)N Z)W ^ N M)N V ()W Z)W ^ N V bN ^ N cN

)] \ W[=\

)] ` W[=` N_

)] < W[< a N_

J J

=

J

J

a N_

a N_

Onder voorwaarde: G G I I M)N ()W Z)WG ^ M)N ()W Z)WI ^ M)N ()W Z)W ^ bN A cN RN

)] \ W[=\

)] ` W[=`

)] < W[<

J

J

J

=

d ; dL K

426

Z)WG 1

d5 F G

436

Z)WI i 1

d5 F I

446

Z)W i 1

J

d5 F J

456

Z)WG 0,1

d5 F G ; dP O)G

Z)W 0,1

d5 F J ; dP O)

POg5

POg5

POg5

Z)WI 0,1 J

d5 F I ; dP O)I

J

466

De doelfunctie (1) minimaliseert de strafkosten van het toewijzen van een legaal

werkrooster aan vast, extra en freelance personeel. De strafkost )WG van een werkrooster

toegewezen aan een vast personeelslid is gelijk aan de som van de preferenties voor

77



roosterattributen, zoals bepaalde activiteiten, rustperioden en werkperioden, en de strafkost als er wordt afgeweken van de gemiddelde of standaard waarden van de middelen

teneinde eerlijkheid tussen de werkroosters te waarborgen. De strafkost NI van een

werkrooster toegewezen aan een extra personeelslid is een vaste vergoeding die de

loonkost representeert voor het huren van dit type personeel voor de complete planningshorizon. Als er activiteiten moeten worden toegewezen aan freelancers is de strafkost gelijk aan de uurvergoeding N vermenigvuldigd met het aantal geplande werkuren J

voor de freelancer in kwestie. Voorts minimaliseert de doelfunctie de duur van onderbemande activiteiten en het aantal keer dat meer personeel wordt gepland dan nodig voor een activiteit. De beperking (2) vereist dat alle activiteiten correct worden bestaft voor elke

vaardigheidcategorie. Mathematische validiteit wordt gewaarborgd door twee slack variabelen bN en

cN die respectievelijk onder- en overbemanning representeren.

Beperking (3) vereist dat exact één werkrooster wordt toegewezen aan een vast personeelslid. Extra en freelance personeel mogen maximaal één werkrooster toegewezen krijgen. In beperking (4) en (5) wordt dit aangegeven. Tenslotte representeert de laatste beperking (6) de binaire beperking.

7.3.2.2 Sub probleem Het verkrijgen van een legaal werkrooster voor een personeelslid vormt het sub probleem. Deze kan gemodelleerd worden als een resource constrained shortest path (RCSP), i.e., een kortste pad probleem dat de middelen beperkt, waarbij, zoals hierboven vermeld, de middelen zorgen voor een gelijkverdeelde werkdruk tussen het vast personeel. Het RCSP is een minimum kostenprobleem waarbij een apart netwerk voor elk personeelslid moet worden samengesteld. Deze netwerken zijn niet cyclisch en bezitten een begin- en eindknoop die respectievelijk het begin en het einde van de maand voorstellen. Daarbij opteren de auteurs voor een activity-on-the-node voorstelling, i.e., de activiteiten (en de rustperioden) worden voorgesteld door de knopen, uitgezonderd de begin- en eindknoop. Alle activiteiten die compatibel zijn met de kwalificatie van het personeelslid worden voorgesteld in het netwerk. De pijlen in het netwerk stellen een link voor tussen twee

78



opeenvolgende activiteiten en/of rustperioden. Figuur 7.3 presenteert een voorbeeld probleem, en figuur 7.4 zet dit probleem om tot een netwerk voor één personeelslid.

Figuur 7.3. Voorbeeld probleem

Het netwerkstructuur incorporeert typisch de kwalificatie- en opeenvolgingregels, zoals verplichte rust na een activiteit, maar kan niet garanderen dat alle horizontale regels op roosterattributen worden gerespecteerd door de paden in het netwerk. Een aantal beperkingen kunnen namelijk niet rechtstreeks worden gemodelleerd door het netwerk en moeten daarom in rekening worden gebracht bij de berekening van het kortste pad. Dit geldt bijvoorbeeld voor de factoren omdat hun consumptie accumuleert naarmate het pad vordert, waardoor hun beperkingen eventueel worden bereikt op intermediaire knopen. Voor deze factoren worden eerlijkheidsmaatstaven vooropgesteld om een gelijkverdeelde werkdruk tussen de vaste personeelsleden te bekomen. Deze eerlijkheidsmaatstaven worden berekend als het minimum van twee waarden. De eerste waarde wordt bekomen door het gemiddelde te berekenen van de totale consumptie van alle activiteiten van een specifieke factor voor de vaste personeelsleden. De tweede waarde betreft de maximaal toelaatbare consumptie van een factorvoor personeelslid.

79



Figuur 7.4. Netwerkstructuur voor een personeelslid

7.3.3 Oplossingsmethodiek Evolutionaire algoritmen zijn, zoals hierboven beschreven, adaptieve heuristische zoekprocedures die de principes van natuurlijke selectie en the survival of the fittest nabootsen. In het bijzonder exploiteert een dergelijk type algoritme op intelligente wijze een willekeurige zoekopdracht binnen een gedefinieerd zoekgebied om het probleem onder studie op te lossen. Een scatter search algoritme is een op populatie gebaseerde metaheuristische optimalisatietechniek die oplossingen combineert tot betere oplossingen. Het betreft dus een strategische constructie in tegenstelling tot een willekeurige omdat het gebruik maakt van flexibel geheugen, het kernconcept van tabu search. Het grote voordeel dat de scatter search methodologie bezit is zijn flexibiliteit, in de zin dat de implementatie van alle elementen kan gebeuren op verschillende manieren en met variërende graad van complexiteit. Het werk van Marti et al. (2006) presenteert een overzicht van de mogelijkheden die met een scatter search algoritme kunnen worden bereikt. Figuur 7.5 stelt een flowchart van het scatter search algoritme voor. De stopconditie wordt vervuld nadat een maximaal aantal roosters geëvalueerd zijn.

80



strategie

start

Diversification Generation meth.

Initiele oplossingen

- willekeurig - heuristisch - willekeurig + heuristisch

°Refset1 °Refset2

Subset Generation meth. Refset1 × Refset1

- volledig random selectie - gecontroleerde random selectie - gecontroleerde selectie gebaseerd op fitheid en diversificatie

Refset2 × Refset2 Refset1 × Refset2

Solution Combination meth. ×

- ind. rooster gebaseerd lokaal zoekagoritme - periode gebaseerd lokaal zoekagoritme - activiteit gebaseerd lokaal zoekagoritme - vol. rooster gebaseerd lokaal zoekagoritme

Improvement meth.

- statisch - dynamisch

Reference set update

Nee

Stop ?

- één-punt crossover - beste tornooi selectie (sociale kwaliteit) - beste tornooi selectie (globale kwaliteit) - willekeurige tornooi select - totale path relinking - beperkte path relinking

Ja

° Oplossing einde

Figuur 7.5. Flowchart Scatter search algoritme

In wat volgt wordt aan de hand van de flowchart de implementatie van het scatter search algoritme voor het oplossen van het crew rostering probleem besproken. We beginnen met de wijze van datarepresentatie en de bepaling van de doelfunctie.

7.3.3.1 Datarepresentatie en doelfunctie De auteurs hanteren een datarepresentatie die de activiteiten toegewezen aan een personeelslid over de planningshorizon rechtstreeks weerspiegelen, doormiddel van een binaire codering. Een 1 geeft aan dat de overeenkomstige activiteit is toegewezen aan het

81



personeelslid in kwestie, een 0 als de activiteit niet is toegewezen. Figuur 7.6 voorziet een voorbeeld van de gehanteerde datastructuur. Pairings Activiteit

Extra personeel

Freelance personeel

Pre-assigned activities

1

...

|P|

1

...

|R|

1

...

|Q|

1 ...

0 ...

...

0 ...

1 ...

... ...

0 ...

0 ...

...

...

...

0 ...

|Cr|

1

...

0

0

...

1

1

...

0

1 ...

1 ...

...

0 ...

...

0 ...

0 ...

...

...

0 ...

...

...

1 ...

|Ce|

0

...

0

1

...

0

0

...

0

1 ...

0 ...

...

0 ...

...

0 ...

0 ...

...

...

0 ...

...

...

0 ...

|Cf|

1

...

0

0

...

0

0

...

0

Crewmember

Vaste crewmembers

Reserve duty

Figuur 7.6. Datarepresentatie

De activiteiten worden voorgesteld op de horizontale as van de matrix en de

verschillende types personeel op de verticale as. De eerste pairing en de S-de vooraf toegewezen activiteit worden in bovenstaand voorbeeld aan extra personeelslid 1

toegewezen. Deze chromosomen worden als input gebruikt voor de bepaling van de doelfunctie die de kwaliteit van de oplossingen, gecodeerd in elk chromosoom, evalueert. De kwaliteit van de roosters wordt bepaald aan de hand van een gewogen gemiddelde van de operationele kosten en de sociale kwaliteit (of levenskwaliteit) van de populatie elementen.

7.3.3.2 De “Diversification Generation” methode In deze eerste stap wordt een groot aantal diverse initiële oplossingen gegenereerd omdat bewezen is dat bruikbare informatie over de structuur van optimale oplossingen kan gevonden worden in een diverse set van elite oplossingen. In de literatuur is ook bewezen dat een hoogkwalitatieve initiële oplossing verkregen door een heuristische techniek, de metaheuristische techniek kan helpen met het vinden van goede oplossingen op een snellere manier. Om die reden hebben de auteurs een heuristische techniek gehanteerd die een werkrooster genereert voor elk personeelslid in willekeurige volgorde. Dat wordt

82



gedaan door het sub probleem op te lossen, rekening houdend met de preferenties en strafkosten. Het algoritme bezit drie strategieën om de initiële oplossing te genereren. In een eerste strategie worden de oplossingen willekeurig gegenereerd. Een tweede methode genereert oplossingen heuristisch en de derde strategie genereert een gedeelte van de oplossingen heuristisch en een ander gedeelte willekeurig. Nadat de initiële oplossingen definitief gegenereerd zijn, wordt een subset van deze

oplossingen aangeduid als referentie oplossingen. R 3q V bezit M beste populatie elementen in termen van oplossingskwaliteit. R 3q VD bezit MD meest diverse oplossingen

met respect voor de oplossingen van R 3q V. De maat van diversiteit wordt bepaald door

de afstand tussen twee oplossingen en wordt berekend als het aantal verschillende toewijzingen tussen de twee oplossingen.

7.3.3.3 De “Subset Generation” methode Na de initialisatie fase hanteert het scatter search algoritme enkel deze referentie oplossingen. In het bijzonder worden in de subset generatie methode twee elementen van de referentie set op gestructureerde wijze geselecteerd en gecombineerd met elkaar. Hierdoor ontstaan zowel punten binnen als buiten het convexe gebied gespannen door de referentie oplossingen. De combinatie van twee elementen kan op drie manieren geschieden. Intensivering wordt gestimuleerd door twee elementen uit dezelfde cluster te combineren, i.e., R 3q V R 3q V en R 3q VD R 3q VD. Diversificatie daarentegen wordt gestimuleerd door twee elementen uit verschillende clusters te combineren, i.e., R 3q V R 3q VD.

Het algoritme is in staat om een elementenpaar op drie manieren te selecteren. De volledige random selectie vormt de eerste strategie en selecteert een elementenpaar volledig willekeurig uit R 3q V of R 3q VD. De gecontroleerde random selectie vormt de

tweede strategie en wordt gekenmerkt door vooraf gedefinieerde waarschijnlijkheden dat het elementenpaar uit R 3q V R 3q V , R 3q VD R 3q VD of R 3q V R 3q VD

83



komt. De uiteindelijke selectie uit de vooraf bepaalde referentie set gebeurt op willekeurige wijze. De gecontroleerde selectie gebaseerd op fitheid en diversificatie waarde stelt de derde strategie voor. Het mechanisme uit welke referentie set een elementenpaar komt is dezelfde als deze beschreven voor strategie twee. De selectie daarentegen gebeurt aan de hand van de fitheid waarde voor R 3q V en de diversificatie waarde voor R 3q VD. Fittere populatie

elementen uit R 3q V en meer diverse populatie elementen R 3q VDmet respect voor

R 3q V hebben een hogere waarschijnlijkheid om geselecteerd te worden.

7.3.3.4 De “Solution Combination” methode Bij elke iteratie wisselen de twee geselecteerde populatie elementen informatie uit op een zodanige manier dat een nieuw individu gecreëerd wordt met attributen van beide ouders. Het nieuwe individu wordt een kind genoemd. De informatie-uitwisseling tussen beide elementen wordt door het algoritme bewerkstelligd door crew gebaseerde methoden of door het path relinking concept. Analoog met natuurlijke selectie, gaan al deze heuristische benaderingen ervan uit dat de ouders hun goede kenmerken doorgeven aan de nieuw gecreëerde oplossingen. Het algoritme behoudt dus minstens of verbetert de goede kenmerken van de ouders naarmate de populatie vordert. Een eerste categorie van methoden die het mogelijk maakt om informatie uit te wisselen, betreft de crew gebaseerde crossover operatoren. Een daarvan, de één-punt crossover operator, werd bij de uiteenzetting over genetische algoritmen besproken en geïllustreerd aan de hand van een voorbeeld. De crossover operator with best tournament selection, creëert een nieuw rooster uit de combinatie van de beste individuele roosters van de ouders. De notie best individueel rooster kan enerzijds de beste zijn in termen van sociale kwaliteit en anderzijds de beste in termen van de globale kwaliteit, i.e., operationele kosten en sociale kwaliteit. In het bijzonder organiseert deze methode een tornooi tussen individuen van de populatie, waarbij het winnende individu wordt geselecteerd voor crossover. Als een nieuw werkrooster voor elk personeelslid willekeurig wordt geselecteerd uit de twee ouders betreft het een crossover operator with random tournament selection.

84



Een andere methode voor het uitwisselen van informatie is gebaseerd op het path relinking concept. Oorspronkelijk was dit concept bedoeld om intensivering en diversificatie te integreren in tabu search (Martí et al., 2006). Het idee achter path relinking is het volgende. Door een pad tussen twee hoogkwalitatieve oplossingen te onderzoeken, zullen nieuwe oplossingen worden gevonden die een significant gedeelte van de attributen, afhankelijk van het onderzochte pad, bezitten van beide ouders. Een pad genereren gebeurt door te starten bij een van de hoogkwalitatieve beginoplossingen en moves te selecteren die progressief attributen van de (leidende) buuroplossing introduceren. Toegepast op het crew rostering probleem streeft path relinking naar het vinden van frequent of significant voorkomende taken in hoogkwalitatieve oplossingen en deze dan te introduceren in andere oplossingen die compatibel zijn met de taak in kwestie. De nieuwe oplossingen worden gegenereerd aan de hand van een heuristische combinatiemethode. Door de combinatie van beide ouders wordt een uitvoerbaar werkrooster gegenereerd voor elk personeelslid door het sub probleem op te lossen met adequate kosten. Deze meegerekende kosten zijn het resultaat van een gewogen gemiddelde gebaseerd op een (negatieve) kost gegeven aan de toegewezen activiteiten aanwezig bij de ouders die de goede karakteristieken van de beginoplossing behouden en die attributen van de leidende buuroplossing introduceren, de operationele kosten en de sociale kwaliteit. De auteurs hebben dit combinatie mechanisme op twee manieren geïmplementeerd. Restricted path solution vormt de eerste manier en beschouwt enkel de activiteiten van de beginoplossing en de leidende buuroplossing. Total path solution vormt de tweede manier en beschouwt daarentegen alle activiteiten compatibel met de kwalificaties van het personeelslid.

7.3.3.5 De “Improvement” methode De vierde stap in het scatter search algoritme gebruikt heuristische technieken om de nieuw gegenereerde oplossingen te verbeteren in termen van totale operationele kosten, gelijkverdeelde werkdruk en individuele preferenties. Deze verbeteringen worden door vier verschillende complementaire lokale zoekalgoritmen geïmplementeerd. Elk zoekalgoritme focust op een verschillend deel van de roostermatrix.

85



Het individuele rooster gebaseerde lokaal zoekalgoritme optimaliseert een werkrooster van één at random gekozen personeelslid, gegeven de werkroosters van de andere personeelsleden. Deze random procedure loopt totdat alle individuele werkroosters geoptimaliseerd zijn. De optimalisatie van een werkrooster gebeurt door het sub probleem op te lossen met adequate strafkosten voor onder- en overbemanning, strafkosten voor eerlijk verdeelde werkroosters en de individuele preferenties. Het periode gebaseerde lokaal zoekalgoritme optimaliseert de planning voor een bepaalde periode, gegeven de taken van de personeelsleden in alle andere periodes. De lengte van de periode wordt zodanig gekozen dat maximaal één activiteit kan toegewezen worden aan een personeelslid binnen deze periode. Hierdoor kunnen activiteiten lineair worden toegewezen aan personeelsleden op basis van individuele preferenties, eerlijkheid en adequate strafkosten voor over- en onderbemanning. Concreet wordt het behandelde roostergedeelte omgezet tot een lineair toewijzingsprobleem (LAP) dat opgelost wordt met behulp van de Hongaarse methode. Deze methode wijzigt een initiële kostenmatrix volgens een bepaalde procedure totdat de optimale toewijzing is gevonden. De kostenmatrix wordt opgesteld, waarbij de kolommen de activiteiten voorstellen en de rijen de personeelsleden. Verder bestaat de kostenmatrix uit de strafkosten en de crew satisfactie voor het volledige werkrooster als de activiteit in kwestie zou worden geïncorporeerd. Daarenboven worden dummy personeelsleden en dummy activiteiten toegevoegd zodat onder- en overbemanning worden toegelaten. Een gelijkaardig algoritme betreft de activiteit gebaseerde zoekopdracht die de toewijzing van één activiteit optimaliseert, gegeven alle andere activiteiten van de crew. Het verschil met het voorgaande zoekalgoritme is dat deze focust op alle activiteiten binnen een bepaalde periode. Het rooster gebaseerde zoekalgoritme streeft naar de verbetering van de crew satisfactie door eerst volledige roosters en daarna delen van roosters tussen personeelsleden te verwisselen, enkel rekening houdend met pairings en reserves. Dit probleem wordt opgelost door een LAP te definiëren gebaseerd op de Hongaarse methode die enkel invloed heeft op de sociale kwaliteit van de roosters. Elk geconstrueerde LAP

86



matrix bestaat uit alle mogelijke wissel alternatieven tussen personeelsleden rekening houdend met de kwalificaties en de vooraf toegewezen activiteiten. De toewijzingskosten bestaan uit de volledige roosterkost als de wissel zich zou voordoen.

7.3.3.6 De “Reference Set Update” methode De populatie van referentie elementen evolueert na elke iteratie. De minst goede oplossingen verdwijnen en nieuwe betere oplossingen worden toegevoegd. Op die manier wordt de kwaliteit van de beste oplossing telkens verbeterd. Een nieuwe oplossing wordt lid van de referentie set indien zijn doelfunctie waarde beter is dan het element met de

slechtste doelfunctie waarde in R 3q V, ofwel indien de nieuwe oplossing meer divers is dan de minst diverse oplossing van R 3q VDmet respect voor R 3q V.

De update van de referentie set kan statisch of dynamisch gebeuren. Bij een statische update worden eerst een aantal nieuwe oplossingen opgeslagen in een pool (Martí et al., 2006). Pas daarna wordt de referentie set geüpdate. Een dynamische update evalueert elke nieuwe oplossing onmiddellijk en maakt dus geen gebruik van een pool. Gedurende de zoekopdracht wordt diversiteit gewaarborgd door het gebruik van artificiële splitsingen in de referentie set, door het voorkomen van duplicatie en het niet toelaten van sterk gelijkaardige oplossingen. Een voorbeeld van deze vier lokale zoekalgoritmen wordt gegeven in Meanhout and Vanhoucke (2007). De auteurs hebben hun algoritme onderworpen aan een testcase. De resultaten worden gepresenteerd in hun werk en bewijzen dat hun algoritme een krachtig wapen vormt voor het oplossen van het airline crew scheduling probleem. Zoals hierboven vermeld, wordt dit algoritme gehanteerd voor de real-world case op SN Brussels Airlines. De regels zijn gelijkaardig, maar het aantal activiteiten en personeelsleden overstijgen deze van de testcase. In volgend deel wordt dieper ingegaan op de implementatie van de case SN Brussels Airlines.

87



7.4 Input: datacollectie en databewerking Een algoritme kan enkel en alleen output genereren als deze van input wordt voorzien. In dit deel wordt eerst beschreven hoe de data werd verzameld. Vervolgens wordt ingegaan op de databewerking noodzakelijk voor de omvorming van de verzamelde data tot bruikbare datafiles voor het algoritme. Figuur 7.7 schematiseert de structuur van de case.

Figuur 7.7. Structuur van de case

7.4.1 Datacollectie In hoofdstuk 4 werd een uitgebreide analyse over de inputblokken gemaakt. In dit deel gaan we de vergaarde kennis van die analyse omzetten naar de praktijk. In het bijzonder kan figuur 5.2 aangepast worden tot figuur 7.8, waarin te zien is welke informatie is verzameld en waar deze is gevonden of door wie deze is bezorgd. In het bijzonder werd alle informatie verzameld tijdens twee gespreken. Een eerste met de heer Dobbelstein (Zaventem, 12 maart 2007) en een tweede met de heer Vaes, Blue One Administrator (Melsbroek, 22 maart 2007). Crew informatie werd verzameld uit de database van Blue One. De historiek is niet van toepassing omdat het algoritme enkel gericht is op het genereren van maandroosters. Bijgevolg moeten ook geen jaarbeperkingen gemodelleerd worden in het algoritme. De kwalificaties gelden voor alle captains van het sub rostering probleem onder studie, behalve

88



voor de bestemmingen. De vooraf toegewezen activiteiten en de vakantiedagen werden ook verzameld uit de database.

Figuur 7.8. Informatiebronnen

Informatie betreffende de activiteiten behoeft een grote opmerking. Een klein aantal reserves en vooraf toegewezen activiteiten waren onmogelijk om te verzamelen omdat een aantal piloten ziek waren in juni 2006. De database van Blue One evolueert namelijk in de tijd, maar is wel in staat om bepaalde momentopnamen in het verleden te genereren. Helaas kon niet worden achterhaald of de zieke piloten reserves of vooraf toegewezen activiteiten moesten vervullen. Alle regels en wetgevingen van toepassing op SN Brussels Airlines staan in de operations manual. Slechts een gedeelte van de regels zijn van toepassing op deze case en werden geïmplementeerd in het algoritme. Een overzicht van deze regels wordt gepresenteerd in bijlage D. De volledige OM staat op de bijgevoegde cd-rom.

89



De doelstellingen die het crew scheduling departement nastreeft werden hierboven vermeld. Het primair doel vormt de gelijke verdeling van de werkdruk, evenwel van dichtbij gevolgd door minimale kosten. Het in rekening brengen van individuele preferenties vormt ook een doel, maar dit doel wordt niet expliciet contractueel vastgelegd. Data over deze preferenties werden verzameld uit de Blue One database. In het bijzonder werden aanvragen voor vrije dagen verzameld. Specifieke aanvragen voor bepaalde vluchten werden niet meer teruggevonden. Het inbouwen van robuustheid wordt bereikt door de regels aan te passen, bijvoorbeeld door de minimaal verplichte rust te verlengen met een twee uur om eventuele vertragingen op te vangen. Omdat het geen primaire doelstelling betreft werd dit in het algoritme niet gedaan.

7.4.2 Databewerking De verzamelde data moet vervolgens worden bewerkt tot bruikbare inputfiles voor het algoritme. De inputfiles bestaan uit een aantal blokken data die met behulp van Excel en de programmeertaal Ruby werden gegenereerd. De inputdata staat op bijgevoeg cd-rom. Een eerste type van datablokken bestaat uit de nodige informatie over de activiteiten en verloven. Zo worden starttijd, eindtijd en service tijd voor de drie types activiteiten voorgesteld door drie kolommen. Voor de pairings worden daarenboven drie extra kolommen toegevoegd die de blok uren, het type bestemming en het al dan niet bevatten van een nightstop voorstellen. De vooraf toegewezen activiteiten bevatten één extra kolom omdat bij deze activiteiten moet worden gespecificeerd welk personeelslid de activiteit in kwestie

moet

volbrengen.

De

goedgekeurde

verloven,

loopbaanverminderingen,

zwangerschapsverloven en dergelijke vormen een subcategorie van de vooraf toegewezen activiteiten en bevatten daarom ook dezelfde kolommen. Echter, hun service tijd wordt op 0 gezet. Het tweede type van databokken bestaat uit een aantal matrices. De successie matrix

(#s(5g5tq #s(5g5tq) bestaat initieel enkel uit 1’en en wordt geüpdate door het

algoritme. Een 1 betekent dat de twee pairings elkaar kunnen opeenvolgen, een 0 krijgen ze

90



als ze elkaar niet kunnen opeenvolgen. De toewijzingsmatrix ( #g c M gq #s(5g5tq) bestaat uit een 1 als het personeelslid gekwalificeerd is voor de pairing en een 0

als deze de nodige kwalificatie niet bezit. In het bijzonder wordt in deze matrix de wel of niet

kwalificatie voor een bestemming gesimuleerd. De preferentie matrix (#g c M gq

#s(5g5tq) stelt de individuele preferenties voor. Omdat de informatie hierover niet

gestandaardiseerd is, bevat de invulling van deze matrix een zekere graad van subjectiviteit. Piloten vragen een vrije dag aan door hun motivatie in te geven in Bleu one. Het resultaat zijn volzinnen. Om de graad van subjectiviteit zo laag mogelijk te houden werden twee categorieën van motivaties gecreëerd. Tabel 7.2 illustreert. De toegewezen strafwaarden zijn

0, 15, of 20. Een pairing toewijzen aan een personeelslid met sterke motivatie resulteert in een vermeerdering van de doelfunctie met 20 strafpunten. Ook werden strafwaarden van 1000 geïntroduceerd voor weekenden tussen twee vakantieweken omdat deze niet meegerekend worden als vakantie, terwijl het personeelslid in kwestie uiteraard geen activiteiten kan verrichten in dat weekend. Strafpunten Gewone motivatie 15 Sterke motivatie

20

Commentaren graag, aanvraag wekelijkse rust zonder motivatie Verjaardag, optreden, kinderen, nog onder anesthesie, trouw, communie, doop, cursus, bevalling vrouw, belangrijke meeting

Tabel 7.2.

Motivatie categorieën

Een beperking moet evenwel aangehaald worden. De laatste matrix houdt rekening met de aanvraag voor vrije dagen door pairings op deze dagen te bestraffen. Deze aanpak moet analoog worden toegepast voor reserves, maar werd niet gedaan. Het betreft een beperking van kleine omvang omdat er slechts 73 reserves zijn en omdat de directe impact van de beperking enkel betrekking heeft op de preferenties, die geen prioritair doel vormen.

91



7.5 Verwerking: inputfiles, strafkosten en parameters De algemene werking van het algoritme werd hierboven reeds uiteengezet. In dit deel wordt eerst beschreven hoe het algoritme de inputfiles concreet inleest en verwerkt tot output. Vervolgens worden de ingestelde strafkosten en parameters gespecificeerd.

7.5.1 Verwerking van de inputfiles Het algoritme werkt omwille van beperkt computergeheugen met weekdata. In het bijzonder wordt eerst week 1 (1 – 7 juni) ingelezen, gevolgd door week 2 (8 – 14 juni), week 3 (15 – 22 juni) en week 4 (23 – 30 juni). De looptijd voor het berekenen van de eerste twee weken bedraagt ongeveer 900 seconden. De laatste twee weken duren 1100 seconden omdat deze bestaan uit 8 dagen. De verwerking via weekdata in plaats van maanddata leidt tot enkele belangrijke implicaties. Enerzijds kan dit leiden tot tegenstrijdige situaties tussen pairings en vooraf toegewezen activiteiten bij de overgang van een week op een andere week. In het bijzonder worden een aantal vooraf toegewezen activiteiten van de eerste dag van de week toch niet toegewezen omdat de pairing van de laatste dag van de vorige week te lang duurt waardoor te weinig rust wordt gegeven. Het betreft een beperking die evenwel eenvoudig kan gemodelleerd worden door bijvoorbeeld een bepaalde rustperiode voor de vooraf toegewezen activiteit te garanderen. Anderzijds zou de bekomen oplossing mogelijks van betere kwaliteit zijn met maanddata. Een aantal vooraf toegewezen activiteiten worden ook niet toegewezen omdat het periode gebaseerde zoekalgoritme ingesteld is op 18 uur. Zoals hierboven beschreven mag in dit tijdsinterval maar één activiteit aan een personeelslid worden toegewezen. Bij SN Brussels Airlines zijn er evenwel piloten die twee korte activiteiten binnen dit tijdsinterval moeten vervullen. Door die twee activiteiten samen te nemen werd deze beperking deels verholpen. Idealiter zou de periode slechts 12 uur mogen bedragen.

92



7.5.2 Strafkosten en parameters Het algoritme verdeelt de werkdruk tussen de roosters aan de hand van vier factoren. Tabel 7.3 illustreert deze factoren samen met hun strafkost per deviatie eenheid van de gemiddelde waarde. Drie factoren worden ook door SN Brussels Airlines gehanteerd. Alleen de TAFB werd door tijdsredenen niet gemodelleerd in het algoritme. Evenwel vergt dit slechts een kleine aanpassing die het resultaat nauwelijks zou beïnvloeden. Verder staan in de tabel ook de strafkosten per uur voor het niet toewijzen van een pairing, reserve en vooraf toegewezen activiteit aan vast personeel. Deze strafkosten moet vermenigvuldigd worden met de duur dat ze niet zijn toegewezen. Als bijvoorbeeld nog vijf uur van de pairings niet toegewezen zijn aan vast personeel dan bestraft het algoritme dit met 5000 strafpunten. Ook de strafkosten voor het negeren van preferenties worden getoond in de tabel. Een grote waarde werd ingevoerd voor het negeren van een vooraf toegestane vakantie. Tabel 7.3.

Ingestelde strafkosten

Tabel 7.4.

Ingestelde parameters

Strafkost

Aantal

Factoren voor gelijkverdeelde werkdruk

Stopconditie

Deviatie service tijd

20

Deviatie lok uren

10

Deviatie aantal nightstops

10

Deviatie vrije dagen

10

maximum aantal gecreëerde roosters R 3q V

R 3q VD

Niet toegewezen aan vaste crew 1.000

Reserve

100 10.000

Gewone motivatie

15

Sterke motivatie

20

Vooraf toegestane vakantiedagen

10

R 3q V R 3q V

45%

R 3q VD R 3q VD

45%

R 3q V R 3q VD

Preferenties negeren

Dag tussen twee vakanties

20

Waarschijnlijkheden Subset Generation

Pairing

Vooraf toegewezen activiteiten

20.000

Referentie oplossingen

10%

1.000 100.000

Een aantal andere parameters moeten vooraf ingesteld worden. Het betreft de stopconditie, het aantal oplossingen in de referentie set en de waarschijnlijkheden waaruit de subset generatie methode een elementenpaar selecteert. Tabel 7.4 illustreert. Alle parameters kunnen uiteraard aangepast worden.

93



Zoals hierboven beschreven, bestaat het algoritme uit vijf methoden die op hun beurt via verschillende strategieën kunnen worden opgelost. Voor deze case worden combinaties van strategieën gebruikt met als doel het genereren van de best mogelijke oplossingen.

7.6 Output, vergelijkende studie en beperkingen De laatste en meest interessante stap van de case wordt hier aangevat. Eerst wordt kort beschreven welke output het algoritme genereert. Daarna wordt de vergelijkende studie aangevat. De meeste beperkingen werden al aangehaald, maar worden nog eens samengevat op het einde van dit deel.

7.6.1 Output en vergelijkende studie Het algoritme genereert geen visueel onmiddellijk hanteerbare werkroosters zoals het systeem Blue One dat doet. Echter is dit ten gepaste tijden zeker programmeerbaar. De output bestaat uit 2 matrices. Een eerste matrix bevat als kolommen de factoren voor een gelijke verdeling van de werkdruk. De rijen stellen de captains voor. Een tweede matrix is gelijkaardig met datarepresentatie voorgesteld in figuur 7.6. De vergelijking tussen SN Brussels Airlines en het scatter search algoritme wordt geanalyseerd aan de hand van de factoren voor een gelijke verdeling van de werkdruk. In het bijzonder wordt de service tijd, het aantal blok uren en het aantal nightstops onderworpen aan een vergelijkende studie. In bijlage A wordt een tabel gepresenteerd met de consumptie van deze drie factoren per captain voor juni 2006 gegenereerd door het algoritme. Bijlage B en C presenteert dezelfde informatie maar opgesteld door SN Brussels Airlines.

7.6.1.1 Doelstelling 1: gelijkverdeelde werkdruk Tabel 7.5 presenteert een overzicht van de behaalde resultaten door SN Brussels Airlines (SNBA) en door het scatter search algoritme (SS) met betrekking tot de primaire doelstelling. Eerst werd het gemiddelde verbruik van de drie factoren berekend, daarna de

94



som van het kwadraat van de afwijking van dat gemiddelde voor alle captains. De laatste berekening resulteert in een afwijkingsmaat voor de factoren. Hoe lager die maat, hoe beter de factor in kwestie wordt verdeeld over de maandroosters.

Tabel 7.5.

Service tijd (duty time) Gemiddelde Afwijking (Sum of Squares) Blok uren (flight time) Gemiddelde Afwijking (Sum of Squares) Aantal nightstops Gemiddelde Afwijking (Sum of Squares)

Vergelijking gelijkverdeelde werkdruk

SNBA

SS

% verschil

110,69 140.539

104,41 43.300

-5,67% -69,19%

53,83 47.294

53,00 12.430

-1,54% -73,72%

6,17 952

5,93 367

-3,88% -61,42%

De blauwe cijfers in de tabel bevestigen dat het algoritme in staat is roosters te genereren die de werkdruk tussen de captains beter kan spreiden dan de manueel opgestelde roosters van SN Brussels Airlines. In het bijzonder worden aanzienlijke verbeteringen behaald van 69 %, 74 % en 61 % voor de respectievelijke factoren service tijd, blok uren en aantal nightstops. Op te merken valt de lagere gemiddelden behaald door het algoritme. Deze lagere gemiddelden vloeien voort uit de aangehaalde beperkingen, waardoor een aantal activiteiten niet zijn toegewezen. De kleine verschillen tussen de gemiddelden van SNBA en deze van het algoritme zorgen voor onnauwkeurigheden, maar zijn niet van deze orde dat ze een globaal vertekend beeld zouden kunnen opleveren.

7.6.1.2 Doelstelling 2: minimale kosten Alhoewel de Crew Scheduling Manager van SN Brussels Airlines duidelijk stelde dat een gelijke verdeling van de werkdruk de centrale doelstelling vormt, kan met niet negeren dat elke maatschappij streeft naar winstmaximalisatie. Minimale kosten vormen dan ook een heel belangrijke doelstelling. Hierboven werd het systeem van overuren, gehanteerd door SN Brussels Airlines, beschreven. Op dezelfde manier zijn de te vergoeden eenheden overuren berekend. Uitgaande van de realistische veronderstelling dat een captain een bruto maandloon

95



verdient van 7000 € en dat freelance personeel bruto 100 € per uur verdient kan berekend worden dat maandelijkse besparingen van 22.227 €, inclusief de 118 uur dat freelance personeel moet worden gehuurd, behaald kunnen worden door het toepassen van het algoritme. De netto huidige waarde, met discontovoet van 4,14 % (rendement van een OLO op 1 jaar op 28 april 2007), van deze besparingen lopen na vijf jaar op tot maar liefst 1.185.401 €. Tabel 7.6 presenteert de resultaten en de berekeningen.

Tabel 7.6.

Vergelijking van de betaalde som aan overuren

Maandelijkse vergoeding aan overuren Totale kost aan overuren Economisch voordeel op basis van de NHW NHW na 1 jaar NHW na 3 jaar NHW na 5 jaar Berekening Eenheden overuren * Vergoeding / uur = Extra kost voor overuren (1) Nodige freelance uren * Vergoeding / uur = Extra kosten freelancers (2) = Totale kost aan overuren (1) + (2)

SNBA

SS

absoluut verschil

38.585 €

16.308 €

-22.277 € 256.694 € 739.874 € 1.185.401 €

413 93 38.585 €

48 93 4.508 €

-365

0 100 0€

118 100 11.800 €

11.800 €

38.585 €

16.308 €

-22.277 €

-34.077 € 118

7.6.1.3 Verdere analyse van de mogelijke besparingen De hierboven berekende besparingen die kunnen gerealiseerd worden zijn aanzienlijk, maar betreffen enkel de rechtstreekse besparingen. In dit onderdeel, wordt verder gezocht naar potentiële extra besparingen. Uit marktonderzoek over de implicaties van eerlijk verdeelde werkdruk en hoge satisfactie in de medische wereld is gebleken dat nog een aantal kanalen voor extra besparingen kunnen zorgen. Onderstaande figuur 7.9 illustreert deze kanalen. Opgemerkt moet worden dat de relaties nog niet specifiek bestudeerd zijn voor de luchtvaartsector. Toekomstig onderzoek hieromtrent wordt dan ook aanbevolen.

96



Figuur 7.9. Kanalen die leiden tot onrechtstreeks besparingen

De eerste relatie (1) wordt bevestigd voor verplegend personeel in het werk van McNeese-Smith (1999). Relatie (2) werd al eerder in deze scriptie bestudeerd in het kader van team-oriented rostering, geïntroduceerd door Thiel (2004). Het werk van Smith et al. (2005) onderzoekt de impact van de servicekwaliteit op de job satisfactie voor verplegend personeel. Deze relatie is positief gecorreleerd en bevestigd daarmee impliciet relatie (3). Relatie (4) wordt bevestigd in Lin (2007). Voor de berekeningen van de mogelijke onrechtstreekse besparingen wordt verondersteld dat roosters met meer gelijkverdeelde werkdruk het aantal passagiers met 0,01 % doet toenemen en de graad van absenteïsme reduceert met 1 %. Verder, worden nog een aantal andere assumpties gemaakt. Deze worden in tabel 7.7 gepresenteerd en werden deels bekrachtigd door de Crew Scheduling Manager van SNBA, deels door eigen ervaringen en deels via de website van Brussels Airlines.

Tabel 7.7.

Assumpties

Waarde Bekrachtigd door Crew Scheduling Manager van SNBA Gemiddelde ticketprijs bij SNBA Tijdbesteding aan opstellen roosters (planner) Graad van absenteïsme op korte termijn Uren werk per week (planner) Website Brussels Airlines Gemiddelde bezettingsgraad Eigen ervaringen Winstmarge/passagier Totaal uren bezig aan input voor algoritme Bruto maandloon planner

97

125 - 150 € 50% 2,4% 38 uur 66,4% 25 € 50 uur 3.500 €



De berekeningen en de totale besparingen worden in onderstaande tabel 7.8 getoond. Drie onrechtstreekse kanalen werden berekend. De rechtstreekse besparingen werden uitgebreid met het voordeel van minder overuren voor de copiloten. Hierbij werd verondersteld dat deze slechts 5000 € per maand verdienen in plaats van 7000 € voor een captain. Het uurloon voor freelancers werd behouden op 100 €.

Tabel 7.8.

Totale potentiële besparingen

Waarde Rechtstreekse besparingen Vermindering overuren captains Vermindering overuren copiloten Onrechtstreekse besparingen Herallocatie planner (1) Extra passagiers (2) Daling absenteïsme (3) Totale besapringen Op 1 maand NHW na 1 jaar NHW na 3 jaar NHW na 5 jaar Inkomsten uit extra passagiers (2) Vluchten/dag * Gemiddelde capaciteit per vliegtuig - 12 RJ-100 met 97 plaatsen - 14 RJ-85 met 82 plaatsen - 6 BAE 146 met 84 plaatsen * Bezettingsgraad = Gemiddeld aantal passagiers/dag * Percentage extra passagiers = Pot. aantal extra passagiers/dag * Winstmarge = Pot. extra ticketinkomsten/dag * aantal dagen = Pot. extra ticketinkomsten/maand

22.277 € 12.541 € 3.500 € 657 € 1.249 € 40.224 € 463.495 € 1.335.940 € 2.140.398 € 150 88

Waarde Herallocatie planner (1) Aantal planners * Werkuren per planner/maand = Totaal werkuren / maand * Tijdpercentage voor opstellen roosters = Uren winst door algoritme * Aantal extra uren bezig met input = Tot aantal uren winst ' --> 1 planner heralloceren

3 163 489 50% 244 50 194 3.500

Daling graad van absenteïsme met 1 % (3) Graad van absenteïsme op korte temijn Streefgraad via satisfactie = Daling van absenteïsme * Vluchten/maand (A) = daling aantal vluchten met reserve (D)

2,40% 1,40% 1% 4.500 45

Gemiddelde aantal blok uren/maand * Aantal captains = Totaal aantal blok uren/maand (B)

53,83 142 7644

66,4% 8.765 0,01% 0,88 25 € 22 € 30 657 €

Gemiddelde vluchtduur in uur (B) / (A) * Daling vluchten met reserve (D) = Aantal uren reserve nodig * slechts 25 % (assump.) creeert overuren * factor 0,7 want onder 75 blok uren * Vergoeding overuren/uur = Totale extra daling overuren

1,70 45 76,44 25% 0,7 93,33 € 1.249 €

De berekeningen zijn niet voor de volle honderd procent wetenschappelijk onderbouwd, maar dergelijke berekeningen zijn dat zelden en daarenboven steunen ze op weldoordachte en realistische assumpties. We besluiten dan ook dat de cijfers uit de tabel bevestigen dat het algoritme de kosten drastisch kan doen dalen. Na vijf jaar kunnen maar liefst potentiële

98



besparingen van 2.140.398 € worden gerealiseerd door de implementatie van het scatter search algoritme van Maenhout and Vanhoucke (2007).

7.6.1.4 Doelstelling 3 en 4: Individuele preferenties en robuustheid De individuele preferenties worden in deze scriptie niet becijferd omdat de gegenereerde output geen efficiënte berekening mogelijk maakt. Mits enkele aanpassingen is een exacte becijfering echter wel mogelijk. De graad van robuustheid vormde geen doelstelling in deze scriptie en wordt dus ook niet becijferd. Wel kan aan de hand van een vergelijking tussen de cijfers voor operaties (Pre-Ops) en na operaties (Post-Ops) van SNBA de nood voor robuuste roosters, aan de hand van de hierboven aangehaalde assumpties, worden becijferd. Tabel 7.9 toont aan dat de werkelijk gepresteerde blok uren dalen met 4 %, i.e., 4 % van de vluchten zijn afgelast geweest in juni 2006. Het rechtstreeks economisch verlies door deze afgelastingen bedraagt 250.089 €. Een robuustere planning had een deel van dit verlies eventueel kunnen vermijden. Toekomstig onderzoek zal dit moeten uitwijzen.

Tabel 7.9.

Pre-Ops Service tijd (duty time) Gemiddelde Afwijking Blok uren (flight time) Gemiddelde Afwijking Eenheden overuren Aantal nightstops Gemiddelde Afwijking

Invloed van 4 % annuleringen per maand

Post-Ops

% verschil

110,69 140.539

104,00 146.460

-6,04% 4,21%

53,83 47.294 413

51,67 41.939 269

-4,01% -11,32% -35,05%

6,17 952

6,15 1.019

-0,23% 7,00%

waarde Berekeningen Daling overuren (1)

13.523 €

Aantal passagiers/maand * Winstmarge/passagier * Afgelastingen = Verlies aan inkomsten (2)

262.944 25 4,01% -263.612 €

Totaal verlies (1) + (2)

-250.089 €

In de tabel 7.9 is ook te zien dat de uiteindelijke overuren na operaties slechts 269 eenheden bedraagt. Dit komt door de afgelaste vluchten. De voorgaande becijfering over de kosten aan overuren op basis van de 413 eenheden zijn evenwel correct omdat het algoritme roosters genereert vóór operaties

99



7.6.2 Overzicht van de beperkingen Alle beperkingen werden terloops aangehaald. In tabel 7.10 wordt een samenvattend overzicht gepresenteerd van de beperkingen in volgorde van belangrijkheid. Ook worden de gevolgen kort samengevat en wordt aangeduid of de beperking in kwestie al dan niet ophefbaar is mits voldoende tijd.

Tabel 7.10.

Overzicht van de beperkingen op de case

Gevolg

ophefbaar

Beperkingen zonder invloed op de case Geen jaarbeperkingen

/

ѵ

Een tiental pairings niet toegewezen

Huur freelance personeel

ѵ

Geen rekening gehouden met TAFB

1 factor minder voor gelijkheid werkdruk

ѵ

Geen preferentie matrix voor reserves

Minder preferenties voldaan

ѵ

Periode gebaseerd lokaal zoekalgoritme

Enkele vooraf toegewezen activiteiten zijn toch niet toegewezen

ѵ

Minder preferenties voldaan

×

Geen kennis van de activiteiten tijdens ziekte

Minder reserves en vooraf toegew. act.

×

Computergeheugen

Eventueel lagere oplossingskwaliteit

ѵ

Beperkingen met kleine invloed op de case

Beperkingen met grotere invloed op de case Niet alle data voor preferenties beschikbaar

7.7 Conclusies en aanbevelingen In dit hoofdstuk werd een werkelijkheidsgetrouwe case opgesteld voor het airline crew rostering probleem aan de hand van cijfers van SN Brussels Airlines. Het hybride scatter search algoritme van Maenhout and Vanhoucke (2007) werd voorgesteld voor de automatische generatie van maandroosters gebaseerd op het personalized rostering concept. De bekomen oplossingen zijn van een kwalitatief hoog niveau en tonen aan dat het algoritme het probleem perfect aankan. In het bijzonder daalt de spreiding van de factoren die instaan voor een gelijke verdeling van de werkdruk met ongeveer 70 % in vergelijking met de manueel opgestelde maandroosters van SN Brussels Airlines en kunnen potentiële maandelijkse besparingen tot 40.000 € worden gerealiseerd. Hiermee bewijst het algoritme dat het een krachtig wapen is dat in staat is de werkdruk eerlijker te verdelen over de crew, terwijl simultaan een drastische kostenreductie kan bereikt worden.

100



Cijfers over het in rekening brengen van de individuele preferenties zijn helaas niet berekend. Hieromtrent is de enige te trekken conclusie dat het algoritme de preferenties modelleert, evenwel zonder bewijs dat er ook daadwerkelijk rekening mee gehouden wordt. Verder zijn algoritme en case nog onderhevig aan andere beperkingen. De belangrijkste is zonder meer het tekort aan computergeheugen. Uitbreiding van dit geheugen zou de oplossingkwaliteit ten goede komen. Ook de andere beperkingen kunnen opgeheven worden mits tijd en toewijding. Het finaal resultaat zou een commercieel systeem kunnen worden dat de concurrentiekracht van SN Brussels Airlines zou kunnen verbeteren. Een belangrijk onderwerp voor toekomstig onderzoek is de constructie van robuuste planningen. Onverwachte wijzigingen zijn uiterst frequent in de luchtvaartsector en leiden in de meeste gevallen tot vertragingen en annuleringen die op hun beurt de operationele kosten doen toenemen, de roosterkwaliteit voor de personeelsleden doet dalen en de klantperceptie reduceert. De vraag naar systemen die in staat zijn deze onzekerheden op te vangen is groot en kan niet genegeerd worden. Verder, moet benadrukt worden dat geïntegreerde systemen meer optimale oplossingen genereren dan gedesintegreerde systemen. Door crew pairing en crew rostering te integreren tot één probleem kan hogere flexibiliteit worden bereikt, waardoor de objectieven makkelijker kunnen worden behaald. Ook voor andere planningsdomeinen wordt integratie aanbevolen. In deze fase zijn verdere verbeteringen van metaheuristische technieken onontbeerlijk om de verhoogde complexiteitsgraad te kunnen beantwoorden.

101



8 Algemeen besluit De luchtvaart is een sterke competitieve sector, waarin alle luchtvaartmaatschappijen streven naar winstmaximalisatie. Een manier om deze doelstelling te bereiken zijn de kosten zo laag mogelijk te houden. De personeelskosten zijn, na de brandstofkosten, de tweede grootste

kost

voor

een

luchtvaartmaatschappij.

Om

die

reden

streven

de

luchtvaartmaatschappijen naar een zo optimaal mogelijke personeelsplanning. De personeelsplanning wordt in operationeel onderzoek het “Airline Crew Scheduling Problem” genoemd, die geformuleerd kan worden als volgt. Crew scheduling is, gegeven de vluchtplanning en de vliegtuigplanning, het proces waarbij anonieme vluchtsequenties of pairings worden gegenereerd. Daarenboven worden alle individuele personeelsleden toegewezen aan de gegenereerde pairings en aan andere activiteiten op een zodanige manier

dat

alle

beperkingen

opgelegd

door

overheidsregels,

collectieve

arbeidsovereenkomsten en bedrijfspecifieke regels worden gerespecteerd, dat alle individuele vluchten adequaat bestaft zijn door personeel en waarbij individuele werkroosters worden opgesteld voor alle personeelsleden met als tweeledig doel het minimaliseren van de kosten en het maximaliseren van de levenskwaliteit van het personeel, eventueel rekening houdend met andere aspecten zoals flexibiliteit en robuustheid. Crew scheduling kan dus worden opgesplitst in twee stappen. Het crew pairing probleem vormt de eerste stap en genereert pairings uit de individuele vluchten met als de doel de minimalisatie van de kosten. Het crew rostering probleem vormt de tweede stap en wijst de individuele personeelsleden toe aan de pairings met als doel het minimaliseren van de kosten en het maximaliseren van de levenskwaliteit van het personeel. Op basis van twee concepten kunnen werkroosters opgesteld worden. De bidlines approach vormt het eerste concept en wordt hoofdzakelijk toegepast in de Verenigde Staten. Op basis van strikte anciënniteit

bieden

personeelsleden

op

anonieme

werkroosters.

Europese

luchtvaartmaatschappijen hanteren het personalized rostering concept. De basis van dit concept is een eerlijk verdeelde werkdruk tussen de personeelsleden en resulteert in persoonlijke werkroosters. Het anciënniteitprincipe wordt dus vervangen door het fair-andequal share principe.

102



Luchtvaartmaatschappijen kunnen reusachtige bedrijven zijn die honderden vluchten per dag verrichten. Dit resulteert in combinatorische mogelijkheden reikend tot in de miljarden. Daarom worden metaheuristische in plaats van exacte optimalisatietechnieken gehanteerd om crew scheduling op te lossen. In het bijzonder worden genetische algoritmen, simulated annealing en tabu search frequent toegepast in het streven naar een zo optimaal mogelijke personeelsplanning. Een hybride vorm van genetische algoritmen en tabu search vormt een scatter search algoritme. Het betreft een krachtige techniek die in staat is hoogkwalitatieve oplossingen te genereren. Een dergelijk algoritme werd ontwikkeld door Maenhout and Vanhoucke (2007) voor het oplossen van het crew rostering probleem op basis van het personalized rostering concept. Bij SN Brussels Airlines worden de werkroosters manueel opgesteld omdat ze streven naar een gelijk verdeelde werkdruk. Vier factoren pogen ze gelijkmatig te verdelen onder de werkroosters. In het bijzonder zijn deze factoren, de blok uren of vlieguren, de service tijd, het aantal nightstops en het aantal uur dat ze weg van huis zijn. Aan de hand van het scatter search algoritme willen we aantonen dat ook een gelijkverdeelde werkdruk mogelijk is via automatische generatie van werkroosters. Een case gebaseerd op werkelijke gegevens van SN Brussels Airlines werd opgesteld met als doel het aantonen dat het scatter search

algoritme

automatische

werkroosters

kan

genereren

met

een

goede

oplossingskwaliteit. De bekomen oplossingen zijn van een kwalitatief hoog niveau en tonen aan dat het algoritme het probleem perfect aankan. In het bijzonder daalt de spreiding van de factoren die instaan voor een gelijke verdeling van de werkdruk met ongeveer 70 % in vergelijking met de manueel opgestelde maandroosters van SN Brussels Airlines en kunnen potentiële maandelijkse besparingen van 40.000 € worden gerealiseerd. Hiermee bewijst het algoritme dat het een krachtig wapen is dat in staat is de werkdruk eerlijker te verdelen over de crew, terwijl simultaan een drastische kostenreductie kan bereikt worden. Het algoritme en de case zijn evenwel onderhevig aan een aantal beperkingen. De belangrijkste is zonder meer het tekort aan computergeheugen. Uitbreiding van dit geheugen zou de oplossingkwaliteit ten goede komen. De andere beperkingen hebben

103



slechts een kleine invloed en kunnen mits tijd en toewijding makkelijk worden opgeheven. Het finaal resultaat zou een commercieel systeem kunnen worden dat de concurrentiekracht van SN Brussels Airlines zou kunnen verbeteren.

104



9 Lijst van de geraadpleegde werken Anbil, R., Gelman, E., Patty, B., and Tanga, R. (1991). “Recent Advances in Crew-Pairing Optimization at American Airlines.” Interfaces, 21 (1), 62-74.

Atlanta Journal-Constitution, The. (2002). “Flight-Delay Problems Down in ’02, Reports FAA.”

Barnhart, C., Hatay, L., Johnson, E.L. (1995). “Deadhead Selection for the long haul Crew Pairing Problem.” Operations research, 43 (3), 491-495.

Beasley, J.E., Krishnamoorthy, M., Sharaiha, Y.M., and Abramson, D. (2000). “Scheduling Aircraft Landings – The Static Case.” Transportation Science, 34 (2), 180-197.

Bélanger, N., Desaulniers, G., Soumis, F., and Desrosiers, J. (2006). “Periodic airline fleet assignment with time windows, spacing constraints, and time dependent revenues.” European Journal of Operational Research, 175, 1754-1766.

Bertsimas, D., and de Boer, S. (2005). “Simulation-Based Booking Limits for Airline Revenue Management.” Operations Research, 53 (1), 90-106.

Boyd, E.A., and Bilegan, I.C. (2003). “Revenue Management and E-Commerce.” Management Science, 49 (10), 1363-1386.

Brussels

Airlines.

(2007).

“Financiele

resultaten

2006.”

Verkrijgbaar

http://company.brusselsairlines.com/nl/news/detail.aspx?uri=tcm:140-16698 (geconsulteerd 20 april 2007).

VI

van:



Bureau of Transportation Statistics. (2002). “2001 Airline On-time Performance”

Campbell, K.W., Durfee, R.B., and Hines, G.S. (1997). “FedEx Generates Bid Lines Using Simulated Annealing. “Interfaces, 27 (2), 1-16.

Cao, J.M., and Kanafani, A. (2000). “The value of runway time slots for airlines.” European Journal of Operational Research, 126, 491-500.

Chen, V.C.P, Günther, D., and Johnson, E.L. (2003). “Solving for an optimal airline yield management policy via statistical learning.” Appl. Statist., 52 (1), 19-30.

Desaulniers, G., Desrosiers, J., Dumas, Y., Marc, S., Rioux, B., Solomon, M.M., and Soumis, F. (1997). “Crew Pairing at Air France.” European Journal of Operational Research, 97, 245-259.

Dorndorf, U., Drexl, A., Nikulin, Y., and Pesch, E. (2007). “Flight gate scheduling: State-of-theart and recent developments.” Omega, 35, 326-334.

Economist, The. (2000). “A jam at 32,000 feet.” Februari 5, 57-58.

El Moudani, W., Cosenza, C.A.N., de Coligny, M., and Mora-Camino, F. (2001). “A Bi-Criterion Approach for the Airlines Crew Rostering Problem.” Lecture Notes in Computer Science, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, 486-500.

VII



Gamache, F., Soumis, F., Villeneuve, D., Desrosiers, J., and Gélinas, E. (1998). “The Preferential Bidding System at Air Canada.” Transportation Science, 32 (3), 246-255.

Gamache, M., Soumis, F., Marquis, G., and Desrosiers, J. (1999). “A Column Generation Approach for Large Scale Aircrew Rostering Problems.” Operations Research, 47 (2), 247262.

Glover, F., Kelly, J.P., and Laguna, M. (1995). “Genetic Algorithms and Tabu Search: Hybrids for Optimization.” Computers and Operations Research, 22 (1), 111-134.

Gosavi, A., Ozkaya, E., and Kahraman, A.F. (2007). “Simulation optimization for revenue management of airlines with cancellations and overbooking.” OR Spectrum, 29, 21-38.

Graves, G.W., McBride, R.D., Gershloff, I., Anderson, D., and Mahidhara, D. (1993). “Flight Crew Scheduling.” Management Science, 39 (6), 736-745.

Grönkvist, M. (2006). “Accelerating column generation for aircraft scheduling using constraint propagation.” Computers & Operation Research, 33, 2918-2934.

Housos, E., and Elmroth, T. (1997). “Automatic Optimization of Subproblems in Scheduling Airline Crews.” Interfaces, 27(5), 68-77.

Hoffman, K.L., and Padberg, M. (1993). “Solving Airline Crew Scheduling Problems by Branchand-Cut.” Management Science, 39 (6), 657-682.

VIII



IBM Deep Computing Institute. (2007). “Description of deep computing.” Verkrijgbaar van: http://www.research.ibm.com/dci/st2_problem.shtml (geraadpleegd 16 februari 2007).

Jarrah, A.I.Z. and Diamond, J.T. (1997). “The Problem of Generating Crew Bidlines.” Interfaces, 27 (4), 49-64.

Karaesmen, I., and van Ryzin, G. (2004). “Overbooking with Substitutable Inventory Classes.” Operations Research, 52 (1), 83-104.

Kohl, N., and Karisch, S.E. (2004). “Airline Crew Rostering: Problem Types, Modeling and Optimization.” Annals of Operations Research, 127, 223-257.

Lee, L.H., Lee, C.U., and Tan, Y.P. (2007). “A multi-objective genetic algorithm for robust flight scheduling using simulation.” European Journal of Operational Research, 177, 1948-1968.

Lim, A., Rodrigues, B., and Zhu, Y. (2005). “Airport Gate Scheduling with Time Windows.” Artificial Intelligence Review, 24, 5-31.

Lin, W.B. (2007). “An empirical of service quality model from the viewpoint of management.” Expert Systems with Applications, 32, 364-375.

Martí, R., Laguna, M., and Glover, F. (2006). “Principles of scatter search.” European Journal of Operational Research, 169, 359-372.

IX


Maenhout, B.,


and Vanhoucke, M. (2007). “A Hybrid Scatter Search Heuristic for

Personalized Crew Rostering in the Airline Industry.” Working paper, 07/454, Ghent University, Belgium.

McGill, J.I., and van Ryzin, G.J. (1999). “Revenue Management: Research Overview and Prospects.” Transportation Science, 33 (2), 233-256.

McNeese-Smith, D.K. (1999). “A content analysis of staff nurse descriptions of job satisfaction and dissatisfaction.” Journal of Advanced Nursing, 29 (6), 1332-1341.

Medard, C.P., and Sawhney, N. (2004). “Airline crew scheduling: From planning to operations.” Carmen Systems AB, Güteborg, Sweden, Carmen Research and Technology Report CRTR-0406.

Mercier, A., and Soumis, F. (2007). “An integrated aircraft routing, crew scheduling and flight retiming model.” Computers & Operation Research, 34, 2251-2265.

Phillips, D. and Irwin, N. (2000). “Flying into a storm of delays.” The Washington Post 103, juli 17, A01.

Pinol, H., and Beasley, J.E. (2006). “Scatter Search and Bionomic Algorithms for the aircraft landing problem.” European Journal of Operational Research, 171, 439-462.

Reeves, C.R. (1993). “Modern Heuristic Techniques for combinatorial problems.” Oxford, U.K., Blackwell Scientific Publication, 196p.

X



Schaefer, A.J., Johnson, E.L., Kleywegt, A.J., and Nemhauser, G.L. (2005). “Airline Crew Scheduling Under Uncertainty.” Transportation Science, 39 (3), 340-348.

Sherali, H.D., Bish E.K., and Zhu X. (2006). “Airline fleet assignment concepts, models, and algorithms.” European Journal of Operational Research, 172, 1-30.

Smith, H.L., Hood, J.N., Waldman, J.D., and Smith, V.L. (2005). “Creating a Favorable Practice Environment for Nurses.” Journal of Advanced Nursing, 35 (12), 525-532.

SN Brussels Airlines (2006). Operations Manuel (OM). SN Brussels Airlines, Brussels, Belgium.

Stojkovic´, M., Soumis, F., and Desrosiers, J. (1998). “The Operational Airline Crew Scheduling Problem.” Transportation Science, 32 (3), 232-245.

Stojkovic´, G., Soumis, F., Desrosiers, J., and Solomon, M.M. (2002). “An optimization model for a real-time flight scheduling problem.” Transportation Research, 36, 779-788.

Thiel, M.P. (2004). “Team–oriented Airline Crew Rostering for Cockpit Personnel.” Proceedings of the 9th International Conference on Computer-Aided Scheduling of Public Transport (CASPT 2004), 1-26.

Van Ryzin, G., and McGill, J. (2000). “Revenue Management Without Forecasting of Optimization: An Adaptive Algorithm for Determining Airline Seat Protection Levels.” Management Science, 46 (6), 760-775.

XI



Vance, P.H., Barnhart, C., Johnson, E.L., and Nemhauser, G.L. (1997). “Airline Crew Scheduling: A New Formulation and Decomposition algorithm. “Operations Research, 45 (2), 188-200.

Yan, S., Tang, C.H., and Lee, M.C. (2007). “A flight scheduling model for Taiwan airlines under market competitions.” Omega, 35, 61-74.

Smith, H.L., Hood, J.N., Waldman, J.D., and Smith, V.L. (2005). “Creating a Favorable Practice Environment for Nurses.” Journal of Advanced Nursing, 35 (12), 525-532.

XII



10 Bijlage De eerste drie bijlagen (bijlage A, bijlage B en bijlage C) presenteren een overzicht van de factoren verantwoordelijk voor een gelijkverdeelde werkdruk per captain. In bijlage A, staan de resultaten van het scatter search algoritme. In bijlage B, staan de resultaten van SN Brussels Airlines vóór operaties. Bijlage C presenteert de resultaten na operaties van SN Brussels Airlines.

10.1 Bijlage A Pre - Operations (SS) Blok uren

# Nightstops

Duty time

# dagen vrijaf

65 40 41 62 50 56 63 50 62 36 61 68 59 60 55 59 55 57 41 61 56 64 39 26 59

8 5 4 7 7 7 7 6 7 4 7 7 6 5 7 5 6 5 5 7 8 8 4 2 6

116 121 79 114 96 109 111 93 110 65 115 107 114 116 107 116 134 125 76 114 109 111 93 50 113

12 13 17 12 13 13 13 15 14 19 13 12 10 13 12 12 10 11 18 12 12 12 18 22 13

Captain 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

XII


26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

Blok uren 58 58 38 48 64 52 57 59 49 37 62 53 63 60 56 58 61 58 57 57 59 55 47 54 61 39 36 56 19 55 51 43 60 65 48 54 42 58 68 24 60 41 60 33 57 62 57 50 60 58

# Nightstops 7 6 5 3 7 4 8 7 3 4 8 4 7 6 6 7 8 7 7 7 5 7 6 8 8 6 4 8 1 6 4 4 8 6 4 7 4 8 7 1 8 4 8 4 6 6 6 5 6 7

Duty time 110 111 71 110 115 127 118 114 121 131 108 100 132 106 117 107 114 108 116 110 114 120 80 103 105 71 73 124 63 111 135 86 107 113 101 107 75 105 112 69 107 83 111 125 116 113 121 134 108 107

XIII


# dagen vrijaf 10 11 18 13 10 11 11 15 12 12 12 15 12 14 13 12 13 11 9 12 15 11 16 12 13 16 19 9 19 11 9 17 13 14 14 10 18 11 14 16 13 20 9 12 13 15 13 13 13 12


76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

Blok uren 52 46 57 48 58 40 58 45 60 61 59 56 63 56 41 60 45 58 45 63 63 40 43 56 53 54 63 58 59 62 37 46 46 35 55 59 52 36 59 39 57 60 60 48 50 60 56 57 60 38

# Nightstops 4 5 6 3 6 3 6 4 7 7 9 7 7 6 6 7 6 7 5 6 7 4 4 5 7 7 6 8 7 7 4 5 4 5 7 6 7 5 9 2 7 5 7 5 5 7 8 5 7 5

Duty time 93 83 108 105 110 71 113 89 109 111 107 115 120 104 79 107 85 105 101 117 111 64 122 114 110 106 130 113 113 106 72 82 97 71 115 105 104 73 110 71 118 105 119 112 93 108 108 117 108 68

XIV


# dagen vrijaf 16 18 13 14 14 19 12 17 11 11 13 10 13 15 14 12 15 13 14 13 13 22 11 11 13 15 13 13 11 12 17 16 14 18 12 11 14 16 10 19 11 13 11 17 16 12 12 11 13 17


126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142

Blok uren 57 49 56 62 49 59 58 34 44 58 58 55 56 59 60 56 42

# Nightstops 5 6 6 8 6 6 7 4 4 8 7 5 8 9 7 4 5

Duty time 106 92 121 114 102 112 108 57 87 109 127 109 111 106 115 134 80

XV


# dagen vrijaf 13 12 10 14 15 13 12 20 14 14 11 13 12 11 14 12 18



10.2 Bijlage B Pre - Operations (SNBA) Blok uren

# Nightstops

Duty time

TAFB

54,83 19,75 58,25 65,75 60,58 70,25 47,25 61,08 41,17 74,00 72,58 69,17 72,83 74,75 63,00 44,17 54,58 36,08 60,83 61,58 65,17 35,92 9,83 63,50 65,50

4 4 8 8 8 9 6 8 4 9 8 7 6 8 8 7 7 3 8 8 9 4 0 10 7

139,92 62,25 134,08 112,08 120,75 133,58 118,92 126,17 68,92 119,83 131,75 158,42 128,33 136,67 134,25 113,00 98,92 78,33 121,58 127,17 127,00 68,25 39,17 110,67 149,17

142,75 94,92 211,25 251,08 185,67 271,17 172,83 215,42 110,92 247,25 248,00 216,75 204,50 208,00 214,75 173,83 197,08 115,75 213,25 220,92 244,50 136,50 16,17 245,58 217,42

Captain 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

XVI


26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

Blok uren 64,08 25,17 37,08 72,50 27,83 66,50 70,42 36,00 45,25 63,92 45,25 72,17 72,67 0,00 67,00 70,33 73,08 65,92 57,33 51,42 69,42 35,75 50,58 71,67 30,08 46,00 59,17 18,58 56,92 36,67 42,25 61,25 74,17 42,50 73,33 38,75 71,67 54,92 11,50 67,75 37,67 66,33 13,75 54,08 65,75 73,67 33,67 70,33 62,75 32,50

# Nightstops 7 3 5 7 1 6 5 4 3 6 5 7 9 0 9 8 8 11 6 6 8 4 10 10 4 4 6 1 5 2 4 9 9 5 9 2 10 6 1 6 4 9 0 6 9 8 4 7 8 4

Duty time 126,50 59,42 103,75 143,83 62,50 139,75 122,92 92,08 83,08 141,17 101,58 128,42 130,50 0,00 140,42 145,50 132,42 131,83 121,33 120,83 127,83 101,42 120,75 130,58 77,58 74,42 138,75 70,33 114,92 76,67 95,42 127,08 128,58 104,92 135,42 74,58 131,83 142,08 51,75 128,08 84,58 127,25 20,75 112,50 120,92 122,42 57,83 121,50 130,00 101,33

XVII


TAFB 195,33 97,75 107,92 223,00 47,58 179,58 179,67 113,08 104,08 189,17 141,42 220,75 248,33 0,00 225,42 231,75 252,33 268,92 171,58 166,75 226,92 112,92 218,92 268,17 114,58 127,75 185,25 50,67 158,00 86,83 127,42 219,42 238,42 133,83 251,17 77,67 249,33 178,00 27,83 203,25 124,00 278,17 20,75 143,92 236,33 228,67 113,33 222,25 208,00 100,50


76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

Blok uren 43,92 52,17 50,25 0,00 38,33 56,42 49,17 63,75 65,92 72,58 65,58 74,92 62,00 19,67 72,42 41,33 72,00 62,58 66,25 66,33 28,58 36,00 66,58 71,75 69,67 66,08 71,00 67,58 69,50 32,83 44,08 47,50 52,00 64,92 62,33 0,00 27,33 67,25 32,92 60,67 70,50 73,08 47,33 49,83 70,08 64,58 48,50 64,58 39,33 66,25

# Nightstops 5 7 7 0 4 5 6 7 9 9 6 9 7 2 9 6 8 6 9 8 4 3 9 9 7 10 7 10 7 4 5 6 5 6 5 0 2 7 3 7 6 9 6 6 7 8 6 7 4 7

Duty time 72,25 114,50 102,75 45,00 89,08 136,42 103,83 143,25 135,58 119,08 136,00 144,33 127,83 50,25 124,42 84,83 132,08 103,50 134,83 115,17 61,92 111,25 119,75 124,00 137,83 123,08 142,67 138,33 119,83 82,33 99,17 90,08 127,42 131,08 141,33 0,00 72,50 138,08 82,75 135,92 130,42 122,25 105,42 114,58 144,92 152,42 113,17 132,33 65,25 135,00

XVIII


TAFB 143,58 187,83 188,83 0,00 114,08 176,33 176,17 215,00 254,00 254,42 181,83 235,75 222,50 63,75 253,25 163,17 220,25 183,33 241,17 214,42 109,92 92,17 234,75 243,25 212,58 249,83 219,92 267,92 199,92 113,75 138,00 152,17 147,75 182,92 173,75 0,00 73,17 217,17 100,83 186,75 195,92 260,42 183,33 156,75 213,08 227,17 154,42 205,75 97,50 203,58


126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142

Blok uren 50,75 39,08 69,42 47,42 55,92 64,00 0,00 36,75 55,17 44,92 74,67 74,67 69,25 73,92 48,67 34,75 66,67

# Nightstops 6 6 5 5 7 8 0 4 6 2 11 9 9 10 6 3 10

Duty time 110,00 110,33 119,75 117,08 129,67 143,00 0,00 81,83 116,83 118,08 122,75 121,42 137,25 136,08 123,33 61,42 119,50

XIX


TAFB 186,67 146,25 188,42 141,42 191,25 190,58 0,00 97,42 174,00 111,42 271,50 237,92 220,08 254,17 175,17 105,50 246,25



10.3 Bijlage C Post - Operations (SNBA) Blok uren

# Nightstops

Duty time

TAFB

51,63 29,62 57,67 62,18 63,48 65,18 46,93 66,33 39,42 70,57 60,42 75,60 69,17 60,55 65,73 37,08 56,15 61,38 65,67 34,42 63,75 34,65 22,70 60,10 73,22

4 5 8 8 8 9 6 9 4 9 8 8 6 7 9 7 7 3 8 9 9 4 1 10 8

137,97 56,95 128,60 111,05 119,78 131,78 99,42 124,20 68,93 117,87 125,12 150,03 126,82 121,42 129,78 110,18 103,17 78,57 124,10 123,18 127,85 68,37 38,53 109,82 144,05

141,18 129,58 208,60 250,50 195,52 270,30 179,10 242,87 110,95 245,22 234,73 254,35 202,75 175,25 252,20 155,37 201,98 115,90 216,10 244,93 248,08 136,87 52,07 245,22 257,98

Captain 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

XX


26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

Blok uren 63,18 23,13 45,68 66,97 26,10 59,32 65,38 45,13 42,62 43,52 45,75 59,75 54,67 0,00 72,68 67,98 65,75 67,53 55,32 60,85 61,58 44,08 46,68 68,67 32,23 42,37 63,18 11,42 50,12 50,35 38,75 64,02 70,47 39,48 69,70 26,77 68,72 64,82 11,22 55,23 41,43 60,53 17,75 43,37 62,65 59,38 33,82 67,15 58,27 45,17

# Nightstops 7 3 5 8 1 6 5 5 3 4 5 6 7 0 7 8 8 11 6 7 8 6 10 10 5 4 6 0 5 2 4 8 9 5 9 0 10 8 1 5 5 9 0 5 9 8 4 7 8 5

Duty time 133,40 60,47 114,00 140,58 69,08 123,77 120,32 85,32 80,62 83,25 98,45 107,58 93,60 0,00 127,73 137,12 129,12 131,83 116,72 117,17 120,27 82,12 107,10 128,65 66,37 74,28 135,42 64,52 112,97 94,02 100,00 122,85 130,25 104,42 134,38 55,48 136,98 128,73 51,83 125,52 77,93 122,37 33,97 94,87 120,48 120,50 60,88 121,15 127,43 94,08

XXI


TAFB 195,25 98,88 120,73 233,27 69,88 177,32 177,67 146,08 102,85 133,68 145,57 189,08 191,55 0,00 226,28 231,25 242,35 275,00 174,97 202,23 219,90 156,72 217,58 265,92 129,00 127,65 197,68 18,52 149,15 100,97 134,60 213,88 240,92 133,07 250,30 35,15 254,78 228,92 27,55 176,18 152,10 275,13 29,95 113,33 238,18 216,73 115,95 222,32 205,90 129,87


76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

Blok uren 39,42 51,97 47,42 0,00 36,65 59,52 43,85 50,73 65,70 64,58 69,03 64,28 41,97 19,00 65,28 42,80 72,02 58,42 72,92 62,75 26,87 29,08 59,40 71,88 65,48 60,55 56,43 70,33 65,60 47,33 45,02 44,88 13,58 59,05 48,93 0,00 31,47 67,25 37,87 70,97 68,63 69,78 39,98 58,97 70,32 70,02 46,02 65,15 37,32 58,75

# Nightstops 5 7 7 0 4 6 6 6 10 9 6 9 5 2 9 6 8 7 10 8 4 2 7 8 7 10 6 11 7 5 6 6 0 6 3 0 2 8 4 8 7 9 4 8 8 8 6 7 4 7


Duty time 66,92 121,52 102,20 0,00 88,80 128,80 104,13 119,32 118,40 112,88 129,13 133,70 73,93 51,78 117,20 79,35 107,23 133,98 113,48 61,10 106,45 117,62 123,60 135,27 120,15 126,83 132,38 120,50 81,65 85,60 89,60 67,50 127,40 93,37 0,00 64,00 142,67 75,45 127,77 124,63 123,08 68,48 98,22 137,62 146,10 112,10 129,47 62,87 129,33

XXII

TAFB 138,22 181,62 188,23 0,00 113,42 201,22 164,75 179,47 268,02 248,55 191,83 234,50 159,22 63,72 246,23 165,17 228,32 202,55 270,62 213,90 109,62 72,50 204,33 236,32 210,67 248,50 198,47 294,92 200,17 156,73 152,22 151,50 18,42 179,18 132,00 0,00 84,13 225,40 120,83 222,23 223,98 260,47 145,52 210,72 227,67 239,58 153,92 212,98 96,68 198,23


Blok uren 49,12 40,45 70,02 60,60 64,43 57,97 0,00 39,63 52,75 45,48 67,63 56,35 49,02 70,13 38,25 33,28 62,85

126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142

# Nightstops 6 6 4 6 9 9 0 5 6 2 10 7 7 10 5 3 10


Duty time 109,90 114,95 124,85 111,03 122,67 123,12 0,00 81,12 115,77 111,38 115,00 104,25 99,52 134,85 86,22 60,95 117,77

TAFB 187,43 150,93 183,13 177,12 243,60 196,27 0,00 130,23 173,10 115,73 255,35 188,98 172,12 253,35 139,07 105,15 245,12

10.4 Bijlage D In deze bijlage wordt een exhaustief overzicht gegeven van de regels toepasselijk op de case SN Brussels Airlines (de flight time limitations).

Een volledige lijst van alle soorten

reguleringen staat in de elektronische bijlage. Flight time limitations De uitgebreide regels: Definities 1) Flight duty period:

2) Rest period:

Periode die begint vanaf het moment dat een CM incheckt voor de flight duty na een periode van rust tot het moment dat hij zijn vlucht of zijn opeenvolging van vluchten heeft uitgevoerd samen met de geassocieerde taken. Periode waarin CM vrij is van verplichtingen en waarbij deze CM wordt voorzien van huisvesting

XXIII


3) Flight time:

4) Crewmember (CM):

5) Flight crewmember: (FCM) 6) Cabin crewmember: (CCM) 7) Base (Hoofdkwartier):

8) Ground duty:


Vanaf het moment dat het vliegtuig beweegt uit eigen krachten met als doel op te stijgen tot het moment dat het vliegtuig tot stilstand komt na de landing. Een persoon die bepaalde taken moet vervullen aan boord van een vliegtuig tijdens flight time Een CM die houder is van een licentie en die verantwoordelijk is voor het besturen van het vliegtuig Een CM die als functie heeft het zorgen voor veiligheid en comfort voor de passagiers De luchthaven waar het vliegtuig gevestigd is of de luchthaven vanwaar de crew in normale omstandigheden vertrekt Verschillende taken op vaste grond

Bron: Operations Manuel 2006, SN Brussels Airlines

Bedrijfsregels Regels & Wetgeving Algemene voorwaarden En definities 1) Medium Haul flight (MH Sector)

FCM

CCM

Geografische limieten:

Idem als FCM

2) Long Haul flight (LH Sector)

Volledige vlucht of deel van vlucht buiten de hierboven opgegeven geografische limieten

Idem als FCM

3) Vermeerderde (Augmented) crew

Met 1 of 2 extra FCM’s

Niet van toepassing

Tussen 20° - 70° Noorderbreedte • Tussen 30° Westerlengte en 40° Oosterlengte Tijdsverschillen niet in rekening, altijd LTB (local time at base) •

XXIV



4) Hoofdkwartier, Missie

Tussen 15 opeenvolgende dagen en 6 maanden op missie dan zal deze plaatst de Hoofdkwartier zijn i.p.v. Brussels National Airport

Idem als FCM

5) Kalender

Calendar day, Duty day, Calender week, Calendar month, Calender year, IATA year => zie chapter 7 FOM (7.2.1.1.2.3)

Idem als FCM

6) Timing

7) Duty • Blank day

1. WOCL = 2:00 – 6:00 LTB (alleen voor MH flights) 2. Morning flight = 6:01 – 7:30 LT 3. Day flight = 7:31 – 13:30 LT 4. Afternoon flight = 13:31 – 14:30 LT 5. Evening flight: • MH = 14:31 – 22:00 LTB • LH = 14:31 – 22:00 LT 6. Night flight: • MH = 22:01 – 6:00 LTB (zonder inbreuk op WOCL) • LH = 22:01 – 6:00 LT 7. Local night: • Van 22:00 tot 8:00 8 opeenvolgende uren tussen 22:00 en 8:00 (alleen LH Sector)

1. Morning flight = 6:01 – 7:30 LT 2. Day flight: • MH = 7:31 – 13:30 LT • LH = 4:01 – 20:00 LT 3. Afternoon flight = 13:31 – 14:30 LT (alleen MH) 4. Evening flight = 14:31 – 22:00 LT (alleen MH) 5. Night flight: • MH = 22:01 – 6:00 LT • LH = 20:01 – 4:00 LT 6. Local night: • Van 22:00 tot 8:00 • 8 opeenvolgende uren tussen 22:00 en 8:00 (alleen LH Sector)

Een kalender dag, zonder geprogrammeerde duty, maar de FCM moet wel ter beschikking staan van SN Brussels Airlines

Niet van toepassing in deze categorie, wel bij off-duty

•

Break

Periode vrij van duties in een goedgekeurde pairing die meetellen als duty

Idem als FCM, maar voor CCM

•

Buffer time

Tijd tussen einde van een rest period en begin van een duty


•

Closing time

Tijd waar duty eindigd


•

Reporting time

Tijd wanneer FCM zich moet


XXV



aanmelden

•

Deadheading

Transport van een FCM als een passagier naar een andere luchthaven (exclusief tijd van luchthaven naar hotel)


•

Duty

Elke taak die een FCM moet voldoen op vraag van zijn werkgever


•

Duty time (DT)

Tijd waar FCM ter beschikking staat van zijn werkgever en deze duty time bestaat uit: 1. Break 2. Flight duty time 3. Ground duty 4. Standby/Reserve 5. Deadheading 6. Flight duty zonder effectieve vlucht (omwille van afgelaste vlucht na aanmeldingsuur) De duty time = Closing time – Reporting time


•

Flight duty

Een vlucht of een serie vluchten, inclusief voorgaande, intermediaire en volgende duties die noodzakelijk zijn om de betreffende vlucht of serie vluchten te voldoen


•

Flight duty time (FDT)

Berekend van Reporting time tot closing time (= Closing – reporting) en bestaat uit: 1. Break 2. Flight time 3. Pre-flight en post-flight duties (die in de reporting en closing time zitten) 4. Transit time 5. Tijd tussen reporting time van de afgelaste vlucht en die nieuwe effectieve vlucht als de FCM een nieuwe vlucht

XXVI




moet voldoen 6. Deadheading voor een vlucht Idem als FCM, maar voor CCM

•

Flight time in Planning / Flight Hrs in planning (FT)

•

Flight time in Periode die begint vanaf het Operations / Flight moment dat het vliegtuig begint Hrs in operations(FT) te bewegen met als doel opstijgen

Periode van STD tot STA


en eindigt als het vliegtuig geparkeerd is of de motoren uit zijn

•

Ground duty

•

Irregularities

•

Pairing

•

Reserve / Standby

•

Sector

•

Stick time

•

Time away from Base (TAFB)

•

Transit time

Idem als FCM, maar voor CCM Alle duties op vaste grond exclusief reserve en standby duties (vb; Cursussen, simulator, medische testen, …) Idem als FCM, maar voor CCM Het gevolg van onvoorziene technische en operationele zaken Idem als FCM, maar voor CCM Een combinatie van duties en rest periods waarbij de CM continu weg is van huis (tijd vanaf reporting time tot closing time van laatste duty) Idem als FCM, maar voor CCM FCM staat ter beschikking van zijn werkgever klaar om een mogelijke duty te voldoen Idem als FCM, maar voor CCM één enkele vlucht inclusief opstijgen en landen Niet van toepassing De effectieve tijd van de vlucht doorgebracht in controle van het vliegtuig (Van toepassing bij vermeerderde crew) Idem als FCM, maar voor CCM Tijd van de pairing

Idem als FCM, maar voor CCM Tijd op vaste grond tussen 2

XXVII



sectoren, zonder dat er een break of rest period wordt gegeven. Transit time = Start volgende flight time – Einde flight time

8) Off – Duty • Free day

•

Idem als FCM, maar voor CCM FCM is vrij van alle duties en FCM moet niet bereikbaar zijn.

Leave

Idem als FCM, maar voor CCM Annual, seniority, special en Legal holidays

•

Rest time

•

Wekelijks verlof

•

Blank day

Idem als FCM, maar voor CCM Periode die onmiddellijk na duty time start om genoeg rust te voorzien. In deze periode is de FCM dan ook vrij van alle duties. Twee vrije dagen , inclusief 2 locale nachten

Idem als FCM, maar voor CCM, maar op het Hoofdkwartier, behalve bij missies.

Niet van toepassing in de categorie off-duty. Wel in de categorie duty

Een kalender dag, zonder geprogrammeerde duty, maar de FCM moet wel ter beschikking staan van SN Brussels Airline

Medium Haul flights (MH Sector) 1) Duty MH Sector; Planningsfase • Reporting, Closing and Transit times

1. Flight duty of DH by air: 1. Flight duty of DH by air: Base Outstation

Reporting STD -70min STD – 40min

Closing STA + 30min STA + 20min

2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty 3. Minimum Transit times: Geen wijziging 40 min

Vliegtuig wijziging 60 min

XXVIII

Base Outstation

Reporting STD - 60min STD - 40min

Closing STA +30min STA +20min

2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty 3. Minimum Transit times: Geen wijziging Vliegtuig wijziging 40 min 60 min Opm: De maximale transit time in combinatie met een flight duty is 2h30 tussen STA van eerste vlucht en STD van tweede vlucht


•

Ground duty

•

Reserve duty

•

Deadheading

•

Flight time Limitations Per period

2) Duty MH Sector; Preoperatie periode • Principe


≤ 9 opeenvolgende uren en bestaat uit afzonderlijke taken Ground + flight duty ≤ 9 opeenvolgende uren

≤ 12 opeenvolgende uren Voor FD DH = FD voor berekening max. FDT en rest period

Na FD FDT + DH = 1 duty met max 15:30 opeenvolgende uren

Geïsoleerd DH ≤ 15:30 opeen – volgende uren

Zie vorige tabel xx

1. Na publicatie van de duty roster kan een andere FDT worden toegewezen op voorwaarde dat de gepubliceerde vrije dagen ongewijzigd blijven. 2. Voor regionale vliegtuigen alleen geldt dat de flight duty roster mag worden gewijzigd minder dan 3 dagen voor de dag van operatie (inclusief die operatie dag), zolang de nieuwe flight duty niet meer dan 1 uur start of eindigt voor of na de geplande flight duty. 3. Bij “force majeur” mogen de principes worden aangepast na toestemming van de DFO

≤ 9 opeenvolgende uren en elke afzonderlijke taak telt voor 3 uur Ground + flight duty ≤ 9 opeenvolgende uren met de flight duty komende na de ground duty ≤ 5 opeenvolgende uren Voor FD DH = FD voor berekening max. FDT en rest period

Na FD FDT + DH = 1 duty met max 15:00 opeenvolgende uren

Zie vorige tabel xx

Niet van toepassing

Niet van toepassing

•

Opmerking

3) Duty MH Sector

XXIX

Geïsoleerd DH ≤ 15:00 opeen – volgende uren


Operatie periode • Principe

•

Times


1. Na publicatie van de duty roster kan een andere duty worden toegewezen op voorwaarde dat de gepubliceerde vrije dagen ongewijzigd blijven (behalve als de CM een handgeschreven toestemming verleent) 2. Er geldt dat de flight duty roster mag worden gewijzigd minder dan 3 dagen voor de dag van operatie (inclusief die operatie dag), zolang de nieuwe flight duty niet meer dan 1 uur start of eindigt voor of na de geplande flight duty. 3. Er geldt dat de flight duty roster meer dan 3 dagen voor de geplande duty mag worden gewijzigd. 3. Bij “force majeur” mogen de principes worden aangepast na toestemming van de DFO

Niet van toepassing

1. Flight duty of DH by air, inclusief min. 1 take-off : Base Outstation

Reporting STD of ETD – 70 min STD of ETD – 40 min

Closing time Einde vlucht + 30 min Einde vlucht + 20 min

2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty • Transit = min. vereiste voor veilige operatie 3. Flight duty of DH by air, zonder take-off : Closing time is 30 minuten nadat de motoren uitgezet zijn OF 30 minuten nadat de crew geïnformeerd is over een rest time als de reporting time niet

XXX

1. Flight duty of DH by air, inclusief min. 1 take-off : Base Outstation



2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty • Transit = min. vereiste voor veilige operatie 3. Flight duty of DH by air, zonder take-off : Closing time is 30 minuten nadat de motoren uitgezet zijn OF 30 minuten nadat de crew geïnformeerd is over een rest time als de reporting time niet gevolgd is door het aanzetten



gevolgd is door het aanzetten van de motoren

•

Flight duty

Idem als FCM, maar voor CCM •

•

•

4) Rest period MH Sector Planning en preoperatie • Berekende rest Time

Bij vertraging na vertrek, waardoor limieten onmogelijk worden, zullen de limieten met 2 uur worden verlengd Op Hoofdkwartier: duty ≤ 14 uur, als vertraging na vertrek dan ≤ 16 uur Als bij aflassen van een vlucht, 60 minuten later geen nieuwe vlucht wordt toegewezen dan is de FCM vrij van alle duties voor deze kalender dag. De dag erna kan hij wel worden toegewezen voor een andere vlucht als deze niet eindigt nadat de oorspronkelijk geplande duty zou geëindigd zijn.

Vrije dagen op Hoofdkwartier

•

Op Hoofdkwartier: duty ≤ 12 uur


Alleen planningsfase Base Rest time = (2*FDT) – 2 uur ≥ 13 uur Rest time = (2*FDT) + 3 uur ≥ 16 uur als FDT WOCL opdringt 1 uur buffer tussen einde rest period en begin volgende duty

Outstation FDT < 4 uur : Rest time = FDT ≥ 8 uur FDT ≥ 4 uur : Rest time = FDT ≥ 10 uur

OPM: Als de FDT volledig of gedeeltelijk valt tussen 20:00 LTB en 04:00 LTB dan is FDT = FDT + 2 uur

•

van de motoren

Aantal duty dagen 1 2 of 3 4 of 5

XXXI

Min. aantal vrije dagen 0 0 of 1 * 2 **

Base Rest time = (2*FDT) – 2 uur ≥ 13 uur Rest time = (2*FDT) + 3 uur ≥ 16 uur als nachtvlucht 1 uur buffer tussen einde rest period en begin volgende duty

Outstation FDT ≤ 4 uur : Rest time = FDT ≥ 8 uur FDT > 4 uur : Rest time = FDT ≥ 10 uur

OPM: Als de FDT volledig of gedeeltelijk valt tussen 20:00 LTB en 04:00 LTB dan is FDT = FDT + 2 uur

Aantal duty dagen 1 2 of 3 4 of 5 6 of 7 8 tot 10

Min. aantal vrije dagen 0 0 2 ** 3 4


6 of 7 8 tot 10


3 4

*1 als volgende duty LH is **2 vrije dagen omvat altijd 2 locale nachten

•

•

Deadheading • •

•

•

•

Ground duty

DH + FDT en FDT + DH = 1 Flight duty Geisoleerde DH: Rest = duty ≥ 8 uren

•

Rest = 12 uur

•

Als gevolgd door FD dan moet rest 1 locale nacht bevatten

Reserve

Duty with break

• •

Rest = 10 uur Rest = 12 uur als volgende duty een nachtvlucht is

•

Rest period op hoofdkwartier FDT 1 +break+ FDT 2 = FDT

•

5) Rest MH Sector Operatie periode

**2 vrije dagen omvat altijd 2 locale nachten

Base Als rest = 1*FDT ≥ 10 uur dan zal de volgende duty behouden blijven Als een vrije dag verminderd wordt door meer dan 1 uur (omwille van een schending van de voorgaande duty) dan zal een extra vrije dag gegeven worden bovenop de geplande vrije dagen

Outstation FDT < 4 uur : Rest time = FDT ≥ 8 uur FDT ≥ 4 uur : Rest time = FDT ≥ 10 uur

Duty with break: de geplande break kan met 1 uur verminderd worden (tot min 6 uur overblijven) en moet de WOCL omsluiten

OPM: • Als de FDT volledig of gedeeltelijk valt tussen 20:00

XXXII

•


•

Rest = 12 uur

•


•

Rest = 12 uur

Base Als rest = 1*FDT ≥ 10 uur (verlengbaar tot 12 uur) dan zal de volgende duty behouden blijven Als een vrije dag verminderd wordt door meer dan 1 uur (omwille van een schending van de voorgaande duty) dan zal een extra vrije dag gegeven worden bovenop de geplande vrije dagen

Outstation FDT ≤ 4 uur : Rest time = FDT ≥ 8 uur

FDT > 4 uur : Rest time = FDT ≥ 10 uur

OPM: • Als de FDT volledig of gedeeltelijk valt tussen 20:00 LTB en 04:00 LTB dan is FDT = FDT + 2 uur


•

6) Vrije dagen

•


LTB en 04:00 LTB dan is FDT = FDT + 2 uur Duty > 14 uur => tabel uitbreidende regels volgen

≥ 104 vrije dagen

• •

•

Wekelijks verlof •

•

•

Nationale Feestdagen

•

47 wekelijks verlof geprogrammeerd als vrije dagen 5 wekelijks verlof geprogrammeerd in combinatie met jaarlijks verlof

•

10 voor voltijds personeelslid. Wordt geprogrammeerd als vrije dag

•

•

•

•

≥ 104 vrije dagen en 10 nationale feestdagen Ziekte, parttime,… verminderen dit aantal proportioneel met 2 vrije dagen voor 5 dagen afwezigheid

47 wekelijks verlof geprogrammeerd als vrije dagen 5 wekelijks verlof geprogrammeerd in combinatie met jaarlijks verlof

10 voor voltijds personeelslid. Wordt geprogrammeerd als vrije dag Parttime personeelslid krijgt de feestdagen die vallen in de actieve periode. Als de actieve dagen variabel zijn dan worden alle feestdagen toegekend

Jaarlijks verlof •

• •

25 dagen, gecombineerd met wekelijks verlof zodat in totaal 30 dagen te verdelen valt in maximaal 2 perioden en tussen 2 perioden mag niet meer dan 16 maanden zitten Minimaal 2 perioden van 15 dagen Voorkeursperiode wordt toegekend via anciënniteit en familie situatie

•

•

•

XXXIII

25 dagen, gecombineerd met wekelijks verlof , verdeeld in 2 keer 16 opeenvolgende dagen en 1 periode van 9 kalender dagen. Tussen 2 periode mag niet meer dan 16 maanden zitten De eerste periode moet plaatsvinden tijdens een legale vakantie periode, behalve als de werknemer een andere periode voorstelt Voorkeursperiode wordt



toegekend via: i. Kinderen met schoolplicht ii. Gezamenlijke vakantie met partner iii. Anciënniteit

•

Anciënniteit – Verlof

Wordt aangevraagd en geprogrammeerd als jaarlijks verlof Jaren tewerkgesteld 2 jaar 4 jaar 6 jaar 9 jaar 14 jaar 16 jaar

7) Maandelijkse Vergoeding

8) Stand-by (STBY) Voorwaarden

anncieniteitsverlof + 1 dag + 2 dagen + 3 dagen + 4 dagen + 5 dagen + 6 dagen

Wordt aangevraagd en geprogrammeerd als jaarlijks verlof Jaren tewerkgesteld 2 jaar 4 jaar 6 jaar 9 jaar 14 jaar 17 jaar +

anncieniteitsverlof + 1 dag + 2 dagen + 3 dagen + 4 dagen + 5 dagen + 6 dagen

Deadheading niet opgenomen in berekening

Doel: ≤ 75 vluchturen per maand Elke uur boven dit doel wordt voor 100 % terugbetaald (dus per uur = maand verg. / 75) Deadheading niet opgenomen in berekening

1. Reserve duty (RS): • Geen RS programmeren voor een vrije dag • RS45: FCM heeft 45 minuten om zich te melden nadat men hem heeft geïnformeerd • RS120 • RS5: reserve in crewroom. Mag max. 2 uur duren na STA en moet voor 11:00 LTB. Maximum FDT = 10 uur of 8 uur als de FCM terugkwam van een nightstop • RS…. (alle types mogelijk) 2. Unsteady line (periode van max. 10 dagen RS en/of STBY) 3. Blank day:

1. Operationele stabiliteit: Geen alleenstaande RS programmeren 2. Blank line: • 4 maal per jaar zal een blank line van 10 opeenvolgende dagen worden toegewezen • Elke blank line moet worden gevolgd door 4 vrije dagen en moet worden voorafgegaan door minstens 2 vrije dagen • Twee blank periodes moeten gescheiden zijn met minstens 40 kalender dagen

XXXIV



Mag niet worden gepland 10 dagen voor of na een duty leave • De duty in deze periode kan een flight duty, reserve of blank day (BL) zijn 3. Reserve: • Binnen de 60 minuten opgeroepen • Als CCM onmiddellijk naar het vliegtuig gaat dan geldt STD – 20 min. • Als CCM niet onmiddellijk naar het vliegtuig gaat dan geldt STD – 30 min op plaats van pick-up 4. Blank Day (BL): CCM moet crewroom bereiken 120 minuten na mededeling •

Long Haul flights (LH Sector) 1) Duty LH Sector; Planningsfase • Reporting, Closing and Transit times

1. Flight duty of DH by air: Base Outstation

Reporting STD - 70min STD - 60min

Closing STA + 30min STA + 30min

2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty

•

1. Flight duty of DH by air: Base

Outstation

Reporting STD - 75min (A330) STD – 70min (A319) STD - 60min (A330) STD – 40min (A319)

Closing STA +30min

STA +30min

2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty

Ground duty ≤ 9 opeenvolgende uren en bestaat uit afzonderlijke taken.

XXXV

≤ 9 opeenvolgende uren en elke afzonderlijke taak telt voor 3 uur



Ground + flight duty ≤ 9 opeenvolgende uren

•

Ground + flight duty niet toegelaten voor LH Sector

Reserve duty ≤ 12 opeenvolgende uren

•

Deadheading Voor FD DH = FD voor berekening max. FDT en rest period

•

≤ 12 opeenvolgende uren Geen RS op de luchthaven RS75: Na berichtgeving moet CCM in 75 minuten aan boord kunnen zijn

Flight time Limitations Per period

Na FD FDT + DH = 1 duty met max 18 opeenvolgende uren

Geïsoleerd DH ≤ 18 opeen– volgende uren

Zie vorige tabel xx

Voor FD DH = FD voor berekening max. FDT en rest period

Na FD FDT + DH = 1 duty met max 18 opeenvolgende uren

Geïsoleerd DH ≤ 18 opeen– volgende uren

Zie vorige tabel xx

2) Duty LH Sector; Preoperatie periode • Principe 1. Na publicatie van de duty roster kan een andere FDT worden toegewezen op voorwaarde dat de gepubliceerde vrije dagen ongewijzigd blijven. 2. Bij “force majeur” mogen de principes worden aangepast na toestemming van de DFO

3) Duty LH Sector Operatie periode • Principe Niet van toepassing

XXXVI

Niet van toepassing

1. Na publicatie van de duty roster kan een andere duty worden toegewezen op voorwaarde dat de gepubliceerde vrije dagen ongewijzigd blijven (behalve als de CM een handgeschreven toestemming verleent) 2. Bij “force majeur” mogen de



principes worden aangepast na toestemming van de DFO

•

Times 1. Flight duty of DH by air, inclusief min. 1 take-off : Base Outstation



2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty • Transit = min. vereiste voor veilige operatie 3. Flight duty of DH by air, zonder take-off : Closing time is 30 minuten nadat de motoren uitgezet zijn OF 30 minuten nadat de crew geïnformeerd is over een rest time als de reporting time niet gevolgd is door het aanzetten van de motoren

•

1. Flight duty of DH by air, inclusief min. 1 take-off : Base

Outstation

Reporting STD – 75min (A330) STD – 70min (A319) STD – 60min (A330) STD – 40min (A319)

Closing time Einde vlucht + 30 min

Einde vlucht + 30 min

2. Ground duty of DH by ground: • Reporting = tijd van bijeenkomst • Closing = einde van duty • Transit = min. vereiste voor veilige operatie 3. Flight duty of DH by air, zonder take-off : Closing time is 30 minuten nadat de motoren uitgezet zijn OF 30 minuten nadat de crew geïnformeerd is over een rest time als de reporting time niet gevolgd is door het aanzetten van de motoren

Flight duty •

•

•

Bij vertraging na vertrek, waardoor limieten onmogelijk worden, zullen de limieten met 2 uur worden verlengd duty ≤ 20 uur, als vertraging na vertrek dan ≤ 22 uur Als bij aflassen van een vlucht, 60 minuten later geen nieuwe vlucht wordt toegewezen dan is de FCM vrij van alle duties voor deze kalender dag. De dag erna kan hij wel worden toegewezen voor een andere vlucht als deze niet eindigt nadat de oorspronkelijk

XXXVII

•


Fligth duty + reserve +operationele verlenging ≤ 20 uur • Idem als FCM, maar voor CCM

•



geplande duty zou geëindigd zijn.

4) Rest period LH Sector Planning en preoperatie • Berekende rest Time

Alleen planningsfase Base Rest time = (2*FDT) – 2 uur ≥ 16 uur Rest time = (2*FDT) + 3 uur voor nachtvluchten (zie tabel 7.2.12)

•

Outstation Rest time = (1,5*FDT) ≥ 16 uur Rest ime = (1,5*FDT) + 5 uur voor nachtvluchten (zie tabel 7.2.12) ≥ 16 uur

Base Rest time = (2*FDT) – 2 uur Rest time = (2*FDT) + 3 uur voor nachtvluchten

Vrije dagen op Hoofdkwartier Aantal duty dagen in pairing ≤ 3 dagen > 3 dagen

Min. aantal vrije dagen NAT AFI ASI 3 2 3 Duty dagen / 2 + 1 afgerond naar beneden

•

•

Één maal per maand mogen 2 LH flight duties worden gecombineerd zonder het minimaal aantal vrije dagen (Op verzoek van FCM mag dit ook een tweede maal)

•

•

•

Na elke pairing worden een aantal vrije dagen gegeven inclusief 2 locale nachten T.Z.A: Als een Aziatische vlucht wordt gevolgd door een Amerikaanse dan moet met 4 vrije dagen, inclusief 3 locale nachten programmeren en visa versa

Deadheading •

•

Outstation Rest time = (1,5*FDT) ≥ 16 uur Rest ime = (1,5*FDT) + 5 uur voor nachtvluchten ≥ 16 uur


• •

Ground duty


•

Rest = 12 uur

•

Rest = 12 uur

•


•


• •

Rest = 10 uur Rest = 12 uur als volgende duty een nachtvlucht is

•

Rest = 12 uur

Reserve

5) Rest LH Sector Operatie periode Base

Outstation

XXXVIII

Base

Outstation


Rest time = 1*FDT ≥ 14 uur Als een vrije dag verminderd wordt door meer dan 1 uur, maar minder dan 24 uur (omwille van een schending van de voorgaande duty) dan zal een extra vrije dag gegeven worden bovenop de geplande vrije dagen Als meer dan een volledige dag wordt geschonden dan zal de volgende duty worden afgelast. Een nieuwe duty kan worden toegewezen rekening houdend met de algemene principes In alle gevallen moet de geplande rest time gedekt worden door overblijvende vrije dagen


Rest time = 1*FDT ≥ 14 uur Uitbreidende regels mogen worden aangewend mits toestemming van de commandant

Rest time = 1*FDT ≥ 14 uur Als een vrije dag verminderd wordt door meer dan 1 uur, maar minder dan 24 uur (omwille van een schending van de voorgaande duty) dan zal een extra vrije dag gegeven worden bovenop de geplande vrije dagen Als meer dan een volledige dag wordt geschonden dan zal de volgende duty worden afgelast. Een nieuwe duty kan worden toegewezen rekening houdend met de algemene principes In alle gevallen moet de geplande rest time gedekt worden door overblijvende vrije dagen

Rest time = 1*FDT ≥ 14 uur Uitbreidende regels mogen worden aangewend mits toestemming van de commandant

OPM: • Als de FDT volledig of gedeeltelijk valt tussen 20:00 LTB en 04:00 LTB dan is FDT = FDT + 2 uur • Duty > 14 uur => tabel uitbreidende regels volgen

OPM: • Als de FDT volledig of gedeeltelijk valt tussen 20:00 LTB en 04:00 LTB dan is FDT = FDT + 2 uur

Idem als MH Sector

6) Vrije dagen • Wekelijks verlof •

Nationale Feestdagen

Idem als MH Sector

•

Jaarlijks verlof

Idem als MH Sector

Idem als MH Sector

Idem als MH Sector

•

•

XXXIX

25 dagen, gecombineerd met wekelijks verlof , verdeeld in 2 keer 15 opeenvolgende dagen en 1 periode van 5 kalender dagen. Tussen 2 periode mag niet meer dan 16 maanden zitten De eerste periode moet plaatsvinden tijdens een



•

•

legale vakantie periode, behalve als de werknemer een andere periode voorstelt Voorkeursperiode wordt toegekend via: iv. Kinderen met schoolplicht v. Gezamenlijke vakantie met partner vi. Anciënniteit

Anciënniteit – Verlof Idem als MH Sector

Idem als MH Sector

Idem als MH Sector

Idem als MH Sector

Idem als MH Sector

1. Operationele stabiliteit: Geen alleenstaande RS programmeren 2. Blank line: • 4 maal per jaar zal een blank line van 10 opeenvolgende dagen worden toegewezen • Elke blank line moet worden gevolgd door 4 vrije dagen en moet worden voorafgegaan door minstens 2 vrije dagen • Twee blank periodes moeten gescheiden zijn met minstens 40 kalender dagen • Mag niet worden gepland 10 dagen voor of na een duty leave • De duty in deze periode kan een flight duty, reserve of blank day (BL) zijn 3. Reserve: • Binnen de 75 minuten opgeroepen • Als CCM onmiddellijk naar het vliegtuig gaat dan geldt STD

7) Maandelijkse Vergoeding 8) Stand-by (STBY) Voorwaarden

XL



Als CCM niet onmiddellijk naar het vliegtuig gaat dan geldt STD – 30 min op plaats van pick-up 4. Blank Day (BL): CCM moet crewroom bereiken 120 minuten na mededeling •

9) Vermeerderde (augmented)crew •

• 10) Combinatie van MH en LH

Flight duty time limitations:

Zie 1) Duty LH Sector; Planningsfase (Reporting, Closing and transit times) Operationele procedures: niet van belang voor algoritme Niet van toepassing

11) Combinatie Europa – LH

Extra vrije dagen ertussen (zie supra)

1. Buffer Europa – LH: Aantal duty dagen 1 2 of 3 4 of 5 6 of 7 8 tot 10

Min. aantal vrije dagen 0 0 2 ** 3 4

**2 vrije dagen omvat altijd 2 locale nachten 2. Buffer LH – Europa: LH + rest + MH toegelaten Aantal duty dagen in pairing ≤ 3 dagen > 3 dagen

Min. aantal vrije dagen NAT AFI ASI 3 2 3 Duty dagen / 2 + 1 afgerond naar beneden

Bron: Operations Manuel 2006, SN Brussels Airlines

XLI

Niet van toepassing


XLII


Universiteit Gent Faculteit Economie en Bedrijfskunde. Personeelsplanning in de luchtvaartsector: Case Brussels Airlines. Bruce Fecheyr-Lippens

Recommend Documents