Optimalisatieplanning voor operationeel beheer van stortklaar beton

Academiejaar 2010-2011

Departement Toegepaste Ingenieurswetenschappen Valentin Vaerwyckweg 1, 9000 Gent

Optimalisatieplanning voor operationeel beheer van stortklaar beton

Masterproef voorgedragen tot het behalen van het diploma van ¨ MASTER IN DE INDUSTRIELE WETENSCHAPPEN: INFORMATICA

Bart Wulteputte Promotoren: Intern: Ann Van Overberge Extern: Joris Van Maldeghem

Academiejaar 2010-2011

Departement Toegepaste Ingenieurswetenschappen Valentin Vaerwyckweg 1, 9000 Gent

Optimalisatieplanning voor operationeel beheer van stortklaar beton

Masterproef voorgedragen tot het behalen van het diploma van ¨ MASTER IN DE INDUSTRIELE WETENSCHAPPEN: INFORMATICA

Bart Wulteputte Promotoren: Intern: Ann Van Overberge Extern: Joris Van Maldeghem

Inhoudsopgave Inhoudsopgave

1

Voorwoord

2

1 Inleiding

4

2 Algemene situatieschets 2.1 Doel van de masterproef . . . . . . . . . . . . . . . . . . . . . 2.2 Beschrijving van ICORDA . . . . . . . . . . . . . . . . . . . . 2.3 Beschrijving van Gebroeders De Rycke NV . . . . . . . . . .

6 6 7 7

3 Literatuurstudie van het Vehicle Routing Problem 3.1 Het Vehicle Routing Problem . . . . . . . . . . . . . 3.2 Basis van het Vehicle Routing Problem . . . . . . . . 3.2.1 Traveling Salesman Problem . . . . . . . . . 3.2.2 Bin Packing Problem . . . . . . . . . . . . . . 3.3 Overzicht van variaties en specialisaties van VRP . . 3.3.1 VRP . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 CVRP . . . . . . . . . . . . . . . . . . . . . . 3.3.3 CVRPTW . . . . . . . . . . . . . . . . . . . . 3.3.4 DCVRP . . . . . . . . . . . . . . . . . . . . . 3.3.5 VRPB . . . . . . . . . . . . . . . . . . . . . . 3.3.6 VRPBTW . . . . . . . . . . . . . . . . . . . . 3.3.7 VRPPD . . . . . . . . . . . . . . . . . . . . . 3.3.8 VRPPDTW . . . . . . . . . . . . . . . . . . . 3.3.9 MDVRP . . . . . . . . . . . . . . . . . . . . . 3.3.10 MDVRPTW . . . . . . . . . . . . . . . . . . 3.3.11 SDVRP . . . . . . . . . . . . . . . . . . . . .

i

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

8 8 9 10 10 11 11 12 12 12 12 12 13 13 13 13 14

3.4 3.5 3.6

3.3.12 SDVRPTW . . . . . . . . . . . . . Classificatie van de opdracht . . . . . . . Algemene oplossingsstrategiëen voor VRP Resultaten van het onderzoek . . . . . . . 3.6.1 Vaststellingen . . . . . . . . . . . . 3.6.2 Keuze van de oplossingswijze . . .

4 Genetische algoritmen 4.1 Inleiding . . . . . . . . . . . . . 4.2 Pseudocode genetisch algoritme 4.3 Terminologie . . . . . . . . . . 4.3.1 Initiële populatie . . . . 4.3.2 Fitnesswaarde . . . . . . 4.3.3 Selectie . . . . . . . . . 4.3.4 Crossover . . . . . . . . 4.3.5 Mutatie . . . . . . . . . 4.4 Bedenkingen omtrent GA’s . .

. . . . . . . . .

5 Implementatie 5.1 Graafklasse . . . . . . . . . . . . 5.1.1 Uitwerking . . . . . . . . 5.2 Entiteiten van de module . . . . 5.2.1 Invoer via xml . . . . . . 5.2.2 Invoer via objecten . . . . 5.3 Klassendiagram van het GA . . . 5.4 Ontwerp van het GA . . . . . . . 5.5 Voorstelling van een chromosoom 5.5.1 Het individu . . . . . . . 5.5.2 Hindernissen . . . . . . . 5.6 Initiële populatie aanmaken . . . 5.6.1 Gevaren . . . . . . . . . . 5.6.2 Constructie . . . . . . . . 5.6.3 Hindernissen . . . . . . . 5.7 Evaluatiefunctie . . . . . . . . . . 5.7.1 Inleiding . . . . . . . . . . 5.7.2 Implementatie . . . . . . 5.7.3 Hindernissen . . . . . . . Inhoudsopgave

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . .

14 14 16 17 17 17

. . . . . . . . .

19 19 21 21 21 22 22 24 24 25

. . . . . . . . . . . . . . . . . .

27 27 27 32 32 36 38 44 45 45 48 49 49 49 52 52 52 53 55 ii

5.8

5.9

Reproductie . . . . . . . . . . . . . . . . . . . 5.8.1 Selectie . . . . . . . . . . . . . . . . . 5.8.2 Hindernissen bij selectie . . . . . . . . 5.8.3 Genetische operatoren . . . . . . . . . 5.8.4 Hindernissen bij genetische operatoren Parameters . . . . . . . . . . . . . . . . . . .

6 Resultaat 6.1 Verwezenlijkingen . . . . . . . 6.1.1 Literatuurstudie . . . 6.1.2 Planningsmodule . . . 6.1.3 GUI . . . . . . . . . . 6.2 Beoordeling t.o.v. doelstelling 6.3 Besluit . . . . . . . . . . . . . Literatuurlijst

Inhoudsopgave

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

56 56 59 60 68 70

. . . . . .

73 73 73 74 75 76 77 79

1

