Rittenplanningsproblemen (vehicle routing problem - VRP) zijn typische problemen binnen het domein van operationeel onderzoek, gericht op het bepalen van de effici¨entste routes om klanten te bedienen met een vloot van vrachtwagens, die elk beperkt zijn in laadcapaciteit en/of reistijd. Door toedoen van files moeten logistieke bedrijven die deze rittenplanningen opstellen voor de distributie van producten, leren leven met het feit dat ze wel weten wanneer hun vrachtwagens vertrekken aan een distributiecentrum maar niet weten wanneer die vrachtwagens zullen aankomen bij de klanten. Kortom, de reistijd tussen twee klanten kan sterk vari¨eren doorheen de dag. Hierdoor worden bijvoorbeeld drukke plaatsen en periodes best zo veel mogelijk vermeden. Een belangrijke variant van het VRP is het orienteering probleem (orienteering problem - OP). Bij dit probleem is het niet langer verplicht om alle klanten te bezoeken maar in plaats daarvan wordt een selectie gemaakt van de meest winstgevende klanten. Een recente trend bij zowel het VRP als het OP is het in acht nemen van tijdstipafhankelijk reistijden (time-dependent travel times - TD). Deze nieuwe problemen worden dan respectievelijk het time-dependent vehicle routing problem en het time-dependent orienteering problem genoemd, ofwel afgekort tot TD-VRP en TD-OP. Deze toevoeging verhoogt het realiteitsgehalte van beide modellen omdat ze de reistijdvariabiliteit, die alom aanwezig is in het echte leven, in rekening brengt. Echter, zowel het TD-VRP als het TD-OP werden op wetenschappelijk vlak nog relatief weinig onderzocht in vergelijking met het aantal wetenschappelijke publicaties omtrent andere OP en VRP uitbreidingen. Dit gebrek aan onderzoek valt te betreuren aangezien tijdstipafhankelijk reistijden niet langer genegeerd kunnen worden in tal van praktische toepassingen. Dit onderzoeksproject heeft daarom als voornaamste doel oplossingsmethoden te ontwikkelen voor verscheidene types van TD-OP waardoor toekomstige rittenplanningssoftware effici¨enter files kan vermijden.

Probleembeschrijvingen

