C.D. Noorlander
Ritplanning kledinginzameling
Literatuuropdracht/computeropdracht,
Rapport 2005.TL.6948, Sectie Transporttechniek en Logistieke Techniek.
Stichting Kledinginzameling Charitatieve Instellingen (KICI) is een
non-profit organisatie die gebruikte kleding inzamelt. Door het hele land
staan op verschillende locaties containers waar men kleding in
kan werpen. Deze kledingcontainers worden geleegd door middel van een
kraanwagen (zoals bij glasbakken) of door de vuilniszakken met kleding met
de hand naar bestelbus te brengen. De opgehaalde kleding wordt afgeleverd
bij een afnemer, die KICI een bepaald bedrag per kilogram kleding vergoed.
Het verschil tussen kosten en baten wordt gedoneerd aan goede doelen.
Voor het verlagen van kosten wil KICI een efficiëntere logistiek behalen
door middel van verbeterde routes. Het gaat hier om de routes die
een vrachtwagen of bestelbus moet rijden. Voor het berekenen van
verbeterde routes is gebruik gemaakt van een computerprogramma.
Voor het te ontwerpen programma is een pakket van eisen opgesteld. Omdat
gekozen is voor een computerprogramma is er nog een extra doelstelling
geformuleerd. De extra doelstelling is dat het programma gebruikt
kan worden als hulp voor het maken van investeringsbeslissingen. Dit wordt
gedaan door uitkomsten uit het programma van verschillende scenario's
(zoals rijden met of zonder aanhanger) met elkaar te vergelijken. Daarom
is het belangrijk dat in het programma parameters (zoals leegtijd, lostijd
en kosten per uur) gewijzigd kunnen worden en dat het programma ruimte
biedt voor het optimaliseren van verschillende scenario's.
Het berekenen van betere oplossingen wordt gedaan door middel van een
algoritme (rekenmethode). Om betere routes te krijgen, heeft het algoritme een
aantal gegevens nodig. Naast de gegevens van de locaties, zoals het aantal
containers en de gemiddelde massa per lediging, zijn ook de afstanden en
rijtijden tussen de locaties, afnemers en vertrekpunten nodig. De tabel met
afstanden en rijtijden wordt de Herkomst-Bestemmingsmatrix (HB-matrix) genoemd.
Het totaal aan gegevens vormt de netwerkgegevens.
Voor het berekenen van de HB-matrix is gebruik gemaakt van het programma
MapPoint. Dit programma is een routeplanner van Microsoft met een lage
aanschafprijs en is eenvoudig te koppelen aan het programma Microsoft
Excel. Deze koppeling verloopt via de programmeertaal Visual Basic
Scripting (VB) dat standaard in Excel is inbegrepen. MapPoint heeft
parameters die gewijzigd kunnen worden, zoals de gemiddelde snelheden van
het voertuig. Er is gebruik gemaakt van de gemiddelde snelheden van een
vrachtwagen, zoals die algemeen worden gebruikt in professionele
routeringsprogrammas.
Voor het generen van de benodigde gegevens is een aantal functies ontwikkeld
in VB en als macro's toegevoegd aan een Excel-bestand. Voor het berekenen van
de HB-matrix worden de locaties per paar ingevoerd in MapPoint die daarna de
optimale afstand en rijtijd bepaalt. De verkregen HB-matrices en de informatie
van de locaties, afnemers en vertrekpunten worden door het programma
weggeschreven als simpele tekstbestanden, die door het algoritme ingelezen
zullen worden.
In de literatuur wordt het probleem, waarbij een vloot aan voertuigen een
aantal locaties moet bezoeken, omschreven als het Vehicle Routing Problem
(VRP). Het VRP is een combinatie van het Traveling Salesman problem (TSP)
en het Bin Packing Problem (BPP). Het TSP is een probleem waarbij een
handelsreiziger een aantal steden bezoeken in een optimale volgorde. Bij
het BPP wordt er gezocht naar een optimale indeling van een container. Het
VRP kent een aantal standaard geformuleerde randvoorwaarden.
Het gebruikte model is een vereenvoudigde weergave van de realiteit en
omgezet naar een VRP, met behulp van de uit de literatuur bekende
randvoorwaarden. Het model gaat uit van een routeplanning voor een week.
In het model begint een chauffeur bij een depot, rijdt daarna naar een
aantal locaties en zal voor het terugrijden naar het depot zijn lading
lossen bij een afnemer. Het aantal beschikbare voertuigen is onbeperkt en
de capaciteit van de voertuigen is gelijk. Als een container tweemaal per
week wordt geleegd, moet het verschil in dagen twee zijn. In het model is
geen rekening gehouden met het feit dat de chauffeurs tussendoor lossen,
routes beginnen bij afnemers, containers overslaan en teruggaan naar een
depot met lading.
Zou er gekozen worden voor een exact algoritme om het model op te lossen,
dan zou de rekentijd groot zijn. Daarom is gekozen voor metaheuristiek.
Dit zijn rekenmethodes die, met het beperken van het aantal stappen, zich
richten op een veelbelovend gebied in de oplossingsruimte, om zo een goede
oplossing te vinden. Er zijn drie bekende metaheuristieken, namelijk het
Genetic Algorithm, Simulated Annealing en Tabu Seach. Er is gekozen voor
Simulated Annealing (SA), omdat uit literatuur blijkt dat SA het meest
geschikt is voor het VRP wanneer er ruimte is voor grotere rekentijd.
SA is een algoritme wat zijn oorsprong vindt in het afschrikken en uitgloeien
staal. Bij het uitgloeien wordt het staal opgewarmd en langzaam afgekoeld,
om zo een verbeterde verdeling van de kristallen in het staal te bereiken.
Bij het omzetten van het uitgloeien naar een minimalisatie probleem wordt
de energiefunctie veranderd in de kostenfunctie. Door gebruik te maken
van een kansfunctie bij het nemen van beslissingen voor wijzigingen, kan
het algoritme uit een lokaal minimum komen. Deze kansfunctie is
afhankelijk van de temperatuur en naarmate de temperatuur daalt, wordt de
kans dat een wijziging die geen verbetering biedt wordt aangenomen
steeds kleiner.
Het algoritme SA gaat uit van een huidige oplossing (beginwaarde). Vanuit
de huidige oplossing wordt een nieuwe oplossing gevormd. Bij het vormen
van een nieuwe oplossing is het belangrijk dat veranderingen niet te groot
zijn. Is deze nieuwe oplossing beter dan de huidige oplossing, dan wordt
de huidige oplossing de nieuwe oplossing. Als dit een aantal keer is
gedaan, dan wordt de temperatuur verlaagd. Het algoritme stopt wanneer de
minimumtemperatuur is bereikt.
Het algoritme is geïmplementeerd in de programmeertaal Delphi. Voor het
vormen van een beginwaarde zijn er drie mogelijkheden, namelijk het inlezen
van een routeplanning, het willekeurig vormen van een routeplanning of het
willekeurige vormen van een routeplannin,g rekeninghoudend met de maximale
afname van een afnemer.
Bij het aanmaken van de nieuwe oplossing, zijn er vier mogelijke wijzigingen
die uitgevoerd worden. De eerste is het wisselen van een locatie uit een route
met een locatie uit een andere route. De tweede wijziging is het verplaatsen
van locaties uit een route naar een andere route en de derde is het
samenvoegen van twee routes tot een route. De laatste wijziging is het
wisselen van de afnemer en het vertrekpunt uit een route met een andere
locatie uit de lijst van beschikbare afnemers en vertrekpunten. Binnen het p
rogramma zit de mogelijkheid om de vier procedures wel of niet te gebruiken.
De netwerkgegevens en het algoritme zijn gevalideerd en geverifieerd. Er
is geconstateerd dat het algoritme en de koppeling van Excel en MapPoint
geen fouten maken. De validatie van de resultaten met de werkelijkheid is
niet eenvoudig. Dit probleem wordt veroorzaakt door de vereenvoudigingen
in het model en het feit dat de chauffeurs de geplande route niet volgen.
Met behulp van de gegevens die KICI heeft over de routes, is er naar gestreefd
om een goede vergelijking te maken. De gegevens van de routeplanning van KICI
die volgen uit het ontwikkelde programma, dat gebruik maakt van de
netwerkgegevens uit MapPoint, zijn vergeleken met de metingen van KICI. Voor
een goede vergelijking zijn de metingen gecorrigeerd naar het model. Er is
niet met grote zekerheid vast te stellen of de gebruikte HB-matrices en de
waarde voor de lostijd en leegtijd een goede weergave zijn van de praktijk.
Route 5011 van KICI komt in uitvoering het beste overeen met de planning. Er
is gekozen om de gebruikte netwerkgegevens verder te gebruiken, omdat de
rijtijd van route 5011 na correctie zo goed als gelijk is met de rijtijd van
de planning.
Met het optimalisatieprogramma zijn een tweetal scenario's onderzocht. Hiervoor
zijn de gegevens van de maand november 2004 gebruikt. Het gaat hier om de
locaties met de gemiddelde massa per lediging en de frequentie per week, bepaald
door metingen uit de maand november 2004. Naast een willekeurige beginwaarde
is ook de planning van KICI van november 2004 gebruikt. Wanneer de totale
operationele kosten van de planning van KICI voor de maand november worden
vergeleken met de resultaten van het programma, met als instelling het rijden
zonder aanhanger, dan is er een kostenreductie te zien 13%. De weekplanning na
optimalisatie met als instelling het rijden met aanhanger kost 34% minder
dan de planning van KICI.
In beide gevallen is uitgegaan van de mogelijkheid dat de afnemer en
vertrekpunt geoptimaliseerd mogen worden. Met de KICI-planning als
beginwaarde en de afnemers en vertrekpunten vast, levert het programma na
optimalisatie een verbetering van 6%.
Wordt de capaciteit van de locaties uitgebreid door het bijplaatsen van
extra containers, waardoor het mogelijk is om elke container maar
één keer per week te legen, dan betekent dit een kostenvoordeel
van 20% ten opzichte van de KICI planning.
Wordt het algoritme de ruimte gegeven alles te optimaliseren, waaronder
ook de afnemers, dan is in de resultaten te zien dat twee afnemers niet
worden gebruikt. Het is mogelijk om een beginwaarde te genereren die
rekening houdt met de maximale afname van de afnemers. Wordt met deze
beginwaarde een optimalisatie uitgevoerd, waarbij de afnemers en
vertrekpunten gefixeerd zijn, dan volgt als resultaat een goede verdeling
van opgehaalde kleding over de afnemers.
De conclusie is dat het programma de gewenste functionaliteit heeft en het
mogelijk maakt verschillende scenario's te analyseren. Het algoritme levert
een betere routeplanning dan de huidige planning van KICI in de maand november
2004.
Wanneer de uitkomsten van het eerste scenario worden geëvalueerd, kan
er worden geconcludeerd dat het rijden met aanhanger, in de maand november 2004,
een kostenbesparing geeft. Wel is hierbij de vraag of de chauffeurs meer dan
8,5 uur willen rijden. Het eenmaal per week legen van de containers geeft niet
een duidelijke kostenbesparing, aangezien er een groot aantal containers
bijgeplaatst moet worden.
Het gebruikte model is een vereenvoudiging van de realiteit. De
routeplanning die volgt uit het programma zal niet direct geschikt zijn
als toepassing. Wel kan het programma meer duidelijkheid geven over wat de
invloed is van een wijziging en hierdoor kan het programma als hulp dienen
voor het maken van investeringsbeslissingen.
Er zijn drie groepen aanbevelingen naar aanleiding van het inzicht dat is
verkregen tijdens het ontwikkelen van het programma. De eerste groep
aanbevelingen gaat over het wijzigen van het gebruikte model, zoals het
toevoegen van kosten voor overuren en het rekening houden met rustpauze.
De tweede aanbeveling is de validatie te verbeteren door uitvoer van
simulatie of door de resultaten uit het programma daadwerkelijk toe te
passen. De laatste aanbevelingen gaan over de technische verbeteringen
voor het programma, zoals het toevoegen van foutcontrole.
Rapporten studenten Transporttechniek en Logistieke Techniek
Gewijzigd: 2005.06.19;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.