Samenvatting In dit proefschrift worden planningsproblemen op het gebied van routering en roostering bestudeerd met behulp van wiskundige modellen en (numerieke) optimalisatie. Kenmerkend voor de bestudeerde klasse van problemen is dat er enerzijds hier-en-nu beslissingen moeten worden genomen, terwijl gedeeltelijk slechts probabilistische informatie over de relevante planningsperiode beschikbaar is, en er anderzijds gedurende de planningsperiode online (direct) gereageerd moet worden op binnenkomende serviceverzoeken. Hiertoe is een nieuw type recourse model ontwikkeld dat idee¨en uit de onderzoeksgebieden stochastisch programmeren en online optimalisatie verenigt. Het model omvat twee stadia. In het eerste stadium, dat het vo´ orstadium ´ van de planningsperiode modelleert, zijn reeds een aantal serviceverzoeken in detail bekend, de zogenoemde vroege serviceverzoeken. Ook is bekend dat er nog meer serviceverzoeken tijdens de planningsperiode zullen binnenkomen, maar details ontbreken. Verondersteld wordt dat over deze zogenoemde late serviceverzoeken probabilistische informatie beschikbaar is. Deze informatie wordt gebruikt bij het nemen van beslissingen aangaande de vroege serviceverzoeken, de eerste-stadium beslissingen. Deze modellering is niet anders dan die van de traditionele recourse modellen van de stochastische programmering. In het tweede stadium, waarin de planningsperiode wordt gemodelleerd, komen de late serviceverzoeken e´ e´ n voor e´ e´ n binnen. Met betrekking tot deze verzoeken moeten online beslissingen gemaakt worden. De probabilistische informatie betreffende de overige late serviceverzoeken wordt in het tweede stadium niet gebruikt bij het maken van beslissingen, precies zoals gebeurt in online optimalisatie. Figuur 1 bevat een schematisch overzicht van de structuur van het twee-stadia recourse model. Naast theoretische interesse is praktische relevantie een belangrijk motief voor het bestuderen van deze klasse van problemen. Het nieuwe type model beschrijft
122 Eerste stadium Tweede stadium Vóór de planningsperiode
Tijdens planningsperiode
Beslissing over vroege verzoeken mede gebaseerd op probabilistische informatie over late verzoeken
Late verzoeken worden één voor één bekend Online beslissingen
Figuur 1. Schematisch overzicht van de structuur van het twee-stadia recourse model.
de genoemde problemen realistischer dan pure stochastisch programmeringsmodellen of pure online optimalisatie. Vo´ or ´ de planningsperiode wordt alle beschikbare (probabilistische) informatie gebruikt om een zo goed mogelijke beslissing te nemen, terwijl gedurende de planningsperiode beslissingen snel genomen worden, uitsluitend gebaseerd op de aanwezige (deterministische) data. Vergeleken met een traditioneel multi-stadia recourse model worden beslissingen gebaseerd op minder informatie, aangezien na het eerste stadium geen rekening wordt gehouden met nog niet bekende late serviceverzoeken. Daar staat tegenover dat beslissingen sneller worden genomen, wat beter overeenkomt met de praktijk. Vergeleken met modellen van online optimalisatie wordt de eerste-stadium beslissing gebaseerd op meer informatie, aangezien rekening wordt gehouden met de late serviceverzoeken door middel van probabilistische informatie. Op deze manier verwachten we een betere beslissing te kunnen nemen. Dat kost natuurlijk de nodige rekentijd, maar in het eerste stadium is dat (binnen zekere grenzen) geen bezwaar. Alleen gedurende de planningsperiode moeten beslissingen online genomen worden. In dit proefschrift wordt het nieuwe type model voor twee toepassingen nader uitgewerkt en numeriek geanalyseerd: een planningsprobleem voor een taxibedrijf voor het vervoer van zieken en gehandicapten en een vergelijkbaar planningsprobleem betreffende de inzet van monteurs voor een woningcorporatie. In hoofdstukken 2, 3 en 4 wordt het planningsprobleem voor een taxibedrijf bestudeerd, aangeduid als het deeltaxiprobleem (klanten delen een taxi). Zieken en gehandicapten bellen naar het taxibedrijf met het verzoek om op een bepaald tijdstip opgehaald en naar een bestemming gebracht te worden. E´en dag voor de planningsdag is slechts een deel van de verzoeken bekend bij het taxibedrijf; de overige verzoeken worden gedaan op de planningsdag zelf. In het deeltaxiprobleem wordt
Samenvatting (Summary in Dutch)
123
e´ e´ n dag voor de planningsdag besloten welke van de bekende verzoeken worden uitbesteed en welke door eigen voertuigen zullen worden uitgevoerd, onder onzekerheid van de late verzoeken die op de planningsdag bekend worden. Aangezien er niet voldoende eigen voertuigen aanwezig zijn om alle verzoeken uit te voeren en uitbesteden een dag van te voren goedkoper is dan gedurende de planningsdag, kan het rendabel zijn om deze beslissing te nemen. Naast de onzekerheid met betrekking tot de late verzoeken is het combineren van verzoeken een belangrijk aspect van het deeltaxiprobleem. Door geschikt te combineren zullen er minder voertuigen nodig zijn om alle verzoeken te kunnen uitvoeren, en zullen er ook minder verzoeken uitbesteed hoeven te worden. In hoofdstuk 2 wordt een variant van het deeltaxiprobleem bestudeerd waarin wordt aangenomen dat alle late verzoeken bekend worden aan het begin van de planningsdag. Vanwege deze vereenvoudigende doch onrealistische aanname komt er op slechts twee momenten informatie beschikbaar: een dag van te voren en aan het begin van de planningsdag. De structuur van het ontwikkelde twee-stadia recourse model is standaard voor stochastisch programmeren; online optimalisatie wordt niet gebruikt. De gebruikte oplossingsmethode is niet standaard, maar ad hoc ontworpen. In beide stadia worden achtereenvolgens twee optimaliseringsproblemen opgelost. Eerst het combineren van verzoeken tot routes en vervolgens het toewijzen van routes aan voertuigen (zowel eigen voertuigen als die van onderaannemers). Vanwege de complexiteit van het probleem is ervoor gekozen om geavanceerde heuristieken te ontwikkelen voor beide deelproblemen. Voor het bepalen van een goede eerste-stadium oplossing is gebruik gemaakt van een genetisch algoritme. Het doel van hoofdstuk 2 is om inzicht te krijgen in het deeltaxiprobleem, het ontwikkelde model en de oplossingsmethode. Door middel van experimenten met kleine instanties hebben we geleerd dat het combineren van verzoeken een complicerende factor is, maar ook zeer rendabel doordat de geschatte kosten sterk dalen. Verder is gebleken dat het rekening houden met de late verzoeken, bij het nemen van een beslissing over de vroege verzoeken, ook rendabel is. Een minpunt is de aanzienlijke rekentijd, veroorzaakt door het veelvuldig aanroepen van zowel de combinatie- als de toewijzingsheuristiek, met name in het tweede stadium. In hoofdstuk 3 bestuderen we het deeltaxiprobleem waarbij de vereenvoudigende doch onrealistische aanname betreffende de late verzoeken is weggelaten. In plaats daarvan wordt nu aangenomen dat de late verzoeken e´ e´ n voor e´ e´ n bekend worden gedurende planningsdag, precies zoals in de praktijk gebeurt. Het
124 ontwikkelde twee-stadia recourse model is een uitbreiding van het model uit het vorige hoofdstuk, en bevat idee¨en van zowel stochastisch programmeren als online optimalisatie. Het eerste stadium bevat nog steeds de twee optimaliseringsproblemen, maar het dynamische tweede-stadium probleem is nu gemodelleerd als een online optimaliseringsprobleem. Om dit probleem te analyseren is gebruik gemaakt van simulatie. Twee typen beslissingen worden hierin genomen waarvoor twee geavanceerde heuristieken zijn ontwikkeld: een heuristiek om late verzoeken te combineren met reeds bestaande routes en een andere heuristiek om routes toe te wijzen aan voertuigen. Wederom is een genetisch algoritme toegepast om het gehele recourse model op te lossen. Zowel het ontwikkelde model als de oplossingsmethode zijn flexibel en kunnen eenvoudig worden aangepast, bijvoorbeeld om onvoorziene gebeurtenissen zoals afgezegde verzoeken en kapotte voertuigen op te nemen. In hoofdstuk 3 zijn numerieke experimenten met relatief kleine instanties uitgevoerd om het deeltaxiprobleem en de vereenvoudigde versie van hoofdstuk 2 te kunnen vergelijken. Het blijkt, niet verrassend, dat betere beslissingen gemaakt kunnen worden indien informatie over de late verzoeken eerder bekend zou zijn. In de praktijk wordt deze informatie evenwel pas bekend gedurende de planningsdag en we hebben aangetoond dat het rendabel is om het realistische model op te lossen in plaats van het vereenvoudigde model. De verschillen in geschatte kosten zijn overigens klein. De rekentijd om het model van hoofdstuk 3 op te lossen voor een relatief kleine instantie is aanzienlijk. Dit wordt veroorzaakt door de twee heuristieken die in de simulatie gebruikt worden om beslissingen te nemen, aangezien beide heuristieken erg gedetailleerd zijn en vaak aangeroepen worden. In hoofdstuk 4 worden beide heuristieken vereenvoudigd om zodoende het model op te kunnen lossen voor grote, realistische instanties met een acceptabele rekentijd en toch kwalitatief goede oplossingen. In de toewijzingsheuristiek leidt een kleine aanpassing tot een grote daling van het aantal aanroepen, zonder een groot kwaliteitsverlies. De vereenvouding van de combinatieheuristiek is minder voor de hand liggend en daarom zijn verschillende alternatieven ontwikkeld die ofwel het aantal aanroepen verminderen ofwel de rekentijd per aanroep. Op basis van numerieke experimenten met kleine instanties is een alternatief gekozen met een bevredigend compromis tussen rekentijd en kwaliteit van de oplossingen. Ook voor het model met de twee snelle, vereenvoudigde heuristieken zijn numerieke experimenten uitgevoerd, ditmaal met grote instanties ge¨ınspireerd op de
Samenvatting (Summary in Dutch)
125
praktijk. De rekentijd is nu zeer acceptabel. Om inzicht te krijgen in de kwaliteit van de door ons model gevonden oplossingen is een vergelijking gemaakt met twee andere modellen, beiden oplosbaar in seconden: het optimistische model (in het Engels aangeduid als myopic model) en het pessimistische model. In het optimistische model wordt alleen de hier-en-nu beschikbare (deterministische) informatie gebruikt. Er wordt dus geen rekening gehouden met de late verzoeken en de bekende routes worden zoveel mogelijk toegewezen aan eigen voertuigen. In het pessimistische model daarentegen worden alle bekende routes uitbesteed om zoveel mogelijk te vermijden dat late verzoeken tegen hoge kosten moeten worden uitbesteed. Het blijkt dat ons vereenvoudigde recourse model beide andere modellen overtreft, tenzij uitbesteden gedurende de planningsdag zeer onwenselijk is (hoge strafkosten). In dat geval is het pessimistische model een snelle concurrent voor ons (vereenvoudigde) recourse model. In hoofdstuk 5 wordt het tweede planningsprobleem bestudeerd: een planningsprobleem betreffende de inzet van monteurs voor een woningcorporatie, aangeduid als het monteursprobleem. Bekende onderhoudsprojecten en toekomstige spoedklussen moeten door dezelfde groep van monteurs uitgevoerd worden. Aangezien de woningcorporatie weet dat zij niet voldoende eigen monteurs in dienst heeft om alle taken (projecten en spoedklussen) uit te voeren, zullen een aantal taken uitbesteed moeten worden aan onderaannemers. In het monteursprobleem wordt bepaald, e´ e´ n dag voor de start van de planningsperiode, welke onderhoudsprojecten door onderaannemers uitgevoerd worden en welke door eigen monteurs. Hierbij is de onzekerheid van toekomstige spoedklussen, die bekend worden gedurende de planningsperiode, een complicerende factor. Het doel is om de totale (verwachte) kosten te minimaliseren. Aangezien uitbesteden gedurende de planningsperiode duurder is dan ervoor, kan het rendabel zijn om deze beslissing te nemen. Het ontwikkelde model is wederom een twee-stadia recourse model waarin idee¨en van stochastisch programmeren en online optimalisatie zijn verenigd. In het dynamische tweede-stadium probleem wordt gebruik gemaakt van simulatie, waarin twee typen beslissingen worden genomen. Ten eerste wordt, na aankomst van een spoedklus, de starttijd van de betreffende klus bepaald (roosteringsbeslissing), en ten tweede worden taken toegewezen aan eigen monteurs of onderaannemers (toewijzingsbeslissing). Voor beide beslissingen is een geavanceerde heuristiek ontwikkeld en het gehele recourse model wordt opgelost met behulp van een genetisch algoritme. Zowel het model als de oplossingsmethode zijn flexibel
126 en kunnen eenvoudig aangepast worden om (additionele) onvoorziene gebeurtenissen op te nemen. Voorbeelden van dergelijke gebeurtenissen zijn ziekte van monteurs en vertragingen in de duur van taken. In de numerieke experimenten zijn twee versies van het probleem geanalyseerd: met en zonder de mogelijkheid van overwerk voor eigen monteurs. In hoofdstuk 5 is meer nadruk gelegd op online optimalisatie doordat twee verschillende online algoritmes zijn ontwikkeld en vergeleken voor de roosteringsbeslissing. Het eerste algoritme is eenvoudig en snel. Iedere spoedklus begint direct nadat deze bekend is geworden, zelfs als er geen eigen monteurs meer beschikbaar zijn. Het tweede algoritme is complexer en flexibeler. In dit algoritme wordt gezocht naar de eerst mogelijke starttijd in het huidige rooster zodanig dat voldoende eigen monteurs beschikbaar zijn om de hele spoedklus uit te voeren. Numerieke experimenten tonen aan dat de geschatte kosten lager zijn wanneer het tweede algoritme wordt gebruikt, precies zoals verwacht. Bovendien blijkt dat het eerste algoritme inderdaad sneller is. Omdat ook het langzamere algoritme weinig rekentijd vraagt, is het mogelijk om probleeminstanties van kleine tot middelgrote woningcorporaties op te lossen. Verder is aangetoond dat uiteraard de geschatte kosten dalen indien overwerken is toegestaan, omdat overwerken goedkoper is dan het gebruiken van onderaannemers. Tot slot blijkt dat ons recourse model (zeer) goed presteert in vergelijking met het optimistische model waarin geen rekening wordt gehouden met de spoedklussen en er zo weinig mogelijk onderhoudsprojecten worden toegewezen aan onderaannemers. In dit proefschrift wordt geconcludeerd dat een veelbelovend nieuw type model is ontwikkeld voor dynamische en stochastische planningsproblemen op het gebied van routering en roostering waarbij gedurende de planningsperiode online beslissingen gemaakt moeten worden. Gezien de complexiteit van dit soort problemen zijn geavanceerde probleemspecifieke heuristieken benodigd om oplossingen van goede kwaliteit te krijgen. Hierbij dient een afweging gemaakt te worden tussen de mate van detaillering en acceptabele rekentijd.