Het OP wordt gedefinieerd op een graaf (graph), een verzameling van knopen (vertices) die geografische locaties voorstellen en waar een beloning kan ontvangen worden. Een boog (arc) stelt een verbinding voor tussen twee knopen en heeft een bepaalde reistijd. Het doel van het OP is om te bepalen welke deelverzameling van knopen bezocht moet worden en in welke volgorde zodat de winst maximaal is en de maximum toegelaten reistijd niet overschreden wordt. Daarenboven moet een toegelaten OP oplossing ook starten en eindigen op een voorafbepaalde knoop. Het OP kan worden uitgebreid tot het orienteering probleem met tijdsvensters (orienteering problem with time windows - OPTW) door aan elke knoop een servicetijd en een tijdsvenster (service time and time window) te koppelen. Enerzijds stelt de servicetijd de tijd voor die nodig is om een knoop te bezoeken en anderzijds staat een tijdsvenster voor de openings- en sluitingstijd van een knoop. Files worden gemodelleerd door het maken van verscheidene veronderstellingen omtrent de benodigde reistijd om een boog af te leggen. Als men deze reistijd ziet als een constante waarde dan wordt de reistijd als deterministisch aanzien. Indien dit niet het geval is, en de reistijd onderworpen is aan variaties met een zeker kans, defini¨eren we de reistijd als stochastisch. Anderzijds moet er een onderscheid gemaakt worden tussen tijdsonafhankelijke en tijdsafhankelijke reistijden. Als de tijd om een boog af te leggen niet afhankelijk is van het tijdstip waarop men vertrekt dan wordt de reistijd als tijdsonafhankelijk gedefinieerd en kan hij voorgesteld worden als ´e´en enkele waarde. In het ander geval spreekt men van een tijdsafhankelijke reistijd. In dit laatste geval wordt de reistijd voorgesteld door een functie afhankelijk van het vertrektijdstip. Het orienteering probleem met deterministische en tijdsafhankelijke reistijden wordt het orienteering probleem met tijdstipafhankelijke reistijden (time-dependent orienteering problem - TD-OP) genoemd. De uitbreiding met tijdsvensters heet het orienteering probleem met tijdstipafhankelijke reistijden en tijdsvensters (time-dependent orienteering problem with time windows - TD-OPTW). Beide problemen worden in dit proefstuk onderzocht. De variant van het orienteering probleem waarbij de reistijd zowel stochastisch als tijdsafhankelijk is, defini¨eren we als het orienteering probleem met tijdstipafhankelijke en stochastische gewichten (time-dependent orienteering problem with stochastic weights - TD-OPSW). In dit geval bestaat de reistijd uit een unieke kansverdeling voor elk vertrektijdstip. De uitbreiding van dit probleem met tijdsvensters (time-dependent orienteering problem with stochastic weights and time windows - TD-OPSWTW) wordt in dit proefstuk onderzocht. Verder worden er ook realistische testproblemen met gekende optimale oplossingen gecre¨eerd voor het TD-OP. Deze zijn gebaseerd op de originele tijdstiponafhankelijke OP testproblemen in combinatie met een gekend snelheidsmodel voor het TD-VRP. Voor het TD-OPTW en het TD-OPSWTW werd een set van realistische testproblemen gegenereerd op basis van het echte wegennetwerk van de Benelux met 425.479 knopen en 519.915 bogen. De reistijd voor elke boog wordt bepaald aan de hand van historische reistijdinformatie die bestaat uit reistijdmetingen per 15 minuten op een typische dinsdag. Metaheuristieken worden in het onderzoeksdomein van het operationeel onderzoek algemeen aanvaard als de meest aangewezen methodes om voor optimalisatieproblemen van een realistische grootte een zeer goede oplossing te vinden binnen een relatief korte tijdspanne. De bijdrage van dit proefstuk bestaat dan ook uit het aanreiken van effici¨ente metaheuristieken voor de drie hierboven vermelde problemen (TD-OP, TD-OPTW, TD-OPSWTW). Deze metaheuristieken zijn gebaseerd op een ant colony system (ACS) en worden aangevuld met nieuwe local search moves. Local search moves proberen bestaande oplossingen te verbeteren door het aanbrengen van kleine wijzigingen aan de huidige oplossing. Daarenboven wordt ook de wiskundige formulering voor de drie problemen beschreven in dit proefstuk. Het ACS is gebaseerd op het gedrag van een mierenkolonie en is een constructie metaheuristiek die verschillende onafhankelijke oplossingen aanmaakt en verbetert gedurende een aantal iteraties. Deze oplossingen worden gecre¨eerd door een agent (een mier genaamd) die hiervoor eenvoudige beslissingsregels tot zijn beschikking heeft. Het ACS start door ´e´en voor ´e´en verschillende initi¨ele oplossingen te cre¨eeren. Het constructieproces start bij de eerste knoop en voegt dan een nieuwe knoop toe op basis van greedy informatie en een geheugenstructuur (feromonen genaamd) verbonden aan de boog die naar die knoop in kwestie leidt. De greedy informatie is gebaseerd op de ratio van de beloning en de afstand tussen de twee knopen. Na de creatie van een geldige oplossing worden, omwille van het streven naar diverse oplossingen, de opgenomen bogen minder aantrekkelijk gemaakt voor een volgende constructieprocedure. Dit wordt verwezenlijkt door de feromoonwaardes te verlagen met een verdampingsfactor. Zodra alle oplossingen van ´e´en iteratie gecre¨eerd zijn worden ze verbeterd door een set van local search moves. Welke local search move wanneer gebruikt worden verschilt per variant van het OP. Het doel van een local search move is om de oplossing te verbeteren door kleine wijzigingen aan de oplossing te maken. Bij het OP is het bijvoorbeeld mogelijk om een extra knoop aan een bepaalde route toe te voegen met het doel een hogere totale beloning te verzamelen. De feromoonwaarden van de bogen die gebruikt werden in de beste oplossing van de iteratie worden verhoogd. Nadien wordt gekeken of de beste oplossing van de iteratie beter is dan de beste oplossing die tot dan toe gevonden werd. Deze procedures worden herhaald gedurende een aantal iteraties. Wanneer na een aantal iteraties geen verbetering wordt gevonden, worden de feromoonwaarden gereset naar hun startwaarden. Voor het TD-OP bestaat de set van local search moves uit een tijdstipafhankelijke insert move, die onbezochte punten probeert toe te voegen aan een oplossing. Deze move kan snel worden uitgevoerd dankzij een lokaal evaluatie criterium. Hierdoor wordt een volledige evaluatie van de oplossing vermeden bij het nagaan van een mogelijke insert kandidaat. Om dit te verzekeren slaan we voor elke knoop in de huidige oplossing de maximale tijd op, dat een bezoek aan de knoop kan worden uitgesteld zonder dat de oplossing onhaalbaar wordt. Voor het TD-OPTW worden de drie volgende local search moves succesvol ge¨ımplementeerd. De insert move en het lokaal evaluatie criterium werden aangepast om rekening te houden met toegevoegde tijdsvensters. Ten tweede wordt een replace move ontwikkeld die ook steunt op het lokaal evaluatie criterium. Deze move probeert een knoop vanuit de huidige oplossing te vervangen door een niet opgenomen knoop met een hogere beloning. Ten derde wordt een swap move gebruikt die de positie van twee opgenomen knopen probeert uit te wisselen met als doel de reistijd te verkorten. De combinatie van tijdstipafhankelijke en stochastische reistijden in samenspraak met de tijdsvensters zorgt voor zeer gecompliceerde berekeningen van de vertrek- en aankomsttijden. Daarom worden de drie belangrijkste berekeningsmoeilijkheden en de manier waarop ze opgelost worden door een benaderingsalgoritme beschreven in dit proefstuk. Dit benaderingsalgoritme wordt ook gebruikt om een stochastische swap local search move, een insert en een replace move te ontwikkelen.