Voorwoord Deze scriptie wordt voorgedragen tot het behalen van het diploma “master in de industriële wetenschappen informatica” aan de Hogeschool Gent. Binnen deze scriptie vindt u alle informatie omtrent het uitwerken van de masterproef. Hierbij komt zowel een deel onderzoek als een deel implementatie aan bod. Het voorstel voor deze masterproef beschrijft de ontwikkeling van een module die als doel heeft om op basis van bepaalde invoergegevens een geoptimaliseerde planning op te stellen. Deze planning heeft als doel de beschikbare middelen zo efficiënt mogelijk te benutten. Het voorstel voor deze opdracht werd ingediend door het informaticabedrijf ICORDA NV in opdracht van hun klant, de firma De Rycke Gebroeders. De opdracht werd uitgewerkt gedurende de periode van februari 2011 tot en met juni 2011 op de afdeling Development van ICORDA te Mariakerke door Bart Wulteputte. Het tot stand komen van deze masterproef heb ik te danken aan vele personen. Vanzelfsprekend dank ik mijn beide promotoren. Bij mijn interne promotor, Ann Van Overberge, kon ik steeds terecht voor vragen en suggesties omtrent de masterproef en het schrijven van de scriptie. Bij mijn externe promotor, Joris Van Maldeghem, kon ik steeds terecht met vragen en opmerkingen. De high-level aanpak en begeleiding zorgden ervoor dat ik steeds een duidelijk doel voor ogen had en mezelf nooit verloor in de immense berg details van de concrete implementatie. Daarnaast wens ik ook nog een andere medewerker van ICORDA NV te bedanken voor zijn tijd en input, namelijk Sander Wollaert (C# Developer). Wanneer ik vast dreigde te komen zitten, reikte deze persoon mij heel vaak 2

een heel nieuwe invalshoek aan, die meestal leidde tot een oplossing voor het probleem in kwestie.

Aan allen een welgemeende dank, zonder jullie had deze masterproef nooit tot stand kunnen komen.

Inhoudsopgave

3

Hoofdstuk 1

Inleiding In deze scriptie komt een onderwerp aan bod dat tot vandaag een extreem belangrijk onderdeel vormt van vrijwel ieder bedrijf dat te maken heeft met transport, distributie en logistiek, namelijk planning van de beschikbare resources met als doel enerzijds een zo hoog mogelijke servicegraad ten opzichte van de klant(en) te bereiken en anderzijds zo weinig mogelijk kosten te maken. De theorie die zich hierop toespitst kan worden samengevat onder de Engelse term “Vehicle Routing Problems”. Het onderwerp “Vehicle Routing Problem” is heel interessant om een aantal redenen. Allereerst moeten we planning van voertuigen in de ruimste zin van het woord beschouwen. Zo denken we bijvoorbeeld aan het opstellen van een rittenplanning bij een transporteur, rittenplanning bij een taxibedrijf, rittenplanning bij een JIT-leverancier enz. We kunnen het onderwerp zelf nog verder opentrekken naar schedulingproblemen zoals het opstellen van uurroosters/examenroosters. Zo breed gaan we in deze thesis echter niet. Het geautomatiseerd opstellen van een planning - rekening houdend met diverse beperkingen en eisen - is een onderwerp waar al veel onderzoek naar gebeurd is, maar waar slechts een handvol (deels) werkende oplossingen voor bestaan. Deze oplossingen werken nota bene enkel voor “schoolvoorbeelden” van problemen en dan vaak nog in een grootteorde qua tijd die niet meer werkbaar is in de praktijk. Het doel van deze scriptie is het ontwerpen en het uitwerken van een 4

efficiënt algoritme dat het Vehicle Routing Problem kan oplossen voor dit specifieke probleem. In de concrete implementatie zal het algoritme ritten (= levering van beton bij klanten door de firma De Rycke NV) gaan inplannen. Ritten hebben enkele restricties zoals tijd, capaciteit en werkuren. Naast de implementatie van het algoritme zelf moet er ook nog een grafische interface gecodeerd worden die toelaat om de ritten visueel te bekijken en/of te wijzigen. Voor meer informatie omtrent het concrete probleem verwijs ik naar de situatieschets.

Hoofdstuk 1. Inleiding

5

Hoofdstuk 2

Algemene situatieschets 2.1

Doel van de masterproef

Het doel van deze masterproef is het verwezenlijken van een module die op basis van externe input een geoptimaliseerde transportplanning voor stortklaar beton kan maken. De bedoeling is dat enerzijds een betere servicegraad voor de klanten bereikt wordt en anderzijds zo weinig mogelijk kosten aan deze servicegraad verbonden zijn. Het is de bedoeling dat deze module ge¨ıntegreerd zal worden in de huidige software, waarmee men momenteel manueel ritten inplant bij de firma De Rycke Gebroeders (die de opdracht voor deze module aan de firma ICORDA heeft gegeven). De module moet tevens een aantal parameters/randvoorwaarden aanvaarden die een invloed hebben op de berekening van een oplossing. De module moet een antwoord kunnen geven op twee elementaire vragen. 1. Kan er nog eentje bij? 2. Zijn we goed bezig? De eerste vraag houdt in dat wanneer de dispatching een telefoonoproep van een klant ontvangt, met de vraag of men vandaag nog X m3 beton kan komen storten, dispatching snel op de visuele weergave van de planning kan zien of dat nog mogelijk is.

6

De tweede vraag houdt in dat de dispatching kan nagaan of er zich gedurende de dag vertragingen voordoen in de planning. En zo ja, in welke mate de verdere planning hierdoor be¨ınvloed wordt. Op basis van deze informatie kan men klanten verwittigen of eventueel zelfs een andere oplossing zoeken om een hogere servicegraad te bereiken.

2.2

Beschrijving van ICORDA

ICORDA is een ICT-integrator en werd opgericht in 1992. Dit softwarehuis concentreert zich vooral op: ontwerp, installatie en onderhoud van ICT-netwerken, analyse, implementatie en onderhoud van softwaretoepassingen, productverkoop.

Het bedrijf richt zich vooral op kleine en middelgrote organisaties die het beheer van hun ICT-netwerkinfrastructuur en softwaretoepassingen geheel of gedeeltelijk toevertrouwen aan een externe partner.

2.3

Beschrijving van Gebroeders De Rycke NV

De firma Gebroeders De Rycke is een toonaangevende regionale leverancier van bouwmaterialen, stortklaar beton en aanverwante producten. De groep De Rycke beschikt over 5 betoncentrales verdeeld over 3 vestigingen (Beveren, Kallo en Herdersem). De diversiteit aan silo’s, mengtypes en granulatenbunkers, gekoppeld aan een hypermoderne sturing, zorgt ervoor dat alle mogelijke recepten geproduceerd kunnen worden. Een modern, uitgebreid en divers wagen- en pompenpark moet een perfecte service ondersteunen. Elk voertuig is uitgerust met een gps-zender/ontvanger die volledig automatisch de ritstatussen genereert. Een up-to-date softwareapplicatie integreert deze statussen in het dispatchinggebeuren, zodat een hoog performante maar toch rendabele flexibiliteit mogelijk wordt.

Hoofdstuk 2. Algemene situatieschets

7

Hoofdstuk 3

Literatuurstudie van het Vehicle Routing Problem Dit hoofdstuk heeft als doel om een algemene inleiding te geven in het Vehicle Routing Problem (VRP)[7][8] en de mogelijke oplossingsmethoden. Allereerst worden VRP en de meest voorkomende varianten beschreven. Vervolgens wordt de aard van het probleem besproken.

3.1

Het Vehicle Routing Problem

Het Vehicle Routing Problem (VRP) is een complex combinatorisch optimalisatieprobleem en werd voor het eerst ge¨ıntroduceerd door Dantzig en Ramser in 1959[1]. Het probleem werd sindsdien uitgebreid bestudeerd. Fisher[2] beschreef het probleem als het zoeken en vinden van een efficiënt gebruik van een vloot voertuigen die een aantal tussenstops moeten maken om passagiers of producten op te pikken en/of af te leveren. Deze definitie houdt impliciet in dat er gestreefd wordt naar een zo hoog mogelijke servicegraad met een zo laag mogelijke totale kost. Het VRP is een NP-compleet1 probleem. Hoewel elke oplossing van het 1

NP-compleetheid is een concept uit de complexiteitstheorie. NP-complete problemen zijn problemen die in de complexiteitsklasse NP liggen en waarvoor bovendien geldt dat ieder probleem in NP in polynomiale tijd ertoe gereduceerd kan worden. Ze kunnen dus ook onderling tot elkaar gereduceerd worden. Daarmee vormen de NP-complete problemen een complete graaf van onderlinge reduceerbaarheid. De introductie van NP-compleetheid

8

probleem in kwestie snel geverifieerd kan worden, is er geen efficiënte manier gekend om een dergelijke optimale oplossing te vinden. Met andere woorden: er bestaat waarschijnlijk wel een optimale oplossing, maar de tijd die nodig is om tot die oplossing te komen - gebruikmakend van eender welk gekend algoritme - stijgt exponentieel naarmate het probleem groter wordt. Door deze karakteristiek loopt de benodigde tijd om middelmatige en grote problemen op te lossen al snel op tot miljoenen of zelfs miljarden jaren. Omdat wetenschappers en programmeurs vaak met NP-problemen geconfronteerd worden, spreekt het voor zich dat zij geen eeuwen kunnen wachten op de oplossing. Daarom zal men de optimale oplossing van het probleem gaan benaderen. Er bestaan verschillende variaties en specialisaties van het VRP. Voor een gedetailleerd overzicht en beschrijving verwijs ik naar paragraaf 3.2. Het probleem dat ik voorgeschoteld krijg, voldoet telkens aan slechts enkele restricties van een bepaalde variatie van het VRP. Tegelijkertijd wordt die bepaalde variatie uitgesloten door enkele andere eisen van mijn variant. Omdat het probleem nauw aansluit bij een aantal verschillende variaties maar nooit perfect binnen één variatie te kaderen valt, is het niet mogelijk om volledig gebruik te maken van het al gedane onderzoek op die variatie. Daarom ben ik op zoek gegaan naar methoden die algemeen bruikbaar zijn voor de verschillende variaties, ongeacht de concrete invulling van die methoden.

3.2

Basis van het Vehicle Routing Problem

Het meest eenvoudige VRP kan beschouwd worden als een combinatie van twee gekende optimalisatieproblemen, namelijk het Bin Packing Problem (BBP) en het Traveling Salesman Problem (TSP). Wanneer we beide problemen willen relateren om tot VRP te komen, dienen we in eerste instantie de klanten toe te wijzen aan voertuigen. Dat kan door het BBP op te lossen. De volgorde waarin de klanten bediend moeten worden, kan in de wiskunde en informatica was een belangrijk hulpmiddel bij de classificatie van problemen.

Hoofdstuk 3. Literatuurstudie van het Vehicle Routing Problem

9

gevonden worden door het TSP op te lossen. Als we deze twee resultaten combineren, bekomen we het meest eenvoudige VRP.

3.2.1

Traveling Salesman Problem

Het “Traveling Salesman Problem” (TSP) is een combinatorisch NP-Hard probleem[4]. TSP gaat over een reizende handelaar die een aantal steden wil bezoeken. Het probleem bestaat erin om de handelaar elke stad slechts eenmaal te laten bezoeken en te laten eindigen in de stad waar hij begonnen is. TSP was het eerste algemeen bekende VRP-probleem.

Figuur 3.1: Oplossing van een Traveling Salesman Probleem

3.2.2

Bin Packing Problem

Het “Bin Packing Problem” (BBP) is een combinatorisch NP-Hard probleem[3] en valt op de volgende manier te beschrijven: gegeven een eindige set van getallen (de groottes van de items) en een constante K die de capaciteit van de “bin” aanduidt. Wat is dan het minimumaantal bins dat nodig is om alle items te bevatten? Uiteraard mogen alle items in slechts één bin zitten en de totale capaciteit van de items in elke bin moet binnen de capaciteitslimiet van de bin blijven. Deze variant is gekend als de Best Packing Version van BPP.


10

3.3

Overzicht van variaties en specialisaties van VRP

Zoals al eerder vermeld, zijn er aanzienlijk wat variaties van het algemene VRP-probleem. Grosso modo heeft elke variant zijn eigen restricties die al dan niet afhankelijk zijn van een minder gedetailleerde gerelateerde variant. Hoe verder we in de onderstaande figuur omlaag gaan, hoe meer restricties er verbonden zijn aan de variant in kwestie en hoe meer de oplossingsmethode/strategie verschilt tussen de varianten onderling.

Figuur 3.2: Overzicht van de meest bekende VRP-variaties

3.3.1

VRP

Beschrijving: We beschikken over een vaste homogene vloot van voertuigen die vertrekken vanuit één depot om diverse klanten zo goed mogelijk te bedienen tegen een zo laag mogelijke totale kost.


11

3.3.2

CVRP

Beschrijving: Capacitated Vehicle Routing Problem is hetzelfde als VRP, met de extra restrictie dat elk voertuig slechts een uniforme capaciteit van een bepaald goed kan transporteren. Doel: Minimalisatie van het gebruik van voertuigen van de vloot en van de totale reistijd. De totale vraag van goederen langs elke route mag niet groter zijn dan de capaciteit van het voertuig dat deze route doet.

3.3.3

CVRPTW

Beschrijving: CVRPTW is een CVRP met Timed-Windows. Dat wil zeggen dat er een restrictie is die zegt dat een klant binnen een bepaald tijdsvenster bediend moet worden.

3.3.4

DCVRP

Beschrijving: DCVRP is een CVRP waarbij er extra restricties gelegd worden op de reistijd en/of reisafstand van een voertuig.

3.3.5

VRPB

Beschrijving: VRPB is een CVRP met Backhauls. Dat wil zeggen dat klanten goederen vragen of goederen afgeven. Deze variant verschilt van VRPPD in het feit dat een voertuig eerst al zijn goederen afgeleverd moet hebben voor zijn route en vervolgens pas pick-ups van klanten mag aanvaarden (die naar het depot gaan).

3.3.6

VRPBTW

Beschrijving: VRPBTW is een VRPB met Timed-Windows, met als extra restrictie dat een klant binnen een bepaald tijdsvenster bediend moet zijn.


12

3.3.7

VRPPD

Beschrijving: VRPPD is een CVRP met pick-up en delivery, waarbij een aantal goederen opgehaald moet worden op bepaalde plaatsen en afgeleverd moet worden op andere plaatsen. Doel: Het vinden van optimale routes zodat zo weinig mogelijk voertuigen ingezet worden en zo weinig mogelijk reistijd wordt besteed. De grote moeilijkheid zit in het feit dat voertuigen onderweg goederen opladen en weer afzetten. De capaciteit van het voertuig mag op geen enkel moment overschreden worden. De goederen onderweg herschikken is niet toegestaan om economische redenen.

3.3.8

VRPPDTW

Beschrijving: VRPPDTW is een VRPPD met Timed-Windows waarbij iedere pick-up en delivery binnen een bepaald tijdsvenster moet worden voltooid.

3.3.9

MDVRP

Beschrijving: Multiple Depot Vehicle Routing Problem stelt dat het bedrijf in kwestie meerdere depots mag hebben van waaruit voertuigen klanten kunnen bedienen. Als klanten rond depots geclustered kunnen worden, dan wordt aangeraden om het probleem te modelleren als een set van onafhankelijke VRP-problemen. Als de klanten niet rond depots geclusterd kunnen worden, moet het probleem worden gemodelleerd als een MDVRP. Verschillende depots kunnen dus dezelfde klant bedienen.

3.3.10

MDVRPTW

Beschrijving: MDVRP met Timed-Windows bevat de extra restrictie aan MDVRP dat de klant binnen een bepaald tijdsvenster bediend moet zijn.


13

3.3.11

SDVRP

Beschrijving: SDVRP is een VRP met Split-Deliveries. Dat wil zeggen dat een klant bediend mag worden door verschillende voertuigen als dat de totale kosten doet zakken.

3.3.12

SDVRPTW

Beschrijving: SDVRPTW is een SDVRP met Timed-Windows. Dit legt de extra restrictie op dat een klant binnen een bepaald tijdsvenster bediend moet zijn.

3.4

Classificatie van de opdracht

Nu we een idee hebben van de diverse varianten van VRP, kunnen we aan de hand van de restricties die opgelegd zijn aan ons probleem bepalen onder welke noemer de opdracht valt. De restricties aan de planning zijn de volgende: Ieder voertuig heeft zijn eigen minimum- en maximumcapaciteit. Sommige voertuigen hebben geen capaciteit maar zijn wel nodig (bv. betonpomp) en moeten ook ingepland worden. De berekening van de planning moet vrij snel gaan. De module mag slechts een beperkt geheugengebruik innemen op de server (300 MB). Een klant mag worden bediend door verschillende wagens, al is hergebruik van hetzelfde voertuig voor een klant wel een pluspunt. Een klant moet worden bediend op het uur dat hij gevraagd heeft en bovendien aan een bepaald debiet. 2 2

Voorbeeld: als de klant een debiet van 40 m3 /uur vraagt, dan is de invulling naar keuze. invulling (a): 4 wagens met een capaciteit van 10 m3 gelost die om het kwartier gelost zijn


14

De planning moet binnen de werkuren vallen. Ritten voor een bepaalde klant moeten elkaar zo goed mogelijk opvolgen (maximaal 5 minuten wachttijd tussen 2 ritten). Voertuigen hoeven niet noodzakelijk naar dezelfde depot terug te keren als het depot van waaruit deze vertrokken zijn. Er is een restrictie aan de tijd dat een voertuig onderweg mag zijn. Beton moet namelijk binnen een bepaalde tijd gestort worden (afhankelijk van de samenstelling) zodra het voertuig geladen is.

We voelen hier al instinctief aan dat ons probleem nooit volledig binnen één bepaalde variant van VRP te classificeren valt. Stel dat we ons probleem classificeren als CVRPTW. Dan schenden we de volgende CVRP-restricties. Alle voertuigen van de vloot moeten een uniforme capaciteit hebben, wat niet het geval is. We hebben bovendien meerdere depots van waaruit een voertuig kan vertrekken en waar een voertuig kan toekomen. CVRPTW laat slechts één depot toe. Naast deze restricties stelt CVRP dat een klant slechts bediend mag worden door één specifiek voertuig. Dat is in ons geval vaak onmogelijk omdat het totaal te leveren volume vaak groter is dan de capaciteit van de wagen waardoor er geen aaneengesloten leveringen door één specifieke wagen uitgevoerd kunnen worden. Als we ons probleem in de categorie MDVRPTW classificeren, dan vallen enkele bezwaren van het voorgaande betoog weg, maar lang niet allemaal. Zo wordt de eis van een homogene, uniforme vloot voertuigen nog steeds geschonden. Daarnaast kan een klant nog steeds door slechts één voertuig bediend worden. De restricties van ons probleem zorgen ervoor dat ons probleem gedeeltelijk binnen vrijwel elke variant valt, maar door weer andere restricties niet binnen die bepaalde variant kan vallen! Bovendien zetten sommige restricties elke variant buitenspel (zoals de eis van een homogene, uniforme vloot). Omdat we merken dat ons probleem toch heel sterk verbonden is met VRP en zijn diverse varianten, kunnen we op zoek gaan naar gemeenschappelijke invulling (b): 2 wagens met een capaciteit van 14 m3 en 2 wagens met een capaciteit van 6 m3 (wagen 1 en 2: gelost na 21 respectievelijk 42 minuten, wagen 3 en 4: gelost na 51 respectievelijk 60 minuten)


15

elementen binnen de oplossingsmethoden voor iedere variant en op basis daarvan een methode vinden die we naar wens kunnen aanpassen, zodat we ons probleem toch kunnen modelleren en oplossen binnen een redelijke tijd.

3.5

Algemene oplossingsstrategi¨ een voor VRP

Ondanks het feit dat VRP vele varianten kent, zijn de mogelijke oplossingmethoden in (heel) grote lijnen voor allemaal deels gelijkaardig. De restricties (per variant) zorgen echter voor een andere invulling in de concrete implementatie van een bepaalde oplossingsmethode. Bovendien genieten bepaalde strategiëen een grotere voorkeur naargelang de concrete variant waarmee men te maken heeft. Daarnaast zijn er vaak hele zware optimalisatiealgoritmen die enkel binnen de variant in kwestie kunnen werken. Deze extra “tweaks” zorgen meestal voor de grootste tijdswinst. Overzicht van de algemene oplossingsmethoden 1. Exacte methoden (a) Brute Force (b) Branch-and-Bound Algoritmen[9][10] (c) Progressive Improvement Algoritmen op basis van Lineair Programmeren[26] 2. Heuristieken[11][12][24] (a) Constraint Programming[13][14] (b) Local Search[27] 3. Metaheuristieken[11][12][24] (a) Genetische Algoritmen[20][15] (b) Simulated Annealing[27][28] (c) Greedy Randomized Adaptive Search Procedure (GRASP)[23] (d) Tabu Search[17][18][19] (e) Ant Colony Optimization[20][21][22][25]


16

3.6 3.6.1

Resultaten van het onderzoek Vaststellingen

De literatuurstudie toont aan dat er al aanzienlijk onderzoek is gebeurd naar VRP. Het feit dat VRP vele varianten kent, maakt een analyse van de opdracht niet eenvoudig. Bovendien moeten we opmerken dat de voorwaarden en restricties voor de diverse varianten soms erg kunstmatig zijn. Dat betekent op zijn beurt dat het vaak gaat om schoolvoorbeelden van bepaalde problemen die in de praktijk niet kunnen worden toegepast op de manier waarop ze beschreven zijn. Daarnaast blijkt uit deze studie ook dat er vele wegen naar Rome leiden. Daarmee bedoel ik dat een bepaalde variant op veel verschillende manieren opgelost kan worden. Daarbij heeft elke oplossingswijze zijn eigen specifieke voor- en nadelen. Bij de keuze van een oplossingswijze moeten we dus kijken naar de voorwaarden en restricties van ons probleem alsook naar de eigenschappen van de oplossingswijze.

3.6.2

Keuze van de oplossingswijze

Na de literatuurstudie was het volledig duidelijk dat de opdracht nooit volledig onder één bepaalde variant van VRP te classificeren zou vallen (zie paragraaf 3.4). We kunnen de opdracht eigenlijk bekijken als een nog onbekende variant op CVRPTW. Daarmee wordt bedoeld dat deze nieuwe variant een mix van voorwaarden van diverse bestaande varianten is, maar toch niet geclassificeerd kan worden als een van deze bestaande varianten. In ons geval hebben we te maken met onder andere de volgende specifieke voorwaarden: ´ en order betekent niet noodzakelijk slechts één rit. E´ Een voertuig mag meerdere keren per order worden ingezet. Voertuigen hebben geen uniforme capaciteit. Niet alle voertuigen vervullen dezelfde functionaliteit (mixer, pomp, pomp met giek).


17

Voertuigen mogen van een werf terugkeren naar een ander depot dan het depot waar ze vandaan kwamen. ...

Wanneer ik naar de mogelijke oplossingswijzen van de verschillende varianten ging kijken, werd het al snel duidelijk dat slechts een paar van de in paragraaf 3.5 opgesomde oplossingswijzen gemeenschappelijk waren voor nagenoeg alle varianten. Het spreekt dan ook voor zich dat we uit deze lijst de oplossingswijze voor deze opdracht gingen kiezen. Icorda wil namelijk in de toekomst een gelijkaardige opdracht uitwerken, maar dan voor bouwmaterialen i.p.v. voor stortklaar beton. Daarom is een oplossingswijze nodig die voor zowel het huidige als het toekomstige probleem gebruikt kan worden. De keuze is uiteindelijk gevallen op genetische algoritmen of kortweg GA’s. Een GA heeft een relatief eenvoudige basisstructuur maar is tegelijkertijd heel flexibel naar de programmeur toe. Dankzij het template pattern3 laat een GA toe dat een programmeur een eigen implementatie kan voorzien waar hij dat wenst om zo het algoritme een specifieke werking te geven, zonder aan de basisstructuur te komen. Naast deze flexibiliteit hebben GA’s de eigenschap dat ze relatief snel tot goede oplossingen kunnen komen (mits een degelijke implementatie). Snelheid en flexibiliteit zijn niet alleen de sleutelwoorden van een GA, maar ook van de te ontwikkelen module. Daardoor zijn GA’s één van de betere keuzes als oplossingswijze voor dit probleem.

3

Het template pattern is een design pattern dat een zekere structuur vastlegt. Dit is de codetemplate.


18

Hoofdstuk 4

Genetische algoritmen Dit hoofdstuk geeft een algemene inleiding in genetische algoritmen[5]. Deze inleiding is nodig om de implementatie in hoofdstuk 5 te kunnen volgen. Er zal allereerst besproken worden wat een genetisch algoritme is en hoe dit concept tot stand is gekomen. Vervolgens geven we een verduidelijking van de werking van dit algoritme, met een verklaring van de belangrijkste terminologie.

4.1

Inleiding

Een genetisch algoritme (GA) is een metaheuristisch algoritme dat behoort tot de meer omvattende klasse van evolutionaire algoritmen. Deze algoritmen imiteren het proces van natuurlijke evolutie en selectie. De theorie van natuurlijke selectie werd voor het eerst voorgesteld door de Britse naturalist Charles Darwin (1809) in 1859[6]. Deze theorie stelt dat individuen met bepaalde gewenste karakteristieken een hogere graad van waarschijnlijkheid hebben om te overleven en zich voort te planten. Bij voortplanting worden deze gewilde karakteristieken doorgegeven aan de nakomelingen (de zogenaamde offspring). Individuen met minder wenselijke karakteristieken zullen geleidelijk verdwijnen uit de volledige populatie. Wanneer we naar de situatie in de natuur kijken merken we dat genetische overerving opgeslagen is in chromosomen, die op hun beurt uit genen bestaan. De karakteristieken van elk individu van elk organisme worden gecontroleerd door de genen die doorgegeven worden

19

aan de nakomelingen wanneer het organisme zich voortplant. Vanwege het proces van natuurlijke selectie zal de populatie geleidelijk aan verbeteren naarmate het aantal individuen met wenselijke karakteristieken toeneemt en het aantal individuen met onwenselijke karakteristieken afneemt. Het idee achter genetische algoritmen is vrij simpel, namelijk natuurlijke evolutie modelleren door gebruik te maken van genetische overerving zoals in de natuur in combinatie met Darwins theorie. Binnen GA’s bestaat de populatie uit een set oplossingen of individuen in plaats van chromosomen zoals in de natuur. Om voortplanting na te bootsen in een algoritme worden er een aantal operatoren ge¨ıntroduceerd die elk een bepaald aspect van voortplanting voor hun rekening nemen. Zo zal de crossover-operator de karakteristieken van 2 ouders gaan mengen. De mutatieoperator zorgt er dan weer voor dat er binnen een oplossing random wijzigingen kunnen gebeuren. Een selectieprocedure die de natuurlijke selectie simuleert, zal een aantal oplossingen uit de huidige populatie selecteren en doorgeven aan de crossover- of mutatieoperator, die op zijn beurt nakomelingen zal produceren. Aan het eind van iedere cyclus vormen de nakomelingen samen met de vorige generatie de nieuwe generatie voor de volgende cyclus. Dit iteratief proces gaat door tot er een oplossing gevonden wordt die voldoet aan de vooropgestelde voorwaarden. Vaak wordt ervoor geopteerd om te werken met een populatie van vaste grootte. Omdat het voortplantingsproces hoogstwaarschijnlijk een onbekend aantal nakomelingen produceert, zal er meestal een selectie binnen deze groep gebeuren. Er zijn verschillende manieren om aan selectie te doen. Voor meer informatie verwijs ik naar paragraaf 4.3.3. De selectieprocedure zal vaak individuen binnen een populatie vergelijken en/of ordenen. Dat gebeurt op basis van een zogenaamde fitnesswaarde, die aangeeft hoe wenselijk de oplossing in kwestie is. Hoe meer wenselijke karakteristieken de oplossing heeft, hoe hoger de fitnesswaarde. Dit type algoritmen (metaheuristieken) wordt vaak gebruikt om op een snelle manier bruikbare oplossingen te genereren voor zoeken optimalisatieproblemen. GA’s zijn relatief eenvoudig om te implementeren.

Hoofdstuk 4. Genetische algoritmen

20

4.2

Pseudocode genetisch algoritme

Het onderstaande algoritme is een sterk vereenvoudigde vorm van het gebruikte GA in de module. population = GenerateInitialP opulation() while termination conditions not met do probabilities = CalculateF itnessP roportionateSelection(population) of f spring = Crossover(population, probabilities) population = M utate(of f spring, probabilities) EvaluateP opulation(population) population = M aintainP opulation(population, populationSize) end while Op basis van de bovenstaande pseudocode zullen we de belangrijkste terminologie van een genetisch algoritme in de volgende paragraaf uitleggen.

4.3 4.3.1

Terminologie Initi¨ ele populatie

De eerste stap in een genetisch algoritme is het opbouwen van de initiële populatie. Deze populatie zal vaak bestaan uit individuen/oplossingen die tot een minimum herleid zijn. Dat wil zeggen dat een individu niet verder geminimaliseerd kan worden zonder dat deze ongeldig wordt. Als we een praktisch voorbeeld van een planning bekijken, dan zal elke basisoplossing bijvoorbeeld een planning zijn die exact één enkel item bevat. We merken echter op dat het geen expliciete vereiste is om te vertrekken van minimale individuen. Als we deze richtlijn niet volgen, is het nog steeds perfect mogelijk om goede oplossingen te vinden met het algoritme. Dan bestaat echter wel het risico dat men vertrekt van te goede oplossingen. Daardoor bestaat de kans dat dergelijke oplossingen al vroeg in het iteratieve proces dominant worden in de populatie. Als dat het geval zou zijn, wordt de Hoofdstuk 4. Genetische algoritmen

21

populatie al snel te homogeen en verliest het GA zijn mogelijkheid om in de oplossingsruimte (de zogenaamde “Solution Space”) te zoeken en oplossingen te combineren. De populatie wordt nu nog amper gewijzigd door crossover en mutatie.

4.3.2

Fitnesswaarde

Omdat we oplossingen met elkaar moeten kunnen vergelijken (EvalutatePopulation(population)), hebben we nood aan een waarde die aangeeft hoe goed (of hoe slecht) een bepaalde oplossing is. Deze zogenaamde fitnesswaarde wordt opgebouwd op basis van diverse vergelijkingscriteria. Bepaalde aspecten/karakteristieken van een oplossing zullen beloond worden, terwijl andere bestraft zullen worden. De fitnesswaarde van een oplossing is dan ook de verzameling van alle individuele aspectscores binnen die oplossing. De fitnesswaarde wordt enkel en alleen gebruikt wanneer individuen voor reproductie door middel van een selectiefunctie gekozen worden.

4.3.3

Selectie

Een belangrijk aspect binnen GA’s is de manier waarop individuen gekozen worden voor reproductie. In de pseudocode komt dit overeen met de methoden CalculateFitnessProportionateSelection(population), Crossover en Mutate. De selectie gebeurt op basis van de fitnesswaarde van individuen. In essentie zijn er verschillende mogelijkheden om een koppel individuen te kiezen naast random selectie. Hieronder zijn de meest frequent gebruikte methoden opgesomd. Roulette Wheel Roulette wheel-selectie is een methode gebaseerd op kansberekening. In essentie gaan we de oplossingenverzameling voorstellen als een roulettewiel waarbij ieder individu een slice van het wiel inneemt, waarvan de breedte recht evenredig is met de fitnesswaarde. De kans om een bepaald individu te selecteren, is dus recht evenredig met de fitnesswaarde van het individu in kwestie. Deze methode zal dus betere individuen een grotere kans geven


22

om gekozen te worden, maar sluit niet uit dat een slechte oplossing gekozen wordt. Het nadeel aan deze methode is dat er rechtstreeks gebruikgemaakt wordt van de fitnesswaarde. Dat kan namelijk problemen geven wanneer een oplossing een heel kleine fitnesswaarde heeft in vergelijking met andere oplossingen, waardoor de kans dat deze oplossing gekozen wordt nihil is. Ook verliest deze methode voor een stuk zijn kracht wanneer we over heel veel oplossingen beschikken. In deze context zullen heel slechte oplossingen procentueel ongeveer evenveel kans hebben om gekozen te worden als heel goede oplossingen, wat niet de bedoeling is. Ranking In ranking worden de individuen gesorteerd volgens hun fitnesswaarde. Vervolgens wordt er een rang toegewezen aan iedere oplossing. De selectie gebeurt nu op basis van de rang in plaats van op het verschil in absolute fitnesswaarden. Het voordeel van deze methode is dat ervoor gezorgd wordt dat heel goede oplossingen vroeg in het proces geen dominantie kunnen opeisen ten opzichte van minder goede oplossingen. Dominantie zorgt ervoor dat de genetische diversiteit verdwijnt en de kans veel groter is dat we in een lokaal optimum terechtkomen. Tournament Bij deze methode worden subgroepen van oplossingen gekozen uit de populatie. Vervolgens gaan de individuen van elke subgroep met elkaar “strijden” op basis van één van voorgaande methoden. Slechts één oplossing uit elke subgroep wordt gekozen voor voortplanting. Elitisme Bij deze methode zijn het enkel de meest fitte individuen die in aanmerking komen voor selectie. Deze methode wordt dan ook vaak gebruikt om de x beste oplossingen uit een populatie over te houden.


23

Na selectie worden de individuen overgedragen aan crossover- en/of mutatieoperatoren.

4.3.4

Crossover

De crossover-operator is een methode om voortplanting te simuleren. Allereerst kiezen we twee ouderoplossingen uit de populatie volgens een bepaalde selectieprocedure. Uit deze twee individuen zullen één of meerdere nakomelingen volgen. Net zoals bij selectie zijn er verschillende mogelijkheden. We bespreken enkel de meest gebruikte, namelijk de single-point crossover.

Figuur 4.1: Single-point crossover

Bij deze methode wordt er een spilpunt aangeduid op een random locatie in beide ouderindividuen. Vervolgens draagt één van beide al zijn code voor dit spilpunt over aan de nakomeling en de andere al zijn code na het spilpunt.

4.3.5

Mutatie

De mutatieoperator neemt allereerst de volledige oudercode over en brengt vervolgens op een random locatie een wijziging aan om een nakomeling te produceren. Voor een simpele binaire bitstring wil dat dus zeggen dat de bit op een bepaalde locatie ge¨ınverteerd wordt. In het geval van een object zal er vaak gemuteerd worden op één of meerdere properties van dat object.


24

Figuur 4.2: Mutatie

4.4

Bedenkingen omtrent GA’s

We kunnen verschillende bedenkingen en opmerkingen maken bij genetische algoritmen. Allereerst moet opgemerkt worden dat genetische algoritmen de eigenschap hebben dat ze snel tot goede oplossingen kunnen komen, zelfs voor grote problemen. Bij veel problemen hebben GA’s echter de neiging om vroegtijdig te convergeren naar lokale optima of zelfs naar arbitraire oplossingen in plaats van naar het globale optimum. Dat betekent dat het algoritme niet weet hoe het moet omgaan met tijdelijk minder goede resultaten voor de fitnesswaarde, die in het verdere verloop wel voor een meerwaarde kunnen zorgen in het totaalplaatje. De waarschijnlijkheid waarmee dit fenomeen zicht voordoet hangt heel sterk samen met de samenstelling van de populatie. Men tracht de diversiteit van de populatie te verzekeren door middel van genetische operatoren. Men moet echter wel beseffen dat een matige tot slechte implementatie van deze operatoren vernietigend is voor zowel de werking als de performantie van het GA. Een goede implementatie alleen garandeert echter geen snel GA. Omdat GA’s met een iteratief proces werken, moet men tijdens iedere iteratie kunnen bepalen of men wel de juiste richting uitgaat. Dat zal in het geval van GA’s bereikt worden door ieder individu binnen de populatie te evalueren met de fitnessfunctie. Aangezien iedere oplossing van een populatie, iedere iteratie geëvalueerd wordt is een efficiënte implementatie van de fitnessfunctie een vereiste. Onderzoek toont aan dat herhaaldelijk gebruik van de evaluatiefunctie binnen complexe problemen vaak het


25

meest belemmerende en limiterende element binnen artificieel evolutionaire algoritmen is. Het vinden van een optimale oplossing van een complex multidimensioneel en multimodaal probleem, zoals bij ons het geval is, vereist vaak heel ’dure’ fitnessfunctie-evaluaties in termen van processoren/of geheugenbewerkingen. Zeker wanneer we naar optimalisatieproblemen uit de praktijk gaan, is het best mogelijk dat een dergelijke evaluatie uren tot zelfs verschillende dagen kan duren, afhankelijk van de omvang en complexiteit van het probleem. In dat geval zal men de exacte fitnessfunctie vaak inruilen voor een benaderende functie die computationeel wel efficiënt is. Daarnaast hangt de efficiëntie van genetische algoritmen, net zoals bij vele andere algoritmen, af van de gebruikte parameters. Het uittesten van verschillende mogelijke combinaties van parameters is dan ook cruciaal voor een optimale werking.


26

Hoofdstuk 5

Implementatie In dit hoofdstuk zal de concrete implementatie van de planningsmodule besproken worden. Onder deze implementatie verstaan we de elementen vervat in entiteiten, datastructuren en het GA zelf. In eerste instantie zal een graafklasse besproken worden die gebruikt wordt als datacontainer voor de invoerdata van de module. Vervolgens gaan we ook dieper in op de entiteiten van de module en het GA zelf. Daarnaast worden de belangrijkste methoden binnen een GA verder uitgediept met betrekking tot de concrete implementatie.

5.1

Graafklasse

De literatuurstudie heeft aangetoond dat er onafhankelijk van de oplossingswijze van de verschillende varianten van VRP vaak gebruikgemaakt wordt van een graaf. De graaf wordt afhankelijk van de variant en oplossingswijze gebruikt als een container van data of als echte voorstellingswijze van een oplossing voor het probleem. Daarom heb ik eerst het ontwerp van een graaf in code gerealiseerd.

5.1.1

Uitwerking

Concept Ik heb ervoor geopteerd om de graaf te gebruiken als datacontainer. Mijn graaf neemt conceptueel de betoncentrales van het bedrijf en alle 27

bouwwerven van alle orders die afgewerkt moeten worden op een bepaalde dag als knopen van de graaf. De verbindingen tussen de twee types knopen van de graaf zullen bevolkt worden door de rijtijden die nodig zijn om van een centrale naar een werf te gaan. Zoals blijkt uit de onderstaande afbeelding, lopen er enkel verbindingen tussen centrales en werven, en niet tussen centrales of werven onderling.

Figuur 5.1: Conceptuele voorstelling van de graaf

Ontwerp In het .NET Framework is er geen standaard graafklasse voorzien. De reden daarvoor is simpel. Een efficiënte implementatie van een graafklasse hangt sterk af van een aantal specifieke factoren van het probleem in kwestie. Een algemene graafklasse zou nooit elk probleem efficiënt kunnen aanpakken, daarom is een probleemspecifieke implementatie nodig. Ik heb in mijn implementatie van een graaf voornamelijk gestreefd naar een generische graaf die vooral voor mijn probleem de ideale implementatie bevat. Dat neemt echter niet weg dat deze graaf voor andere problemen gebruikt kan worden. Hoofdstuk 5. Implementatie

28

Figuur 5.2: Klassendiagram van de graafklasse en zijn componenten

Hoofdstuk 5. Implementatie

29

BaseGraph Deze generische klasse vormt de basis van overerving voor de klassen Graph en NoEdgeKeyGraph. Deze klasse bevat 4 generische parameters, namelijk steeds de aanduiding van het type sleutel en waarde voor een knoop (vertex) en een tak (edge). Het is in deze klasse dat de volledige functionaliteit en implementatie van de graaf vervat zit. Zowel de knopen als de takken worden ge¨ındexeerd door middel van een sleutel. Dat laat een snelle opzoeking van zowel knopen als takken toe en is precies wat we nodig hebben voor ons specifiek probleem. De klasse bevat een aantal interne klassen (Vertex, Edge, DirectionType). Het was een bewuste keuze om de graafstructuur te benaderen als één klasse en niet als een collectie van verschillende aparte klassen die samen de structuur opmaken. Graph Deze generische klasse erft over van BaseGraph en doet niet veel meer dan enkele protected methoden publiek maken. Deze klasse is dan ook bedoeld voor gebruik in eventuele andere problemen. NoEdgeKeyGraph Deze generische klasse erft eveneens over van BaseGraph maar vereenvoudigd deze enigzins. Er hoeft namelijk door geen sleutelwaarde meer ingegeven worden bij het toevoegen van een tak in deze graaf. De automatische nummering zorgt ervoor dat men zich geen zorgen meer hoeft te maken over het uniek zijn van de sleutel voor een tak. Deze aanpak zorgt tevens voor een vereenvoudigd gebruik van de graaf. Vertex Dit is een interne generische klasse binnen BaseGraph die een knoop zal voorstellen. Iedere knoop bevat een lijst met de takken die verbonden zijn met de naburige knopen van de knoop in kwestie. Hierbij hangt de concrete invulling van de lijst af van het DirectionType van de graaf (gericht of ongericht). Daarnaast bevat de knoop uiteraard ook nog data.


30

Edge Deze interne generische klasse van BaseGraph stelt een tak voor. Dat is de verbinding die tussen twee knopen ligt. Uiteraard kan een tak ook data bevatten zodat we een gewogen of ongewogen graaf kunnen bekomen. In de module wordt gebruikgemaakt van een instantie van de NoEdgeKeyGraph. De knopen van deze graaf worden conceptueel bevolkt met betoncentrales en bouwwerven, met de nadruk op conceptueel (zie volgende paragraaf). De takken zijn gericht en hebben als gewicht de rijtijd tussen een bepaalde betoncentrale en een bepaalde werf. Omdat we twee verschillende entiteiten (centrale/werf) als knoopdata willen gebruiken, hebben we nood aan een wrapperklasse.

Figuur 5.3: Klassendiagram van de klasse vertexwrapper

VertexWrapper Deze klasse dient als datatype voor de knoopdata. De graaf bevat dus knoopdata van het datatype VertexWrapper, maar in de code kan er wel onderscheid gemaakt worden tussen een betoncentrale en een bouwwerf. De betoncentrale komt overeen met de entiteit Station en de werf komt overeen met de entiteit ConstructionYard, die op haar beurt vervat zit in de entiteit Order (zie volgende paragraaf voor meer informatie over de entiteiten). De entiteit Order zal echter gebruikt worden als knoopdata Hoofdstuk 5. Implementatie

31

i.p.v. de entiteit ConstructionYard. De reden daarvoor is om de link tussen Order en ConstructionYard niet te verliezen binnen de datastructuur. De entiteit Order bevat een verwijzing naar de entiteit ConstructionYard en niet omgekeerd. Er wordt in de graaf echter wel ge¨ındexeerd op de unieke bouwwerfcode en niet op de ordercode. Daardoor klopt het conceptuele plaatje (zie figuur 4.1) nog steeds en hoeven we geen aparte dictionary bij te houden die de link legt tussen een bepaalde constructionyard en een bepaalde order.

5.2 5.2.1

Entiteiten van de module Invoer via xml

In een allereerste versie van de opdracht was het zo dat de invoer voor de module via een xml-bestand zou verlopen (zie fig. 5.4). De structuur van dat bestand lag al vast voor de opdracht goed en wel van start ging. De bestandsstructuur wordt rechtstreeks weerspiegeld in de entiteiten die de module gebruikt d.m.v. serialisatie. De tag ConcretePlanning in xml stemt dus effectief overeen met een klasse ConcretePlanning. De tag Orders wordt op zijn beurt een property van de klasse ConcretePlanning.

Figuur 5.4: Een fractie van een invoer-xml

Omdat de structuur al vast lag, lag ook het grootste deel van de entiteiten al vast. In het volgende klassendiagram staan dan ook nagenoeg alle gebruikte entiteiten omtrent de invoer. Deze komen ook terug bij de uitvoer. Hoofdstuk 5. Implementatie

32

Figuur 5.5: Klassendiagram van gebruikte entiteiten in de module


33

PlanningHelper De klasse PlanningHelper is, zoals de naam al suggereert, een helperklasse. Dat wil zeggen dat deze enkel wordt gebruikt om een bepaalde actie te ondersteunen/helpen. In ons geval gaat de PlanningHelper de data verzamelen die nodig is als invoer voor de planningsmodule. Vervolgens wordt deze data verpakt in de entiteit die als invoer (en als uitvoer) voor de module zal dienen, namelijk een object van het datatype ConcretePlanning. De data wordt opgehaald via een RESTful-webservice die de data op zijn beurt ophaalt uit de database van IApprove. Die data wordt binnen de helper omgevormd van entiteiten van IApprove tot entiteiten van de module. ConcretePlanning De klasse ConcretePlanning is de verzameling van alle data die dient als invoer voor de planningsmodule. Tegelijkertijd zal de output van de module eveneens verpakt worden in een dergelijk object. In essentie zijn er 3 grote groepen invoer: 1. een lijst van de af te werken orders voor een bepaalde dag, 2. een lijst met de beschikbare betoncentrales, 3. een lijst met voertuigen die ingezet kunnen worden voor een bepaalde dag. Vehicle Deze klasse stelt een voertuig van een bepaald VehicleType voor. De meeste eigenschappen spreken voor zich. Enkel de property DischargeM3PerHour is mogelijk onduidelijk. Deze eigenschap verwijst naar het debiet waarmee het voertuig een lading kan lossen en heeft dus rechtstreeks invloed op de lostijd van een voertuig. VehicleType Dit is een enum van 3 types. Enkel mixer en pump worden momenteel gebruikt. Helaas is de labeling in de database van de types niet volledig in orde en worden vele mixers ook gelabeld als pump. Daardoor moeten Hoofdstuk 5. Implementatie

34

de echte betonpompen in code onderscheiden worden op basis van de pumplinelength. Station Deze klasse stelt een betoncentrale voor. Order Deze klasse stelt een order voor die door de module moet worden ingepland. In deze klasse wordt er een zekere prioriteit gesteld ten opzichte van andere orders als dat nodig zou zijn. Daarnaast zal een order meestal (maar niet noodzakelijk) een RequiredDischargeM3PerHour opleggen. Deze waarde bepaalt de snelheid waarmee beton gestort wordt en bijgevolg ook hoeveel wagens er ingezet moeten worden per uur. ConstructionYard Deze klasse stelt een bouwwerf voor. De eigenschap WaitingMinutes spreekt waarschijnlijk niet volledig voor zich. Dit is een wachttijd die in acht moet worden genomen bij korte ritten. Het is namelijk zo dat beton in een mixer gemengd wordt en er een minimale periode verstreken moet zijn voor deze stortklaar is. Bij heel korte ritten (in reistijd) is de beton nog niet stortklaar wanneer de wagen aankomt op de werf. Daarom wordt er een kleine wachtperiode op de werf voorzien waarbij de mixer in een hoog tempo het beton mengt en stortklaar maakt. Daarnaast bevat deze klasse ook een lijst van StationDurations. StationDuration Deze klasse stelt de reisweg van en naar een centrale voor. De rijtijd (DrivingMinutes) wordt berekend aan de hand van Microsoft MapPoint1 . PlanningOutput Deze klasse is de verzameling van output van de module. Hierin komen diverse planningsvoorstellen te staan die in de GUI gevisualiseerd kunnen 1

Microsoft MapPoint (http://www.microsoft.com/mappoint/en-us/home.aspx) laat toe om onder andere aan de hand van co¨ ordinaten de tijd van de reisweg te berekenen.


35

worden, samen met een aantal meetresultaten. We hebben ervoor gekozen om slechts één van deze planningsvoorstellen te visualiseren. PlanningResult Deze klasse stelt één concreet planningsvoorstel voor. Een planningsvoorstel bestaat uit een lijst van leveringen (Deliveries) samen met een score en een lijst van mogelijke fouten die de module heeft ondervonden. Deze lijst met fouten kan eveneens gevisualiseerd worden. Delivery Deze klasse stelt een levering voor. Een order wordt opgesplitst in één of meerdere leveringen naargelang het gewenste volume. De levering koppelt dus een bepaald voertuig met een bepaald volume aan een bepaalde order/klant.

5.2.2

Invoer via objecten

Eén van de vereisten was dat er niet mocht worden geraakt aan deze al opgestelde entiteiten, omdat dat invloed kon hebben op de werking van het oude programma (Iboplan). Ongeveer halfweg de masterproef werd beslist dat de module niet meer ge¨ıntegreerd zou worden in het oude programma, maar in een nieuw programma (IApprove). Voor de entiteiten van de module heeft deze switch enkele gevolgen. Omdat niet aan de oorspronkelijke entiteiten geraakt mocht worden, moesten enkele nieuwe klassen ontworpen worden die slechts een uitbreiding waren op enkele van die entiteiten. Daarnaast werd ook de manier waarop input aan de module gegeven wordt bij deze switch aangepast. De invoer komt nu niet langer van een xml-bestand waarvan het pad aan de module werd doorgegeven, maar van een webservice waarbij een object aan de module wordt doorgegeven.

Dankzij een eenvoudig maar degelijk ontwerp van de persistentielaag van de module was deze switch van xml- naar objectinvoer snel geklaard.


36

Figuur 5.6: Klassendiagram van persistentie in de module

DataSource Deze klasse is een singleton en wordt door de module gebruikt als bron van alle invoerdata. Het aanspreekpunt van de module voor data blijft dus ongewijzigd, ongeacht de manier waarop de data binnenkomt (xml vs. object). Als men dus in de toekomst een rechtstreekse koppeling tussen module en database zou willen, kan dat simpelweg door één enkele lijn code te wijzigen. IDataSource Deze

interface

definieert


enkele

getter-methoden

waaraan

de

37

implementerende klassen moeten voldoen. Deze inferface zorgt samen met de klasse DataSource voor aanzienlijke flexibiliteit met betrekking tot data-exploitatie. Het is deze interface die de werking van DataSource (het singleton) zwaar be¨ınvloedt. XmlDataSource Deze klasse implementeert de interface IDataSource en leest een xml bestand in waarvan de inhoud wordt geconverteerd naar een object van de klasse ConcretePlanning. Deze klasse is ondertussen overbodig geworden wegens de nieuwe manier waarop de invoerdata worden doorgegeven. Deze klasse werd na 3 maanden vervangen door de klasse ObjectDataSource. ObjectDataSource Deze klasse implementeert eveneens de interface IDataSource en krijgt via de RESTful-webservice een ConcretePlanning object aangereikt. Vanwaar dit object concreet komt, maakt voor de module niet uit. In ons geval komt de invoer momenteel van IApprove.

5.3

Klassendiagram van het GA

Nu we alle bouwstenen voor de module (entiteiten, datalaag enz.) hebben, kunnen we aan de slag met het eigenlijke ontwerp van het GA. We hebben tot dusver de meeste aspecten van een GA bekeken vanuit een theoretisch standpunt. Daarnaast hebben we nu ook een grondige kennis van alle entiteiten die de basis van de module vormen. Het wordt nu stilaan tijd om eens naar de eigenlijke implementatie van het GA te kijken, alsook naar de klassen die bij deze implementatie horen. Helaas is het onmogelijk om alle klassen met betrekking tot het GA in één afbeelding te krijgen zonder dat deze onleesbaar wordt. De lijn die vanaf de klasse GeneticAlgorithm naar de rechterkant van de afbeelding loopt, is verbonden met de lijn die binnenkomt op de tweede afbeelding bij de klasse Solution. Ik geef eerst het klassendiagram omtrent het GA zodat u beter kunt volgen wanneer ik dieper inga op de implementatie in paragraaf 5.4 en verder.


38

Figuur 5.7: Deel 1 van het klassendiagram van het GA


39

Figuur 5.8: Deel 2 van het klassendiagram van het GA

DataModel Deze klasse is een singleton en wordt op diverse plaatsen in de module gebruikt. Enerzijds dient deze klasse om de gemeenschappelijke data voor de volledige module te centraliseren. De rest van de module legt


40

referenties naar de objecten die in de diverse properties zijn opgeslagen. Wijzigingen aan deze objecten zorgen dus voor wijzigingen in alle objecten die ergens een referentie hebben naar een dergelijk object. In het datamodel zit, ondere andere, onze graaf die alle info bevat om voertuigen correct te kunnen inplannen (locaties, reistijden enz.). Daarnaast bevat het datamodel een lijst van orders, betoncentrales (Stations) en voertuigen (mixers, pompwagens, combiwagens), steeds ge¨ındexeerd volgens hun unieke id. Enkel VehiclesToIndex is een enigszins vreemde property. We hebben verschillende types voertuigen (Mixer, Pompwagen enz.), maar omdat bepaalde types geen volume kunnen vervoeren, is het nutteloos om deze op te nemen in een chromosoom. Concreet wil dat zeggen dat enkel voertuigen van het type mixer worden opgenomen in een chromosoom. De link tussen een voertuig en zijn overeenkomstige index in een chromosoom wordt op deze manier gelegd. Dat voorkomt dat elke solution intern deze waarden zou moeten bijhouden (al zijn het maar referenties). GeneticAlgorithm GeneticAlgorithm is de abstracte uitwerking van het genetische algoritme. De template van het GA is in grote lijnen dezelfde als in de theoretische uiteenzetting van een GA (zie ook paragraaf 4.2). In de huidige implementatie zijn er een aantal extra zaken (hook methods) opgenomen om de programmeur die van deze klasse overerft een aantal extra mogelijkheden te geven. De programmeur is echter niet verplicht om hier gebruik van te maken.


41

Figuur 5.9: Implementatie van het genetische algoritme

CVRPTW GA Deze klasse erft over van GeneticAlgorithm en bevat de concrete implementatie voor alle abstracte methoden van het GA. Het is dan ook een object van deze klasse die parameters zal aanvaarden en die het GA kan starten. Voor meer uitleg omtrent de concrete werking van het GA verwijs ik naar paragraaf 5.4 en verder. ParameterArgs Deze klasse heeft als doel om allerlei parameters aan de module door te geven van buitenaf. Voor meer informatie over deze klasse verwijs ik naar paragraaf 5.9.


42

Solution Een object van deze klasse bevat het chromosoom onder de property SelectionTable. Daarnaast zijn er ook enkele hulpmethoden voorzien die logisch thuishoren in deze klasse, zoals bijvoorbeeld calculateFitness(). SolutionComparator Deze klasse dient simpelweg om oplossingen met elkaar te kunnen vergelijken. DataSack Deze klasse is essentieel binnen het chromosoom. Het is in objecten van deze klasse dat alle ritten worden ingepland. Meer info omtrent het gebruik van deze klasse is ook terug te vinden in paragraaf 5.5.2. RitDelivery Deze klasse stelt een ritvoorstel voor of, met andere woorden, een ingeplande rit. Deze klasse bevat voornamelijk tijden en locaties. RitComparer Deze klasse dient simpelweg om ritten met elkaar te kunnen vergelijken. ConcretePlannerError Dit is een klasse die een Exception voorstelt. Alle fouten zullen verpakt worden in een dergelijk object en worden samen met de resultaten verpakt in een object van de klasse ConcretePlanning. De reden waarom deze klasse niet overerft van Exception is tweeledig. Enerzijds werd mij gevraagd om compatibel te zijn met de errorklasse MessageArgs van een bibliotheek van ICORDA. Dat was nodig voor een gemakkelijkere integratie van de module in het programma IApprove. Daarnaast zijn Exceptions niet serialiseerbaar. Ik heb tijdens het debuggen af en toe de nood gehad om mijn volledige populatie weg te schrijven. Hierdoor kon ik vanaf een bepaalde situatie vertrekken om een specifieke fout na te gaan. Het wegschrijven was enkel mogelijk als ik niet overerfde van Exception. Serialiseerbaar zijn is ook de reden waarom ik de klasse SerializableDictionary heb geschreven (de .NET Dictionary is eveneens niet serialiseerbaar). Hoofdstuk 5. Implementatie

43

ErrorFactory Deze klasse is een factory die fouten genereert op basis van een foutcode. Wanneer er zich in code een bekende fout voordoet, zal het bijhorende foutobject via deze klasse aangemaakt worden op basis van de doorgegeven foutcode.

5.4

Ontwerp van het GA

Zoals uit het klassendiagram blijkt, heeft een GA het grote voordeel dat enerzijds de globale werking ervan grotendeels vastligt dankzij het template pattern en dat er anderzijds aanzienlijke flexibiliteit is voor de programmeur, omdat hij toch een eigen implementatie kan voorzien voor de sleutelmethoden. Om het GA ook met ons specifiek probleem overweg te laten kunnen, is het dus aan de programmeur om een efficiënte implementatie te voorzien op de nodige locaties. Om te weten op welke locaties een eigen implementatie nodig is, kijken we allereerst naar de gemeenschappelijke elementen voor alle GA’s: 1. een genetische voorstelling van een oplossing in de vorm van een chromosoom; 2. een manier om een initiële populatie aan te maken; 3. een evaluatiefunctie die toelaat om oplossingen numeriek met elkaar te vergelijken; 4. een manier om voortplanting te simuleren; 5. een manier om parameters in te stellen (voor bijvoorbeeld populatiegrootte, break-condities, kans van operatorgebruik enz.).

Elk van de bovenliggende items kan een significante impact hebben op de efficiëntie en snelheid van het GA. Daarom moet men zich tijdens de implementatie steeds twee vragen stellen, namelijk: Heb ik dit item (variabele, functie enz.) wel nodig? Kan dit item (object, functie enz.) niet eenvoudiger en/of efficiënter?


44

Bij het ontwerp van een GA moet men steeds rekening houden met beide bovenstaande vragen. Hierbij moeten we dus steeds efficiëntie en rekentijd afwegen ten opzichte van geheugengebruik. De server waarop de module uitgevoerd zal worden, neemt verschillende taken voor zijn rekening. Dit heeft op zijn beurt invloed op het toegestane geheugengebruik. Concreet werd er een limiet opgelegd van 300 MB geheugengebruik. De module dient hier zeker onder te blijven. Tegelijkertijd werd ook de eis gesteld dat de berekeningstijd van de module “werkbaar” moest blijven. Ik plaats werkbaar tussen aanhalingstekens omdat dat in mijn geval een vrij flexibel iets is. Concreet wil dat zeggen dat er nooit een tijd vermeld is geweest als limiet. Toch spreekt het voor zich dat ik steeds gestreefd heb naar een zo laag mogelijke rekentijd. Meer informatie omtrent de rekentijd vindt u in paragraaf 6.1.2. In de volgende paragrafen zal verder ingegaan worden op de ideeën achter de concrete implementatie van de gemeenschappelijke elementen voor alle GA’s. Daarnaast zullen ook de hindernissen die overwonnen moesten worden (per onderdeel) besproken worden.

5.5 5.5.1

Voorstelling van een chromosoom Het individu

Wanneer we het eerste item van de lijst met alle gemeenschappelijke elementen voor GA’s bekijken, zien we dat we nood hebben aan een voorstelling van een oplossing. Vaak gebeurt de representatie van een oplossing op basis van strings (al dan niet binair). Voor VRP is een dergelijke voorstelling echter verre van ideaal. De oplossing moet namelijk meer weergeven dan enkel en alleen of een bepaald item geselecteerd is. Voor ons probleem moet een oplossing weergeven welke voertuigen gebruikt worden voor welke klant(en) en bovendien op welk(e) tijdstip(pen). Bovendien heeft de volgorde waarin voertuigen worden ingepland voor een bepaalde klant ook een invloed op de volledige oplossing. Het is duidelijk dat hier iets meer nodig is dan een simpele bitstring. In ons geval bestaat iedere oplossing uit een set van alle orders die we wensen in te plannen, waarbij per order steeds een selectietabel van alle voertuigen Hoofdstuk 5. Implementatie

45

hoort. Deze representatie laat ons al toe om te bepalen welke voertuigen geselecteerd zijn voor een bepaalde order. Dit is al een goede start maar deze representatie zegt niks over de volgorde waarin deze selectie gebeurd. Bovendien hebben we op deze manier ook geen zicht op het hergebruik van een bepaald voertuig binnen een bepaalde order. Om volgorde en hergebruik van voertuigen te kunnen aanduiden wordt er per voertuig nog een set van ritten bijgehouden. Een rit duidt aan op welk tijdstip het voertuig voor de order in kwestie in gebruik is alsook welk volume het voertuig transporteert.

Figuur 5.10: Interne represenatie van een individu/oplossing

Deze figuur is een sterk vereenvoudigde voorstelling van een individu/oplossing. De grote lijnen zijn duidelijk, maar een beetje extra uitleg is hier zeker op zijn plaats. We hebben initieel N orders. Voor ieder van deze N orders hebben we initieel de keuze uit dezelfde M beschikbare voertuigen (dit zijn de horizontale hokjes). Het oranje kader duidt aan dat een voertuig geselecteerd is en dat er bovendien minstens één rit ingepland is. De oranje tekst toont de ordening van ritten voor Hoofdstuk 5. Implementatie

46

een bepaald voertuig. Het spreekt uiteraard voor zich dat rit 1 voor rit 2 plaatsvindt. In het gegeven voorbeeld zijn de oranje ritten steeds gesorteerd. Dat zou betekenen dat voor een bepaalde order een bepaald voertuig steeds een bepaald volume naar een bepaalde locatie zou brengen en dat een volgende wagen hetzelfde zou doen. Deze aanpak zorgt er echter voor dat er kostbare tijd verloren gaat tijdens de momenten waarop de wagen van of naar de centrale rijdt. Gedurende deze tijd zou er dan niks gebeuren op de werf. Daarom introduceren we een betere aanpak met behulp van de blauwe tekst. De blauwe tekst stelt de ordening van de ritten binnen een bepaalde order voor. Concreet wil dat zeggen dat wagens elkaar gaan afwisselen voor een bepaalde order om zo de rijtijden van en naar de werf/centrale te overbruggen. Van zodra een wagen klaar is met het storten van beton moet een volgende wagen al de werf oprijden om zijn plaats in te nemen. Het is duidelijk dat deze aanpak een stuk beter is dan die van de oranje ritten. We moeten echter opmerken dat de blauwe ritten nog steeds een vereenvoudigde voorstelling zijn van de werkelijke aanpak. In realiteit is het zo dat er ”on the fly” wordt beslist. Dat betekent dat een volledige dagplanning nooit vooraf opgemaakt wordt. Wanneer een bepaalde wagen op de betoncentrale aankomt, beslist de dispatcher naar welke werf de wagen gestuurd zal worden. Dat kan dezelfde werf of een compleet andere werf zijn. Wanneer we dit gegeven vertalen naar de voorstelling van een individu is het best mogelijk dat de blauwe tekst over diverse orders heen staat. Concreet betekent dat dat de eerste rit van wagen 1 naar order 1 gaat, zijn tweede rit naar order 3 gaat en zijn derde rit weer naar order 1 gaat. Wanneer we de gegevens van bovenstaande paragrafen in acht nemen, kunnen we al snel concluderen dat nagenoeg elk individu verschillend zal zijn. Aangezien het verschil tussen twee individuen slechts het verschil betekent tussen één enkele eigenschap van een rit (tijdstip, wagen, volume enz.), betekent dat dat een populatie al vrij groot kan worden zonder dat er 2 gelijke individuen aanwezig zijn in de populatie. Dat waren althans de verwachtingen. Na implementatie bleek echter dat het aantal verschillende individuen beduidend lager lag dan wat de theorie voorspelde. De reden daarvoor is simpel. De genetische operatoren werken niet volledig at random. Dat betekent op zijn beurt dat ze de creatie van de nakomelingen Hoofdstuk 5. Implementatie

47

voor een deel gaan sturen. Die sturing is noodzakelijk (meer daarover in paragraaf 5.8). Het is duidelijk dat de samenstelling alsook de grootte van de populatie een aanzienlijke invloed hebben op de performantie alsook op de convergentiesnelheid en -tijd om tot een goede oplossing te komen. Een kleine populatie zal over het algemeen een povere performantie hebben ten gevolge van het feit dat er niet genoeg variatie binnen de oplossingen is. Een grote populatie zal over het algemeen een betere performatie hebben en heeft als bijkomend effect dat vroegtijdige convergentie naar een oplossing vermeden wordt. Een te grote populatie heeft naast een extra kost voor geheugenplaats ook nog het nadeel dat er aanzienlijk veel extra iteraties nodig zijn om tot een (goede) oplossing te komen. Het is duidelijk dat de juiste parameters voor het GA essentieel zijn voor een goede en snelle werking.

5.5.2

Hindernissen

Ontwerp Bij het ontwerp van het chromosoom/het individu/de oplossing was de grootste hindernis het ontwerp zelf. Mijn literatuurstudie had mij enkel de schoolvoorbeelden van chromosomen opgeleverd. Uiteraard is het duidelijk dat een simpele bitstring hier niet voldoende zou zijn. De nuttigere implementaties van een chromosoom werden ofwel afgeschermd door de ontwerpers, ofwel was de implementatie simpelweg niet van toepassing. Ik wou graag een chromosoom hebben waaruit ik op een eenvoudige en gestructureerde manier de oplossing voor het probleem kon halen zodra deze berekend was. Ik wou het idee achter een bitstring (geselecteerd/niet geselecteerd) ook in mijn ontwerp behouden. Daarom heb ik een speciale klasse DataSack ontworpen (zie paragraaf 5.3). Ik wou naast het al dan niet geselecteerd zijn van een voertuig ook de ingeplande ritten van dat voertuig kunnen structureren en dat bovendien per order. De klasse DataSack zorgde voor deze structuur.


48

5.6

Initi¨ ele populatie aanmaken

Zoals al eerder vermeld, heeft ieder GA de nood om een initiële populatie (van individuen/oplossingen) aan te maken. De manier waarop dat gebeurt heeft een grote invloed op de werking en het resultaat van het GA.

5.6.1

Gevaren

Over het algemeen worden de initiële oplossingen at random gekozen, maar ze kunnen net zo goed geconstrueerd worden volgens bepaalde richtlijnen. Het construeren van oplossingen houdt potentieel gevaar in, namelijk dat we vertrekken van te goede oplossingen. Als dat het geval zou zijn, is de kans groot dat dergelijke oplossingen al vroeg in het iteratieve oplossingsproces dominant worden in de populatie. Nu moeten we ons natuurlijk de volgende vraag stellen: Hoe schadelijk is een dergelijke dominantie? Om hierop te kunnen antwoorden, moeten we even teruggaan naar de theorie (zie ook hoofdstuk 4) omtrent GA’s. Dominantie betekent dat het GA snel zal evolueren naar een homogene populatie. Een homogene populatie is op zijn beurt vernietigend voor de kracht en snelheid van een GA. Er is immers diversiteit in de populatie nodig als we vooruitgang willen boeken in de nakomelingen. Een GA tracht immers steeds het goede van twee ouderoplossingen te combineren om een nakomeling te produceren. Wanneer we met een homogene populatie te maken hebben, combineert een GA eigenlijk twee min of meer gelijke ouderoplossingen. Dat resulteert op zijn beurt in een nakomeling die opnieuw min of meer gelijk is aan de ouderoplossing. Er is dus met andere woorden amper of zelfs geen evolutionaire vooruitgang geboekt. Dat betekent dat er veel meer iteraties nodig zijn om tot een goede oplossing te komen. Met andere woorden: hoe homogener de populatie, hoe meer iteraties en dus hoe meer rekentijd er nodig is.

5.6.2

Constructie

Nu we ons bewust zijn van de gevaren kunnen we met de eigenlijke constructie beginnen. Ik heb mijn minimale oplossing gedefinieerd als een


49

oplossing waarbij exact één enkele rit is ingepland voor een bepaalde order. Een rit inplannen gebeurt op basis van het vereiste debiet van de order, de rijtijd van en naar de werf en nog enkele andere tijden (afkomstig van de invoerparameters van de module). Nu de definitie van de minimale oplossing vastligt, kunnen we beginnen met de effectieve constructie. Ik heb twee constructiewijzen uitgeprobeerd, namelijk: 1. exhaustieve constructie 2. random constructie

In de volgende paragrafen geef ik meer informatie over deze twee mogelijkheden. Voor welke constructiewijze ik gekozen heb en waarom zal ik nadien bespreken. Exhaustieve constructie Mijn eerste manier van initialiseren was exhaustieve constructie. Dit houdt in dat ik elke mogelijke minimale oplossing ging aanmaken. Concreet wil dat zeggen dat ik voor elke order (van de in te plannen orders) elk mogelijk voertuig exact één keer inplande. Voor N orders en M voertuigen construeerde ik dus NxM individuen. Het idee achter deze constructiewijze was simpel. Zorg ervoor dat de beginpopulatie zo divers mogelijk is door alle mogelijkheden aan te reiken. Voordelen heel diverse beginpopulatie Geen meervoudige identieke minimale oplossingen in de beginpopulatie

Nadelen Omvang van de beginpopulatie rechtstreeks afhankelijk van de invoergegevens (aantal orders/voertuigen)


50

Random constructie Mijn tweede constructiewijze was random constructie. Via deze methode worden at random oplossingen geconstrueerd. Er wordt nog steeds slechts één rit ingepland voor een bepaalde order. Het is nu echter best mogelijk dat er (door toeval) gelijke beginoplossingen in de populatie terechtkomen. Voordelen Relatief diverse beginpopulatie Omvang van de beginpopulatie onafhankelijk van de invoergegevens (aantal orders/voertuigen)

Nadelen Meervoudige identieke beginpopulatie

minimale

oplossingen

mogelijk

in

de

Mogelijk verlies van de optimale oplossing bij een limitatieve beginpopulatie

Keuze Om tot een verantwoorde keuze te komen, zat er voor mij niks anders op dan te testen op basis van diverse parameters. Naast het testen van de individuele constructiewijzen heb ik ook de combinatie van beide geprobeerd. Bij het testen heb ik de zwakke punten van beide methoden proberen te maximaliseren. Voor de exhaustieve methode heb ik (onder andere) getest met heel weinig orders en/of voertuigen. Dat had een heel kleine beginpopulatie als gevolg, waardoor de volgende generaties al snel ongewild extreem homogeen werden. Testen met heel veel orders en/of voertuigen had een heel grote populatie tot gevolg. Aangezien ik er later voor geopteerd hebt om elitisme (zie ook paragraaf 4.3.3) in te voeren, resulteerde dat in veel constructiewerk dat de volgende iteratie al verloren ging. Bij het testen van de random methode bleek dat de populatie enkel homogeen kon worden wanneer er heel weinig orders en/of voertuigen Hoofdstuk 5. Implementatie

51

aanwezig waren als invoergegevens. De populatie werd in dat geval echter minder homogeen dan bij de exhaustieve methode. De meervoudige identieke minimale oplossingen bleken een minder groot nadeel dan een te kleine of te grote beginpopulatie. Omdat de module moet kunnen omgaan met zowel weinig als veel invoergegevens, heb ik uiteindelijk gekozen voor de random constructiewijze. De nadelen van deze methode waren steeds kleiner dan die van de exhaustieve methode onder dezelfde omstandigheden.

5.6.3

Hindernissen

Rit inplannen Het grootste probleem was het inplannen van een rit. Op het ogenblik van implementatie was het zo dat de module een hoop foutieve en onbruikbare data binnenkreeg. Zo werden er bijvoorbeeld wagens doorgestuurd die geen volume konden meenemen. Daarnaast waren er ook bouwwerven die niet aan betoncentrales gekoppeld waren. Met andere woorden: er waren geen reistijden beschikbaar van of naar de werf. Daarnaast waren er ook nog bepaalde orders waarvoor er geen debiet ingesteld was. Het is extreem moeilijk om een rit in te plannen als je geen compleet overzicht hebt van alle factoren die de leveringstijd be¨ınvloeden. Toen ik dit probleem signaleerde, kreeg ik als antwoord dat de module moest kunnen omgaan met foutieve data. Daarom heb ik ervoor geopteerd om bepaalde defaultwaarden te gebruiken als er foutieve data aanwezig is. Deze waarden werden later omgevormd naar parameters die men naar eigen goeddunken kan instellen. Dit voorval heeft ervoor gezorgd dat de module nu vrij robuust is.

5.7 5.7.1

Evaluatiefunctie Inleiding

Zoals al aangehaald bij de theoretische uiteenzetting van een GA is de evaluatiefunctie een essentieel onderdeel van het algoritme. We moeten in staat zijn om te bepalen hoe goed een individu is ten opzichte van de rest. Hoofdstuk 5. Implementatie

52

Een goede fitnessfunctie moet relatief snel kunnen worden berekend. De functie wordt voor ieder individu van de populatie en in elke iteratie aangeroepen. De totale rekentijd hangt dus voor een aanzienlijk deel samen met de snelheid van deze functie.

5.7.2

Implementatie

De berekening van de fitnesswaarde is in ons geval geen eenvoudige opdracht. We hebben allereerst een vrij ingewikkelde structuur voor een chromosoom (zie paragraaf 5.5). Daarnaast moeten we ook de beoordelingscriteria vastleggen en er een puntensysteem aan koppelen. Het puntensysteem is nodig om de goede en slechte eigenschappen van individuen respectievelijk te belonen en af te straffen. In ons geval komt de totale fitnesswaarde van een individu neer op de som van de fitnesswaarden van de individuele orders. Beoordelingscriteria van een order Zijn er ritten ingepland voor een order? Is een order volledig ingepland? Hoeveel verschillende voertuigen zijn er gebruikt voor een order? Hoeveel voertuigen worden er hergebruikt binnen een order? Hoe verhouden de normale en maximale capaciteit van alle geplande ritten zich t.o.v. het gewenste volume? Hoeveel capaciteit wordt er onbenut gelaten om de order uit te voeren?

Men kan zich afvragen of al deze beoordelingscriteria wel noodzakelijk zijn. Het antwoord daarop is zowel ja als nee. Het beoordelingssysteem kan eenvoudiger. Zo kan men bijvoorbeeld enkel rekening houden met het criterium van hoeveel het ingeplande volume van het gewenste volume afwijkt. Deze eis vormt tenslotte de kern van de zaak. Een vereenvoudiging heeft echter een vervelend gevolg: de score die gegeven wordt zal eveneens


53

vereenvoudigen. Dat betekent dat men minder mogelijkheden krijgt om de inplanning te beoordelen. Ik geef een kort voorbeeld van wat de gevolgen zijn van werken met minder criteria. Stel: we hebben een order in oplossing X die al gebruikmaakt van 5 voertuigen en waarbij er nog 10 m3 geleverd moet worden. Dan zal deze order dezelfde score krijgen als de overeenkomstige order in oplossing Y waar er 7 voertuigen gebruikt worden en er eveneens nog 10 m3 geleverd moet worden. Dit kleine verschil tussen twee orders heeft echter verschillende gevolgen voor de volledige planning. Zo staan er in oplossing X 2 extra voertuigen ter beschikking om leveringen te doen in vergelijking met oplossing Y. Het mag duidelijk zijn dat de subtiele verschillen tussen dezelfde orders in verschillende oplossingen een aanzienlijk verschil zullen maken in de volledige planning van de individuele oplossing. De toegekende score zal minder zeggen over de kwaliteit van een oplossing naargelang er minder criteria gebruikt werden bij het samenstellen van die score. Daarom heb ik er uiteindelijk voor geopteerd om zoveel mogelijk (nuttige) criteria te hanteren bij het samenstellen van de score. Aan elk van de criteria wordt ook een zekere gewichtsfactor gekoppeld. Er wordt zowel met positieve als negatieve gewichten gewerkt om criteria respectievelijk te belonen of af te straffen. Door middel van dit puntensysteem wordt er in eerste instantie een zekere prioriteit toegekend aan de diverse gebruikte criteria. Het tweede doel van de gewichten is om diverse oplossingen zoveel mogelijk van elkaar te kunnen onderscheiden zonder limitaties op te leggen aan de maximale te behalen score. Ik verduidelijk deze stelling aan de hand van een voorbeeld. Wanneer we een maximale score zouden instellen wordt de beoordeling om diverse redenen minder evident. Je moet allereerst binnen de maximale beoordeling blijven, wat het gebruik van gewichtsfactoren bemoeilijkt. Daarnaast wordt het heel moeilijk om conclusies te trekken uit oplossingen die de maximale score bereikt hebben. Stel dat 10 oplossingen de maximale score behaald hebben. Dan is er geen snelle manier meer om na te gaan welke van deze oplossingen nu eigenlijk de beste is. Wanneer we met een puntensysteem zonder maximale score werken, stellen de voorgaande Hoofdstuk 5. Implementatie

54

problemen zich niet. We mogen nu naar hartenlust met gewichtsfactoren werken zonder dat dat een effect heeft op een snelle beoordeling van de populatie op basis van de fitnesswaarden. Bovendien zorgen gewichten ervoor dat er sneller gaten ontstaan in de scores van individuen in de populatie. Betere oplossingen zullen hogere scores behalen en zullen onderling zelden dezelfde score behalen. Dat bevordert de diversiteit van de populatie en laat het GA toe om sneller de betere oplossingen te selecteren voor evolutionaire vooruitgang.

5.7.3

Hindernissen

Afstellen van het puntensysteem De grootste hindernis bij de implementatie van dit onderdeel was het correct afstellen van het puntensysteem. De juiste gewichten vinden voor elk criterium was een lang en pijnlijk proces van trial-and-error. Omdat er zowel beloond als afgestrafd kan worden, al naargelang het gehanteerde criterium, leidden de eerste probeersels al snel tot aanzienlijke problemen. Zo heb ik onder andere te kampen gehad met: Vroegtijdige beëindiging van het GA omdat scores negatief werden (ook voor goede oplossingen). Geen beëindiging van het GA omdat de scores bleven stijgen. Er werden op een bepaald moment ritten ingepland zonder volume. De beloning hiervoor overwon de bestraffing. Scores die na het bereiken van bepaalde aspecten gelijk bleven ondanks het onvoltooid zijn van een oplossing. Scores die inconsistent werden naargelang de invoergegevens (bij invoer van veel orders en wagens haalde ik soms lagere scores voor oplossingen dan bij de invoer van weinig orders en/of wagens)

Het meest vervelende aspect van het debuggen was dat er vaak een combinatie van de hierboven opgesomde problemen tegelijkertijd aanwezig was binnen een populatie. Dat zorgde ervoor dat het niet eenvoudig was om te bepalen bij welke criteria het toegekende gewicht fout zat. Hoofdstuk 5. Implementatie

55

5.8

Reproductie

Eén van de belangrijkste zaken binnen een GA is de voortplanting van de populatie met evolutionaire vooruitgang als doel. De manier waarop dat gebeurt is via selectie en genetische operatoren. Onder selectie verstaan we het selecteren van geschikte “ouders”. Het produceren van een nakomeling, het zogenaamde “kind”, gebeurt door middel van genetische operatoren. In de volgende subparagrafen gaan we verder in op de concrete werking binnen mijn implementatie.

5.8.1

Selectie

Selectie doet niet veel meer dan oplossingen selecteren uit de populatie, die vervolgens zullen worden gebruikt om nakomelingen te produceren. Binnen mijn implementatie heb ik er uiteindelijk voor gekozen om met roulette wheel-selectie te werken (zie paragraaf 4.3.3). Ik heb echter in eerste instantie met random selectie gewerkt. Deze implementatie was een stuk eenvoudiger. Een simpele random generator en de implementatie was klaar. Merkwaardig genoeg duurt het met random selectie een aanzienlijk aantal extra iteraties om tot een oplossing te komen. De reden daarvoor is in eerste instantie niet volledig duidelijk. Er worden namelijk minder berekeningen gemaakt ten opzichte van roulette wheel en toch is deze methode trager. Het antwoord schuilt waarschijnlijk binnen de werking van roulette wheel. Om met roulette wheel-selectie te kunnen werken, hebben we dus gedurende iedere iteratie van het algoritme de fitnesswaarde van elke oplossing binnen de populatie nodig. Deze methode heeft als grote nadeel dat we dus steeds de fitnesswaarde moeten herberekenen. Dat vraagt uiteraard tijd. Daarnaast moet er ook nog een zekere kans toegekend worden aan elk individu alvorens er effectief geselecteerd kan worden. Ook deze berekening vraagt opnieuw extra tijd. Om te verklaren waarom roulette wheel-selectie beter werkt dan random selectie, gaan we uit van een simpel voorbeeld.


56

Voorbeeld:

Figuur 5.11: Vereenvoudigde voorstelling van roulette wheel-selectie[29]

De illustratie toont de kansverdeling binnen een voorbeeld populatie van 5 individuen (een typische populatie van 400 of meer is vrij moeilijk af te beelden). De percentages stellen de ingenomen plaats van een bepaald individu op het roulette wheel voor. Die ingenomen plaats werd berekend op basis van de individuele fitnesswaarden. Vervolgens gaan we aan het virtuele roulette wheel draaien. De plaats waar het wiel stopt ten opzichte van het selectiepunt zal bepalen welk individu er wordt geselecteerd. We doen dit steeds tweemaal per selectie iteratie (niet te verwarren met een iteratie van Hoofdstuk 5. Implementatie

57

een GA). Nu we 2 individuen selecteerd hebben, kunnen we deze doorgeven aan genetische operatoren die nakomelingen zullen produceren op basis van dit ouderpaar. We zorgen er uiteraard voor dat we geen twee dezelfde ouders selecteren. Dit zou nefast zijn voor het voortplantingsproces. Daarmee is echter nog niet verklaard waarom roulette wheel-selectie beter werkt dan random selectie. Wanneer we teruggaan naar de theorie omtrent GA’s weten we dat het doel van een GA evolutionaire vooruitgang is. Wanneer we even kijken naar de natuur (waarop een GA gemodelleerd is), dan weten we dat de grootste vooruitgang wordt geboekt door nakomelingen van de sterkste/fitste individuen te krijgen. Roulette wheel-selectie speelt net op deze eigenschap in. Aangezien de verdeling van het wiel rechtstreeks gekoppeld is aan de fitheid van de individuen, hebben de sterkste individuen dus de grootste kans om geselecteerd te worden voor reproductie. Dat verklaart dan ook waarom er minder iteraties nodig zijn (in vergelijking met random selectie) om tot een goede oplossing te komen. Zodra een ouderpaar geselecteerd is, kan dat doorgegeven worden aan de genetische operatoren (zie paragraaf 5.8.3). Het resultaat van deze genetische operatoren is één of meerdere nakomelingen. Deze nieuwe individuen vormen de basis van de nieuwe generatie. In mijn implementatie wordt ernaar gestreefd om een bepaald aantal nakomelingen te bekomen voor de volgende generatie. Dit aantal is een in te stellen parameter. Om zoveel mogelijk nakomelingen te bekomen uit één ouderpaar, wordt er tweemaal crossover en tweemaal mutatie uitgevoerd op het ouderpaar. Dat zorgt ervoor dat we iedere ronde maximaal 4 nakomelingen kunnen bekomen. Omdat er uitzonderingen zijn waarbij de genetische operatoren geen nakomelingen produceren, is het mogelijk dat er in een gegeven ronde geen nakomelingen zijn. Aangezien we een vast aantal kinderen proberen te bereiken, zijn dergelijke selectierondes heel nefast. Deze verhogen de tijd die nodig is om een nieuwe generatie te produceren en dus ook de totale rekentijd. Daarom is er een veiligheid ingebouwd in het selectieproces. Deze failsafe zorgt ervoor dat wanneer er geen nakomelingen geproduceerd worden gedurende een bepaalde ronde er toch geteld worden. Daardoor komen we toch aan ons vast aantal nakomelingen, al komt het werkelijk geproduceerde Hoofdstuk 5. Implementatie

58

aantal niet overeen met het vooropgestelde doel. In de praktijk bleek deze ingreep een positieve impact te hebben op de benodigde rekentijd. Zodra de nieuwe generatie geproduceerd is, wordt deze samengevoegd met de vorige generatie. Het samenvoegen van twee generaties gebeurt niet in ieder GA. Dat was echter een persoonlijke en doordachte keuze. Omdat we vaak niet het beoogde aantal nakomelingen bekomen, is een aanvulling van de populatie geen slecht idee. Bovendien vermijd je op deze manier dat je potentieel goede oplossingen uit de voorgaande generatie verliest. De samengevoegde populatie is nu naar alle waarschijnlijkheid vrij groot geworden. Omdat roulette wheel-selectie het beste werkt met een populatie die niet heel groot is moeten we eventueel gaan snoeien (in het engels “pruning”) in de populatie. Dat betekent concreet dat er slechts een vooropgesteld aantal individuen in de populatie mag overblijven alvorens het GA aan zijn volgende iteratie begint. In mijn implementatie gebeurt dat door middel van elitisme (zie paragraaf 4.3). Het aantal dat moet overblijven is een parameter die ingesteld kan worden. Bovendien kan men ook dit aantal procentueel laten toe- of afnemen indien nodig (eveneens in te stellen via een parameter).

5.8.2

Hindernissen bij selectie

Bij de implementatie van dit onderdeel heb ik vrij weinig problemen ondervonden. Het grootste probleem was het uitbouwen van de veiligheid bij selectie. De eerste implementatie van deze failsafe zorgde voor aanzienlijk extra rekentijd. Wanneer een bepaalde selectieronde geen nakomelingen produceerde, telde ik er toch steeds één. Dat zorgde ervoor dat het selectieproces niet in een oneindige lus terechtkwam (aangezien we naar een vast aantal nakomelingen streven). Tegelijkertijd was het zo dat bepaalde invoer ervoor zorgde dat er al na 100-200 geproduceerde nakomelingen veel lege selectieronden voorkwamen. Wanneer we dan tot streefcijfers van 400 gaan is het duidelijk dat er verschillende keren tevergeefs wordt geprobeerd om nakomelingen te bekomen. Dat zorgde er uiteindelijk voor dat ik afstapte van een lineaire toename en een exponentiële toename implementeerde. Ik demonstreer het nut van een exponentiële curve aan de hand van een voorbeeld. Hoofdstuk 5. Implementatie

59

Stel dat we al 50 nakomelingen bekomen hebben in 100 selectieronden en dat we theoretisch gezien slechts 150 verschillende nakomelingen kunnen produceren. Dan is het duidelijk dat een streefcijfer van 400 onbereikbaar is. De failsafe vermijdt dat je in een oneindige lus terechtkomt, maar vermijdt niet dat er nog 200-300 keer geprobeerd wordt om extra nakomelingen te bekomen (aangezien we de nakomelingenteller telkens slechts met 1 verhogen). Het is echter beter om toch nog enkele keren een poging te doen tot voortplanting en tegelijkertijd in een versneld tempo naar het vooropgelegde streefcijfer te evolueren. De beste manier om dat te verwezelijken is door middel van een exponentiële curve. In mijn implementatie zal er steeds 10 procent toegevoegd worden aan de nakomelingenteller in het geval van een lege selectieronde. Bij lage aantallen zal dat ervoor zorgen dat we ongeveer dezelfde (virtuele) vooruitgang boeken als wanneer we een volledige selectieronde (van 4 geproduceerde nakomelingen) achter de rug hebben. Bij hogere aantallen zal dat een versnelde beëindiging van de selectieproducere tot gevolg hebben. Stel dat we uiteindelijk maar 100 nakomelingen hebben geproduceerd. Dan hebben we nog steeds de samenvoeging van de vorige generatie met deze nieuwe generatie, waardoor het eindtotaal van de nieuwe populatie opnieuw dicht tegen het streefcijfer zal liggen. Op die manier garanderen we een voldoende grote en diverse populatie voor het algoritme.

5.8.3

Genetische operatoren

Wanneer we terugblikken op de structuur van ons chromosoom (zie paragraaf 5.5.1), dan zien we dat een individu/oplossing een vrij ingewikkelde structuur heeft. Het is dan ook niet evident om evolutionaire vooruitgang te definiëren op basis van deze structuur. Toch hebben we nood aan deze definitie als we het GA willen laten werken. In de volgende paragrafen gaan we verder in op het idee achter de implementatie van de genetische operatoren crossover en mutatie.


60

Crossover Bij de implementatie van deze operator heb ik twee vormen van crossover uitgewerkt, namelijk: 1. crossover in orders, 2. crossover in ritten.

1. Crossover in orders Het idee achter deze implementatie steunt op het algemene principe van single-point crossover (zie paragraaf 4.3.4). Hierbij wordt bij beide ouders het chromosoom in twee gesplitst op een random gekozen spilpunt en worden de twee helften van de ene ouder gecombineerd met de twee helften van de andere ouder. Bij onze structuur is het mogelijk om het chromosoom zowel horizontaal als verticaal op te splitsen. Crossover in orders maakt eigenlijk een verticale splitsing van het chromosoom. In de praktijk betekent dat dat we twee oplossingen gaan splitsen op een random punt in de orders, het zogenaamde spilpunt. Concreet wil dat zeggen de volledige inplanning van de eerste X orders uit oplossing A en de laatste Y orders uit oplossing B zullen worden samengevoegd tot een nieuwe oplossing. Deze nakomeling beschikt over dezelfde orders van de beide ouders, maar heeft nu bovendien (als het random punt goed valt) een samenvoeging van twee verschillende inplanningen.


61

Ik illustreer dit concept aan de hand van een illustratie. Voorbeeld:

Figuur 5.12: Vereenvoudigde voorstelling van crossover in orders

In het voorbeeld maken we gebruik van een chromosoom dat bestaat uit 5 orders en M voertuigen. Stel dat het random spilpunt voor crossover bij order 3 gelegen is. Aangezien het toch de bedoeling is dat de combinatie van beide ouders gemaakt wordt, zal allereerst één van beide ouders gedupliceerd worden. Hoofdstuk 5. Implementatie

62

Door deze actie hebben we al een deel van het gewenste resultaat. We nemen dit geclonede object als nakomeling. Vervolgens zal het deel voor het spilpunt van de andere ouder gekopieerd worden in de nakomeling. Het resultaat is een crossover-op basis van orders. Resultaat:

Figuur 5.13: Voorbeeld van een nakomeling gevormd door crossover in orders

Analyse van deze methode Omdat dit een eerste idee was omtrent de uitwerking van de crossover-operator, was een analyse omtrent de performantie van deze methode aangewezen. Na aanzienlijk wat testing en debugging bleek dat deze methode zowel aanzienlijke voor- als nadelen had. Eén van de grootste voordelen is het feit dat deze methode een grote sprong voorwaarts kan verwezenlijken. Vooral in het geval waarbij het spilpunt net goed valt. Het ideale scenario is dat alle ingeplande ritten van de eerste ouder zich voor het spilpunt bevinden en dat alle ritten van de tweede ouder


63

zich na het spilpunt bevinden. In dat geval krijgen we dus alle ingeplande ritten van de beide ouders gecombineerd in één enkele nakomeling. Aan dit voordeel zijn echter ook twee mogelijke nadelen verbonden. Allereerst is het net zo goed mogelijk dat het zelfs bij het ideale scenario volledig fout gaat. Als de andere helft van beide ouders gekozen zou worden, eindigen we immers met een compleet lege oplossing. Dat is uiteraard een situatie die zich extreem zelden voordoet, maar niet noodzakelijk uitgesloten is.

Een ander nadeel is dat het aantal correct geproduceerde nakomelingen omgekeerd evenredig is met het aantal al ingeplande ritten in de ouders. Dat betekent concreet dat na een bepaald aantal iteraties deze methode er niet meer in slaagt om een geldige oplossing te produceren. Dat komt omdat er tijdens de crossover geen rekening gehouden wordt met de concrete bezetting van een bepaald voertuig over de beide ouders heen. Ik leg deze opmerking verder uit aan de hand van het illustratieve voorbeeld. Wanneer we kijken naar de geproduceerde nakomeling, dan merken we dat order 1 en order 4 gebruikmaken van hetzelfde voertuig. Dat betekent dat het voertuig in kwestie dubbel geboekt kan zijn gedurende een bepaalde periode. De kans dat één of meerdere voertuigen overboekt worden stijgt vanzelfsprekend exponentieel naarmate de ouderoplossingen meer ingeplande ritten bevatten. Wanneer er ergens in een individu een dergelijke boeking voorkomt, dan zal de fitnessfunctie een extreem slechte score geven aan deze oplossing. Dat heeft als gevolg dat een dergelijk individu heel snel uit de populatie zal verdwijnen. Omdat de nadelen pas na een vijftiental iteraties echt van toepassing zijn, is het logisch dat we het gebruik van deze methode limiteren tot de eerste vijftien iteraties. In verdere iteraties zal het algoritme zijn vooruitgang realiseren door gebruik te maken van de operatoren crossover in ritten en mutatie. 2. Crossover in ritten Deze manier van crossover is een stuk eenvoudiger dan de voorgaande methode. In deze methode is het namelijk zo dat er slechts voor één enkele Hoofdstuk 5. Implementatie

64

order een crossover plaatsvindt. We gaan dus een horizontale crossover doen. Allereerst wordt er net zoals in de voorgaande methode een ouder gedupliceerd. Dit object zal opnieuw de basis vormen voor het kind. Vervolgens wordt er een random order geselecteerd. Het is deze order waarbinnen we een crossover gaan realiseren. Er wordt nu een random spilpunt gekozen. Alle ritten van de andere ouder die na dit spilpunt gelegen zijn (binnen de specifieke order van het chromosoom) worden nu overgedragen aan de nakomeling. Voorbeeld: Na een crossover in ritten op order 1, krijgen we het volgende resultaat. Resultaat: Een crossover in ritten vindt enkel plaats als de random gekozen order nog niet voltooid werd. Dit doen we om te vermijden dat een volledig ingeplande order opnieuw uit elkaar getrokken zou worden. Dat heeft als gevolg dat het best mogelijk is dat de nakomeling niet meer dan een kopie van een ouder is. Om te vermijden dat we naar een homogene populatie gaan, zal in dit geval de mutatieoperator op de nakomeling losgelaten worden. Analyse van deze methode Ik heb in een van de eerste versies deze methode op een aantal orders tegelijkertijd laten uitvoeren. Helaas bekomen we dan dezelfde nadelen als bij crossover in orders. Uit testing bleek echter dat een eenmalig gebruik van deze methode een gunstiger effect had op de rekentijd van het GA. Uit de illustratie blijkt duidelijk dat het perfect mogelijk is om achteruitgang te boeken bij deze operatie. Meestal is de scoreimpact op de totaalscore in een dergelijk geval echter vrij klein, al is dat uiteraard afhankelijk van het aantal orders dat als invoer werd gegeven. Over het algemeen blijkt echter dat zelfs een stapje terug zetten soms aanleiding geeft tot een betere oplossing op het einde. Deze methode van crossover blijft dan ook werken voorbij het punt dat crossover in orders het


65

Figuur 5.14: Vereenvoudigde voorstelling van crossover in ritten

moeilijk krijgt. Het zijn crossover in ritten en mutatie die voor een continue evolutie in de populatie zorgen gedurende iedere iteratie. Mutatie De mutatieoperator staat in voor het aanbrengen van een kleine wijziging in een oplossing die voor vooruitgang kan zorgen. We hebben een vrij ingewikkelde structuur voor een chromosoom, dus kunnen we ons de vraag stellen wat vooruitgang precies betekent. Ik heb vooruitgang gedefinieerd Hoofdstuk 5. Implementatie

66

Figuur 5.15: Voorbeeld van een nakomeling gevormd door crossover in ritten

als een toename in de ingeplande ritten. Concreet wil dat zeggen dat een mutatie het inplannen van een nieuwe rit betekent. In mijn implementatie verloopt de mutatie volgens een bepaald stramien en is deze niet compleet random. Een kleine sturing binnen deze operator was omwille van de opgelegde randvoorwaarden wel nodig. Zo stelt één van de randvoorwaarden bijvoorbeeld dat we de voertuigen zoveel mogelijk moeten proberen hergebruiken en dan liefst nog in dezelfde orders. Allereerst is het zo dat er enkel een mutatie kan worden verricht op een random order die nog niet volledig werd ingepland. Er wordt dus eerst een random order gekozen, maar als blijkt dat deze al voltooid is, dan zal er een nieuwe order gekozen worden uit de groep van niet-voltooide orders. De bedoeling is dus dat er een rit ingepland wordt voor de geselecteerde order. Vervolgens zal er geprobeerd worden om een voertuig dat al gebruikt werd binnen het order te hergebruiken (als er al een voertuig gebruikt werd uiteraard). Als dat lukt, is er een nieuwe rit ingepland en hebben we dus een mutatie. In het andere geval gaan we systematisch op zoek naar een voertuig Hoofdstuk 5. Implementatie

67

dat we mogelijk kunnen inplannen op het gewenste tijdstip. Wanneer we een dergelijk voertuig vinden, plannen we dat voertuig in. Hierbij wordt na het inplannen nagegaan of deze nieuwe rit geen dubbele boeking veroorzaakt met een andere rit binnen het chromosoom. Als dat wel het geval zou zijn, wordt deze inplanning ongedaan gemaakt en wordt er een nieuwe poging ondernomen om een ander voertuig in dezelfde order in te plannen. Wanneer na een aantal keer proberen de operator er niet in geslaagd is om een rit in te plannen, worden de pogingen tot inplanning gestaakt. Wanneer men er echter wel in slaagde een geldige rit in te plannen, wordt nagegaan of de order voltooid werd. Als dat het geval is, wordt de order als ingepland gemarkeerd. Het is dus best mogelijk dat de mutatie niet plaatsvindt. Dat heeft als gevolg dat er geen vooruitgang geboekt wordt. Dat lijkt op het eerste gezicht geen goede zaak, maar eigenlijk maakt dit niet zoveel uit. Het betekent alleen dat er voor een bepaalde order niet onmiddellijk een rit ingepland kon worden. Dit heeft echter geen invloed op de score van het individu. Als er wel een rit ingepland werd, dan verandert uiteraard de score van het individu. Het is echter zo dat de kloof tussen een rit wel of niet inplannen niet al te groot is. Dat zorgt er op zijn beurt voor dat wanneer een mutatie niet plaatsvindt, het individu in kwestie hoogstwaarschijnlijk niet onmiddellijk uit de populatie zal verdwijnen. Daardoor krijgen we automatisch een meer diverse populatie, wat de werking van het GA alleen maar ten goede komt.

5.8.4

Hindernissen bij genetische operatoren

Vooral het debuggen van de genetische operatoren was de grootste hindernis in dit onderdeel. Ik heb veel tijd verloren met het zoeken naar “onverklaarbare” gebeurtenissen alsook met algemene debugging. Eén van deze gebeurtenissen was bijvoorbeeld dat er zaken leken te veranderen in individuen van de populatie ook al werden deze niet geselecteerd voor reproductie. Daardoor verkreeg ik na een bepaald aantal iteraties een compleet homogene populatie. En met ’compleet’ bedoel ik in dit geval niet gelijkaardig, maar eerder exact hetzelfde. Elk individu van de populatie was op dit punt volledig hetzelfde. De reden voor dit alles was het feit dat ik bij het creëren van het duplicaatobject geen zogenaamde “deep Hoofdstuk 5. Implementatie

68

clone” nam. Concreet betekende dit dat C# achter de schermen slechts een referentie naar de diverse objecten kopieerde. Wanneer ik een genetische operator toepaste, zorgde dit er uiteraard voor dat geleidelijk aan meer en meer objecten tegelijkertijd dezelfde aanpassing kregen. Een andere gebeurtenis zorgde er bijvoorbeeld voor dat ik onder bepaalde omstandigheden in een infinite loop terechtkwam. Hierdoor crashte Visual Studio steeds omdat het zonder geheugen viel. Omdat de foutmelding in de crashlogs van Visual Studio extreem cryptisch was en dus niks vermeldde over een geheugentekort, heeft het enkele dagen geduurd alvorens ik de reden gevonden had. Bovendien kon ik de fout niet reproduceren en was het dus steeds wachten tot het event zich nog eens voordeed.


69

5.9

Parameters

´ en van de vereisten van de module was dat het mogelijk moest zijn om E´ van buitenaf de werking te be¨ınvloeden. De makkelijkste manier om dat te verwezenlijken is door middel van parameters. In mijn implementatie wordt gebruikgemaakt van een eigen parameterobject. Dit kan naar de toekomst uitgebreid worden als dat nodig zou zijn. Klassendiagram

Figuur 5.16: Klassendiagram van het parameterobject

Een korte verklaring voor de items is wel op zijn plaats. Elke parameter heeft zijn plaats binnen de module.


70

CUTOFF VALUE FOR BIG ORDERS: Deze eigenschap vertelt aan een GA vanaf welk volume een bepaalde order beschouwd mag worden als een grote order (grote orders krijgen voorrang bij het plannen). DEFAULT CLEANING MINUTES CONSTRUCTIONYARD: Hoeveel minuten heeft een chauffeur om zijn voertuig te reinigen op de werf. DEFAULT REQUIRED DISCHARGE: Deze eigenschap vertelt het GA wat het debiet op een order moet zijn als er geen geldig debiet ingesteld werd. PLAN DELAYED ORDERS: Moet een order dat vertraging opgelopen heeft (en waarvan de voertuigen al weg moesten zijn) nog ingepland worden. DELAYED ORDER OFFSET: Hoeveel speling qua tijd moet er op een vertraagde order zitten t.o.v. het huidige tijdstip. EARLY BREAK: Vanaf hoeveel iteraties mogen we het GA vroegtijdig beëindigen met als reden dat de beste oplossing in de populatie onveranderd blijft. MAPPOINT CORRECTIONFACTOR: Corrigeer de theoretische reistijden met een bepaalde factor zodat deze nu meer overeenstemmen met de realiteit. MAX ITERATIONS: Deze eigenschap limiteert het aantal iteraties dat het GA maximaal naar een oplossing mag zoeken. Dit vermijdt een oneindige rekentijd. MAXIMUM SOLUTIONCOUNT: Hoeveel planningsvoorstellen mag de module maximaal retourneren. MINIMAL SOLUTIONCOUNT: Hoeveel planningsvoorstellen moet de module minimaal retourneren. MIN POPULATIONCOUNT: Wat is de minimale populatiegrootte die behouden moet blijven gedurende elke iteratie. MINIMAL UNLOADING MINUTES: Wat is de minimaal benodigde tijd om een mixer te ontladen bij een klant. Hoofdstuk 5. Implementatie

71

MINIMUM REQUIRED DISCHARGE BIG ORDERS DEFAULT: Wat is het minimale debiet voor een grote order wanneer deze geen werkbaar debiet meekreeg. MUTATIONPROBABILITY: Wat is de kans dat de mutatieoperator effectief een mutatie teweegbrengt in een individu - standaard = 100 procent. REDUCTIONFACTOR: Met welk percentage neemt de grootte van een populatie af gedurende iedere iteratie - standaard blijft de grootte behouden. RETAINPOPULATIONCOUNT: Hoeveel individuen mogen er na elitisme overblijven voor de volgende iteratie. UNPLANNABLE ORDER CUTOFF: Hoeveel keer moet een order als onplanbaar gedetecteerd worden alvorens het verwijderd wordt.


72

Hoofdstuk 6

Resultaat In dit laatste hoofdstuk vindt u een beknopt overzicht van de behaalde resultaten tijdens deze masterproef. Om dit overzichtelijk te doen, wordt elk luik afzonderlijk behandeld. Daarna worden de resultaten vergeleken met de vooropgestelde vereisten. Om het geheel af te ronden, leest u nog eens het globale resultaat.

6.1 6.1.1

Verwezenlijkingen Literatuurstudie

Het eerste dat ik verwezenlijkt heb, was een grondig onderzoek naar alle zaken die met mijn onderwerp te maken hadden. Dat heeft mij na enig zoekwerk geleid tot het domein van de Vehicle Routing Problems (of kortweg VRP). Ik heb de verschillende vormen van VRP onderzocht om te kijken in welke mate ik iedere variant kon relateren aan mijn probleem. Helaas heb ik moeten concluderen dat mijn probleem niet onder te brengen was onder een bepaalde VRP-variant. Toch liet ik mij niet ontmoedingen en ging ik verder graven. Ik ben uiteindelijk de oplossingswijzen van de diverse varianten met elkaar gaan vergelijken. Daaruit bleek dat bepaalde oplossingswijzen ingezet konden worden voor elke variant, mits de nodige aanpassingen uiteraard. Ik ben uiteindelijk tot de conclusie gekomen dat het gebruik van een Genetisch Algoritme als oplossingswijze een goede keuze zou zijn om deze masterproef tot een goed einde te kunnen brengen.

73

6.1.2

Planningsmodule

Ik heb een volledige planningsmodule uitgewerkt op basis van de specifieke randvoorwaarden van de opdracht. Er lagen bij aanvang van de implementatie wel al enkele zaken vast. Zo was het al lang beslist dat er met specifieke entiteiten gewerkt moest worden (zie paragraaf 5.2). Ook de manier van invoer lag al vast. De invoer zou verlopen via XML. Na verloop van tijd is men echter overgestapt op een andere manier van invoer, namelijk invoer via een object dat doorgegeven wordt via een RESTful-webservice. Dankzij een degelijk ontwerp van de datalaag van de module was deze switch geen enkel probleem. De concrete implementatie van het GA bracht uiteraard de nodige fouten, moeilijkheden en frustraties met zich mee. Maar zodra deze hindernissen overwonnen waren kon ik met trots een robuust afgewerkt product tonen. Toch werd er na voltooiing van de implementatie nog veel tijd besteed aan het verminderen van de berekeningstijd. Tijd is immers geld. De module had initieel een rekentijd van ongeveer 5 minuten. Na enkele tweaks werd dit al teruggebracht naar 2 minuten. Dit was voor ICORDA en voor De Rycke een aanvaardbare wachttijd. Persoonlijk vond ik dit nog steeds onaanvaardbaar en daarom heb ik nog verdere tweaks gerealiseerd. De rekentijd bedraagt nu tussen de 5 en 30 seconden, afhankelijk van de hoeveelheid invoer. De module werd uiteindelijk ge¨ıntegreerd in het programma IApprove. Wanneer men in de grafische interface (zie paragraaf 6.1.3) een planningsvoorstel wil aanmaken, verzamelt het programma de data uit de database en verpakt die in een ConcretePlanning-object (dit alles duurt ongeveer 10 seconden). Vervolgens wordt deze data doorgestuurd naar de module via de RESTful-webservice. Hierbij moet opgemerkt worden dat het doorsturen ongeveer 5 seconden of meer in beslag neemt. Vervolgens doet de module zijn werk en stuurt ze een aantal planningsvoorstellen terug via de webservice (het terugsturen duurt opnieuw ongeveer 5 seconden). Tenslotte wordt het beste planningsvoorstel gevisualiseerd. Ik mag toch wel zeggen dat ik een heel goed en vooral werkbaar resultaat heb bekomen.

Hoofdstuk 6. Resultaat

74

6.1.3

GUI

Naast de planningsmodule zelf mocht ik ook de visualisatie van een planningsvoorstel uitwerken. Om dat te verwezenlijken heb ik gebruikgemaakt van de DevExpress XtraScheduler Component1 . Deze interface werd gerealiseerd onmiddellijk na de implementatie van de eerste versie van de planningsmodule. De visuele weergave heeft mij dan ook aanzienlijk geholpen in het debuggen en het tweaken van de module. We leggen de interface (zie bijlagen voor vergrootte versie van de afbeelding) uit aan de hand van een voorbeeld. Wanneer men een bepaalde datum en tijd ingeeft of wanneer men simpelweg op herplan drukt (bereken op basis van huidig tijdstip), krijgt men interactie met de module. Het resultaat wordt gevisualiseerd. We krijgen een grafische weergave van de ingeplande ritten. De verticale kolommen duiden de ritten aan die ingepland werden op het voertuig in kwestie. Per rit kan men bovendien enkele extra gegevens zoals volume en werflocatie bekijken. De blauwe streepjes aan de zijkant van elk blokje duiden een specifieke tijdspanne aan. Boven en/of onder dit blauwe streepje is er vaak nog wat ruimte. Dat komt omdat de nauwkeurigheid van de Scheduler component beperkt is tot een minimum van 5 minuten. De planning gaat echter tot een precisie van seconden.

1

http://www.devexpress.com/Products/NET/Controls/WinForms/#main\ delimiter"026B30Dcontrols


75

Figuur 6.1: Een gevisualiseerd planningsvoorstel

Naast de visualisatie heb ik ook nog enkele filtermogelijkheden voorzien zodat de gebruiker kan filteren op specifieke ordercodes en/of voertuigen. De foutboodschappen die de module heeft geproduceerd kunnen opgevraagd worden uit het resultaat. In het geval van IApprove is het zo dat alle fouten en opmerkingen onderaan rechts komen te staan. Ook bij deze grafische interface mag ik zeggen dat ik een goed en werkbaar resultaat heb bekomen.

6.2

Beoordeling t.o.v. doelstelling

De voornaamste doelstelling was het ontwikkelen van een module die op basis van externe input een geoptimaliseerde planning voor stortklaar beton kon maken. Het moest bovendien mogelijk zijn om de module antwoord te laten geven op enkele elementaire vragen (zie paragraaf 2.1). Dankzij de uitwerking van zowel de planningsmodule als een interface voor deze module mag ik stellen dat deze doelstellingen met succes gerealiseerd werden. Daarnaast zijn er ook enkele uitbreidingen (die vermeld werden in het Hoofdstuk 6. Resultaat

76

uigebreide voorstel) uitgewerkt. De realisatie van een full-automatic planning (via een druk op de knop in de grafische interface). Een grafische interface die de bezetting van voertuigen in de tijd toont. Een beperkte rapportering werd gerealiseerd door de fouten die de module heeft ondervonden te visualiseren.

Naast deze vooropgestelde doelen en uitbreidingen is er gedurende de uitwerking nog een extra verzoek bijgekomen. Men wou namelijk graag in het midden van de dag kunnen herplannen. Er is dus ook een herplanfunctionaliteit uitgewerkt. Ook deze bijkomende doelstelling werd met succes gerealiseerd. Naast de specifieke doelstellingen van de opdracht waren er ook nog enkele algemene doelstellingen met betrekking tot de masterproef. Zo moesten er onder andere 625 werkuren gepresteerd worden. Dat is mij helaas niet gelukt al zit ik slechts enkele uren van dit streefdoel. De reden voor het niet bereiken van deze doelstelling is enigszins te rechtvaardigen. Op een bepaald moment was ik klaar met de implementatie en waren er alleen nog enkele bugs die weggewerkt moesten worden. Zodra deze opgelost waren, was ik definitief klaar en kon de module uitgerold worden. Toen restte mij enkel nog het schrijven van de scriptie. Toch heb ik zoals het hoort mijn best gedaan om naar dit doel te streven. De overige algemene doelstellingen werden volledig en op tijd behaald. Hierbij denken we aan het uitgebreid voorstel, de poster, een eerste versie van de scriptie (25 p.), de website en de eerste versie van de scriptie aan de interne promotor. Ook de definitieve versie werd tijdig afgewerkt en ingediend.

6.3

Besluit

Bij aanvang van deze masterproef heb ik veel tijd gestoken in mijn literatuurstudie. Ik ben meer dan een maand met onderzoek bezig geweest. De resultaten van het onderzoek hebben mij toegelaten om de Hoofdstuk 6. Resultaat

77

planningsmodule op een efficiënte manier uit te werken. Na maanden van implementatie en debugging mag het resultaat er zeker wezen. Ik ben trots op deze toch wel vrij robuuste planningsmodule. Ik mag toch wel zeggen dat deze masterproef mij veel heeft bijgebracht. Ik heb een volledige module naar eigen goeddunken mogen uitwerken en heb deze vervolgens mogen integreren in een bestaand programma (IApprove). Daarnaast heb ik ook een interface mogen maken die het resultaat van mijn module visueel kan weergeven. De implementatie van dit alles verliep soms extreem moeizaam, met de gebruikelijke frustraties tot gevolg. Gelukkig kon ik steeds rekenen op het ervaren team developers van ICORDA om mij te helpen in momenten van nood. Al bij al heb ik enkele mooie, leerrijke maanden achter de rug. In ruil voor het geleverde werk kreeg ik naast het genoegen van een mooi resultaat ook nog een job aangeboden. Ik heb in het voorwoord al mijn dank betuigd aan alle personen die geholpen hebben om deze masterproef tot een goed einde te brengen. Bij deze wil ik graag nogmaals mijn dank uitspreken. Ik denk hierbij aan mijn promotoren, aan iedereen binnen ICORDA en aan de docenten van de Hogeschool Gent. Bedankt iedereen!


78

Literatuurlijst [1] Dantzig, G.B.; Ramser, J.H. The Truck Dispatching Problem, 1959. [2] Fisher, M. Handbooks of Operations Research and Management Science, chapter 1, 8:1-31, 1995. [3] Falkenauer, E. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2:5-30, 1996. [4] “Traveling salesman problem” Wikipedia.com. 17 maart 2011. Wikipedia url: http: // en. wikipedia. org/ wiki/ Travelling_ salesman_ problem [5] “Genetic Algorithm” Wikipedia.com. Januari 2010. Wikipedia url: http: // en. wikipedia. org/ wiki/ Genetic_ algorithm [6] Darwin C.R.On the origin of species, 1859. [7] Paolo Toth, Daniele VigoThe Vehicle Routhing Problem. USA, 2002. [8] B. Golden, S. Raghavan, E. WasilThe Vehicle Routhing Problem: Latest Advances and New Challenges. USA: Springer Science, 2008. [9] Jens Lysgaard, Adam N. Letchford, Richard W. EgleseA New Branch-and-Cut Algorithm for the Capacitated Vehicle Routing Problem. 15/09/2003 [10] Daniele VigoBranch and bound algorithms for CVRP (lecture notes). 8/2007 [11] Al-Dahoud AliComputational Intelligence and Modern Heuristics. India: In-Teh, Februari 2010.

79

[12] Zbigniew Michalewicz, David B. FogelHow to Solve It: Modern Heuristics. Germany: Springer Science, 2007. [13] Christian Bessiere Principles and Practice of Constraint programming - CP 2007. Germany: Springer Science, 2007. ´ vez, Ocotla ´ n D´ıaz-Parra, J. [14] Marco Antonio Cruz-Cha ´ ndez, Jose ´ CrispÌn Zavala-D´ıaz, Mart´ın G. A. Herna Mart´ınez-RangelSearch Algorithm for the Constraint Satisfaction Problem of VRPTW. Mexico. 2007-2007. [15] Olli Br¨ aysyGenetic Algorithms for the Vehicle Routing Problem with Time Windows. Finland, 2001 [16] Erboa Cao, Mingyong LaiAn Improved Genetic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service. China [17] Cesar Rego, Catherine Roucairol Using Tabu search for solving a dynamic multi-terminal truck dispatching problem. European Journal of Operational Research 83 (1995) 411-429 [18] Fermin Alfredo Tang Montane, Roberto Dieguez GalvaoA tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service [19] Fred Glover, Manuel LagunaTABU SEARCH. 1997. [20] Francisco Baptista Pereira, Jorge Tavares Bio-inspired Algorithms for the Vehicle Routing Problem. Germany: Springer Science, 2009. [21] Bernd Bullnheimer, Richard F. Hartl, Christine StraussAn improved ant system algorithm for the vehicle routing problem. Oostenrijk: Universiteit van Wenen. 1997. [22] Luca Maria Gambardella, Eric Taillard and Giovanni AgazziMACS-VRPTW: A MULTIPLE ANT COLONY SYSTEM FOR VEHICLE ROUTING PROBLEMS WITH TIME WINDOWS. Zwitserland.1999

Literatuurlijst

80

[23] MAURICIO G.C. ADAPTIVE SEARCH UK, pp. 63-76, 1999

RESENDEGREEDY RANDOMIZED PROCEDURES.McGraw-Hill, London,

[24] Michel Gendreau, Jean-Yves Potvin, Oli Br¨ aysy, Geir Hasle, Arne Lokketangen Metaheuristics for the Vehicle Routhing Problem and its Extensions: A Categorized Bibliography. Canada:CIRRELT. August, 2007 [25] Michel Gendreau, Jean-Yves Potvin, Francios Guertin, Rene SeguinNeighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Transportation Research Part C 14 (2006) 157˜ n174 [26] Gilbert Laport, Yves Nobert, Martin DesrochersOptimal Routing under Capacity and Distance Restrictions. Canada: INFORMS. 1985 ˜ o, Fernando Ciriaco, Leonardo D. Oliveira, [27] Taufik Abra ´lico,Paul Jean E. JeszenskyPseudo-Codes for Bruno A. Ange GA, SA STTS, RTS, 1-opt LS, PSO, and woPSO SIMO MC-CDMA MuDs. Brazil ´sar Branda ˜ o de Oliveira, Germano Crispim [28] Humberto Ce Vasconcelos, Guilherme Bastos Alvarenga Reducing Traveled Distance in the Vehicle Routing Problem with Time Windows using a Multi-Start Simulated Annealing. Canada, Vancouver, 2006 [29] Roulette Wheel Selection Newcastle University Augustus 2011. http: // www. edc. ncl. ac. uk/ highlight/ rhjanuary2007g02. php/

Literatuurlijst

81

Bijlage 1: GUI

Literatuurlijst

82

Optimalisatieplanning voor operationeel beheer van stortklaar beton

Recommend Documents