💻 computer science

A Hybrid Metaheuristic for the Family Capacitated Vehicle Routing Problem

Dit artikel introduceert ILS+SP, een hybride metaheuristiek die Iterated Local Search combineert met Set Partitioning post-optimalisatie, die de bestaande state-of-the-art methoden voor het oplossen van het Family Capacitated Vehicle Routing Problem aanzienlijk overtreft door bijna optimale oplossingen te bereiken op grootschalige benchmark-instanties.

Oorspronkelijke auteurs: Bruno Oliveira, Diogo Lima, Marcos Roboredo

Gepubliceerd 2026-07-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Bruno Oliveira, Diogo Lima, Marcos Roboredo

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. Je hebt een vloot identieke vrachtwagens, die allemaal vertrekken vanuit een centraal magazijn. Jouw taak is om pakketjes te bezorgen bij verschillende klanten.

Maar hier is de twist: je klanten zijn niet alleen individuen; ze zijn georganiseerd in families. Bijvoorbeeld, de "familie Smith" heeft vijf huizen in verschillende straten, maar jouw contract vereist dat je slechts naar twee van die huizen rijdt. De "familie Garcia" heeft drie huizen, maar je hoeft er slechts naar één te gaan.

Dit is het Family Capacitated Vehicle Routing Problem (F-CVRP). Het is een enorm puzzelwerk met twee belangrijke regels:

De Familie-regel: Je moet exact het aantal huizen bezoeken dat voor elke familie vereist is, maar je mag zelf kiezen welke specifieke huizen je bezoekt.
De Vrachtwagen-regel: Elke vrachtwagen heeft een gewichtslimiet (capaciteit). Je mag ze niet overbeladen.

Het doel is simpel: vind de goedkoopste manier om alle vrachtwagens te laten rijden om aan deze regels te voldoen zonder dat je zonder benzine of tijd komt te zitten.

Het Probleem: Het is te moeilijk om perfect op te lossen

Naarmate het aantal families en huizen groeit, wordt het aantal mogelijke routes zo enorm dat zelfs de snelste supercomputers van de wereld jaren zouden nodig hebben om het perfecte antwoord te vinden. Daarom hebben de auteurs, Bruno, Diogo en Marcos, een "slimme gokker" (een metaheuristiek) bedacht om heel snel een zeer goed antwoord te vinden.

Ze noemen hun oplossing ILS+SP. Laten we dat ontleden met een kookanalogie.

Het Recept: ILS+SP

1. De "Iterated Local Search" (ILS) – De Proeverijnde Chef

Stel je een chef voor die probeert een soeprecept te perfectioneren.

Het Begin: De chef maakt een basissoep (een initiële oplossing).
De Proef (Local Search): De chef proeft de soep en maakt kleine aanpassingen: "Misschien een snufje zout meer?" of "Vervang de wortels door aardappelen?" Ze blijven deze kleine veranderingen maken om de smaak te verbeteren.
De "Simulated Annealing" Twist: Soms maakt een verandering de soep tijdelijk minder lekker. Een normale chef zou dit direct afwijzen. Maar deze chef gebruikt een speciale regel (Simulated Annealing): als de soep slechts een klein beetje minder lekker is, kan hij de verandering toch accepteren. Waarom? Omdat je soms de soep een beetje "niet lekker" moet maken om later een compleet nieuw, geweldig smaakprofiel te ontdekken. Dit helpt hen te ontsnappen aan "slechte buurten" waar ze vastzitten met een middelmatig recept.
De Schudbeweging (Perturbatie): Als de chef in een lus van kleine aanpassingen terechtkomt die niet helpen, doet hij iets drastisch: hij gooit de helft van de soep eruit en begint opnieuw met een wilde nieuwe combinatie van ingrediënten. Dit wordt "perturbatie" genoemd. Het dwingt de zoektocht om in een compleet nieuw deel van de keuken te kijken.

De auteurs hebben een speciaal ingrediënt aan de gereedschapskist van deze chef toegevoegd: MemberRelocate. Omdat dit een "familie"-probleem is, wisselt de chef niet alleen ingrediënten uit, maar wisselt hij familieleden uit. Als ze het huis #1 van de Smiths bezoeken, kunnen ze vragen: "Wacht, huis #2 ligt dichterbij. Laten we huis #1 vervangen door huis #2 en kijken of dat tijd bespaart."

2. De "Set Partitioning" (SP) – De Meesterredacteur

Nadat de chef urenlang heeft staan tweaken, schudden en proeven, heeft hij een enorm notitieboek vol met verschillende soepvariaties (routes) die hij onderweg heeft geprobeerd.

