A Methodological Framework for Evaluating Metaheuristics: An Application to Vehicle Routing

Abstract

Combinatorische optimalisatieproblemen, waarbij gezocht wordt naar de beste oplossing uit een eindig aantal oplossingen, behandelen vaak problemen met een grote economische relevantie, zoals de planning van ritten voor de distributie van goederen en het invullen van dienstregelingen. Dit heeft geleid tot de ontwikkeling van een groot aantal procedures die in staat zijn een oplossing voor deze problemen te genereren. Hierbij wordt een onderscheid gemaakt tussen exacte en heuristische methoden. Veel combinatorische optimalisatieproblemen zijn moeilijk op te lossen en worden daarom als NP-moeilijk aangeduid. Hiermee wordt bedoeld dat er geen snel (d.i. polynomiaal) exact algoritme bestaat dat elke instantie van het probleem in een redelijke tijd optimaal kan oplossen. Exacte methoden garanderen dat de optimale oplossing gevonden wordt en kunnen bijgevolg een enorme hoeveelheid rekentijd vereisen om een dergelijke oplossing te waarborgen. Deze algoritmes zijn daarom enkel toepasbaar op kleine probleeminstanties. Het merendeel van de ontwikkelde oplossingsmethoden zijn heuristisch van aard en in staat goede oplossingen te genereren binnen een aanvaardbare rekentijd, zonder te garanderen dat deze oplossing ook de optimale oplossing is. Hoe effectief of effici¨ent een heuristiek is, wordt gewoonlijk beoordeeld in een empirische studie waarbij de performantie van een heuristiek toegepast op een optimalisatieprobleem ge¨evalueerd wordt door instanties van een of meerdere probleembenchmarks op te lossen en de vergelijking te maken met de resultaten die bestaande methoden behaald hebben op deze benchmarks. Deze evaluatiebenadering legt de nadruk op het competitief zijn, op het ontwikkelen van een algoritme dat ‘beter’ kan presteren dan reeds bestaande algoritmes. ‘Beter’ betekent het behalen van een verbeterde oplossingskwaliteit, vereisen van minder rekentijd voor eenzelfde oplossingskwaliteit, of een gunstigere afweging van beide prestatiemaatstaven. Wat een dergelijke competitieve evaluatiebenadering niet toelaat, is het verklaren waarom een nieuw voorgestelde heuristiek beter presteert. Kan het toegeschreven worden aan een ingenieus ontwikkelde operator werkzaam binnen het algoritme? Of misschien ligt het simpelweg aan een meer effici¨ente implementatie van een bestaande methode? Dragen alle componenten significant bij tot de behaalde prestatiewaarde, of zouden bepaalde elementen weggelaten kunnen worden om zo de effici¨entie te verhogen? Dit zijn allemaal vragen die vaak onbeantwoord blijven wanneer een heuristiek gepresenteerd wordt in een onderzoekspublicatie. Hoewel enige competitie tussen onderzoekers zeker kan aanzetten tot innovatieve ontdekkingen, is het erkend dat ‘ware innovatie’ gefundeerd is op het begrijpen van hoe een heuristische oplossingsmethode zich gedraagt, niet op bewijs van concurrentievermogen. Het is het ultieme doel van wetenschap om te begrijpen, niet om te winnen van anderen. Een competitieve evaluatie is nuttig indien het doel is om de snelst en best mogelijke procedure te ontwikkelen voor een specifieke probleemcontext. Indien het doel is te begrijpen hoe een prestatiewaarde behaald werd, te ontdekken welke elementen in de heuristiek een bijdrage leveren en conclusies af te leiden die niet enkel gelden voor de specifiek onderzochte probleeminstanties, dan is een statistische evaluatie vereist. De doelstelling van dit doctoraatsonderzoek is dan ook het promoten van een werkwijze voor het experimenteren met heuristieken waarbij de focus ligt op het verkrijgen van begrip en inzicht in hoe een heuristiek tot een prestatiewaarde komt. De verworven kennis kan dan gebruikt worden bij het ontwerpen en optimaliseren van algoritmes alsook bij het vergelijken van verschillende algoritmes. Om deze doelstelling te vervullen wordt een evaluatiemethodologie voorgesteld op basis van de concepten uit Design of Experiments en het gebruik ervan gedemonstreerd in een aantal experimentele studies. De methodologie is toepasbaar op een breed scala aan optimalisatieproblemen en algoritmes, maar in deze thesis ligt de focus op het analyseren van de performantie van een large neighbourhood search algoritme toegepast op instanties van het rittenplanningsprobleem met tijdvensters. Dit is een belangrijk probleem in menig distributiesysteem en heeft daarom heel wat onderzoekswerk naar zowel exacte als heuristische methoden ge¨ınspireerd. Maar relatief weinig onderzoeksinspanningen zijn geleverd waarbij statistische technieken toegepast worden bij de analyse van deze problemen of waarbij men erop uit is te begrijpen hoe het probleem van invloed is op de performantie van een algoritme. Dit doctoraatsonderzoek beschouwt het als de volgende stap in experimenteel onderzoek naar rittenplanningsproblemen om een beter begrip en inzicht te verkrijgen in de effecten die parameters en componenten hebben op de performantie van een heuristisch algoritme. De voorgestelde methodologie is in staat aan te duiden welke elementen een significante impact hebben op de oplossingskwaliteit die een algoritme behaalt en hoe de probleemkenmerken deze effecten be¨ınvloeden. Multilevel experimentele ontwerpen worden gebruikt om effici¨ent te analyseren hoe effecten vari¨eren naargelang de probleeminstantie die opgelost moet worden. Zo kunnen verschillende aanbevelingen voor verschillende delen van de probleemruimte afgeleid worden. Verder laat het onderzoekers ook toe vaststellingen te doen voor een volledige populatie van probleeminstanties in plaats van een beperkt aantal benchmarkinstanties. De methodologie omvat een iteratief proces waarbij gegevens eerst geobserveerd worden om vervolgens vragen die uit deze observaties voortkomen te beantwoorden in vervolgstudies, die op hun beurt weer tot observaties kunnen leiden waarbij vragen gesteld worden. Het vertrekpunt is dus het uitvoeren van een verkennende analyse om bloot te leggen hoe de elementen van het algoritme gecorreleerd zijn met de prestatiewaarde evenals de correlaties van de probleemkenmerken met de algoritmeparameters en -componenten. Vervolgens zal een verklarende analyse, waarbij hypotheses geformuleerd en getoetst worden, uitzoeken hoe geobserveerde correlaties tot stand komen. De verkennende analyse is in eerste instantie volledig gebaseerd op een multilevel regressieanalyse en vervolgens enkel op de elementen en probleemkenmerken die het belangrijkst zijn om een goede prestatie van het algoritme te behalen. Deze focus op de belangrijkste effecten wordt verkregen door een functional analysis of variance (fANOVA) uit te voeren voordat het multilevel regressiemodel wordt opgesteld. De rangschikking van effecten die fANOVA als output aanlevert zal leiden tot een meer beknopt regressiemodel met minder variabelen. De regressieanalyse voorziet een meer gedetailleerde analyse van de effecten die algoritme-elementen hebben en laat ook toe om verklarende analyses uit te voeren. De toepassing van de methodologie wordt ge¨ıllustreerd aan de hand van een gevalstudie waarbij de performantie van een large neighbourhood search algoritme op het rittenplanningsprobleem met tijdvensters wordt geanalyseerd. Een verkennende studie geeft aan dat alle destroy en repair operatoren opnemen in het algoritme niet noodzakelijk tot de beste resultaten leidt. Enkel regret-2 als repair operator gebruiken wordt gesuggereerd als de gemiddeld beste keuze. De destroy operator die hierbij het best presteert is random removal. Deze bevindingen worden bevestigd door een fANOVA die niet gebonden is aan de assumpties waaraan regressiemodellen dienen te voldoen en dus de analyse meer robust maakt. De verkennende analyse leidde ook tot nieuwe vragen, zoals waarom klanten willekeurig verwijderen beter werkt dan een geografische cluster van klanten te verwijderen indien deze klanten opnieuw in de oplossing worden ingevoegd, gebruikmakende van een moeilijkheidscriterium (d.i. de regretwaarde). Verklaringen worden daarom gezocht voor het geobserveerde prestatieverschil tussen deze twee destroy operatoren in het geval zij gebruikt worden met een bepaald type repair operator. Uit de verklarende analyse blijkt dat geografische clusters van klanten verwijderen het aantal invoegingsalternatieven waaruit gekozen kan worden tijdens de repair-fase reduceert. Verschillende klanten hebben zelfs geen enkele haalbare (d.i. ‘feasible’) invoegingsoptie in een van de bestaande routes en worden daarom beschouwd als ge¨ısoleerde gevallen (bij het begin van de repair-fase). De plaatsing van deze klanten uitstellen blijkt nefast te zijn voor de oplossingskwaliteit. Daarom wordt getest of een betere oplossing verkregen kan worden indien deze ge¨ısoleerde klanten een hogere prioriteit krijgen door toe te laten dat zij ingevoegd worden in een individuele route die vanuit het depot rechtstreeks naar de betreffende klant rijdt en vervolgens terugkeert naar het depot. Een dergelijke optie werd voorheen gezien als een laatste alternatief. Doordat deze individuele routes eerder gecre¨eerd kunnen worden tijdens het herstelproces worden ook goede invoegingsalternatieven toegevoegd voor andere verwijderde klanten, resulterend in een posifief effect op de oplossingskwaliteit. Een regret operator zal dus een betere inschatting maken van hoe moeilijk de plaatsing van een klant is en dus een betere prioritering indien iedere individuele klant bestaande routes in de nabijheid heeft waarin deze ingevoegd kan worden. Door middel van een dergelijke gedetailleerde analyse van een destroy en repair iteratie werd het merendeel van het performantieverschil tussen beide destroy scenario’s verklaard. De verkennende analyse kan niet enkel gebruikt worden als vertrekpunt voor volgende verklarende analyses die trachten geobserveerde correlaties te verklaren, maar kan ook dienen om goedpresterende parameterwaarden en componenten te kiezen, voor zowel een gemiddelde probleeminstantie als voor iedere individuele instantie. De methodologie wordt hier dus toegepast om het algoritme te tunen zodanig dat de beste prestatie verkregen wordt. Beslissingsregels worden afgeleid voor iedere parameter en component en zijn geformuleerd op basis van de (significante) probleemkenmerken om zo een algoritmeconfiguratie te bekomen, gepersonaliseerd op iedere probleeminstantie. Het is aangetoond dat er vaak niet een enkele configuratie bestaat die het best presteert voor iedere individuele probleeminstantie, maar dat de prestatie van een heuristische methode varieert over de set van instanties die opgelost dienen te worden. De overtuiging is dat de methodologie die in deze thesis wordt voorgesteld die prestatievariatie kan exploiteren. Eerst wordt een enkele configuratie uit de analyse afgeleid die voorspeld wordt het best te presteren voor een gemiddelde probleeminstantie, gelijkaardig aan de configuratie verkregen uit bestaande automatische algoritmeconfiguratoren zoals irace. Hierbij wordt de invloed van probleemkenmerken op de effecten van parameters en componenten buiten beschouwing gelaten. Deze configuratie presteert gelijkaardig aan die verkregen uit irace en beter en beter naargelang het regressiemodel op meer data getraind wordt. Vervolgens wordt nagegaan hoe de instantiespecifieke configuraties presteren. Deze blijken geen voordeel te bieden ten opzichte van een enkele configuratie voor een gemiddelde instantie. Dit is waarschijnlijk te wijten aan het feit dat de gegenereerde probleeminstanties vrij homogeen zijn en dus geen mogelijkheid bieden om prestatievariatie te exploiteren. De kernboodschap van dit doctoraatsproefschrift is dat wetenschappelijk onderzoek doen eerder gaat over begrijpen dan over het winnen van een competitie. Een grondige analyse uitvoeren op experimentele resultaten kan waardevolle kennis opleveren die niet beperkt is tot de specifieke experimentele context, maar die nuttig kan zijn voor elk gerelateerd onderzoek. Wanneer men geconfronteerd wordt met een rittenplanningsprobleem, kan de beslissing over welke oplossingsstrategie¨en toe te passen of hoe ze te optimaliseren beargumenteerd worden op basis van eerder uitgevoerde analyses. Deze analyses dienen rekenschap te geven aan zowel het algoritme als de probleeminstanties die opgelost worden, zodanig dat hun wisselwerking onderzocht kan worden. Deze thesis spoort aan om onderzoek uit te voeren dat niet gebonden is aan de specificiteiten van een experiment, maar dat veralgemeenbaar is naar een breder geheel van gelijkaardige contexten. Dit proefschrift biedt de onderzoeksgemeenschap een plan van aanpak om dit uit te voeren en om te leren over zowel het probleem als de oplossingsmethode.