💻 computer science

A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

Deze studie toont aan dat een Ant Colony Optimisation-benadering die flexibele capaciteitsrestricties incorporeert, een geografische clustering-baseline in een echt Colombiaans inbound logistiek netwerk aanzienlijk overtreft, waarbij substantiële reducties in vlootgrootte, reisafstand en operationele kosten worden bereikt terwijl de voertuigbenutting wordt gemaximaliseerd.

Oorspronkelijke auteurs: Joseph Javier Sánchez Acuña

Gepubliceerd 2026-06-29

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Joseph Javier Sánchez Acuña

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de manager bent van een bezorgbedrijf in Colombia. Je hebt een centraal magazijn in een stad genaamd Guadalajara de Buga, en je moet pakketten ophalen bij 30 verschillende locaties verspreid over het hele land — van kusthavens tot bergdorpen. Je hebt een wagenpark van 10 identieke vrachtwagens, en elke vrachtwagen is officieel geklasseerd om 150 pakketten te kunnen vervoeren.

Echter, je bedrijf heeft een slimme regel: als de wiskunde het perfect uitkomt, kan een vrachtwagen een klein beetje extra meenemen — tot wel 5% meer (ongeveer 157 pakketten) — zonder de wet te overtreden of de vrachtwagen te beschadigen. Dit is jouw "flexibele capaciteit".

Het probleem is dat je huidige systeem voor het plannen van routes, genaamd "Rout Now," een beetje rigide is. Het werkt als een leraar die leerlingen in groepjes verdeelt op basis van wie het dichtst bij elkaar zit (met behulp van een kaart met rechte lijnen). Zodra de groepjes zijn gevormd, stuurt het een vrachtwagen om ze op te halen. Omdat het de groepen vormt op basis van "rechte lijnen" in plaats van "werkelijke wegen," eindigt het er vaak op dat sommige vrachtwagens halfleeg zijn en andere overbeladen, waardoor je gedwongen wordt om alle 10 de vrachtwagens te gebruiken, zelfs wanneer je er slechts 8 nodig zou hebben.

De Nieuwe Oplossing: De "Mierenkolonie"-aanpak

De auteur, Joseph Javier Sánchez Acuña, testte een nieuwe, slimmere manier om deze routes te plannen met behulp van een computerprogramma dat geïnspireerd is op hoe mieren voedsel vinden. Dit wordt Ant Colony Optimisation (ACO) genoemd.

Hier is hoe het artikel het verschil uitlegt met behulp van eenvoudige concepten:

1. De "Rechte Lijn" versus de "Werkelijke Weg"

De Oude Manier (Rout Now): Stel je voor dat je een roadtrip probeert te plannen door rechte lijnen op een stuk papier te tekenen. Je zou kunnen denken dat twee steden dicht bij elkaar liggen omdat ze naast elkaar staan op de kaart. Maar in werkelijkheid moet je, om tussen hen te komen, misschien over een enorme berg rijden of een lange omweg nemen. Het oude systeem negeert de werkelijke wegen en groepeert stops simpelweg op basis van hun locatie op een platte kaart.
De Nieuwe Manier (Mieren): Het nieuwe systeem kijkt naar het werkelijke wegennetwerk (met behulp van een digitale kaart genaamd OpenStreetMap). Het weet dat de "dichtstbijzijnde" stad op een kaart er in werkelijkheid soms het moeilijkst te bereiken is via de weg.

2. De "Inpak"-analogie

