Een model voor het genereren van een
routeplanning voor chauffeurs
Auteurs Max Santosa en Quico van den Berg
Studentnummers 17085241 en 17093910
Docent Mevrouw MacDuff
Datum 28 november 2021
,Voorwoord
Voor u ligt het eindrapport “Een model voor het genereren van een routeplanning voor chauffeurs”.
Dit rapport is geschreven in het kader van het project modelleren van de opleiding Toegepaste
Wiskunde aan De Haagse Hogeschool in Delft. Het onderzoek is uitgevoerd in opdracht van PostNL in
de periode van september 2021 tot en met november 2021. Graag willen we onze begeleidster
mevrouw MacDuff bedanken voor de inhoudelijke ondersteuning gedurende het onderzoek.
Wij wensen u veel leesplezier toe bij het lezen van dit rapport.
Max Santosa en Quico van den Berg
Den Haag, 28 november 2021
2
, Samenvatting
PostNL is een Nederlands postbedrijf dat zich vooral bezighoudt met het bezorgen en ophalen van
pakketten bij klanten in de Benelux. Het bezorgen en ophalen van pakketten gebeurt elke werkdag.
PostNL probeert voor elke werkdag een betrouwbare routeplanning voor haar chauffeurs te maken,
waarbij de benodigde kosten zo laag mogelijk zijn. Het doel van dit onderzoek is het genereren van
een routeplanning voor één werkdag waarmee PostNL dit bereikt. De werkwijze van het onderzoek is
bepaald aan de hand van de volgende hoofdvraag: “Met welke routeplanning kunnen PostNL-
chauffeurs pakketten bezorgen en ophalen zodat de totale kosten geminimaliseerd worden?”
Ten eerste is onderzocht welke factoren invloed hebben op het genereren van een toelaatbare
routeplanning. Hierbij is de dataset van PostNL nader geanalyseerd. Hieruit volgt dat de volgende
factoren belangrijk zijn voor het genereren van de routeplanning: de totale werktijd van de
chauffeurs, de totaal afgelegde afstand van de wagens, het aantal wagens, de tijdsvensters en de
gewichten van de pakketten.
Ten tweede is uitgezocht welke wiskundige modellen in de literatuur aansluiten op het probleem. Dit
is uitgevoerd om te bepalen op welke wijze de routeplanning tot stand kan komen. Uit het
literatuuronderzoek zijn drie modellen gevonden: tabu search, simulated annealing en route
eliminatie algoritme. Deze modellen zijn beoordeeld aan de hand van vooraf opgestelde criteria.
Hieruit blijkt dat het route eliminatie algoritme het best past bij de probleemstelling. Daarom is voor
dit model gekozen om te implementeren.
Ten derde is een methode gezocht om een toelaatbare routeplanning te genereren voor het
verkrijgen van een startoplossing. Dit is gedaan, omdat vanuit PostNL geen huidige routeplanning
aangeleverd is. Daarnaast hanteerde het gekozen model een slechte startoplossing. Uiteindelijk is
een eigen methode bedacht voor het verkrijgen van een routeplanning. De startoplossing probeert
een vooraf gesorteerde lijst pakketten zo snel mogelijk toe te wijzen aan een wagen. Het resultaat
hiervan is een routeplanning met kosten € 6858,48.
Ten vierde is een model geïmplementeerd op basis van het route eliminatie algoritme om de
startoplossing te optimaliseren. De werking van het model is het minimaliseren van het aantal
wagens in de startoplossing. Het model kiest willekeurig een combinatie van wagens. Van beide
wagens wordt geprobeerd de bijbehorende pakketten in één wagen te plaatsen. Na het verkrijgen
van een nieuwe oplossing, wordt gekeken of de nieuwe oplossing geaccepteerd wordt. Het resultaat
van de eindoplossing is een routeplanning met kosten variërend tussen € 6400 en € 6800.
Na afronding van het onderzoek zijn sterke en zwakke punten van het onderzoek geanalyseerd. Een
sterk punt van het programma is dat de gehanteerde codestructuur te gebruiken is voor het inlezen
van andere datasets. Hiermee kan voor een andere dataset een routeplanning gegenereerd en
geoptimaliseerd worden. Echter is de gebruiksvriendelijkheid van het programma vrij laag en kan het
algoritme tijdens het optimaliseren vast blijven zitten in een lokaal minimum. Helaas kunnen de
resultaten uit het onderzoek niet vergeleken worden met de huidige situatie van PostNL, omdat er
geen recente routeplanning gegeven is.
Tot slot zijn er een aantal aanbevelingen gegeven aan PostNL voor het genereren van toekomstige
routeplanningen en potentiële vervolgonderzoeken. Zo wordt er sterk aangeraden om in de
gebruikte datasets van PostNL pakketten voor te sorteren om snel een startoplossing te generen
tegen lage kosten. Verder wordt er gesuggereerd om het model te gebruiken voor het optimaliseren
van routeplanningen als de huidige datastructuur gehanteerd blijft. Vervolgonderzoeken die zouden
kunnen leiden tot verdere vermindering van de totale kosten zijn het groeperen van pakketten op
postcode en het inzetten van meerdere chauffeurs voor een wagen.
3
routeplanning voor chauffeurs
Auteurs Max Santosa en Quico van den Berg
Studentnummers 17085241 en 17093910
Docent Mevrouw MacDuff
Datum 28 november 2021
,Voorwoord
Voor u ligt het eindrapport “Een model voor het genereren van een routeplanning voor chauffeurs”.
Dit rapport is geschreven in het kader van het project modelleren van de opleiding Toegepaste
Wiskunde aan De Haagse Hogeschool in Delft. Het onderzoek is uitgevoerd in opdracht van PostNL in
de periode van september 2021 tot en met november 2021. Graag willen we onze begeleidster
mevrouw MacDuff bedanken voor de inhoudelijke ondersteuning gedurende het onderzoek.
Wij wensen u veel leesplezier toe bij het lezen van dit rapport.
Max Santosa en Quico van den Berg
Den Haag, 28 november 2021
2
, Samenvatting
PostNL is een Nederlands postbedrijf dat zich vooral bezighoudt met het bezorgen en ophalen van
pakketten bij klanten in de Benelux. Het bezorgen en ophalen van pakketten gebeurt elke werkdag.
PostNL probeert voor elke werkdag een betrouwbare routeplanning voor haar chauffeurs te maken,
waarbij de benodigde kosten zo laag mogelijk zijn. Het doel van dit onderzoek is het genereren van
een routeplanning voor één werkdag waarmee PostNL dit bereikt. De werkwijze van het onderzoek is
bepaald aan de hand van de volgende hoofdvraag: “Met welke routeplanning kunnen PostNL-
chauffeurs pakketten bezorgen en ophalen zodat de totale kosten geminimaliseerd worden?”
Ten eerste is onderzocht welke factoren invloed hebben op het genereren van een toelaatbare
routeplanning. Hierbij is de dataset van PostNL nader geanalyseerd. Hieruit volgt dat de volgende
factoren belangrijk zijn voor het genereren van de routeplanning: de totale werktijd van de
chauffeurs, de totaal afgelegde afstand van de wagens, het aantal wagens, de tijdsvensters en de
gewichten van de pakketten.
Ten tweede is uitgezocht welke wiskundige modellen in de literatuur aansluiten op het probleem. Dit
is uitgevoerd om te bepalen op welke wijze de routeplanning tot stand kan komen. Uit het
literatuuronderzoek zijn drie modellen gevonden: tabu search, simulated annealing en route
eliminatie algoritme. Deze modellen zijn beoordeeld aan de hand van vooraf opgestelde criteria.
Hieruit blijkt dat het route eliminatie algoritme het best past bij de probleemstelling. Daarom is voor
dit model gekozen om te implementeren.
Ten derde is een methode gezocht om een toelaatbare routeplanning te genereren voor het
verkrijgen van een startoplossing. Dit is gedaan, omdat vanuit PostNL geen huidige routeplanning
aangeleverd is. Daarnaast hanteerde het gekozen model een slechte startoplossing. Uiteindelijk is
een eigen methode bedacht voor het verkrijgen van een routeplanning. De startoplossing probeert
een vooraf gesorteerde lijst pakketten zo snel mogelijk toe te wijzen aan een wagen. Het resultaat
hiervan is een routeplanning met kosten € 6858,48.
Ten vierde is een model geïmplementeerd op basis van het route eliminatie algoritme om de
startoplossing te optimaliseren. De werking van het model is het minimaliseren van het aantal
wagens in de startoplossing. Het model kiest willekeurig een combinatie van wagens. Van beide
wagens wordt geprobeerd de bijbehorende pakketten in één wagen te plaatsen. Na het verkrijgen
van een nieuwe oplossing, wordt gekeken of de nieuwe oplossing geaccepteerd wordt. Het resultaat
van de eindoplossing is een routeplanning met kosten variërend tussen € 6400 en € 6800.
Na afronding van het onderzoek zijn sterke en zwakke punten van het onderzoek geanalyseerd. Een
sterk punt van het programma is dat de gehanteerde codestructuur te gebruiken is voor het inlezen
van andere datasets. Hiermee kan voor een andere dataset een routeplanning gegenereerd en
geoptimaliseerd worden. Echter is de gebruiksvriendelijkheid van het programma vrij laag en kan het
algoritme tijdens het optimaliseren vast blijven zitten in een lokaal minimum. Helaas kunnen de
resultaten uit het onderzoek niet vergeleken worden met de huidige situatie van PostNL, omdat er
geen recente routeplanning gegeven is.
Tot slot zijn er een aantal aanbevelingen gegeven aan PostNL voor het genereren van toekomstige
routeplanningen en potentiële vervolgonderzoeken. Zo wordt er sterk aangeraden om in de
gebruikte datasets van PostNL pakketten voor te sorteren om snel een startoplossing te generen
tegen lage kosten. Verder wordt er gesuggereerd om het model te gebruiken voor het optimaliseren
van routeplanningen als de huidige datastructuur gehanteerd blijft. Vervolgonderzoeken die zouden
kunnen leiden tot verdere vermindering van de totale kosten zijn het groeperen van pakketten op
postcode en het inzetten van meerdere chauffeurs voor een wagen.
3