Resultaten

Het algoritme voor het TD-OP behaalt met korte berekeningstijden goede resultaten op de gegeneerde testproblemen met 20 tot 100 knopen. De optimale oplossing wordt gevonden voor 40% van de testproblemen. Verder wijst een sensitiviteitsanalyse uit dat het algoritme robuust is voor wijzigingen van de inputparameters. Gemiddeld wordt een afwijking van 1,4% met de optimale oplossing behaald, met een rekentijd van 0,5 seconden per testprobleem. Voor de uitbreiding van het probleem met tijdsvensters behaalt het aangepaste algoritme gemiddeld een afwijking van 0,2% met de optimale oplossing in een gemiddelde rekentijd van 0,4 seconden voor testproblemen die 20 tot 100 knopen bevatten. Een vergelijking tussen het ACS en een eerder voorgestelde plossingsmethode toont aan dat de performantie van de eerdere oplossingsmethode 6,2% lager ligt. Wanneer de optimale OPTW oplossing uitgevoerd wordt in een tijdstipafhankelijke omgeving, dan zijn gemiddeld de oplossingen tenminste 11,4% slechter dan oplossingen gegenereerd door het ACS. De gemiddelde TD-OPTW oplossing verschilt qua structuur 35,6% van de optimale OPTW oplossing. Voor het TD-OPSWTW behaalt het SACS oplossingen, die 23,8% beter zijn dan de optimale OPTW oplossing, uitgevoerd in een tijdstipafhankelijke en stochastische omgeving. Het SACS wordt vergeleken met oplossingen die gegenereerd werden door het ACS (ontwikkeld voor het TD-OPTW) te gebruiken. Als invoerwaarde voor de reistijd van elke boog worden verschillende percentielen van de reistijd distributie uitgeprobeerd. Het SACS presteert echter steeds beter ongeacht het gekozen percentiel voor het ACS. Wanneer het zekerheidsequivalent opgelost wordt door het ACS voor TD-OPTW dan scoort het SACS gemiddeld 1,3% beter. Beide oplossingen verschillen qua structuur echter gemiddeld 28,3% van elkaar. Het zekerheidsequivalent bestaat erin het TD-OPSWTW te reduceren tot een TD-OPTW door telkens de gemiddelde waarde te nemen als waarde voor de reistijd op elke boog. Een verrassend praktisch inzicht dat verworven is, is dat wanneer er een kans is om te laat te komen bij een knoop, dit zowel kan leiden tot een toename als tot een afname van de standaardafwijking van de vertrektijd van die knoop. Ter vergelijking, bij een bezoek aan een knoop dat met 100% zekerheid binnen het tijdsvenster valt, is de standaardafwijking van de vertrektijd gelijk aan die van de aankomsttijd. Bovendien veroorzaakt een kans op wachten aan een knoop altijd een daling van de standaardafwijking. De impact op de standaardafwijking bij een kans op een te late aankomst hangt onder andere af van de ratio van de standaardafwijking van de aankomsttijd en de grootte van de servicetijd. In het algemeen is in het begin van de route de servicetijd nog vrij hoog in vergelijking met de standaardafwijking van de aankomsttijd. Deze laatste bedraagt namelijk nul aan het begin van de route en verhoogt naarmate men het einde van de oplossing bereikt. Daarom zal een kans op een late aankomst bij een knoop in het begin van de route de standaardafwijking van de vertrektijd verhogen, terwijl een mogelijk te laat bezoek aan een knoop op het einde van de route de standaardafwijking van de vertrektijd zal doen dalen.

