The Inventory Routing Problem with time-dependent travel times

Wouter
Lefever

“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

Bibliografie

[1] El-Houssaine Aghezzaf. Robust distribution planning for supplier-managed inventory agreements when demand rates and travel times are stationary. Journal of the Operational Research Society, 59(8):1055-1065, 2008.

[2] Dana H Ballard. Generalizing the hough transform to detect arbitrary shapes. Pattern recognition, 13(2):111-122, 1981.

[3] Cock Bastian and Alexander HG Rinnooy Kan. The stochastic vehicle routing problem revisited. European Journal of Operational Research, 56(3):407-412, 1992.

[4] Walter J Bell, Louis M Dalberto, Marshall L Fisher, Arnold J Green eld, Ramchandran Jaikumar, Pradeep Kedia, Robert G Mack, and Paul J Prutzman. Improving the distribution of industrial gases with an on-line computerized routing and scheduling optimizer. Interfaces, 13(6):4-23, 1983.

[5] Aharon Ben-Tal and Arkadi Nemirovski. Robust convex optimization. Mathematics of Operations Research, 23(4):769-805, 1998.

[6] Aharon Ben-Tal and Arkadi Nemirovski. Robust solutions of uncertain linear programs. Operations research letters, 25(1):1-13, 1999.

[7] Aharon Ben-Tal and Arkadi Nemirovski. Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming, 88(3):411-424, 2000.

[8] Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations research, 52(1):35-53, 2004.

[9] Robert L Carraway, Thomas L Morin, and Herbert Moskowitz. Generalized dynamic programming for stochastic combinatorial optimization. Operations Research, 37(5):819-829, 1989.

[10] G u Clarke and JW Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4):568-581, 1964.

[11] Leandro C Coelho, Jean-Francois Cordeau, and Gilbert Laporte. Thirty years of inventory routing. Transportation Science, 2013.

[12] Moshe Dror. Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution. European Journal of Operational Research, 64(3):432-441, 1993.

[13] Moshe Dror, Gilbert Laporte, and Francois V Louveaux. Vehicle routing with stochastic demands and restricted failures. Zeitschrift fur Operations Research, 37(3):273-283, 1993.

[14] Moshe Dror, Gilbert Laporte, and Pierre Trudeau. Vehicle routing with stochastic demands: Properties and solution frameworks. Transportation science, 23(3):166-176, 1989.

[15] Moshe Dror and Pierre Trudeau. Stochastic vehicle routing with modi ed savings algorithm. European Journal of Operational Research, 23(2):228-235, 1986.

[16] Michel Gendreau, Gilbert Laporte, and Rene Seguin. Stochastic vehicle routing. European Journal of Operational Research, 88(1):3-12, 1996.

[17] Michel Gendreau, Gilbert Laporte, and Rene Seguin. A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Operations Research, 44(3):469-477, 1996.

[18] Bruce L Golden and WR Stewart. Vehicle routing with probabilistic demands. In Computer Science and Statistics: Tenth Annual Symposium on the Interface, NBS Special Publication, volume 503, pages 252-259, 1978.

[19] Eleni Hadjiconstantinou and Daron Roberts. Routing under uncertainty: an application in the scheduling of eld service engineers. The vehicle routing problem, pages 331-352, 2002.

[20] Edward PC Kao. A preference order dynamic program for a stochastic traveling salesman problem. Operations Research, 26(6):1033-1045, 1978.

[21] Veronique Lambert, Gilbert Laporte, and Francois Louveaux. Designing collection routes through bank branches. Computers & Operations Research, 20(7):783-791, 1993.

[22] Gilbert Laporte, Francois Louveaux, and Helene Mercure. The vehicle routing problem with stochastic travel times. Transportation science, 26(3):161-170, 1992.

[23] Jovan Popovic. Vehicle routing in the case of uncertain demand: A bayesian approach. Transportation planning and Technology, 19(1):19-29, 1995.

[24] Daron Roberts and Eleni Hadjiconstantinou. Algorithmic developments in stochastic vehicle routing. In Operations Research Proceedings 1997, pages 156-161. Springer, 1998.

[25] Hisham Said and Khaled El-Rayes. Automated multi-objective construction logistics optimization system. Automation in Construction, 43(0):110-122, 2014.

[26] Ben Shepherd. Logistics costs and competitiveness: measurement and trade policy applications. 2011.

[27] Moshe Sniedovich. Analysis of a preference order traveling salesman problem. Operations Research, 29(6):1234-1237, 1981.

[28] Oguz Solyali, Jean-Francois Cordeau, and Gilbert Laporte. Robust inventory routing under demand uncertainty. Transportation Science, 46(3):327-340, 2012.

[29] Allen L Soyster. Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5):1154-1157, 1973.

[30] William R Stewart Jr and Bruce L Golden. Stochastic vehicle routing: A comprehensive approach. European Journal of Operational Research, 14(4):371-385, 1983.

[31] Dusan Teodorovic, Emina Krcmar-Nozic, and Goran Pavkovic. The mixed fleet stochastic vehicle routing problem. Transportation Planning and Technology, 19(1):31-43, 1995.

[32] Dusan Teodorovic and Goran Pavkovic. A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand. Transportation Planning and Technology, 16(4):261-273, 1992.

[33] Frank A Tillman. The multiple terminal delivery problem with probabilistic demands. Transportation Science, 3(3):192-204, 1969.

Download scriptie (1.01 MB)
Universiteit of Hogeschool
Universiteit Gent
Thesis jaar
2014