De Oude Manier: Het oude systeem probeert de vrachtwagens te vullen door eerst de dichtstbijzijnde buren te pakken. Het is alsof je probeert een koffer in te pakken door de dichtstbijzijnde voorwerpen erin te gooien zonder naar de vorm van de tas te kijken. Je eindigt met gaten en verspilde ruimte, waardoor je een tweede koffer (een tweede vrachtwagen) moet openen, ook al is er nog ruimte in de eerste.
De Nieuwe Manier: Het mierenalgoritme is als een meester-inpakker. Het pakt niet alleen het dichtstbijzijnde item; het kijkt naar de hele koffer. Het vraagt zich af: "Als ik deze zware doos hier neerzet, kan ik die lichtere doos daar dan nog wel kwijt?" Het gebruikt de "flexibele capaciteit" (de 5% extra ruimte) heel zorgvuldig. Het bouwt de route stap voor stap op en controleert constant of de vrachtwagen te vol raakt. Als een vrachtwagen bijna vol is, maar net genoeg ruimte heeft voor nog één stop, neemt de mier deze stop. Zo niet, dan sluit hij die vrachtwagen af en begint hij aan een nieuwe.

3. De Resultaten: Efficiënter Inpakken

De auteur testte dit nieuwe systeem tegen het oude systeem met behulp van echte gegevens van 10 verschillende drukke dagen. Dit is wat er gebeurde, vooral op de drukste dag (Scenario S-3):

Minder Vrachtwagens: Het oude systeem gebruikte alle 10 vrachtwagens. Het nieuwe mierensysteem had slechts 8 vrachtwagens nodig. Dat is een reductie van 20% in het benodigde wagenpark.
Minder Rijden: De vrachtwagens reden 20% minder afstand (wat ongeveer 2.232 kilometer bespaarde).
Geld Bespaard: Omdat ze minder reden en minder vrachtwagens gebruikten, daalden de brandstofkosten met 16%.
Voller Vrachtwagens: Het oude systeem liet vrachtwagens draaien op ongeveer 79% capaciteit (veel lege ruimte). Het nieuwe systeem vulde ze tot 99,5%, wat betekent dat bijna elke centimeter van de vrachtwagen werd benut.

4. Waarom het Werkte (Het "Geheime Recept")

Het artikel betoogt dat de magie niet alleen was dat het nieuwe systeem "slimmer" was in algemene zin. De magie was dat het de flexibele capaciteit (de 5% extra ruimte) op een gecoördineerde manier mocht gebruiken.

Het oude systeem kon dit niet omdat het de vrachtwagens vastlegde in specifieke geografische groepen voordat het überhaupt begon met het plannen van de route. Het was alsof je de groepen vastlegde voordat je de route bepaalde. Het was alsof je probeerde meubels in een kamer te verplaatsen nadat je de muren al had geverfd; de groepen waren immers al vastgesteld. Het mierensysteem bouwde de route en de groep echter tegelijkertijd op. Het kon zeggen: "Deze vrachtwagen is vol, maar als ik deze ene extra stop erin prop en de 5% extra ruimte gebruik, kan ik een volledige vrachtwagen besparen."

De Kern van het Verhaal

De studie bewijst dat voor een logistiek bedrijf in een gebied met lastige wegen (zoals de bergen van Colombia), het gebruik van een door biologie geïnspireerd computerprogramma (Ant Colony Optimisation) dat rekening houdt met werkelijke wegafstanden en flexibele laadregels gebruikt, aanzienlijk beter is dan de oude methode van groeperen op basis van de afstand in een rechte lijn.

De auteur concludeert dat dit geen gelukstreffer is; de resultaten zijn 20 keer per scenario getest en bleken statistisch significant. De nieuwe methode bespaart geld, bespaart brandstof en vermindert het aantal benodigde vrachtwagens, alles door de "koffers" (vrachtwagens) intelligenter in te pakken.

Technische Samenvatting: Een Metaheuristische Oplossing voor het Capacitated Vehicle Routing Problem

1. Probleemdefinitie en Context
De studie behandelt een reëel Capacitated Vehicle Routing Problem (CVRP) dat voortvloeit uit een inbound operatie voor de inzameling van grondstoffen in Colombia. Het logistieke netwerk bestaat uit een centraal depot in Guadalajara de Buga (Valle del Cauca) dat dertig distributiecentra bedient, verspreid over diverse Colombiaanse regio's (kusten, het Andesgebergte en industriële zones). De operatie wordt geconfronteerd met variabele vraagcycli (643 tot 1.192 pakketten per cyclus) en maakt gebruik van een homogene vloot van tien Foton FRR Cummins vrachtwagens.

