G.C. van der Vlist en W.L. Kuipers
Crew Scheduling op het juiste spoor. De mogelijkheden en beperkingen van
geautomatiseerde systemen voor het plannen van het rijdend personeel bij NS
Reizigers.
Doctoraalopdracht,
Rapport 99.3.LT.5238, Transporttechnologie, Logistieke Techniek.
Het plannen van het rijdend personeel betekent bij NS Reizigers dat aan
iedere rit uit de dienstregeling het benodigde personeel wordt toegewezen.
Dit vindt bij NS Reizigers plaats op de afdeling Logistiek alwaar
handmatig, met behulp van ondersteunende systemen, de diensten voor het
rijdend personeel worden opgesteld.
'Bestemming: Klant' volgt uit de doelstelling van NS Reizigers om
concurrerend en hoogwaardig collectief personenvervoer te bieden. Hierin
wordt ernaar gestreefd een forse groei in het aantal vervoerde reizigers
te bewerkstelligen. Tegelijkertijd dient er een kwaliteitsverbetering
plaats te vinden.
Voor het rijdend personeel houdt dit in dat kritische overgangen tijdens
de dienst zo veel mogelijk vermeden dienen te worden. Zo wordt er voor
gezorgd dat de invloed van het personeel op de punctualiteit van de
uitvoering van de dienstregeling geminimaliseerd wordt. Verder wordt er
naar gestreefd het personeel productgebonden in te zetten. Hierbij kan het
product nader ingevuld worden.
Het onderzoek is uitgevoerd in het kader van 'Bestemming: Klant' waarbij
gebruik is gemaakt van het geautomatiseerde planningssysteem TURNI.
Doel van het onderzoek is het verkrijgen van inzicht in de mogelijkheden
en beperkingen van geautomatiseerde svstemen voor het plannen van het
rijdend personeel bij NS Reizigers. Verder richt het onderzoek zich op de
evaluatie van het pakket TURNI en de analyse van verschillende varianten
voor de inzet van het rijdend personeel. Deze varianten worden met het
systeem TURNI ontworpen ter ondersteuning van NSR Logistiek, ten behoeve
van het project 'Bestemming: Klant'.
De modellering nodig voor het vormen van diensten kan gebeuren door de
taken en de bijbehorende opvolgingen tussen de taken in een graaf weer te
geven. Uitgaande van een modellering waarin in de graaf de kanten taken,
en de knopen de betreffende opvolgingen zijn, is een dienst nu een pad
door deze graaf dat aan de regels voldoet. Het aantal mogelijke paden kan
snel toenemen bij de planning van het rijdend personeel van NS Reizigers.
Dit komt doordat de duur van de taken soms erg kort is waardoor het aantal
mogelijke combinaties sterk zal toenemen. Om er voor te zorgen dat de
structuur in de gevormde diensten overeen zal komen met een gekozen
uitgangspunt, is het vooral van belang dat bij het vormen van de graaf
alle regels omtrent de verschillende mogelijke opvolgingen duidelijk
zijn.
Het CSP, gemodelleerd met behulp van een graaf, kan op twee manieren worden
opgelost. Allereerst het Network Flow Problem, waarbij gezocht wordt naar
die stroom door het netwerk, waarbij alle taken doorlopen worden en de
totale kosten minimaal zijn. Vervolgens is er het Set Covering Problem,
waarbij gezocht wordt naar een minimani aantal paden, onder de voorwaarde
dat iedere taak minimaal één keer doorlopen is. Meest toegepaste
modellering voor het CSP is het Set Covering Problem. De meest succesvol
toegepaste algoritmen voor het Set Covering Probleem zijn gebaseerd op
Lagrange relaxatie in combinatie met de subgradient methode. Hierop is ook
TURNI gebaseerd.
Met behuip van TURNI zijn in het kader van het project 'Bestemming: Klant'
verschillende varianten doorgerekend. Verder is bekeken in welke mate TURNI
in het planningsproces van NS Reizigers opgenomen kan worden. Hiervoor
worden aanbevelingen gedaan omtrent de aspecten van het planningspakket
die voor verandering in aanmerking komen.
Rapporten studenten Logistieke Techniek
Gewijzigd: 2000.02.06;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.