De stap van Set Partitioning is als een meesterredacteur die naar dat hele notitieboek kijkt. De redacteur kookt niet; hij kiest alleen maar uit. Hij kijkt naar al die beste "stukjes" soep die de chef gedurende de dag heeft gemaakt en vraagt: "Als ik dit specifieke gerecht van 10:00 uur combineer met dat specifieke gerecht van 14:00 uur, kan ik dan een perfecte maaltijd maken?"

Deze laatste stap zorgt ervoor dat zelfs als de chef de perfecte combinatie tijdens het kookproces heeft gemist, de redacteur deze vindt door de beste delen van het werk van de dag wiskundig samen te stellen.

De Resultaten: Werkt het?

De auteurs hebben hun "ILS+SP"-recept getest tegen de huidige beste methoden ter wereld.

De Test: Ze gebruikten 144 grote, moeilijke puzzels (met meer dan 50 klanten) die andere onderzoekers al hadden geprobeerd op te lossen.
De Score: Hun methode won of deelde op elke enkele instantie.
De Verbetering: Voordat dit artikel verscheen, waren de beste methoden gemiddeld ongeveer 1,84% verwijderd van de perfecte oplossing. De methode van de auteurs verkleinde die kloof tot 0,01%. In de wereld van logistiek is dat als het verschil tussen net naast het doel schieten en bijna elke keer de roos raken.
Snelheid: Ze testten het ook op nog grotere puzzels (tot 142 klanten). Hun methode vond geweldige oplossingen in gemiddeld ongeveer 37 seconden.

Samenvatting

Het artikel presenteert een nieuwe, hybride manier om een complex logistiek routeprobleem op te lossen waarbij je moet kiezen welke familieleden je bezoekt. Door een "proeverijnde chef" te combineren die slimme, soms riskante, kleine veranderingen aanbrengt met een "meesterredacteur" die de beste delen van het werk van de dag samenstelt, hebben ze een tool gecreëerd die sneller en nauwkeuriger is dan alles wat voorheen voor dit specifieke probleem is gepubliceerd.

Technische Samenvatting: Een Hybride Metaheuristiek voor het Family Capacitated Vehicle Routing Problem

Probleemdefinitie

Het artikel behandelt het Family Capacitated Vehicle Routing Problem (F-CVRP), een generalisatie van het Family Traveling Salesman Problem (FTSP) en het klassieke Capacitated Vehicle Routing Problem (CVRP). In het F-CVRP vertrekt een homogene vloot van $K$ voertuigen met capaciteit $Q$ vanuit één enkel depot om een set klanten te bedienen die zijn opgedeeld in families. In tegenstelling tot de standaard CVRP, waarbij elke klant moet worden bezocht, vereist het F-CVRP dat een specifiek aantal leden ( $v_l$ ) van elke familie $l$ wordt bezocht, terwijl de overige leden van die familie onbezocht kunnen blijven. Het doel is om de totale routekosten te minimaliseren, terwijl aan de voertuigcapaciteitsbeperkingen en de exacte bezoekvereisten voor elke familie wordt voldaan.

Naarmate de probleeminstanties schalen, worden exacte methoden computationeel onhaalbaar. Daarom richt het artikel zich op het ontwikkelen van een snelle, hoogwaardige heuristiek die in staat is om oplossingen te leveren binnen strikte tijdbudgetten, zowel als een zelfstandige solver als een leverancier van primal bounds voor exacte frameworks.

Methodologie: De ILS+SP Hybride Metaheuristiek

De auteurs stellen ILS+SP voor, een hybride metaheuristiek die een Iterated Local Search (ILS) framework combineert met een Set Partitioning (SP) post-optimalisatiefase. Het algoritme werkt als volgt:

1. Iterated Local Search (ILS) Kern

De zoektocht wordt gedreven door een ILS-framework dat een pool van routes ( $P$ ) bijhoudt en de beste gevonden haalbare oplossing ( $s^*$ ) bijhoudt.