Een cruciale operationele beperking is het flexibele capaciteitsbeleid: hoewel de nominale voertuigcapaciteit $Q = 150$ pakketten is, staat het bedrijfsbeleid een gecontroleerde overbelasting van 5% toe, wat een effectieve planningscapaciteit van $Q_{eff} = 157,5$ pakketten tot gevolg heeft. De routing moet worden uitgevoerd over niet-Euclidische wegennetwerken afgeleid van OpenStreetMap (via OSMnx), waarbij topologische complexiteiten (bergcorridors, eenrichtingsverkeer) een significante asymmetrie creëren tussen Euclidische afstanden en werkelijke reiskosten.

Het huidige planningssysteem, "Rout Now", hanteert een "cluster-first, route-second" architectuur: het verdeelt knooppunten in 10 geografische clusters met behulp van k-means (gebaseerd op platte coördinaten) en sequentieert vervolgens elk cluster onafhankelijk met behulp van Simulated Annealing (SA). Deze aanpak resulteert in heterogene vlootbenutting (35%–90%) en zet systematisch alle 10 voertuigen in, zelfs wanneer theoretische ondergrenzen suggereren dat 6–8 voertuigen zouden volstaan.

2. Methodologie
Het onderzoek stelt een Ant Colony Optimisation (ACO) metaheuristiek voor en evalueert deze, ontworpen om te opereren op de volledige graaf van actieve knooppunten zonder voorafgaande geografische partitionering.

Wiskundige Formulering: Het probleem wordt gemodelleerd als een Mixed-Integer Linear Programme (MILP) met behulp van de Miller–Tucker–Zemlin formulering voor subtour-eliminatie. De capaciteitsbeperking wordt expliciet versoepeld naar $Q_{eff} = 157,5$ om het overbeladingsbeleid binnen de optimalisatielogica te modelleren.
ACO Architectuur:
- Constructie: Mieren construeren iteratief routes met meerdere voertuigen. Een belangrijk onderscheidend kenmerk is het dynamische maskeringmechanisme: de verzameling haalbare volgende knooppunten ( $F_k$ ) wordt in realtime gefilterd om te garanderen dat de geaccumuleerde lading $Q_{eff}$ niet overschrijdt. Dit stelt het algoritme in staat om knooppunten efficiënt te "verpakken", waarbij de 5% marge alleen wordt benut wanneer dit nodig is om een nieuwe route te voorkomen.
- Transitie-waarschijnlijkheid: De waarschijnlijkheid van het selecteren van een knooppunt hangt af van feromoonsporen ( $\tau$ ) en heuristische zichtbaarheid ( $\eta = 1/C_{ij}$ ). Gezien de hoge variantie in Colombiaanse wegkosten (47% standaarddeviatie ten opzichte van het gemiddelde), werd het heuristische gewicht ( $\beta = 2,0$ ) gekalibreerd om het feromoongewicht ( $\alpha = 1,0$ ) te domineren, waarbij de prioriteit ligt op directe kostenefficiëntie.
- Update-mechanisme: Standaard verdampings- en depositieregels zijn van toepassing, waarbij bogen die bijdragen aan oplossingen met lage kosten en hoge consolidatie worden versterkt.
Experimenteel Ontwerp:
- Scenario's: Tien verschillende operationele scenario's (S-1 tot S-10), die een volledige maand aan planningscycli vertegenwoordigen, zijn geëxtraheerd uit echte bedrijfsgegevens.
- Herhaling: Elk scenario werd 20 keer onafhankelijk uitgevoerd met verschillende willekeurige seeds om de stochastische variantie te isoleren.
- Baseline Vergelijking: De ACO-resultaten werden vergeleken met de "Rout Now" baseline (k-means + SA) met gebruik van identieke OSMnx afstandmatrices om de interne validiteit te waarborgen.
- Statistische Validatie: De non-parametrische Wilcoxon signed-rank test werd toegepast op de gemiddelde totale afstanden van de 20 runs per scenario om de statistische significantie te testen.

