NS: waarom treinen herplannen NP-hard is

Begin bij de beroemdste puzzel uit de planningswereld. Een handelsreiziger moet een aantal steden bezoeken, elk precies één keer, en eindigen waar hij begon. Welke volgorde geeft de kortste reis? Het heet het handelsreizigersprobleem, en het klinkt als iets voor een regenachtige middag.

Met vijf steden zijn er 12 verschillende rondritten, met de hand na te lopen. Met tien zijn het er 181.440. Elke stad die erbij komt, vermenigvuldigt het aantal routes met het aantal steden dat er al ligt. Schuif en zie wat dat doet.

De voor de hand liggende aanpak is brute kracht: probeer elke route en bewaar de kortste. Die vindt gegarandeerd het perfecte antwoord, en voor een handvol steden gaat dat prima. Daarna wordt hij nooit meer klaar.

De slimmere aanpak begint met een snelle, redelijke route en verbetert die. Nearest neighbour gaat steeds naar de dichtstbijzijnde stad die nog niet bezocht is. Dat is snel, maar het werkt zich vast in hoeken en houdt lange sprongen over voor het eind. 2-opt zoekt daarna twee stukken van de route die elkaar kruisen, of die andersom korter zijn, en verbindt ze opnieuw. Herhaal tot er niets meer te verbeteren valt.

Probeer ze alle drie op dezelfde kaart. Brute kracht loopt duizenden routes na om zeker te zijn. Het slimme duo komt meestal op dezelfde route uit, of binnen een paar procent, na een paar tientallen stappen. Kies daarna 30 steden en probeer brute kracht nog eens.

Het handelsreizigersprobleem heeft een vreemde eigenschap. Krijgt u een route aangereikt, dan is in een oogwenk na te rekenen hoe lang die is. Zelf de kortste route vinden kent geen bekende kortere weg: elke methode die hem gegarandeerd vindt, wordt explosief trager naarmate het probleem groeit.

Zulke problemen heten NP-hard. Ze zijn minstens zo moeilijk als een hele familie problemen die makkelijk te controleren zijn, maar voor zover iemand weet moeilijk op te lossen. Vindt u een snelle exacte methode voor één ervan, dan hebt u er een voor allemaal. Of dat überhaupt kan, de vraag P versus NP, is een van de zeven Millennium Prize Problems, met een miljoen dollar voor wie het beslecht. Niemand heeft dat nog gedaan.

Bij NP-harde problemen zoekt u dus niet naar een truc die ze makkelijk maakt. U zoekt een slimme manier om een heel goed antwoord te vinden in de tijd die u hebt.

NS heeft elke dag uitgebreide en strakke planningen voor het onderhoud van haar treinen. Elke trein die binnenkomt heeft zijn slot, zijn spoor en zijn team. Komt een trein te laat binnen, dan kan de planning niet meer worden gevolgd, en moet die worden hersteld met een herplanningsalgoritme.

Het verband met de handelsreiziger is direct. De steden worden de treinen die onderhoud nodig hebben, de route wordt de volgorde en het spoor voor elke trein, en de afstand wordt het aantal minuten vertraging. Daar komen regels bij die de handelsreiziger nooit had: welk werk op welk spoor past, welk team vrij is, welke trein op tijd weg moet voor de avondspits.

Laat hieronder één trein te laat komen en probeer drie manieren om de dag te herstellen. Het addertje: een spoor houdt één trein tegelijk, en elk team heeft zich voorbereid op de trein die de planning stuurt. Wacht op uw eigen spoor, en elke trein achter de late erft de vertraging. Improviseer, en elke trein neemt het eerste vrije spoor: treinen staan waar niemand ze verwachtte, teams moeten zoeken naar onderdelen of een trein, en terwijl ze met de ene bezig zijn, zijn ze niet klaar voor de volgende. Binnen een uur is het hele bord door elkaar gegooid. Een slimme herplanner kijkt vooruit en verplaatst alleen wat loont.

Dit maakt planningsproblemen boeiend in plaats van saai. Rekenkracht alleen wint niet. U wint door het probleem goed genoeg te begrijpen om te weten welke kortere wegen veilig zijn: welke delen van de planning kunnen blijven staan, welke keuzes vroeg zijn uit te sluiten, waar een goed antwoord waarschijnlijk ligt.

En geen twee zijn hetzelfde. Een werkplaats, een bezorgvloot, een ziekenhuisrooster en een productielijn lijken van een afstand allemaal op de handelsreiziger, maar elk heeft eigen regels, een eigen doel en een eigen tijdslimiet. Een standaard solver past zelden. Elk vraagt om een eigen, creatieve oplossing.

• Begin bij wat er ligt: een verstoorde planning herstellen is een ander probleem dan van nul plannen, en vaak een veel kleiner.
• Gebruik de structuur: regels die grote delen van de zoekruimte uitsluiten, zijn meer waard dan een snellere computer.
• Ruil bewust kwaliteit tegen tijd: een methode die in een minuut binnen één procent zit, verslaat een perfecte die morgen klaar is.
• Houd meer dan één methode achter de hand: een rustige ochtend en een chaotische spits vragen om een andere aanpak.

In plaats van één vaste regel voor elke verstoring hebben wij een nieuw herplanningsframework voorgesteld en toegepast, met in totaal vier oplossingsmethodes.

• Een framework dat de verstoorde planning als vertrekpunt neemt, in plaats van de dag opnieuw te plannen.
• Vier oplossingsmethodes binnen dat framework, elk met een eigen balans tussen de kwaliteit van de nieuwe planning en de tijd die nodig is om die te vinden.
• Een vergelijking van de methodes, zodat per situatie de juiste kan worden gekozen.