Initiële Oplossing: Gegenereerd via een Best Parallel Insertion (BPI) heuristiek, waarbij $K$ routes worden geconstrueerd door iteratief klanten in te voegen om de kostenstijging te minimaliseren, waarbij wordt gewaarborgd dat de bezoekaantallen per familie worden nagekomen.
Lokale Zoektocht (RVND): De lokale zoektocht maakt gebruik van een Random Variable Neighborhood Descent (RVND) strategie. Het verkent een portfolio van negen buurten:
- Inter-route (5): Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
- Intra-route (3): Exchange, Reinsertion, Or-opt2.
- Gespecialiseerd (1): MemberRelocate, een problemspecifieke operator die een bezochte klant verwijdert en een niet-bezocht lid van dezelfde familie op de beste positie in alle routes invoegt.
- Alle buurten waarborgen de structurele beperkingen van de familiebezoekaantallen en het aantal actieve routes ( $K$ ).
Acceptatiecriterium: In tegen afwijking van standaard lokale zoektochten, accepteert het algoritme verslechterende bewegingen op basis van een Simulated Annealing (SA) criterium met een tijdgestuurd afkoelschema. Dit stelt de zoektocht in staat om lokale minima te ontsnappen.
Perturbatie: Om de zoektocht te diversifiëren, past het algoritme een van drie willekeurige perturbaties toe (RandomSwap, RandomShift of RandomMemberRelocate) op de huidige oplossing voordat de lokale zoektocht opnieuw wordt ingegaan.
Penalty Handling: Capaciteitsbeperkingen worden afgehandeld via een dynamische penalty-coëfficiënt ( $\theta$ ) in de objectieve functie, die wordt aangepast op basis van de haalbaarheid van de huidige oplossing om de zoektocht naar haalbare regio's te leiden.

2. Set Partitioning (SP) Post-Optimalisatie

Bij het uitputten van het tijdbudget voert het algoritme een laatste optimalisatiestap uit. Het formuleert een Set Partitioning probleem over de pool van capaciteitshaalbare routes ( $P$ ) die tijdens het gehele zoekproces zijn verzameld.

Het SP-model selecteert een subset van routes om de totale kosten te minimaliseren, terwijl aan de familiebezoekvereisten wordt voldaan en er exact $K$ routes worden gebruikt.
Omdat de pool $P$ de routes bevat die de beste tot nu toe gevonden oplossing ( $s^*$ ) vormen, is de optimale oplossing van de SP gegarandeerd minstens even goed als $s^*$ .

Belangrijkste Bijdragen

Het artikel benadrukt vier primaire bijdragen die dit werk onderscheiden van de huidige stand van de techniek (specifiek de ILS door Bernardino en Paias, 2024):

Hybridisering met Set Partitioning: De introductie van een SP post-optimalisatiefase om de routepool te heroptimaliseren, een matheuristic component die ontbrak in eerdere benaderingen.
Verbeterde Lokale Zoektocht: De implementatie van de MemberRelocate buurt, die niet-bezochte familieleden optimaal invoegt op de beste positie over alle routes, in plaats van ze simpelweg ter plaatse te wisselen.
Gerandomiseerde Buurtverkenning: Het gebruik van RVND om de volgorde van de buurtverkenning te randomiseren, wat contrasteert met de vaste volgorde die in eerdere literatuur werd gebruikt.
Simulated Annealing Acceptatie: Het gebruik van een SA-criterium om verslechterende oplossingen te accepteren, wat de strikte verbeteringsgerichte acceptatie van eerdere methoden vervangt, waardoor de balans tussen intensificatie en diversificatie wordt verbeterd.

Computationele Resultaten

De auteurs hebben ILS+SP geëvalueerd op twee benchmark-sets:

Standaard Benchmark (144 instanties): Afgeleid van de Augerat et al. (1995) set, bestaande uit instanties met meer dan 50 klanten.
- Prestaties: De methode won of deelde de eerste plaats op elke instantie tegenover de state-of-the-art heuristiek van Bernardino en Paias (2024).
- Gap Reductie: De gemiddelde gap tot de Best Known Solution (BKS) werd verminderd van 1,84% (vorige beste) naar 0,01%.
Scalability Benchmark (120 instanties): Een nieuwe set grotere instanties (tot 142 klanten) afgeleid van de CVRP Set X (Uchoa et al., 2017).
- Prestaties: Het algoritme bereikte een gemiddelde gap van 0,47% met een gemiddelde looptijd van 37 seconden, wat de schaalbaarheid naar grotere probleemomvang aantoont.

Betekenis en Claims

Het artikel positioneert ILS+SP als een robuuste en schaalbare oplossing voor het F-CVRP. De auteurs beweren dat door een matheuristic post-optimalisatie (SP) te integreren met een geavanceerd ILS-framework voorzien van problemspecifieke buurten en SA-acceptatie, de methode de bestaande heuristieken aanzienlijk overtreft. De resultaten suggereren dat de aanpak niet alleen in staat is om de best bekende oplossingen voor gevestigde benchmarks te evenaren of te verbeteren, maar ook effectief schaalt naar grotere, complexere instanties, waardoor het een waardevol instrument is voor zowel zelfstandige toepassing als integratie in exacte oplossingsframeworks.