Case Study Januari 2010

   

Case Study

 

Januari 2010 

  Personeelsdiensten plannen bij de NS 

Wij zijn  de weg  kwijt 

Groep 4  Marije Stolwijk   Cliff Voetelink   Wieke de Wit    Vrije Universiteit   

1622854  1554506  1627910 

Inhoudsopgave  1. Inleiding ............................................................................................................................................... 2  2. Probleemomschrijving ......................................................................................................................... 3  2.1. De probleemomschrijving als input‐output relatie ...................................................................... 3  2.1.1 Input ....................................................................................................................................... 3  2.1.3 Voorwaarden ......................................................................................................................... 4  3. Modellering ......................................................................................................................................... 6  3.1 Probleemaanpak ........................................................................................................................... 6  3.2 Modelleren diensten per standplaats ........................................................................................... 6  3.2.1 Deelprobleem 1 ..................................................................................................................... 6  3.2.2 Deelprobleem 2 ................................................................................................................... 12  4. Alternatieve aanpak .......................................................................................................................... 18  4.1 Individuele aanpak ...................................................................................................................... 18  4.2 Groepsaanpak ............................................................................................................................. 19  5. Conclusie ........................................................................................................................................... 21  6. Bronvermelding ................................................................................................................................. 22  Appendix A ‐ Vragen en begrippen ....................................................................................................... 23  Appendix B ‐ Het planningsproces ........................................................................................................ 25  Appendix C ‐ Planningsregels ................................................................................................................ 26  Appendix D ‐ Literatuurstudie diensten toewijzen ............................................................................... 29  Appendix E ‐ Literatuurstudie roosteren ............................................................................................... 32  Appendix F ‐ Model deelprobleem 1 ..................................................................................................... 36  Appendix G ‐ Set Covering ..................................................................................................................... 38  Appendix H ‐ Uitbreiding per personeelstype ....................................................................................... 39     

 

1   

1. Inleiding    In 2001 heerste er onvrede over de personeelsplanning van de NS. Het rijdend personeel had moeite  met het in 1999 ontwikkelde concept “rondje om de kerk” in de nieuwe strategie ‘Bestemming klant’,  waarbij  personeel  vaker  wordt  ingezet  bij  dezelfde  route  zodat  zij  meer  affiniteit  krijgen  met  de  reizigers  op  het  traject  en  ter  bevordering  van  de  punctualiteit.  Het  probleem  was  echter  dat  sommige  trajecten  geliefder  zijn  dan  andere  (bijvoorbeeld  door  de  hoeveelheid  agressiviteit  op  de  route  of  door  het  soort  trein  waar  in  gereden  wordt).  De  indeling  van  de  diensten  werd  niet  als  eerlijk beschouwd. In de provincie Groningen werd wel positief op het rondje om de kerk gereageerd  maar  het  Amsterdamse  personeel  had  er  meer  moeite  mee.  Hierdoor  ontstond  er  verdeeldheid  onder  het  personeel.  Tegelijkertijd  waren  er  ook  tegenstellingen  in  de  belangen  van  verschillende  vakbonden,  de  Ondernemingsraad  (OR)  en  de  directie.  De  emoties  liepen  hoog  op  en  er  werd  besloten  dat  “Bestemming  klant”  toch  ingevoerd  zou  worden  maar  dat  de  OR‐NSR  een  nieuw  voorstel zou doen. De OR‐NSR nam vervolgens in november 2001 ORTEC en Basis&Beleid in de hand  om  hen  te  ondersteunen  bij  het  ontwikkelen  van  een  alternatief  productiemodel.  Een  productiemodel  is  een  planningsproces  waarbij  diensten  worden  gevormd  en  worden  toegewezen  aan standplaatsen. Vervolgens moeten van deze diensten ook nog roosters worden gemaakt.     De  nieuwe  strategie  ‘Lusten  en  lasten  delen’  werd  uiteindelijk  medio  juni  2002  gepresenteerd  en  goedgekeurd door alle partijen. Het productiemodel resulteerde vooral in voorwaarden die werden  opgenomen in de CAO zodat in de toekomst met dit model doorgewerkt kan worden.     Op dit moment woedt er weer een nieuwe discussie over de personeelsdiensten en is het tijd dat er  met een frisse blik naar het oude productiemodel wordt gekeken.   Wij  gaan  een  nieuw  productiemodel  ontwikkelen  met  behulp  van  beknopte  informatie  die  ORTEC  ons  heeft  geleverd.  Wij  buigen  ons  over  het  proces  van  het  maken  van  de  diensten.  Is  de  manier  waarop dat nu gebeurt optimaal of kan er met een kleine verandering een beter resultaat geboekt  worden?        

2   

2. Probleemomschrijving    Het nieuwe productiemodel is er vooral voor om de personeelsleden weer tevreden te krijgen over  hun  rooster.  Om  het  probleem  duidelijk  in  kaart  te  brengen  hebben  wij  ons  afgevraagd  wat  het  probleem  precies  is.  Wij  hebben  onszelf  een  aantal  vragen  gesteld  en  enkele  hiervan  ook  beantwoord. Deze zijn terug te vinden in Appendix A.     Gegeven is een dienstregeling en materieelplanning voor een bepaalde dag van de week. Voor deze  dag wordt meestel de dinsdag gekozen, omdat dit wordt gezien als de meest doorsnee dag van de  week.  De  dienstregeling  gaat  over  het  gehele  netwerk  van  de  NS  en  geeft  voor  elke  treinserie  de  geplande  aankomst‐  en  vertrektijd  van  deze  dag  op  alle  stations.  We  plannen  diensten  in  over  trajecten.  Voor  elk  traject  is  bekend  hoeveel  en  welk  soort  personeel  aanwezig  moet  zijn.  Zo  verkrijgen we een lijst met taken die op een dag moeten worden uitgevoerd. Een taak is een activiteit  die  op  een  bepaalde  plaats  en  tijd  door  een  bepaald  personeelstype  gedaan  moet  worden.  Een  voorbeeld  van  een  taak  is  dat  er  een  machinist  een  bepaalde  trein  op  een  gegeven  tijdstip  moet  besturen op treinserie 1700 met voldoende wegbekendheid op het traject Amersfoort‐Utrecht. Deze  lijst  met  taken  wordt  door  het  productiemodel  omgezet  in  diensten  die  aan  de  verschillende  standplaatsen worden toegewezen. Hierbij moet rekening worden gehouden met de vele restricties  die volgen uit CAO, arbeidstijden wet (ATW) en de ‘Lusten en lasten delen’‐regels. Elke standplaats  heeft nu een lijst met diensten die door deze standplaats moeten worden uitgevoerd. Deze diensten  zijn  nog  anoniem.  Op  elke  standplaats  is  vervolgens  een  personeelsplanner  die  de  verschillende  diensten  aan  personeel  toewijst.  Hierbij  moeten  dan  ook  weer  aan  verschillende  voorwaarden  worden voldaan.     Wij  delen  dit  probleem  op  in  twee  stappen.  De  eerste  stap  is  het  toewijzen  van  diensten  aan  verschillende  standplaatsen.  De  tweede  stap  is  het  omzetten  van  de  anonieme  diensten  naar  weekroosters  per  standplaats.  Voor  deze  tweede  stap  hebben  wij  geen  eigen  model  ontwikkeld,  maar slechts een literatuurstudie gedaan.  

2.1. De probleemomschrijving als input‐output relatie  De  eerste  stap  is  het  toewijzen  van  diensten  aan  verschillende  standplaatsen.  Kortweg  kan  dit  probleem  als  volgt  omschreven  worden  als  input  –  output  relatie  met  bijbehorende  voorwaarden  waar rekening mee moet worden gehouden.    2.1.1 Input   • Een  takenlijst  voor  iedere  dag  (weekdag,  zaterdag,  zondag)  waarop  voor  alle  taken  het  volgende is gespecificeerd:  o De tijdsduur die de taak in beslag neemt.  o Het tijdstip en dag waarop de taak aanvangt en waarop de taak eindigt.  o Begin‐ en eindlocatie van de taak.  o Het  benodigde  type  werknemer  dat  nodig  is  voor  het  uitvoeren  van  de  taak  (conducteur, machinist, etc.).  o Het type materieel waarop de taak wordt uitgevoerd.  o De treinserie en het traject waarop de taak wordt uitgevoerd.  o De taak vindt wel of niet plaats op een agressietraject/treinserie. 

3   

•

De  capaciteiten  van  elke  standplaats:  bekend  is  het  aantal  mensen  dat  hoort  bij  elke  standplaats,  hieruit  kan  het  maximaal  aantal  taken  worden  geschat  dat  kan  worden  uitgevoerd door elke standplaats.  

  2.1.2 Output   • Voor elke standplaats zijn anonieme personeelsdiensten toegekend voor een bepaalde dag,  waarbij een dienst bestaat uit een collectie taken voor een bepaald type werknemer die op  één dag moet worden uitgevoerd.     De  tweede  stap  is  het  toewijzen  van  deze  diensten  aan  personen.  Er  moeten  roosters  worden  gecreëerd.  Dit  is  weer  een  op  zichzelf  staand  probleem  dat  per  standplaats  wordt  opgelost.  De  output van de eerste stap is de input voor dit roosterprobleem. De output van dit roosterprobleem  zijn weekroosters per individu die alle diensten uit stap één omvatten.   2.1.3 Voorwaarden  Bij het bepalen van de oplossing van dit probleem moet rekening worden gehouden met:  • De Bemanningsregels  • De CAO regels  • De Lusten & Lasten regels  o Variatie in trajecten  o Verdeling A/B treinen  o Verdeling agressiewerk  o Variatie in materieelsoorten  • De roosterbaarheid van dienster per standplaats  o Goede verdeling van de weekenddiensten en weekdiensten  o De gemiddelde dienstlengte mag niet meer dan 8 uur bedragen  o Het aantal dag‐ en nachtdiensten, het aantal vroeg\laat diensten en de hoeveelheid  korte en lange diensten  • Commerciële doelstellingen   o Punctualiteit  o Groei  o Kwaliteit van product en arbeid  o Efficiëntie  • De robuustheid van het rooster  • De totale kosten  Er wordt in ons probleem geen rekening gehouden met stochastische factoren.    Voor uitleg van  bepaalde  begrippen  verwijzen  wij  naar Appendix A. De  uitgebreide  planningsregels  zijn te vinden in Appendix C.    Voor ons probleem  zijn  de dienstregeling en de  materieelinzet gegeven. Deze  worden  in  de  eerste  twee  fasen  van  het  planningsproces  gemaakt.  Het  planningsproces  bestaat  uit  het  maken  van  de  dienstregeling,  het  toewijzen  van  het  materieel  en  planning  van  personeel.  Dit  wordt  uitgelegd  in  Appendix B. 

4   

De  focus  bij  dit  nieuwe  productiemodel  ligt  erop  dat  er  voor  personeel  voldoende  variatie  is.  Het  probleem  zonder  de  regels  van  variatie  is  echter  ook  al  heel  complex.  Nederland  heeft  een  druk  bezet  spoorwegennet  met  zeer  veel  taken  die  elke  dag  moeten  worden  uitgevoerd.  Het  is  al  ingewikkeld om een toegelaten oplossing te vinden zonder al deze extra variatierestricties. Om een  begrip te krijgen van hoe personeelsplanning kan worden aangepakt, hebben wij een literatuurstudie  gedaan.  De  literatuurstudie  over  het  maken  van  diensten  is  te  vinden  in  Appendix  D  en  de  studie  over het roosteren staat in Appendix E.         

5   