3. Belangrijkste Resultaten
De ACO-benadering vertoonde systematische en statistisch significante verbeteringen ten opzichte van de baseline in alle tien de scenario's:

Vlootreductie: In het scenario met de hoogste vraag (S-3; 1.192 pakketten) reduceerde de ACO de actieve vloot van 10 voertuigen (baseline) naar 8 voertuigen, wat overeenkomt met de theoretische ondergrens ( $\lceil 1192/157,5 \rceil = 8$ ). Over alle scenario's heen werd de actieve vloot met ongeveer 20% verminderd.
Afstand en Kosten:
- Totale Afstand: Verminderd met gemiddeld 20,05% (variërend van 19,97% tot 20,25%). In S-3 daalde de afstand van 11.023 km naar 8.790,5 km.
- Brandstofkosten: Geschatte besparingen van 16,05% in het kritieke scenario (ongeveer 941.340 COP per cyclus).
- Operationele Tijd: Verminderd met 20,02%.
Capaciteitsbenutting: De ACO bereikte bijna perfecte consolidatie, waarbij de gemiddelde capaciteitsbenutting steeg van ~79,47% (baseline) naar 99,50% in S-3. Routes in de ACO-oplossing opereerden tussen 96% en 101% van de nominale capaciteit, waarbij specifieke routes de 5% overbeladingsmarge gebruikten om de noodzaak voor een negende voertuig te voorkomen.
Statistische Significantie: De Wilcoxon signed-rank test leverde een statistiek op van $W=0$ (alle verschillen bevoordeelden ACO) met een p-waarde $< 0,01$ , waarmee de nulhypothese van mediane gelijkheid werd verworpen en de robuustheid van de verbeteringen werd bevestigd.

4. Betekenis en Bijdragen
Het artikel claimt drie primaire wetenschappelijke bijdragen:

Empirische Evaluatie van Flexibele Beperkingen: Het documenteert hoe het expliciet modelleren van een flexibele capaciteitsbeperking ( $Q_{eff}$ ) binnen een constructieve metaheuristiek zorgt voor gecoördineerde lastconsolidatie die structureel onmogelijk is voor pre-partitioneringsarchitecturen. De studie toont aan dat de 5% tolerantie niet louter een veiligheidsbuffer is, maar een strategische hefboom voor vlootreductie wanneer deze dynamisch wordt beheerd.
Robuustheid in Real-World Topologie: Het werk levert bewijs dat bio-geïnspireerde metaheuristieken (specifiek ACO) klassieke "cluster-first, route-second" heuristieken in complexe, niet-Euclidische wegennetwerken overtreffen. De studie benadrukt dat geografische pre-partitionering (k-means) geen rekening houdt met de asymmetrieën in het wegennetwerk, terwijl ACO opereert in de ware kostenruimte.
Identificatie van het Causale Mechanisme: Het artikel identificeert de "dynamische maskering" van onhaalbare knooppunten tijdens de routeconstructie als het causale mechanisme voor succes. Dit stelt het algoritme in staat om een "efficiënte verpakking" van de vraag uit te voeren, waarbij de overbeladingsmarge organisch wordt benut om het aantal routes te minimaliseren, een capaciteit die ontbreekt in de baseline's vaste geografische clusters.

5. Beperkingen en Toekomstig Werk
De auteurs merken op dat de studie beperkt is tot een specifieke industriële context zonder tijdvensters (VRPTW) of beperkingen op de werktijd van chauffeurs. Voorgestelde richtingen voor toekomstig onderzoek zijn:

Het uitbreiden van het model naar VRPTW om ontvangstschema's te integreren.
Het adresseren van vraagonzekerheid via Stochastic VRP (SVRP).
Het ontwikkelen van multi-objective formuleringen (bijv. het minimaliseren van CO₂-emissies) met behulp van evolutionaire algoritmen.
Het integreren van de ACO-kern als een microservice voor gecontroleerde A/B-testen binnen bestaande logistieke systemen.