Van hazenpad naar snelweg: routeplanning voor firma Happy Easter

Routeplanning & firma Happy Easter

Routeplanning is een proces waarbij de meest efficiënte route voor een voertuig wordt bepaald aan de hand van het aantal bestemmingen én alle externe factoren die van invloed zijn tijdens de reis. Dit houdt in dat we een doelfunctie hebben – bijvoorbeeld het minimaliseren van de afstand of reistijd – en een set aan formules die de restricties voor de externe factoren wiskundig omschrijven. Firma Happy Easter heeft dit jaar veel klanten die zich op verschillende plekken in het land bevinden. Een overzicht van het land is weergegeven in het figuur hieronder. Firma Happy Easter bevindt zich met haar kudde Paashazen in het midden van het land en de klanten zijn weergegeven met rode cirkels en cijfers.

Een viertal hazen is opgetrommeld om de eieren voor de Paasdagen bij de mensen (13 klanten) te bezorgen. Welke route moet ieder van deze vier hazen bewandelen om de eieren te bezorgen zodat de afstanden zo klein mogelijk zijn? En hoe lossen we daardoor dit zogenoemde voertuigrouteringsprobleem op?
 

De afstandenmatrix en routeplanning

We beginnen met het berekenen van de afstand tussen ieder van de locaties, dit noemen we ook wel een afstandenmatrix. Deze afstanden worden vervolgens gebruikt om paasei-ritjes te combineren tot een efficiënt en uitvoerbaar plan. Bekend zijn de volgende gegevens:

• De horizontale afstand van ieder vakje is 2 kilometer, de verticale afstand is 1 kilometer.
• De hazen mogen zich niet diagonaal voortbewegen. Door middel van deze regels kunnen we de afstanden tussen ieder van de locaties berekenen. Als voorbeeld: de afstand tussen punt 1 en 7 is 5 kilometer (2 horizontaal en 1 verticaal). De afstand tussen klanten 6 en 11 is 3 kilometer.

Daarmee kunnen we een tabel maken met daarin vanuit elke locatie naar alle andere locaties de bijbehorende afstand. In dit voorbeeld met slechts een aantal locaties is dit goed te doen. Wanneer we echter 5000 locaties moeten bezoeken, dan heb je al snel 5000 x 5000 = 25.000.000 routeafstanden nodig! Bij CQM hebben we gelukkig onze eigen optimalisatiesoftware, genaamd CQMaps, waarmee onderlinge afstanden tussen een grote verzameling adressen in slechts enkele minuten berekend kunnen worden. Daarmee losten we al eerder het grootste handelsreizigersprobleem ter wereld op.
 

Routeplanning & het minimaliseren van de afstand

De volgende stap is het minimaliseren van de afstand van de routes, rekening houdend met het aantal eieren die de Paashazen in hun mandje kunnen dragen. Met de hand zou je hiermee aan de slag kunnen gaan door:

1. een viertal logisch uitziende routes te maken waarin de locaties met elkaar verbonden zijn

en

ii. de totale afstand te berekenen en dit te vergelijken met eventueel andere op het oog goed uitziende alternatieven.

Naarmate een probleem alsmaar groter en complexer wordt komt er een ‘solver’ in het spel. Dit is een stukje wiskundige software met rekenregels waarmee routeringsproblemen op een slimme manier kunnen worden opgelost. De solver rekent in dit geval voor ons uit wat de kortste routes zijn die we moeten afleggen om alle paaseieren te bezorgen, gegeven de capaciteit van de mandjes van de Paashazen. Heb jij de oplossing in onderstaande tabel ook kunnen vinden?

De afstanden van de individuele routes is 24 kilometer voor de haas die de klanten in het vlak linksboven voor zijn rekening neemt, 16 kilometer voor de haas die de paaseieren linksonder bezorgt, 24 kilometer voor de haas rechtsboven en 20 kilometer voor de laatste haas (rechtsonder).
 

Routeplanning in de praktijk

In de praktijk zijn er echter veel restricties waar Happy Easter met zijn kudde Paashazen rekening mee moeten houden:

• Capaciteitsrestrictie - In het mandje van ieder van de hazen passen slechts 10 eieren. Daarnaast mogen ze maximaal 6 uur per dag eieren bezorgen en mogen ze iedere twee uur van vers hooi en chocolade-eieren genieten. Door deze restricties kan de uiteindelijke oplossing veranderen.

• Tijdvensters - De klanten kunnen aan Happy Easter een tijd voor bezorging meegeven. Om te zorgen dat de mensen wel thuis aanwezig zijn tijdens het bezorgen van de paaseieren zorgt de firma ervoor dat de Paashaas maximaal een kwartiertje eerder of later voor de deur staat.
   
• Verschillende producten - Er zijn twee soorten paaseieren, rode en gele eieren. De rode eieren zijn twee keer zo groot als de gele eieren. Dit beïnvloedt het aantal eieren dat in het mandje passen.
   

Routeplanning bij CQM

Door rekening te houden met bovenstaande restricties verandert het simpele voorbeeld al snel in een complexe optimalisatiepuzzel. Daarnaast hebben we in de praktijk niet te maken met vier hazen en dertien klanten, maar met vele klanten en transportbewegingen.

Hoe bepaal je dan wat een optimaal transportplan is? En welke routes je het beste kunt kiezen? Bij CQM werken we al jaren aan dit soort vraagstukken waar veel routeberekeningen nodig zijn. Dit maakt automatische transportplanning mogelijk. Voorbeelden van projecten: Transvision, Den Hartogh, DHL en Heisterkamp. We gebruiken hiervoor regelmatig CQMaps, onze eigen software in automatische routeplanning.

Wil jij ook met routeplanning aan de slag?

Neem dan contact op met Arjen. Volg ons daarnaast op LinkedIn of meld je aan voor onze digitale nieuwsbrief. 

Fotocredit: Pixabay.