3. Modellering  3.1 Probleemaanpak  Om tot individuele roosters te komen kunnen we twee stappen onderscheiden. Allereerst wijzen we  per standplaats diensten toe die door deze standplaats moeten worden uitgevoerd. Vervolgens is het  de taak om per standplaats deze anonieme diensten om te zetten in roosters. De eerste stap kunnen  we  verder  onderverdelen  in  twee  deelproblemen.  Deze  twee  deelproblemen  zullen  we  in  dit  hoofdstuk modelleren. Het omzetten van anonieme diensten in roosters modelleren we niet. 

3.2 Modelleren diensten per standplaats  Het toewijzen van diensten aan standplaatsen splitsen we op in twee deelproblemen:  1. Voor  elke  standplaats  wordt  bepaald  hoeveel  taken  er  op  welke  treinseries  worden  uitgevoerd  2. Aan elke standplaats wordt een lijst met diensten toegewezen    Deelprobleem  1  zorgt  ervoor  dat  het  probleem  in  deelprobleem  2  gemakkelijker  kan  worden  opgelost. Taken op bepaalde treinseries kunnen nu nog maar door een beperkt aantal standplaatsen  worden uitgevoerd in plaats van door elke mogelijke standplaats. Het aantal mogelijke diensten bij  deelprobleem 2 wordt nu aanzienlijk verkleind als we de resultaten uit deelprobleem 1 als restrictie  meenemen  bij  deelprobleem  2.  In  de  door  ons  bestudeerde  literatuur  wordt  er  geen  onderscheid  gemaakt in deze stappen. Wij denken echter dat we het probleem sneller kunnen oplossen door het  te  splitsen  in  deze  twee  deelproblemen.  Deelprobleem  2  gaan  we  oplossen  met  Set‐Covering  in  combinatie met kolomgeneratie. De oplossing wordt sneller gegenereerd als er meer restricties zijn.  3.2.1 Deelprobleem 1  In  deelprobleem  1  gaan  we  per  standplaats  bepalen  hoeveel  taken  deze  moet  uitvoeren  op  elke  serie. We willen dat de hoeveelheid passagieren geminimaliseerd wordt aangezien diensten met veel  passagieren  duur  zijn  en  vermeden  dienen  te  worden.  Als  er  een  treinserie  aan  een  standplaats  wordt  toegewezen,  worden  alle  bijbehorende  trajecten  ook  aan  deze  standplaats  gekoppeld.  Dat  betekent nog niet dat de standplaats op al die trajecten taken moet uitvoeren. Het aantal taken dat  een standplaats op een bepaalde serie moet uitvoeren nemen we mee naar deelprobleem 2.     Het model neemt nog niet alle ‘Lusten & lasten delen’‐regels mee. Bij het oplossen van het model zal  aan  de  meeste  restricties  die  daarbij  horen  wel  voldaan  worden.  Mochten  er  echter  problemen  ontstaan waardoor de oplossing die uit het model komt niet aan deze regels voldoet, dan kunnen we  deze problemen aanpakken door extra restricties in te voeren op het gebied waar dat nodig is. In ons  model hebben we de belangrijkste basisrestricties en twee efficiëntierestricties opgenomen. Daarna  presenteren  wij  de  zogenaamde  optionele  restricties  (uit  de  ‘Lusten  &  lasten  delen’‐regels)  die  eventueel  later  toegevoegd  kunnen  worden.  Ook  hier  kunnen  niet  alle  problemen  die  kunnen  ontstaan mee worden opgelost. Waarschijnlijk zullen er tijdens het oplossen van het model nieuwe  restricties moeten worden bedacht om uiteindelijk tot een toegelaten oplossing te komen. De vraag  is echter wel of dit een goede aanpak is. Het steeds opnieuw oplossen van een model kost veel tijd.  Wellicht  kost  het  zoveel  tijd  dat  het  beter  is  om  meteen  alle  restricties  mee  te  nemen  zodat  de  oplossing  meteen  toegelaten  is.  Zo’n  model  zal  echter  zó  groot  worden  dat  deze  misschien  niet 

6   