Praktische toepassing

Naast het oplossen van theoretische problemen zijn de verworven inzichten en oplossingsconcepten ook toegepast op een praktische gevalstudie. Bij deze case worden routeplanningen opgesteld voor twee logistiek bedrijven. Om aan alle eisen uit de praktijk te voldoen, zoals het gebruik van meerdere voertuigen, het inlassen van een lunchpauze en capaciteitslimieten wordt de oplossingsmethode voor het TD-OPTW drastisch aangepast omdat een oplossing nu anders ge¨evalueerd en aangepast wordt door de local search moves. Het voornaamste besluit uit deze gevalstudie is dat het de moeite loont om tijdstipafhankelijke reistijden in acht te nemen tijdens het optimalisatieproces. Het verder verhogen van de performantie van de voorgestelde metaheuristiek en het beter formuleren van de doelfunctie voor deze specifieke gevalstudie behoren tot de voornaamste uitdagingen voor de toekomst.

Conclusie

Orienteering problemen met tijdstipafhankelijke en stochastische reistijden vormen complexe problemen die effici¨ente oplossingsmethoden vereisen. Deze methoden moeten namelijk in staat zijn om tijdrovende evaluaties van oplossingen zoveel mogelijk te omzeilen nadat kleine aanpassingen aan een oplossing werden aangebracht. Deze problemen kunnen worden toegepast op rittenplanningsproblemen die te maken hebben met files. Want op een realistisch wegennetwerk zijn de reistijden afhankelijk van het vertrektijdstip. Daarenboven zorgen tal van factoren er ook voor dat men nooit zeker is van het aankomsttijdstip op de bestemming. In dit proefstuk worden oplossingsmethoden voorgesteld die in staat zijn deze problemen op een effici¨ente manier op te lossen. Deze oplossingsmethoden worden uitvoerig getest op realistische test problemen en ´e´en van hen wordt ook toegepast op een realistische gevalstudie in de logistieke sector.