The Inventory Routing Problem with time-dependent travel times
“Sorry meneer, uw haringen staan nog in de file!”
Het zou een flard kunnen zijn uit een telefoongesprek tussen een handelaar en zijn logistieke partner. Voor de handelaar een behoorlijk frustrerend antwoord. Hij betaalt immers de logistieke partner om de producten op tijd te leveren. Is dat dan zo moeilijk? We vragen het even aan de logistieke partner en die toont ons een resem schema’s, grafieken en diagrammen waaruit blijkt dat zijn distributieplan optimaal was. Mistroostig geeft hij toe dat uitzonderlijke omstandigheden zijn plan waarschijnlijk in de war gestuurd hebben, maar dat brengt de haringen natuurlijk niet bij de handelaar. Het is een verhaal waar niemand echt gelukkig van wordt: een gefrustreerde handelaar die blijft wachten op zijn haringen, een neerslachtige planner die zijn zoveelste optimale distributieplan in de al overvolle vuilbak smijt, de vrachtwagenchauffeur die opnieuw zijn Champions League match mist, …
Centraal in bovenstaand verhaal – voor de wiskundige althans – staat het ‘optimale’ distributieplan, dat bepaalt wat, wanneer en bij wie geleverd moet worden. Optimaliteit is een vreemd begrip in onze wereld. Voor de wiskundige die zich beweegt via de assenstelsels van zeven-dimensionale ruimten, is optimaliteit zijn beste vriend. Het onderscheidt één oplossing als de beste en biedt de zekerheid dat die oplossing steeds de beste blijft. In het echte leven is optimaliteit echter meer volatiel. Wie af en toe eens met de auto door Brussel rijdt, leert al vlug dat de snelste weg niet altijd dezelfde is. Er bestaat dus niet zoiets als ‘de beste weg door Brussel’. Bijgevolg kunnen we ook niet echt spreken van een ‘optimaal’ distributieplan.
Om deze kloof tussen de wiskundige modellen en de realiteit te dichten, stellen we een aantal aangepaste modellen, die rekening houden met onzekerheid, voor. Het doel is om modellen te ontwikkelen die globaal genomen goed presteren zodat bijvoorbeeld wanneer er wat file is, niet alles in het honderd loopt. Belangrijk bij het ontwikkelen en evalueren van deze modellen zijn de eigenschappen snelheid en optimaliteit. Laat ons eerst concentreren op de laatste eigenschap: optimaliteit. Hebben we nu niet net een alinea gespendeerd om aan te tonen dat optimaliteit een eerder ledig begrip is in de realiteit? Lijdt de auteur misschien aan een acute vorm van schizofrenie? Mogelijks, maar dan heeft dat niet zozeer met het begrip optimaliteit te maken. We gebruiken de notie optimaal als zijnde de beste onder de andere gevonden oplossingen, niet zozeer een absolute, wiskundig te bewijzen optimaliteit. De keuze voor de tweede eigenschap, snelheid, is vooral gerelateerd met de wiskundige tak waarin dit probleem zich situeert: Operations Research. In dit domein is het niet uitzonderlijk dat berekeningen uren, dagen, maanden of zelfs jaren kunnen duren. Nodeloos om te zeggen dat niemand daarop zit te wachten.
Tussen de verschillende modellen kan men fundamenteel twee types onderscheiden. Het eerste type verzamelt eerst een aantal interessante oplossingen(distributieplannen) om daarna de beste tussen de gevonden oplossingen te zoeken. Men kan het vergelijken met een wedstrijdje ‘De zwaarste steen zoeken’. Eerst verzamel je in een bepaald gebied de stenen die er het zwaarst uitzien en daarna spuit je met de hogedrukspuit de stenen zo ver mogelijk weg. De steen die het meest weerstand biedt tegen de hogedrukspuit, is hoogstwaarschijnlijk de zwaarste steen. Concreet gaan we voor ons probleem de oplossingenruimte doorzoeken naar de interessantste oplossingen. Eens die gevonden zijn laten we een stroom van duizenden mogelijke scenario’s los op de gevonden oplossingen om te bepalen welke oplossing zich het best recht houdt.
Het tweede type modellen kan men best vergelijken met een marathon afvalrace. Initieel is iedereen, elke oplossing, in de running. Elke ronde wordt een winnaar uitgeroepen. Heb je lange tijd niet gewonnen, moet je de wedstrijd verlaten. Om de afvalrace wat spannender te maken, is elke ronde wat moeilijker dan de vorige. De oplossing die overblijft op het einde is de winnaar van de afvalrace en heeft dus behoorlijk wat hindernissen overwonnen.
Tot zover de theorie. In praktijk zien we dat toch het een en ander fout loopt. Bij het zoeken van de zwaarste stenen wordt duidelijk dat die niet erg makkelijk los te wrikken zijn en de marathon afvalrace lijkt steeds meer en meer op een never ending story. Hoog tijd dus voor wat men in de wiskunde heuristieken noemt. Heuristieken zijn zowat de wonderzalf en tegelijkertijd de achilleshiel van de wiskunde. Het zijn eigenlijk niets anders dan snuggere vondsten om sneller tot een hopelijk goede oplossing te komen. De keerzijde van de medaille is dat het bewijs van optimaliteit vervalt. Ha optimaliteit, een oude vriend! Aangezien we weten dat een ‘optimaal’ distributieplan in realiteit een ijdele hoop is, vormt het vervallen van de wiskundige optimaliteit hier geen probleem. De snelheid die de heuristieken introduceren kunnen we echter wel goed gebruiken. Vanaf nu is het betere duw- en trekwerk toegelaten in de afvalrace en als een steen moeilijk loswrikbaar is, halen we met veel plezier de sloophamer boven.
Vooraleer we onze nieuwe modellen de arena insturen, laten we ze eerst eens oefenen in de zandbak. De fictieve vijand? Tien testcases. Al snel wordt duidelijk dat niet elke methode geschikt is voor alle testcases. Tijd voor een tactiek die reeds bij de Romeinen werkte: verdeel en heers. De steenzoekers zullen we voornamelijk gebruiken voor de kleine cases: een klein gebied, gemakkelijk te doorzoeken, en dan de waterkraan open. De afvalrace moet het hoofd bieden aan de complexe cases: vele oplossingen zullen de volgende ronde niet halen zodat de duur van de race toch wat beperkt blijft.
Vanaf nu zijn we klaar om de planner met raad en daad bij te staan. Over een ‘optimaal’ distributieplan zal hij voortaan niet meer kunnen spreken, maar op zijn minst zal zijn vuilbak al een stuk minder vol zijn. En nu maar hopen dat die haringen uiteindelijk nog zijn toegekomen.
Wouter Lefever