binnen  afzienbare  tijd  opgelost  kan  worden  of  helemaal  geen  oplossing  kan  geven.  Welke  aanpak  sneller en efficiënter is kan alleen blijken uit ervaringen in de praktijk.    We hebben ons model opgesteld als een gemengd geheeltallig lineair programmeringsprobleem. De  variabelen die het aantal taken per serie toegewezen aan een standplaats aangeven, zijn in praktijk  wel geheeltallig. In ons model hebben we deze echter gerelaxeerd omdat dit het probleem een stuk  eenvoudiger maakt en weinig effect heeft op de optimale waarde van deze beslissingsvariabelen.     Ons model moet drie keer worden opgelost: voor een weekdag, een zaterdag en een zondag.    1, … ,  standplaatsen.   Er zijn  1, … ,  treinseries te verdelen over    Model  De  output  van  ons  model  is  het  aantal  taken  dat  op  treinserie    moet  worden  uitgevoerd  door  ).   standplaats   (de    Beslissingsvariabelen                          0     1                        0                                                                                                   1, . . , ; 1, … ,     Invoer                                                         1       . 1                   0                                                                                                                                                                                                                                          1   0                                                                     100.000.000     We minimaliseren de kosten voor passagieren. De doelstellingsfunctie is:  min

 

7   

Als er door alle standplaatsen samen meer taken op een serie worden uitgevoerd dan er op die serie  zijn,  wordt  er  gepassagierd.  Elke  keer  dat  er  gepassagierd  wordt,  volgt  er  een  boete  ter  hoogte    afhankelijk van de serie waarop de taak wordt uitgevoerd.     Onder de restricties:                       

1     

Het aantal taken op serie   dat door alle standplaatsen samen gedaan wordt, moet groter zijn dan het  aantal taken dat volgens de dienstregeling op serie   uitgevoerd moet worden. Deze restrictie zorgt  er ook voor dat elke treinserie aan een standplaats wordt toegewezen.                            ,   2                      ,               · Deze  restricties  zorgen  ervoor  dat  als  een  bepaalde  treinserie  niet  gereden  wordt  door  een  standplaats, het aantal taken dat door deze standplaats wordt uigevoerd op deze serie gelijk is aan  nul.                     

  3     

         

               

                

 

Het aantal taken dat aan standplaats   wordt toegewezen mag niet meer zijn dan het aantal taken  dat per dag op standplaats   kan worden gedaan en er moeten minsten    taken worden uitgevoerd  door standplaats  .    0,25 

4    

                              

 

Iedere standplaats rijdt minstens 25% A‐treinen. Wij modelleren dit als volgt: het aantal taken dat op  een  standplaats  op  een  A‐trein  wordt  uitgevoerd  moet  minstens  25%  van  alle  taken  op  die  standplaats zijn.     Efficiëntie  restricties:  5     

 

              ,  

Alle  series  die  aan  een  standplaats  worden  toegewezen  moeten  minimaal  één  overeenkomstige  standplaats hebben zodat ze allemaal bereikbaar zijn zonder te passagieren.     We willen ervoor zorgen dat het aantal taken dat wordt uitgevoerd door standplaats   voordat een  andere  standplaats  bereikt  wordt, ongeveer  gelijk  is  aan  het  aantal  taken  dat  wordt  uitgevoerd  ná  deze  standplaats  tot  de  volgende  standplaats.  Aangezien  series  die  verder  gelegen  zijn  van  de  standplaats  minder  vaak  gereden  kunnen  worden,  zal  het  aantal  taken  in  verdere  series  kleiner  moeten zijn aan een fractie van het aantal taken dat wordt uigevoerd op series voorgaand aan deze  series. We introduceren de volgende gegevens:     

8   

 

,

                                  ,

 

   éé  

 

 

 

 

 

,

 

     

,

,

     

 

 

 

   

   

 

 

 

 

 

 

 

 

 

  

                

,

   

 

   

6    

 

   éé       

 

                               

   

     

    

    

    

 

                               

 

   

   

 

 

  

 

    

   

 

 

 

      

    

  , ,

 

,

  Deze restrictie leggen we met behulp van Figuur 1 uit.   

  FIGUUR 1: SCHEMATISCHE WEERGAVE BIJ RESTRICTIE (6)    Beschouw  de  standplaats  Groningen   die  de  taken  moet  doen  zoals  in  Figuur  1  te  zien  is.  De  zwarte lijnen komen overeen met verschillende treinseries. Dan willen we dat de som van de taken  op  de  treinseries  Zwolle  –  Amsterdam  (van   naar  een  standplaats  verder  weg  van  )  en  Zwolle  –  Maastricht (van   naar een standplaats verder weg van  ) kleiner of gelijk is aan een fractie van de  som van de taken met betrekking tot de treinseries Zwolle – Groningen (van   naar een standplaats  dichterbij  ).  Deze  fracties  worden  handmatig  gekozen  zodat  efficiëntie  optimaal  is.  Als  er  geen  restrictie zou gelden, wordt er een heel groot getal als fractie gekozen (zeg 100.000).     Een overzicht van dit model is te vinden in Appendix F.    De  efficiëntie  regels  zullen  ervoor  zorgen  dat  het  niet  optimaal  is  om  aan  iedere  standplaats  een  aantal taken van elke serie toe te wijzen. Het gevaar is dat er juist te weinig variatie per standplaats  zal zijn. Hiervoor hebben we optionele restricties.     

9   

Optionele restricties  We  formuleren  de  optionele  restricties  algemeen.  Wellicht  is  het  nodig  om  een  meer  specifieke  restrictie  voor  een  bepaalde  standplaats,  treinserie  of  traject  in  te  voeren.  Dit  zou  dan  ter  plekke  moeten worden geformuleerd.    Onze eerste optionele restricties betreffen de variatie in trajecten. Het is goed denkbaar dat er niet  genoeg  variatie  is  na  het  oplossen  van  het  model.  Hiervoor  introduceren  we  een  nieuwe  beslissingsvariabelen die bijhouden of een traject   wordt toegewezen aan standplaats  . Een traject  is een lijn tussen twee standplaatsen. Als er meerdere treinseries tussen twee standplaatsen rijden,  1, … ,  trajecten.  behoren die allemaal tot hetzelfde traject. Er zijn    Optioneel (1)  Beslissingsvariabelen  1                           0                                                                                                Invoer                                               

,         ,  

Als  treinserie    wordt  toegewezen  aan  standplaats    dan  worden  alle  trajecten  op  serie    aan  standplaats   toegewezen.      Optioneel (2)  1    

18 

Het gemiddeld aantal trajecten per standplaats moet minstens achttien zijn.     Optioneel (3)                 1   0                                                                                      9                                                           10

1

                         

 

3  Alle  standplaatsen  moeten  op  minstens  tien  trajecten  rijden.  Voor  drie  standplaatsen  mag  de     restrictie  worden  afgezwakt  naar  negen  trajecten.  Om  de  rekentijd  te  bevorderen  kunnen  de  worden  weggelaten  door  alleen  te  eisen  dat  elke  standplaats  minstens  tien  trajecten  moet  rijden 

10   

waarbij  er  dus  geen  uitzonderingen  zijn:  ∑ regel van ‘Lusten en lasten delen’.    Optioneel (4)            1   0                                                          1              

10   

 .  Dat  is  echter  niet  volgens  de  exacte 

 

Deze restricties zorgen ervoor dat minstens één van alle treinseries die door standplaats   gaan, aan  standplaats   wordt gekoppeld.     Optioneel (5)            1   0                                                   0,5 

                                

 

Maximaal 50% van de trajecten op een standplaats mag een agressietraject zijn. Het gaat hier dus om  trajecten  en  niet  om  treinseries.  Wij  modelleren  dit  hetzelfde  als  bij  A‐treinen  in  het  model:  het  aantal taken dat op een standplaats op agressietrajecten wordt uitgevoerd mag maximaal 50% van  het totaal aantal taken op die standplaats zijn.     Optioneel (6)  Beslissingsvariabelen                    1       0                                                                                                              1                        0                                                                                     Invoer   1                0                                                                                   1, … ,8                                             , ,     3                                       

 

4

 

1

              

3   Voor iedere standplaats geldt dat materieeltypes worden gereden uit tenminste vier clusters (er zijn  er  in  totaal  acht).  Maximaal  drie  standplaatsen  mogen  materieeltypes  rijden  uit  tenminste  drie    weg te laten en geen uitzonderingen   clusters. Wederom kan de rekentijd bevorderd worden de  toe te staan, in  dat geval  worden de restricties  ∑ moeten de restricties  ∑

4

1

 vervangen worden door ∑

11   

3  en ∑

3 

 weggelaten  en  4  

.  

  Optioneel (7)   In het boekje van de NS [1] staat een aantal restricties dat geldt op weekniveau. Wij kunnen een paar  restricties  in  dit  model  meenemen  op  dagniveau.  Dit  verschil  van  week  en  dag  zal  geen  groot  probleem  zijn  aangezien  de  vijf  doordeweekse  dagen  aan  elkaar  gelijk  zijn.  We  behandelen  de  percentages taken in dag‐ en nachtdiensten.    Beslissingsvariabelen                     

 

 

 

  

 

  

 

  Invoer      N. B.    

 

 

 

 

 

   

   

   

    

    

     

   

   

   

   

   

   

   

       

                ,    

                      

Het aantal nachttaken behorende bij treinserie   dat uitgevoerd wordt door alle standplaatsen moet  minstens zo groot zijn als het totaal aantal nachttaken behorende bij treinserie  . Uit (13) en (1) volgt  direct: ∑

              

  Optioneel (8)   

                         

 

 

Deze restrictie geeft een onder‐ en bovengrens aan het aantal taken in nachtdiensten. Hieruit volgen  in combinatie met (1) automatisch ook de grenzen voor de taken in de dagdiensten.   De  optionele  restricties  (7)  en  (8)  kunnen  uitgesplitst  worden  in  conducteurstaken,  machinisttaken  en andere taken. Dit is uitgewerkt in Appendix H.  3.2.2 Deelprobleem 2  In  deelprobleem  2  worden  de  diensten  gegenereerd  en  over  de  standplaatsen  verdeeld.  De  doelstellingsfunctie  van  deelprobleem  2  is  het  minimaliseren  van  de  kosten  van  de  diensten.  De  kosten hangen sterk samen met de efficiëntie. In de restricties moet rekening gehouden worden met  de CAO, ATW, variatieregels en de capaciteit van elke standplaats.     Invoer:  alle  taken  die  moeten  worden  uitgevoerd  in  het  hele  land  op  een  bepaalde  dag  en  de  personeelscapaciteit per standplaats. 

12   

Uitvoer: de anonieme diensten per standplaats.    Voor het oplossen van deelprobleem 2 maken we gebruik van zowel dynamische kolomgeneratie als  Set‐Covering. Abbink et al. [3] en [4] maken gebruik van soortgelijke technieken met behulp van het  programma  TURNI,  hierbij  wordt  gebruik  gemaakt  van  dynamische  kolomgeneratie,  Lagrange  relaxatie en een aantal heuristieken.     Uit deelprobleem 1 hebben we nu een aantal restricties die we kunnen gebruiken in deelprobleem 2.  Zo  hebben  we  voor  de  kolomgeneratie  de  extra  restrictie  op  welke  treinseries  een  bepaalde  standplaats mag rijden. Andere output van deelprobleem 1 is het aantal taken dat voor een bepaalde  standplaats wordt uitgevoerd op een treinserie. Deze kunnen wij in afgezwakte vorm meegeven aan  het Set‐Covering model.     Het Set‐Covering model dat wij hebben opgesteld is gebaseerd op het model van Abbink et al. [4], de  volledige  literatuurstudie  hierover  is  te  vinden  in  Appendix  D.  Meer  informatie  over  Set‐Covering  Modellen is te vinden in Appendix G.    Kolomgeneratie  In  deelprobleem  2  hebben  we  te  maken  met  een  groot  ILP‐probleem.  Er  zijn  veel  restricties  en  mogelijk  nog  meer  toegestane  diensten.  Kolomgeneratie  is  een  krachtige  methode  om  grote  LP‐ problemen op te lossen. Met kolomgeneratie worden toegestane diensten gegenereerd. Een dienst  bestaat uit een kolom met op elke rij een 1 of een 0, met 1 als de taak op rij   wordt uitgevoerd in  dienst  , 0 anders. Deze diensten moeten allemaal voldoen aan de eisen die voor een enkele dienst  gelden, zoals eisen aan maximale duur, pauzes en overstaptijden. Door de restricties die we hebben  verkregen uit deelprobleem 1 zijn er wel minder toegelaten diensten, maar het aantal diensten is nog  steeds  heel  erg  groot.  Het  idee  achter  kolomgeneratie  is  dat  niet  álle  kolommen  bekeken  worden,  maar slechts een aantal welke gegenereerd worden. Het idee is om ‘goede’ kolommen (diensten) te  genereren die met grote kans tot de optimale oplossing behoren. Hierdoor reduceren we de omvang  van  het  probleem  enorm.  Dit  principe  wordt  enkele  malen  herhaald.  Er  zijn  twee  verschillende  manieren om kolomgeneratie toe te passen:    1. Er  wordt  van  tevoren  een  verzameling  kolommen  gegenereerd.  Deze  kolommen  zijn  toegelaten diensten die met de grootste kans in de optimale oplossing zitten. Daarna wordt  met  deze  deelverzameling  kolommen  (diensten)  het  gereduceerde  ILP‐probleem  opgelost  met behulp van Set‐Covering.  2. Met dynamische kolomgeneratie worden de kolommen simultaan met de oplossing van Set‐ Covering  gegenereerd.  Door  dynamische  kolomgeneratie  worden  de  mogelijke  toegelaten  diensten niet allemaal van tevoren bepaald maar komen deze tijdens het oplossen aan bod.  Alle mogelijke toegelaten diensten van tevoren bepalen zou waarschijnlijk niet mogelijk zijn  aangezien  dit  een  zeer  grote  verzameling  diensten  zou  zijn.  Dit  principe  werkt  als  volgt:  er  wordt  in  kolomgeneratie  een  initiële  oplossing  gevonden  die  diensten  bevat  die  elke  taak  minstens één keer uitvoert. Vervolgens worden deze diensten weer aangepast zodat ze ook  aan  de  extra  restricties  voldoen  die  door  het  Set‐Covering  model  worden  opgelegd.  Het  programma TURNI maakt gebruik van deze manier van kolomgeneratie. Zie ook Abbink et al.  [4] 

13   

  De restricties die voor kolomgeneratie worden meegenomen zijn de restricties die gelden voor een  bepaalde  dienst.  De  kolommen  moeten  voldoen  aan  de  voorwaarden  die  in  Appendix  C  worden  besproken (CAO, ATW en variatieregels). Hierbij komt nog de restrictie die volgt uit deelprobleem 1.  Voorbeelden van restricties zijn:  • Een  dienst  begint  en  eindigt  in  dezelfde  standplaats  (de  dienst  wordt  dan  ook  aan  deze  standplaats gekoppeld).  • Alleen  taken  die  in  de  treinseries  zitten  die  uitgevoerd  mogen  worden  door  een  bepaalde  standplaats kunnen in een dienst zitten die aan deze standplaats wordt toegewezen.   • Er is een maximale en een minimale tijdsduur van een dienst.  • Lunchpauzes moeten voorkomen bij lange diensten.  • De regels aan overstaptijd moeten in acht worden genomen.  • Er moet rekening gehouden worden met de regels van nachtdiensten.    Set‐Covering Formulering  Er  zijn  1, . . ,   taken  te  verdelen  en  1, … ,   mogelijke  diensten.  Een  dienst  bestaat  uit  een  1, … ,   lijst taken die door een bepaald persoon op een dag moeten worden uitgevoerd. Er zijn  standplaatsen.     Beslissingsvariabelen  1                0                                                     Invoer          1                          0                                                                                           De Set‐Covering formulering:  min

                                                                   1  

onder  1                                                   

                     2                        3          

    0,1                           Ad (1)   Bij  de  criteriumfunctie  zijn  de  kosten  nog  algemeen  gesteld.  De  totale  kosten  van  alle  diensten  die  nodig  zijn  om  alle  taken  uit  te  voeren  worden  geminimaliseerd.  Hiernaast  kunnen  in  de  restricties  nog  extra  kosten  worden  gemaakt  zodat  ongewenste  (combinaties 

14   

van) taken in diensten, zoals veel passagieren, een oneerlijke verdeling van leuk en niet leuke  werk, worden afgestraft. Dit wordt ook geminimaliseerd door de criteriumfunctie.  Ad (2)   Er wordt gezorgd dat elke taak door minimaal één dienst wordt uitgevoerd.  Ad (3)   Dit zijn de overige restricties met betrekking tot de eisen voor de diensten per standplaats.  De  restricties  die  in  dit  model  worden  opgenomen  zijn  dus  nog  niet  op  individueel  niveau  maar  ze  verbieden  wel  bepaalde  combinaties  van  diensten.  Dit  zijn  bijvoorbeeld  CAO  voorwaarden zoals het percentage nachtdiensten of de gemiddelde lengte van een dienst.       We bespreken nu een aantal mogelijke restricties:  • De gemiddelde dienstlengte van alle diensten die op standplaats   worden uitgevoerd moet  kleiner zijn dan  .                                0             

                       

:

  • Uit deelprobleem 1 komt voor elke standplaats het aantal taken dat deze op de verschillende  treinseries  moet  uitvoeren.  Deze  restrictie  voeren  wij  in  het  Set‐Covering  model  niet  in  als  harde grens, maar deze moet wel binnen bepaalde grenzen blijven.                                                1                  1                                        1                            

       

,

 

 

      

,

 

:

:

•

  Het  aantal  diensten  toegewezen  aan  een  standplaats  moet  binnen  de  capaciteit  van  deze  standplaats  zitten  en  er  moeten  niet  te  weinig  diensten  aan  een  standplaats  worden  toegewezen.                                                   

                       

             

                       

:

:

 

15   

•

De Herhaling Binnen Dienst (HBD), het aantal trajecten in een dienst gedeeld door het aantal   verschillende trajecten in een dienst, is gemiddeld over alle diensten kleiner dan 2,6 met een  bandbreedte van 0,1. De bandbreedte wordt meegenomen bij kolomgeneratie.                        2,6

•

 

  Per standplaats is de HBD over de diensten gemiddeld kleiner dan 3.  3 :

•

           

 

:

  Voor machinisten geldt dat iedere standplaats maximaal 50% van de totale landelijke rijtijd  op agressietreinen uitvoert.                                1       0                                                                                                                                                        1         0                                                                                                                                0,5

          

 

:

•

  Voor  conducteurs  geldt  dat  het  percentage  agressietreinen  kleiner  is  dan  50%  voor  elke  standplaats.                        1         0                                                                                                                                                           1         0                                                                                                                                   0,5 :

•

           :

  Iedere standplaats rijdt minstens 25% A‐treinen. Het percentage A‐treinen is de rijtijd op A‐ treinen  gedeeld  door  de  rijtijd  op  A‐  en  B‐treinen  samen.  Deze  restrictie  hebben  we  al  in  ‘verzwakte’ vorm bij ons eerste deelprobleem meegenomen.                    1        0                                                                                                                     1       0                                                                                                     0,25 :

           :

 

16   

 

 

•

In  deelprobleem  1  wordt  optioneel  ook  het  aantal  taken  in  nachtdiensten  voor  een  standplaats   bepaald. Er geldt nu dat elke standplaats minimaal een bepaalde fractie van die  nachttaken moet uitvoeren.  1               0                                                                        1    

 

             

    

 

 

            

   

 1 

 

    

   

:

•

  Voor  iedere  standplaats  geldt  dat  materieeltypes  worden  gereden  uit  ten  minste  vier  clusters. We  gebruiken weer de resultaten  uit de  optionele restricties  van  deelprobleem  1.  Het  gemiddeld  aantal  verschillende  clusters  waaruit  gereden  wordt  op  standplaats    moet  groter  of  gelijk  zijn  aan  het  aantal  verschillende  clusters  wat  bij  deelprobleem  1  aan  standplaats   is toegewezen.                    1                    ̂   0                                                                                     ̂ :

•  

   :

  Er zijn nog meer restricties en die kunnen we allemaal formuleren mocht dat nodig zijn.   

17   

4. Alternatieve aanpak  Om van een enorme lijst met taken tot individuele roosters te komen, beginnen wij tot nu toe steeds  bij het grote geheel. Eerst is er een lijst met taken, daarna diensten per standplaats en tot slot komen  er individuele roosters. De vraag is of dit ook andersom kan. Elk personeelslid van de NS heeft eigen  preferenties.  Is  het  mogelijk  om  meer  rekening  te  houden  met  deze  persoonlijke  preferenties?  De  roosters kunnen wellicht opgesteld worden door te beginnen met kijken naar de individuen en aan  de hand daarvan taken te verdelen om vervolgens toe te werken naar een situatie waarbij alle taken  zijn verdeeld. Misschien valt het begrip ‘dienst’ dan wel helemaal weg, omdat iedereen losse taken  toegewezen krijgt tot het moment dat alle taken verdeeld zijn. 

4.1 Individuele aanpak  Wij denken dat niet mogelijk om per individu de precieze taken toe te kennen aan de hand van de  persoonlijke preferenties. Allereerst is het onmogelijk om de precieze preferenties van ieder individu  vast te stellen en daar rekening mee te houden. Alle individuen zouden naast elkaar gezet moeten  worden  om  de  taken  één  voor  één  toe  te  kennen  zoals  weergegeven  in  Figuur  2.  Dit  zou  op  de  volgende  twee  manieren  kunnen:  via  geheeltallige  lineaire  programmering  of  dynamische  programmering.    

 

FIGUUR 2: TAKEN VERDELEN AAN INDIVIDUEN  

  Dynamisch programmeren  Gezien  het  feit  dat  er  ongeveer  25.000  taken  te  verdelen  zijn,  lijkt  dynamische  programmering  onmogelijk.  Omdat  er  steeds  per  individu  een  taak  verdeeld  wordt,  moet  er  rekening  gehouden  worden  met  het  aantal  taken  dat  al  toegekend  is  per  individu,  de  tijden  waarop  deze  taken  uitgevoerd moeten worden per individu en bovendien zouden alle efficiëntie restricties dan ook in de  toegelaten beslissingen verwerkt moeten worden. De toestand bij dynamisch programmeren zou dan  onhandig groot worden.    Lineair programmeren  Een  andere  manier  is  geheeltallige  lineaire  programmering,  de  beslissingsvariabelen  zouden  dan    1 als taak   wordt toegewezen aan individu   en 0 anders. Gezien het feit dat er  zoiets zijn als  ongeveer  50.000  taken  zijn  en  nog  eens  ongeveer  3.300  personeelsleden  zijn  er  gigantisch  veel  beslissingsvariabelen waardoor dit probleem niet binnen afzienbare tijd kan worden opgelost. 

18   

  Kortom:  het  probleem  wordt  te  groot  wanneer  er  rekening  wordt  gehouden  met  alle  preferenties  van elke individu. 

4.2 Groepsaanpak  Ons idee is om van tevoren een aantal preferentiegroepen in elke standplaats te vormen. Met behulp  van  kolomgeneratie  worden  er  diensten  gegenereerd  zoals  in  ons  deelprobleem  2.  Deze  diensten  voldoen aan de CAO regels. Vervolgens worden diensten aan standplaatsen toegewezen met behulp  van  Set‐Covering, waarbij  er restricties  worden  ingevoerd  die  ervoor  zorgen dat er per  standplaats  ongeveer  genoeg  diensten  zijn  voor  elke  preferentiegroep.  Per  standplaats  worden  de  diensten  verdeeld over de groepen, zoals weergegeven in Figuur 3. Deze stap zal vrij voor de hand liggend zijn,  omdat  er  uit  het  Set‐Covering  model  voldoende  diensten  komen  die  aan  de  preferenties  van  de  verschillende  groepen  voldoen.  Tot  slot  wordt  per  standplaats  per  groep  het  roosterprobleem  opgelost.    

FIGUUR 3: DIENSTEN VERDELEN AAN GROEPEN OP EEN STANDPLAATS  

 

  Groepen  De groepen worden samengesteld op basis van preferenties. Deze groepen zijn zodanig dat de  groepen wel nog steeds dezelfde eigenschappen hebben (conducteur/machinist, full‐ timers/parttimers etc.). Er zal wel een maximum aan het aantal groepen moeten worden gesteld  want als er met alle aspecten rekening wordt gehouden in elke groep, komen er teveel groepen en  kan het probleem alsnog niet opgelost worden. Het is complex om deze groepen te specificeren.  Voorbeelden van groepen zijn:  ‐ Groep weinig variatie  ‐ Groep veel variatie  ‐ Groep veel nachtdiensten  ‐ Groep alleen dagdiensten  ‐ Groep geen voorkeur 

19   

We zouden met behulp van een enquete per individu kunnen vaststellen in welke groep hij/zij valt.  Een groep zal bijna nooit exact aansluiten op de individuele preferenties, maar het zal wel voor een  groot deel overeen komen.   Problemen  Bij  kolomgeneratie  zijn  er  niet  voldoende  restricties  die  ervoor  zorgen  dat  er  niet  ontzettend  veel   mogelijke  diensten (kolommen)   gegenereerd  kunnen  worden.   In het  model  dat wij  in ons verslag  hebben  beschreven  hebben  we  juist  vanuit  deelprobleem  1  restricties  die  ervoor  zorgen  dat  er  minder  kolommen  gegenereerd  kunnen  worden.  Wij  denken  dat  de  grote  hoeveelheid  mogelijke  diensten  bij  het  nieuwe  model  een  probleem  zal  geven.  Aan  de  andere  kant  wordt  het  personeelsprobleem  bij  de  NS  nu  ook  ongeveer  op  deze  manier  opgelost  met  behulp  van  het  programma  TURNI.  We  denken  toch  dat  ons  eerdere  model  het  probleem  efficiënter  oplost.  Daarnaast houden we nog steeds geen rekening met alle individuele preferenties, maar slechts met  de belangrijkste aspecten die een bepaalde groep specificeren.    We gebruiken het begrip diensten nog steeds. Wij denken dat het niet mogelijk is om dit begrip los te  laten en alleen met taken te werken. Doordat er wordt gewerkt in groepen per standplaats, zijn er  veel meer partijen. Voor elk van deze groepen zullen restricties moeten gelden voor efficiëntie. Deze  efficiëntierestricties  zullen  daardoor  veel  strenger  zijn  omdat  er  minder  speling  is  omdat  de  groepsgrootte kleiner is. Als deze restricties vervolgens ook nog eens worden meegenomen op taak‐ niveau is het de vraag of het probleem nog kan worden opgelost.     Uitbreiding  We  kunnen  onze  aanpak  uitbreiden  door  te  kijken  naar  zeer  specifieke  preferenties  van  personeelsleden. Voordat we diensten gaan genereren, kennen we bepaalde taken toe aan personen  met  minderheidspreferenties  zoals  ‘voorkeur  voor  alleen  maar  agressietreinen’.  Dit  zijn  alleen  de  preferenties die haaks op de preferenties van de meerderheid staan. Door vooraf aan deze personen  taken  toe  te  kennen  zullen  de  diensten  van  de  meerderheidspreferenties  er  dus  niet  slechter  op  worden. Omdat het hier om weinig mensen gaat, zullen deze diensten vrij gemakkelijk met de hand  in  te  plannen  zijn.  De  taken  die  door  deze  personen  worden  uitgevoerd  worden  verwijderd  uit  de  takenlijst. Het probleem kan vervolgens op de hierboven beschreven manier worden opgelost.    Een probleem  bij  deze  uitbreiding  is  dat de mensen  met  specifieke preferenties elke  dag hetzelfde  zullen doen. Als we een weekrooster voor hen willen opstellen, moeten we het grote probleem nu  zeven keer (voor elke dag) oplossen in plaats van drie keer. Hierdoor duurt het nog langer voordat er  een  oplossing  is  en  dat  is  ook  niet  gewenst.  Als  er  meerdere  personen  met  dezelfde  specifieke  preferenties zijn, kunnen deze zelf rouleren met de diensten. Maar zo komen we weer richting het  groepsidee als hierboven beschreven.    Kortom,  wij  denken  dat  onze  eerste  aanpak  het  beste  is  en  dat  het  niet  handig  is  om  vanaf  individueel niveau naar een oplossing toe te werken.         

20   

5. Conclusie  Bij  de  NS  is  het  indelen  van  personeelsdiensten   een  complex  probleem.  omdat  er  veel  mogelijke  oplossingen  zijn  en  omdat  er  veel  voorwaarden  zijn  waaraan  diensten  moeten  voldoen.    In de meeste artikelen die wij hebben gelezen worden er direct diensten gegenereerd en toegekend  aan  standplaatsen,  de  omvang  van  dit  probleem  is  echter  enorm.  In  ons  werkstuk  hebben  we  een  alternatieve  aanpak  besproken  om  dit  probleem  aan  te  pakken:  het probleem wordt  opgesplitst  in  twee deelproblemen, waarbij het doel is om de omvang van deelprobleem twee flink te reduceren  door gebruik te maken van de output van  deelprobleem één.  Eerst wordt een hoeveelheid taken (en verschillende treinseries) aan standplaatsen toegekend met  behulp  van  een  gemengd  geheeltallige  lineaire  programmeringsformulering.  Hierbij  wordt  er  rekening  gehouden  met  efficiëntie  en  variatie  van  het  werk  dat  door  de  verschillende  personeelsleden  moet  worden  uitgevoerd.  De  output  van  dit  model  wordt  in  verzwakte  meegenomen naar deelprobleem twee: het Set‐Covering model. In dit tweede deelprobleem worden  de  diensten  toegekend  aan  de  standplaatsen,  de  diensten  worden  gegenereerd  met  behulp  van  dynamische kolomgeneratie.  Een  alternatieve  aanpak  om  dienstroosters  te  maken  door  te  kijken  vanuit  de  wensen  van  de  individuele werknemers achten wij niet mogelijk, omdat de omvang van het probleem te groot is. 

       

 

21   

6. Bronvermelding  [1]      [2]  [3]   [4] 

[5] 

[6]  [7]    

ORTEC  Consultants  bv,  Beschrijvenderwijs:  Plannen  en  bijsturen  van  rijdend  NSR   personeel, versie v7, 20 februari 2002  Nordbeck H., Het rijdend personeel laat van zich horen, Project: JE BENT ERBIJ  Abbink  E.,  van’t  Wout  J.    en  Huisman  D.,  ARRIVAL‐TR‐0137,  Solving  Large  Scale  Crew  Scheduling Problems by Using Iterative Partitioning, November 2007  Abbink, E., Fischetti, M., Kroon, L.G., Timmer, G., & Vromans, M.J.C.M. 2004a,  Reinventing crew scheduling at Netherlands Railways, Tech. rept. ERS‐2004‐046‐  LIS. Erasmus Research Institute of Management, Erasmus University Rotterdam,  juni 2004  Ridder  A.A.N.,  Tijms  H.C.,  Timmer  G.T.,  Dictaat  Bedrijfseconometrie  deel  I,  Afdeling  Econometrie, Faculteit der Economische Wetenschappen en Bedrijfskunde, Vrije Universiteit  Amsterdam,  september 2007.   Caprara A.,  Kroon  L., Monaci  M.,  Peeters M., Toth P.,  ARRIVAL‐TR‐0137,  Passenger Railway  Optimization, januari 2006.  Hartog A., Huisman D., Abbink E., Kroon L., Decision support for crew rostering at NS, Springer  2009, 1: pagina’s 121‐133.    

22   

Appendix A ­ Vragen en begrippen    •

• • •

•

•

•

•

•

Wat is punctualiteit en hoe wordt dit gemeten?  Dit  is  het  percentage  treinen  dat  binnen  een  marge  van  drie  minuten  arriveert   ten opzichte van de ingeroosterde tijd.   Wat wordt er bedoeld met ‘kwaliteit van het product’ en ‘kwaliteit van arbeid’ en hoe wordt  dit meetbaar gemaakt?   Hoe kunnen we in ons model rekening houden met de groei?  Hoe  kwantificeert  men  bepaalde  voorkeuren?  Wordt  er  een  score  toegekend  aan  de  verschillende treinseries/trajecten en aan het verschillende materieel? In welke mate en op  welke wijze moeten deze criteria worden meegenomen bij het opstellen van de diensten?   Wij  denken  dat  de  beoogde  variatie  in  materieel  het  beste  in  het  model  kan  worden  opgenomen  door  een  restrictie  aan  de  verhouding  stop‐  en  sneltreinen  te  leggen.  Aan  het  aantal dubbeldekkers in een dienst kan een maximum gesteld worden. Bepaalde trajecten zijn  agressielijnen,  hier  kan  een  scoren  van  de  mate  van  agressie  aan  worden  gegeven  (bijvoorbeeld op de schaal van 1 tot 10). Er kan een maximale agressiescore worden gesteld  in het model. Voor de variatie in trajecten/treinseries stellen wij een extra vraag:  Hoe  kwantificeert  men  de  mate  van  variatie  (afwisseling)  in  verschillende  routes?   Wordt  dit  gemeten  aan  de  hand  van  de  volgende  maatstaven?  Zo  ja,  hoe?      1. Het aantal verschillende treinseries of trajecten?    2. De lengte van het traject?     3.  Het  aantal  keer  dat  hetzelfde  traject  op  eenzelfde  dag  wordt  gereden?  Wij gaan er nu vanuit dat de mate van variatie afhangt van het aantal verschillende trajecten  dat in een dienst wordt gereden.   Wat is efficiëntie en hoe wordt dit gemeten?  In  onze  context  kan  efficiëntie  worden  uitgedrukt  in  het  aantal  uren  dat  in  totaal  gepassagierd  en  gewacht  wordt  door  het  personeel.  Passagieren  en  wachten  brengen  onnodig extra kosten met zich mee. Hoe minder er gepassagierd wordt, hoe beter. Voor het  wachten gelden natuurlijk wel de restricties met betrekking tot minimale overstaptijd.   Hoe  wordt  de  uitkomst  beïnvloed  als  ‘echte’  nachtdiensten  worden  ingevoerd?  Een  echte  nachtdienst is een dienst die ‘laat’ start en ‘vroeg’ eindigt.  Een  nachtdienst  kan  zowel  een  late  als  een  vroege  dienst  vervangen  waardoor  het  aantal  belastende  diensten  afneemt.  Nachtdiensten  maken  het  ‘schuiven’  van  werk  naar  standplaatsen met relatief veel capaciteit mogelijk wat waarschijnlijk een positief effect heeft  op de efficiëntie, zie ook [2].  De dienstregeling is bekend, maar wat moet er precies gedaan worden? Welke taken zijn er  allemaal? Wat doen treinsurveillanten?  o Treinen over het hele land moeten van A naar B worden gereden door een machinist  (zowel treinen met passagiers, als zonder).  o Treinkaartjes over het hele land moeten door conducteurs gecontroleerd worden.  o Bepaalde trajecten moeten door meerdere conducteurs bereden worden.  Op welke manier moet er rekening worden gehouden met het feit dat bij een overstap van  personeel er steeds een kans is dat het misgaat?  

23   

Iedere  keer  als  er  een  overstap  moet  plaatsvinden,  gaat  de  vervolgtaak  met  een  bepaalde  kans mis, waardoor er mogelijk vertraging optreedt. In hoeverre dit effect heeft, is afhankelijk  van hoe het dienstrooster van het personeelslid verder in elkaar zit. Als dit personeelslid werk  doet over het hele land dan zal dit een veel grotere invloed hebben dan als het werk slechts  beperkt is tot bepaalde trajecten. Dit is een afweging tussen de hoeveelheid variatie van het  werk  (wensen  van  het  personeel)  en  de  mate  waarin  dingen  fout  kunnen  gaan.  Dit  deelprobleem kan op twee manieren worden aangepakt:   o Buffers, dat wil zeggen dat we de overstaptijden vergroten  o Isolatie,  zodat  de  ellende  beperkt  blijft  tot  een  beperkt  aantal  trajecten  en  veel  minder gevolgen heeft voor andere treinseries.    Het meenemen van stochastische factoren  • Op welke manier moet er rekening gehouden worden met afwezigheid van personeel door  ziekte?  Kan  dit  ingecalculeerd  worden  door  verwachtingen  /  gemiddeldes  te  nemen  en  op  basis van historische gegevens?    In  ons  onderzoek  gaan  we  er  vanuit  dat  alles  deterministisch  is.  We  hoeven  ons  dus  niet  bezig  te  houden met dit laatste vraagstuk.     

24   

Appendix B ­ Het planningsproces    1. Het maken van een dienstregeling  Het gehele planningsproces voor dienstrooster, materiaalinzet en personeelsplanning begint met het  ontwikkelen  van  de  dienstregeling.  Dertien  maanden  voor  de  ingang  van  een  nieuw  spoorboekje  wordt door de afdeling Jaarplan begonnen met de studie naar de mogelijke dienstregelingpatronen.   Allereerst wordt het Basis Uurpatroon (BUP) opgesteld. Dit is een overzicht voor één standaard uur  van  alle  treinen  die  tijdens  dat  uur  rijden.  Dit  wordt  gedaan  voor  drie  gevallen:  een  daluur,  een  ochtendspitsuur  en  een  avondspitsuur.  Tevens  worden  de  Basis  Spooropstellingen  (BSO)  gemaakt.  Hierin  wordt  aangegeven  welke  sporen  op  stations  wanneer  in  gebruik  zijn.  Uiteindelijk  wordt  dit  uitgewerkt tot een gehele 7x24 dienstregeling, die deels als input wordt gebruikt voor het plannen  van personeelsdiensten.    2. Toewijzen materieel  Als  er  een  begin  is  gemaakt  aan  de  dienstregeling  wordt  er  gekeken  naar  de  capaciteit  van  het  materiaal,  dit  is  ongeveer  negen  maanden  voor  de  ingang  van  een  nieuw  spoorboekje.  Dit  materieelrooster is noodzakelijk omdat er wel een trein aanwezig moet zijn op het goede station wil  er volgens de dienstregeling een trein rijden. Op basis van het drukste uur van de dag (tussen 8 en 9  uur ’s ochtends) wordt het materieel toegewezen. Daarna wordt er een uitwerking gemaakt voor alle  andere uren van de dag. Uiteindelijk wordt dit uitgewerkt tot een gehele 7x24 materieelinzet.    3. Planning van het personeel  De personeelsdiensten worden gemaakt door de afdeling Jaarplan. Een personeelsdienst bestaat uit  een aantal personeelsactiviteiten op één werkdag, zoals treinritten en overige werkzaamheden, voor  een  bepaald  type  personeelslid:  machinisten,  conducteurs  of  treinsurveillanten.  Een  personeelsdienst is anoniem. Er worden drie verschillende dagdiensten gemaakt op basis van de drie  verschillende soorten dagen: weekdagen, zaterdagen en zondagen. Diensten horen bij een bepaalde  standplaats. Een standplaats is een “vrij groot” station waaraan meer dan één treinserie gekoppeld is  en waar meer dan één traject gereden wordt met zowel snel‐ als stoptreinen.  De  personeelsdiensten  (output)  worden  vervolgens  naar  de  desbetreffende  standplaats  gestuurd.  Daar  worden  persoonlijke  roosters  gemaakt  waarbij  voor  elke  dag  van  de  week  een  dienst  wordt  toegekend aan een rijdend personeelslid.     Bij  het  maken  van  de  diensten  moet  rekening  gehouden  worden  met  planningsregels.  Er  moet  bijvoorbeeld  rekening  worden  gehouden  met  de  minimale  en  maximale  lengte  van  diensten,  het  aantal nachtdiensten en lunchpauzes.      3.1 Het opdelen van het personeelsplanningproces  Dit proces kan worden opgedeeld drie procesfasen.      Fase 1:   Het maken van een voorontwerp     Fase 2:   Het maken van de concept diensten     Fase 3:   Het maken van de definitieve diensten  Voor meer informatie hierover zie Ortec [1].     

25   

Appendix C ­ Planningsregels    Er  zijn  een  behoorlijk  aantal  planningsregels  waaraan  de  personeelsdiensten  moeten  voldoen.  Wij  zullen alleen de belangrijkste regels hier noemen. Voor het volledige overzicht verwijzen wij naar het  stencil van ORTEC [1].    1.  Bemanningsregels  • Er moet een conducteur en een machinist op elke trein aanwezig zijn  • De machinist moet bekend zijn met de weg en het materieel  • Bij agressietreinen wordt een extra bevoegde hoofdconducteur toegevoegd    2.  De CAO regels  • Een dienst moet minimaal 4 uur lang zijn en mag maximaal 9,5 uur duren  • Maximaal 5% van de diensten per standplaats mogen korter zijn dan 5 uur en maximaal 12  diensten per werknemer mogen langer zijn dan 9 uur  • Een nachtdienst die de periode 2h00‐4h00 bevat mag niet eindigen na 7h00   • Een werknemer mag maximaal 35 nachtdiensten per 13 weken hebben  • Diensten langer dan 5,5 uur moeten een lunchpauze hebben met minimale lengte van een  half uur en het liefst halverwege de dienst of op een gangbaar etenstijdstip  • Een  werknemer  mag  niet  meer  dan  een  amplitudedienst  per  week  hebben  (een  amplitudedienst is een dienst waarbij in het rooster is vastgesteld tussen welke tijdstippen  de  dienst  kan  beginnen,  de  feitelijke  start‐  en  eindtijden  worden  pas  de  donderdag  van  tevoren bekend gemaakt)    In het model van 2002 moest ook nog worden voldaan aan de regels van procesvereenvoudiging en  de  regels  van  het  basisakkoord.  Deze  regels  gelden  voor  het  huidige  model  niet  meer.  Voor  het  model  van  2002  waren  de  regels  van  procesvereenvoudiging  in  principe  niet  hard,  maar  moest  bij  overtreding goedkeuring worden gevraagd bij het management team.     Procesvereenvoudiging  • Er  wordt  gebruik  gemaakt  van  treinteams:  machinist  en  eerste  conducteur  zijn  aan  elkaar  gekoppeld voor tenminste 70% (de rest van de tijd kan gebruikt worden voor het besturen  van lege treinen of surveillantdiensten)  • Er moet een overstaptijd op ander materieel van minimaal 25 minuten zijn  • Machinisten en conducteurs dienen 20 minuten van tevoren aanwezig te zijn en 15 minuten  na  de  rit  mogen  zij  vertrekken  (voor  deze  voor‐  en  natijden  gelden  nog  specifiekere  regels  zoals beschreven in [1])    Regels basisakkoord  Voor diensten die langer zijn dan 5,5 uur gelden variatieregels  • De dienst moet een treinserie hebben die en traject van meer dan 150 km bevat   Of er moet zijn voldaan aan twee van de volgende drie regels:  • De dienst bevat meer dan één treinserie  • De dienst bevat meer dan één traject 

26   

•

Een dienst bevat een intercity en een sprinter of het bevat twee verschillende intercity’s    3. Criteria ‘Lusten en lasten delen’  Voor het nieuwe model gelden ook de regels van ‘Lusten en Lasten delen’. Deze regels schrijven niet  in detail voor op welke wijze de opsplitsing van het werk per standplaats moet worden geregeld. Het  stelt alleen kwaliteitseisen waaraan een dienstpakket van een bepaalde  standplaats moet voldoen.  Deze regels zijn:  • Variatie in trajecten (zowel binnen de diensten als over de diensten heen)  • Verdeling A/B treinen  • Verdeling agressiewerk  • Variatie in materieelsoorten  Deze eisen worden vertaald in kwantitatieve regels waaraan een dienst moet voldoen. Hiervoor geldt  bijvoorbeeld dat de verwachting is dat iedere standplaats op gemiddeld minimaal achttien trajecten  rijdt.  Vijf  procent  van  alle  standplaatsen  mag  van  dit  aantal  afwijken,  maar  deze  zullen  dan  wel  minstens tien trajecten rijden. Verder geldt dat Herhaling Binnen Dienst (HBD, het aantal trajecten in  de dienst gedeeld door het aantal verschillende trajecten in de dienst) gemiddeld over alle diensten  kleiner  dan  2,6  is  met  een  bandbreedte  van  0,1.  Per  standplaats  moet  de  HBD  over  de  diensten  kleiner zijn dan drie, met mogelijke uitzondering voor maximaal drie standplaatsen waarvoor de HBD  kleiner dan 3,3 is. De standaardafwijking van het percentage A‐treinen (rijtijd op A‐treinen gedeeld  door  rijtijd  op  A‐  en  B‐treinen  samen)  per  standplaats  is  maximaal  twaalf  tot  veertien.  In  iedere  standplaats moet ten minste 25% A‐treinen rijden. De kwantitatieve regels voor agressietreinen zijn  als  volgt:  voor  machinisten  geldt  dat  iedere  standplaats  maximaal  50%  van  de  totale  (landelijke)  rijtijd op agressietreinen uitvoert. Voor conducteurs geldt dat het percentage agressietreinen kleiner  is dan 50%. Dit heeft een andere betekenis dan de 50%‐norm bij machinisten. Daarnaast geldt voor  conducteurs dat de standaardafwijking van het percentage agressietreinen per standplaats maximaal  11,5  is.  Voor  materieel  geldt  per  standplaats:  iedere  standplaats  rijdt  op  ten  minste  vier  materieeltypes (in totaal zijn er acht) met uitzondering van maximaal drie standplaatsen die elk op  ten minste drie materieeltypes rijden. De conducteurs per standplaats rijden niet meer dan 65% op  dubbeldeks materieel en de machinisten niet meer dan 60% op MAT’64.      4. Personeel en passagieren  Elk personeelslid is aan een standplaats gekoppeld. In principe starten en eindigen treinen alleen in  standplaatsen zodat personeelsleden altijd beginnen bij hun eigen standplaats. In het rooster zal het  echter ook voorkomen dat een personeelslid moet beginnen of eindigen op een standplaats die niet  zijn  eigen  standplaats  is. De  reistijd die  het  kost  voor  het  personeelslid om  naar de juiste  plaats  te  komen valt ook onder de dienstijd. Dit proces wordt passagieren genoemd.     5. De roosterbaarheid van diensten  Verder  is  er  nog  een  aantal  normen  voor  de  roosterbaarheid  van  diensten.  Er  wordt  bijvoorbeeld  gesteld  dat  er  een  redelijke  verdeling van de weekenddiensten  moet zijn  (landelijk  gemiddeld  75%  van diensten op een doordeweekse dag, 13% op zaterdag en 12% op zondag) en dat een dienstlengte  gemiddeld niet langer is dan acht uur per dag. Belangrijk is dat er gekeken wordt naar de redelijkheid  van  bepaalde  aspecten,  zoals  de  hoeveelheid  nachtdiensten,  de  hoeveelheid  vroeg/laat  diensten  (een vroege dienst begint voor 6h00 en een late dienst na 18h00) en de hoeveelheid lange en korte  diensten. Deze normen gelden per standplaats en over alle diensten heen. 

27   

Naast deze grote hoeveelheid regels zijn er ook nog specifieke regels voor bepaalde doelgroepen of  treintrajecten.  Zo  is  het  wenselijk  om  zogenoemde  ouderenroosters  (voor  55+‐ers)  te  maken.  Wat  ook  van  belang  is,  zijn  de  aantrekkelijke  en  minder  aantrekkelijke  trajecten.  Het  is  niet  ‘eerlijk’  om  hetzelfde personeelslid elke keer op een agressietraject te zetten. Dit is echter meer een zaak voor  het persoonlijk inroosteren van de diensten op de standplaatsen zelf en wij houden ons hier dan ook  niet verder mee bezig.     6. Commerciële doelstellingen  Naast  al  deze  personeelsregels  moet  er  ook  rekening  gehouden  worden  met  commerciële  doelstellingen zoals     • Punctualiteit  • Groei  • Kwaliteit van arbeid en product  • Efficiëntie  Deze  termen  zijn  echter  lastig  te  meten.  De  vraag  is  hoe  men  punctualiteit,  groei,  kwaliteit  van  arbeid, kwaliteit van product en efficiëntie definieert. Een trein die meer dan drie minuten te laat is,  wordt niet meer punctueel genoemd. Echter een trein die zoveel vertraagd is dat deze uitvalt wordt  niet  als  te  laat  beschouwd.  Punctualiteit  hangt  in  sterke  mate  samen  met  het  aantal  keer  dat  een  personeelslid moet overstappen tijdens een dienst. Bij elke overstap is er namelijk een kans dat het  personeelslid  niet  op  tijd  is  voor  de  volgende  rit.  Het  zou  zelfs  zo  kunnen  zijn  dat  door  de  eerste  vertraging  van  een  personeelslid  een  sneeuwbaleffect  ontstaat  waardoor  alle  treinen,  waarin  het  betreffende personeelslid zit, ook verlaat zijn. Bij de ontwikkeling van het nieuwe model zou hier dan  ook  rekening  mee  gehouden  moeten  worden  door  bijvoorbeeld  een  restrictie  te  leggen  op  het  maximaal  aantal  overstappen  dat  tijdens  een  dienst  gemaakt  mag  worden  of  door  bepaalde  treinseries te isoleren.   Groei  kan  wel  gemeten  worden,  maar  het  is  lastig  om  te  zeggen  of  het  ene  model  de  groei  beter  stimuleert dan het andere model.   Daarnaast zijn kwaliteit en efficiëntie begrippen die moeilijk meetbaar zijn. Het is heel lastig  aan te  geven of een nieuw ontwikkeld rooster nou efficiënter is dan het oude rooster. Een criterium voor  efficiëntie zou de hoeveelheid tijd passagieren of wachten kunnen zijn. Passagieren en wachten zorgt  eigenlijk voor ‘loze’ tijd in een dienst en zal zo efficiënt mogelijk vermeden moeten worden.  Bij  kwaliteit  is  er  onderscheid  tussen  de  kwaliteit  van  arbeid  en  de  kwaliteit  van  het  product.  Het  begrip  kwaliteit  zou  eerst  goed  gedefinieerd  moeten  worden  en  daarna  kwantificeerbaar  gemaakt  moeten worden.     7. Robuustheid en kosten  Een doelstelling die met bovenstaande samenhangt, is de robuustheid van het rooster. Hierbij wordt  gekeken naar in hoeverre het dienstrooster in staat is mogelijke vertragingen op te vangen zodat er  geen sneeuwbaleffect ontstaat.   Een andere belangrijke doelstelling is dat de kosten van het nieuwe model ongeveer gelijk moeten  blijven aan de kosten van het oude model.     

28   

Appendix D ­ Literatuurstudie diensten toewijzen     Wij bespreken twee artikelen over het toewijzen van diensten aan standplaatsen.    1. Bespreking artikel: Reinventing crew scheduling at Netherlands Railways  In  dit  artikel  van  Abbink  et  al.  [4]  wordt  een  heldere  samenvatting  gegeven  van  het  probleem  dat  rond 2001 bij de NS speelde, zoals ook in dit verslag beschreven. Er wordt een model gegeven voor  het verdelen van de diensten over het personeel op alle standplaatsen. Als criteriumfunctie worden  de totale kosten van de diensten genomen. Hierbij moet onder andere rekening gehouden worden  met  de  mogelijkheden  van  personeel  op  bepaalde  standplaatsen,  de  CAO  en  de  wensen  van  het  personeel. De output van dit model is een precieze toewijzing van alle diensten die worden gevoerd  aan  bepaalde  standplaatsen,  zodat  elke  standplaats  deze  diensten  weer  kan  verdelen  over  hun  personeel.    Er zijn  1, … ,  taken die verdeeld moeten worden onder het personeel en  1, … ,  mogelijke  toegestane diensten. Hierbij komen nog  1, … ,  extra restricties.  De volgende beslissingsvariabele wordt ingevoerd:    1                        0                                                                                                                  min

                                                                     1  

onder  1                          

                                  2  

                        

                                  3  

0,1                                  

                                  4  

  De doelstellingsfunctie (1) minimaliseert de kosten van de diensten. De matrix   bestaat uit nullen  en enen. Als een bepaalde taak   aan een dienst   wordt toewezen is   één, anders nul. Restrictie  (2)  zorgt  er  voor  dat  elke  taak  aan  een  dienst  wordt  toegewezen.  In  restrictie  (3)  staan  de  overige  bijvoorwaarden die  nog  niet verder  gespecificeerd  zijn. Deze  restricties  zijn nog  niet op individueel  niveau maar ze verbieden wel bepaalde combinaties van diensten. Andere restricties komen uit de  CAO zoals het percentage nachtdiensten of de gemiddelde lengte van een dienst.     Dit model wordt opgelost met de techniek van Set Covering in het programma TURNI.     2. Bespreking artikel: Solving large scale crew scheduling problems by using iterative partitioning  Een model voor het personeelplannen wordt besproken in een artikel van Abbink et al. [3].  Ook zij  hebben als input alle verschillende taken die in een gehele week moeten worden uitgevoerd. Bij de  NS  wordt  nu  veelal  gebruik  gemaakt  van  het  programma  TURNI.  De  schrijvers  merken  op  dat  de  oplossing kan worden verbeterd. Ze stellen onder andere dat door het plannen van een gehele week  met  daarin  de  restricties  een  betere  algemene  oplossing  geeft.  Daarnaast  geven  ze  aan  dat  een 

29   

oplossing voor een standplaats kan worden verbeterd als de toegewezen taken aan die standplaats  opnieuw  door  TURNI  worden  geroosterd  tot  diensten.  Het  probleem  wordt  gemodelleerd  als  een  Set‐Covering  probleem.  Ze  beschrijven  het  model  waarin  twee  achtereenvolgende  dagen  tegelijk  worden  ingepland,  in  tegenstelling  tot  het  hiervoor  beschreven  model  waarbij  slechts  één  dag  tegelijk bekeken wordt.    Notatie  , : Verzameling taken voor dag 1 respectievelijk dag 2  • , : Toegestane  diensten  voor  dag  1  respectievelijk  dag  2.  Bij  het  maken  van  deze  • diensten  zijn  alle  restricties  van  pauzes,  maximale  diensttijd,  minimale  overstaptijd  ect.  meegenomen.   , : Verzameling  diensten  voor  dag  1  respectievelijk  dag  2  waarin  taak  i wordt  • uitgevoerd  • , : 1 als dienst   respectievelijk   in de oplossing wordt opgenomen  •

: kosten voor dienst   

• • •

: verzameling van extra restricties  , : ondergrens, respectievelijk bovengrens voor extra restrictie    , : gewicht voor dienst   respectievelijk   voor restrictie 

 

  Model                                                                             1   Onder 

 

1                                                

                     2  

1                                                

                    3  

          

                     4      

0,1                                                     0,1                                                    

                    5                       6  

  Restrictie  (1)  is  de  doelstellingsfunctie.  In  de  doelstellingsfunctie  worden  de  totale  kosten  geminimaliseerd.  Restrictie  (2)  en  (3)  garanderen  dat  er  voor  iedere  taak   tenminste  één  dienst  is  waarin  deze  taak  wordt  uitgevoerd.  Hierbij  kan  het  voorkomen  dat  een  taak  door  meer  dan  één  dienst  wordt  uitgevoerd.  Het  kan  echter  zijn  dat  dit  goedkoper  is  dan  het  vermijden  van  dubbele  bezetting, omdat door die dubbele bezetting andere taken makkelijker kunnen worden uitgevoerd.  Restrictie (4) geeft alle extra restricties weer. Hierbij kan gedacht worden aan het aantal diensten dat  maximaal  op  een  dag  bij  een  bepaalde  standplaats  kan  worden  uitgevoerd.  De  extra  restricties  kunnen  ook  bestaan  uit  restricties  die  met  bepaalde  boete  overschreden  mogen  worden.  Deze  restricties moeten samen met de boete in de doelstellingsfunctie worden meegenomen.    

30   

Alle  toegelaten  diensten  voldoen  aan  de  restricties  die  hiervoor  moeten  gelden,  zoals  duur  van  de  dienst, regels m.b.t. pauzes en begin en eind moet in dezelfde standplaats zijn. Om deze toegelaten  diensten  te  vinden  wordt  gebruik  gemaakt  van  kolomgeneratie.  De  diensten  worden  gegenereerd  door het oplossen van een kortste pad probleem in een acyclisch netwerk. In dit netwerk worden de  knopen voorgesteld als de mogelijke taken en bestaat er een pijl tussen twee knopen als een dienst  door dezelfde personeelslid kan worden uitgevoerd.     De schrijvers van het artikel bespreken vervolgens kort vier partitionerings methoden:  • Dag  partitionering:  Voor  elke  dag  van  de  week  wordt  een  verschillende  oplossing  gecreëerd.  Hiervoor is geen initiële oplossing nodig.   • Geografische patritionering: Nadat voor elke  standplaats is vastgesteld welke diensten hieraan  zijn  toegewezen,  kan  het  model  opnieuw  worden  opgelost  voor  deelproblemen.  Het  land  kan  worden  opgesplitst  in  verschillende  regio’s  van  gelijke  grootte.  Van  alle  taken  van  de  standplaatsen in een regio kunnen dan nieuwe diensten worden gemaakt.   • Serie partitionering: De standplaatsen langs een grote serie kunnen worden samengevoegd tot  een  cluster.  Ook  hiervan  kan  de  oplossing  worden  verbeterd  door  alle  taken  van  deze  standplaatsen opnieuw tot diensten in te delen.   • Partitionering op basis van kolom informatie: Naast de diensten die werkelijk worden gekozen,  genereert  TURNI  ook  diensten  die  met  grote  kans  ook  gekozen  zouden  kunnen  worden.  Het  is  mogelijk om elk paar diensten die gekozen zijn in de optimale oplossing een score te geven. Deze  score is gebaseerd op hoe vaak taken in deze diensten samen voorkomen in de verzameling van  alle diensten van TURNI. Er wordt een graaf      ,  geconstrueerd waarbij de diensten de  knopen zijn en de score  ,  tussen deze diensten de kanten zijn. Het is nu de bedoeling om  een  partitie  van  knopen  in    gelijke  deelverzamelingen  te  delen  waarvoor  geldt  dat  het  totale  gewicht van de kanten tussen de verschillende deelverzamelingen wordt geminimaliseerd, ofwel:  min

, ,

,

,

 

,

Resultaten  De  verschillende  manieren  van  partitioneren  zijn  toegepast  op  echte  data.  Er  wordt  vergeleken  hoeveel diensten er totaal nodig zijn om alle taken uit te voeren. Hierin kwam sterk naar voren dat  het  toepassen  van  elk  van  deze  methoden  een  verbetering  van  het  aantal  diensten  met  zich  meebracht. Het toepassen van al deze methoden achter elkaar bracht de beste verbetering met zich  mee.      

31   

Appendix E ­ Literatuurstudie roosteren    Nadat er voor elke standplaats is vastgesteld welke diensten hieraan worden toegekend, moeten er  roosters worden opgesteld. Deze roosters moeten ook weer aan allerlei eisen voldoen. Om een idee  te krijgen van hoe dit probleem kan worden aangepakt, hebben wij weer een korte literatuurstudie  gedaan.     1.  Bespreking artikel: Decision support for crew rostering at NS  Als  de  diensten  per  standplaats  bekend  zijn  moet  er  een  rooster  worden  gemaakt.  Dit  probleem  wordt  per  standplaats  opgelost.  Volgens  het  artikel  van  Hartog  et  al.  [6]  kan  dat  op  verschillende  manieren:  - Rooster per individu waarin specifieke karakteristieken zoals vakanties worden meegenomen  - Individuen kunnen bieden op bepaalde diensten  - Er wordt een cyclisch rooster geconstrueerd  Bij  het  roosteren  van  treinen  wordt  het  meest  gebruik  gemaakt  van  een  cyclisch  rooster.  Werknemers  worden  ingedeeld  in  groepen  die  dezelfde  eigenschappen  hebben.  Bij  deze  eigenschappen kan gedacht worden aan type werknemer (conducteur of machinist), full‐timers/part‐ timers of de wegbekendheid. Voor een groep ter grootte   wordt een rooster gemaakt van   weken.  De input wordt gegeven door een verzameling diensten per dag van een gehele week. Schematisch  kan  een  rooster  gezien  worden  als  een  verzameling  rijen  en  kolommen,  waarbij  de  kolommen  de  verschillende  dagen  van  de  week  weergeven  en  de  rijen  staan  voor  de  verschillende  weken.  Elk  personeelslid begint het rooster bij een andere week en voert de week daarna het rooster uit dat een  rij lager staat. Dit gaat net zo lang door tot elk personeelslid alle rijen (weken) heeft gehad.    Het  roosterprobleem  kan  worden  opgedeeld  in  twee  fasen.  In  de  eerste  fase  worden  de  diensten  verdeeld over de verschillende groepen. Dit kan worden gezien als een toewijzingsprobleem. Dit kan  worden  geformuleerd  als  een  gemengd  IP  probleem  met  0‐1  variabelen.  De  restricties  voor  dit  probleem moeten ervoor zorgen dat iedere groep ongeveer even veel leuk werk krijgt, dat er daarna  met grote kans een toegestane oplossing mogelijk is en dat elke dienst aan precies één groep wordt  toegewezen.   In de tweede fase is het per groep de taak om van alle toegewezen diensten een rooster te creëren.  Hierbij moet rekening gehouden worden met allerlei CAO regels. De kwaliteit van het rooster wordt  bepaald door de volgorde van de roosterdagen en de variatie in de diensten. Deze tweede fase is ook  weer opgesplitst in twee stappen. In de eerste stap wordt aan iedere dag van het rooster een vroege,  late  of  nachtdienst,  een  vrije  dag  of  een  speciale  dag  toegewezen.  In  de  tweede  stap  worden  de  specifieke  diensten  toegewezen  in  het  rooster.  De  doelstelling  is  om  de  totale  boete  die  bepaald  wordt door ongewilde combinaties van diensten en dagen te minimaliseren.     Notatie  1, …   is de verzameling dagen van een rooster, met | | = 7   1, … ,   is  de  verzameling  rooster  dagen.  In  stap  1  is  deze  gelijk  aan  vroege  dienst,  late  dienst, nachtdienst of speciale dag (WTV, CO of RES). In stap 2 is deze gelijk aan alle diensten.   1, … ,  staat voor alle mogelijke combinaties van versschillende soorten rooster dagen  en verschillende weekdagen.   staat voor aantal roosterdagen van    -

32   

-

 staat voor de mogelijke combinaties van toewijzingen van rooster dagen aan dagen. Het  is bijvoorbeeld alleen mogelijk om een maandag‐dienst aan maandag toe te wijzen.   1, . .  is de verzameling van ongewilde patronen in roosterdagen   staat voor de boete als patroon   op dag   begint    staat  voor  verzameling  patronen  met  een  zogenoemd  ‘Rood  Weekend’.    Een  Rood  Weekend vindt eens per drie weken plaats en is een periode van minstens 60 uur rust.  

  Beslissingsvariabelen:  1                     0                                                                                1              ,      0                                              Model    Voor beide stappen ziet het model er als volgt uit:                                                                                                                1  

min   onder: 

1                                                    

                                  2  

                                                 

                              3  

: ,

,

,

 

  :

 

,

,

1        

, :

,

 

,

             4

 

  1                                                  

, ,

 

 

,

,

                                   5  

1                      

0,1                                                              0,1                                                            

                       6   , ,

                          7                               8           

  De  doelstelling  (1)  is  om  de  totale  boete  te  minimaliseren.  Restricties  (2)  en  (3)  zorgen  ervoor  dat  elke  dag  precies  één  roosterdag  krijgt  toegewezen  en  dat  elke  roosterdag  op  een  specifieke  dag  precies  vaak  genoeg  voorkomt.  Restrictie  (4)  zijn  voorbeelden  van  restricties  waarin  het  wordt  afgestraft  als  een  vroege  dienst  op  tijdstip    plaatsvindt  en  vervolgens  een  late  dienst  op  tijdstip  1. Zo zijn er restricties voor elke    .  Restrictie (5) zorgt dat er voldoende rusttijd tussen twee  opeenvolgende diensten zit. In de eerste stap wordt er niet over specifieke diensten gepraat, maar  wordt  de  restrictie  toch  meegenomen.  Er  wordt  dan  voor  gezorgd  dat  een  dag   niet  kan  worden  opgevolgd door een dag  . Deze restricties zullen allemaal apart moeten worden ingevoerd. Restrictie  (6) zorgt dat er voldoende Rode Weekenden worden ingepland.    

33   

Voor stap 2 kunnen nog een aantal restricties worden toegevoegd. Allereerst is er nog een restrictie  voor de maximale werktijd per week.   staat voor de werktijd van roosterdag  ,   is de maximale  werktijd en   het aantal dagen in deze periode.                     

               9  

: ,

Een andere restrictie is dat een vrije dag tenminste 30 uur moet duren. Het vertelt dus iets over de  tijd tussen een taak op dat   en dag  2.     ,  

 

 

2           

,

                     10  

 

,

Hierbij is de starttijd van dienst   minder dan 30 uur na de eindtijd van dienst   en geldt  , , , 2 . De laatste extra restrictie gaat over het aantal diensten waarin een gedeelte van de nacht  valt. Definieer   als de verzameling diensten die een gedeelte van de nacht omvatten.   geeft de  lengte van een periode waarin maximaal   van deze diensten zijn toegestaan.         ,

            11  

:

Dit  model  is  toegepast  op  het  roosterprobleem  voor  station  Utrecht.  De  resultaten  waren  veelbelovend. De roosters werden in een fractie van de tijd gegenereerd dan de tijd die nodig is om  handmatig  alle  roosters  te  formuleren.  Verder  voldeden  de  roosters  aan  alle  relevante  regels,  wat  niet het geval  is bij  handmatig roosteren.   De roosters die  uit  het model  kwamen  werden ook nog  eens door het personeel geprefereerd boven de oude roosters.     2.  Bespreking artikel: Passenger railway optimization  Een  mogelijke  formulering  van  het  model  in  het  artikel  van  Caprara  et  al.  [7]  is  met  een  gerichte  Multi  graaf      , .  Hierin  worden  de  knopen  gerepresenteerd  door  diensten  die  moeten  worden  uitgevoerd  en  de  pijl  ,   bestaat  als  de  dienst    direct  kan  worden  gevolgd  door  .  Hierbij kan het voorkomen dat er meerdere pijlen van   naar   gaan, doordat er verschillende vormen  van rust tussen deze diensten zitten. Vandaar dat het ook gaat om een Multi graaf. Het is nu de taak  om een minimale kosten verzameling van circuits te vinden die elke knoop precies één keer omvat.  Om het roosterprobleem op te lossen wordt ook nog de volgende variabele ingevoerd:    1                          0                                                                                           Daarnaast wordt   ingevoerd als de kosten voor pijl  . De doelstelling is vaak om de totale lengte  van de roosters te minimaliseren, wat er dan op neerkomt om de totale hoeveelheid personeel nodig  om alle diensten uit te voeren te minimaliseren. In dit geval kunnen de kosten van pijl      ,   worden weergegeven als de tijd tussen het begin van dienst   en het begin van dienst   in het geval  :  verzameling  pijlen  dat  naar  knoop      gaat,  ze  elkaar  opvolgen  in  het  rooster.  , respectievelijk vanuit knoop   vertrekt.   Model        

 

                                                                       1  

34   

onder:   

                   

 1                                    | |

1                          

                    2                       3                  4  

,

0,1                                           

                      5      

  Hierbij  staat  de  familie    voor  de  verzameling  van  minimale  paden  of  circuits    die  niet  in  een  toegestane oplossing kunnen zitten. Merk op dat    staat voor alle reeksen van pijlen die niet door  één enkel team kunnen worden uitgevoerd vanwege de operationele restricties.   Restrictie  (1)  geeft  de  doelstellingsfunctie  weer,  die  zoals  eerder  genoemd  de  totale  kosten  minimaliseert.  Restricties  (2)  en  (3)  zorgen  ervoor  dat  elke  knoop  (dienst)  in  precies  één  circuit  voorkomt. Restrictie (3) zegt namelijk dat er precies één pijl naar knoop   mag gaan, en restrictie (2)  stelt dat het  aantal  pijlen  naar  knoop   gelijk  is  aan  het  aantal pijlen vanuit  knoop  . Restrictie (4)  zorgt ervoor dat niet alle pijlen uit zo’n verzameling   gekozen kunnen worden.   Het grootste nadeel van dit model is de zwakheid van restrictie (4) als men kijkt naar de LP‐relaxatie.  Vaak  worden  voor  het  oplossen  van  het  gerelaxeerde  model  heuristieken  gebruikt.  Restrictie  (4)  wordt dan weggelaten en er worden extra restricties opgenomen. Het idee achter de heuristiek is dat  de  roosters  één  voor  één  geproduceerd  worden  en  dat  in  het  huidige  rooster  de  volgende  dienst   volgend op dienst   zo gekozen wordt dat de extra kosten voor toevoegen van deze dienst minimaal  zijn.      

35   

Appendix F ­ Model deelprobleem 1    Beslissingsvariabelen                          0     1                        0                                                                                                  Invoer                                                         1       . 1                   0                                                                                                                                                                                                               1   0                                                                                 ,                     éé                                                                ,                                

 

   éé       

   

,

     

                             

  ,

   

 

 

 

 

 

    

 

 

 

 

 

 

 100.000.000  

  1, . . , ;

1, … ,  

  min

 

  Onder  1     

                                         

36   

   

   

 

   

 

 

    

   

 

 

    

 

      

    

  2     

                                   

          

                               

,         ,  

                                       

3     

 

  0,25 

4    

              

 

   

5     

                                ,  

   

6   

            

,

, ,

 

,

,

  0,1 ,   

0   

37   

Appendix G ­ Set Covering    Uit  de  kolomgeneratie  komen  toegestane  diensten.  Deze  diensten  moeten  ook  nog  voldoen  aan  eisen per standplaats. Het oplossen van dit probleem doen we met Set‐Covering. Set‐Covering is een  andere  manier  om  naar  dit  probleem  te  kijken.  In  plaats  van  het  dienstrooster  probleem  als  een  ingewikkeld  geheeltallig  programmeringsprobleem  te  formuleren,  die  vanwege  de  grote  omvang  bijna nooit binnen afzienbare tijd kan worden opgelost, wordt de Set‐Covering formulering gegeven  door:  min

 

onder  1    voor  0,1           voor 

1, … ,

 

1, … ,  

  Hierbij  zijn    de  kosten  van  een  specifieke  dienst  .  Gegeven  is  nu  de  0‐1  overdekkingsmatrix    =  ( ). Het getal   = 1 als taak   in dienst   uitgevoerd (overdekt) wordt. Een kolom   van de matrix    is hierbij een mogelijke dienst die door één werknemer op een dag gedaan wordt. Een rij is een taak  die  overdekt  moet  worden.  We  zijn  geïnteresseerd  in  de  goedkoopste  verzameling  diensten  (kolommen) waardoor alle taken (rijen) overdekt worden.    Een  Set‐Covering  formulering  kan  uitkomst  bieden  als  het  aantal  mogelijk  diensten  dat  een  werknemer kan uitvoeren relatief beperkt is. Dit correspondeert met een klein toegelaten gebied en  veel  restricties.  Het  probleem  is  echter  wel  dat  naarmate  het  aantal  taken  toeneemt,  het  aantal  toegelaten diensten ook snel toeneemt.   In  plaats  van  dat  de  restricties  expliciet  in  het  model  worden  opgenomen,  worden  ze  nu  impliciet  verwerkt door slechts toegelaten diensten te beschouwen die voldoen aan de CAO voorwaarden en  andere  voorwaarden.  Omdat  het  aantal  kolommen  hier  zeer  groot  is  maken  we  gebruik  van  kolomgeneratie.   De  restricties  van  het  Set‐Covering  model  dwingen  dan  af  dat  elke  taak  wordt  uitgevoerd  en  de  minimalisatie  leidt  er  toe  dat  de  goedkoopste  verzameling  diensten  wordt  geselecteerd  die  de  gegeven taken overdekken.     In de  meeste praktische toepassingen  is  de  omvang van  het Set‐Covering  probleem dermate  groot  dat het uit oogpunt van rekentijd onmogelijk is om de geheeltallig programmeringsformulering exact  door te rekenen. Men kan dan gebruik maken van verschillende heuristieken. Het is bekend dat de  heuristiek die op probabilistische principes gebaseerd is goed werkt, voor meer informatie hierover  verwijzen wij naar het Bedrijfseconometrie dictaat [5].     

38   

Appendix H ­ Uitbreiding per personeelstype    We  kunnen  bepaalde  restricties  uitsplitsen  naar  de  verschillende  soorten  personeelstypes.  De  formulering zou moeten worden aangepast door de volgende restricties toe te voegen en de oude  restricties  te  verwijderen.  Samengevat  worden  aan  alle  parameters  met  betrekking  tot  de  dag‐  en  nachttaken in drieën gesplitst met betrekking tot conducteurs, machinisten en overig, waardoor de  restricties  ook  worden  gesplitst.  Het  overige  kan  ook  weer  worden  opgesplitst  in  surveillanten  en  andere  type  werknemers  van  de  NS,  dit  doen  wij  vanwege  de  overzichtelijkheid  hier  niet.  Zonder  enige toelichting is direct duidelijk dat:   

wij = wijd + wijn    

 

∀i, j  

wijd = wijd ,c + wijd , m + wijd ,o  

∀i, j  

wijn = wijn,c + wijn ,m + wijn ,o  

∀i, j  

  Het totaal aantal taken per personeelstype op een bepaalde treinserie dat uitgevoerd wordt door alle  standplaatsen  moet  ‘minstens’  één  keer  worden  uitgevoerd.  Introduceer  voor  alle  i   de  volgende  gegevens  Ki = Di + Ni ,  Ki = Di + Ni  en  Ki = Di + Ni .  c

c

c

m

m

m

o

o

o

 Waarbij  Ni = Ni + Ni + Ni   c

m

o

en  Di = Di + Di + Di .   c

m

o

  J

∑ (w

d ,c ij

j =1

J

∑ (w

d ,m ij

j =1 J

∑ (w

d ,o ij

j =1

+ wijn,c ) ≥ Kic    

∀i  

+ wijn,m ) ≥ Kim  

∀i  

+ wijn,o ) ≥ Kio    

∀i  

Het totaal aantal nachttaken dat uitgevoerd wordt op treinserie   door een bepaald personeelstype  moet  minstens  net  zo  groot  zijn  als  het  totaal  aantal  taken  dat  er  is  op  treinserie    voor  dat  personeelstype.  J

∑w j =1

n ,c ij

J

∑w j =1

n,m ij

J

∑w j =1

n ,o ij

≥ Nic    

 

∀i  

≥ Nim    

 

∀i  

≥ Nio    

 

∀i  

 

  De volgende eisen hebben betrekking op het feit dat het totaal aantal nachttaken per personeelstype  op  een  standplaats  tussen  bepaalde  grenzen  moet  liggen  van  het  totaal  aantal  taken  dat  op  die  standplaats wordt uitgevoerd. 

39   

I

I

i =1

i =1

∑ wijn,c ≥ α cj ∑ (wijn,c + wijd ,c )     I

I

∑w i =1

I

n,o ij

 

∀j  

 

∀j  

 

∀j   

 

i =1

I

∑w i =1

≥ α mj ∑ ( wijn,m + wijd ,m )  

n,m ij

∀j  

≥ α oj ∑ (wijn,o + wijd ,o )     i =1

  I

I

i =1

i =1

∑ wijn,c ≤ β cj ∑ (wijn,c + wijd ,c )     I

I

∑w i =1

n,m ij

≤ β jm ∑ ( wijn,m + wijd ,m )  

∀j  

i =1

I

I

i =1

i =1

∑ wijn,o ≤ β oj ∑ (wijn,o + wijd ,o )    

∀j  

 

Verder geldt met betrekking tot de capaciteitseisen per personeelstype:   I

∑ (w i =1

d ,c ij

I

∑ (w i =1

d ,m ij

I

∑ (w i =1

d ,o ij

+ wijn,c ) ≤ M cj   

∀j  

+ wijn,m ) ≤ M mj  

∀j  

+ wijn,o ) ≤ M oj   

∀j  

 

wijn,c , wijn ,m , wijn ,o , wijd ,c , wijd ,m , wijd ,o ≥ 0  

∀i, j  

   

40