🤖 AI

An Enhanced Large Neighborhood Search Approach for the Capacitated Facility Location Problem with Incompatible Customers

Dit artikel stelt een verbeterde Large Neighborhood Search-methode voor die hybride vernietigingsoperatoren combineert met een exacte hersteloplosser om bestaande state-of-the-art metaheuristieken te overtreffen bij het oplossen van het Capacitated Facility Location Problem met incompatibele klanten, waarbij nieuwe beste oplossingen worden bereikt voor alle benchmarkinstanties.

Oorspronkelijke auteurs: Ida Gjergji, Lucas Kletzander, Nysret Musliu, Andrea Schaerf

Gepubliceerd 2026-05-28

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Ida Gjergji, Lucas Kletzander, Nysret Musliu, Andrea Schaerf

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://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 enorm distributiebedrijf. Je hebt een lijst met klanten die pakketten nodig hebben, en een lijst met potentiële magazijnen waar je die pakketten zou kunnen opslaan. Je doel is eenvoudig: open de juiste magazijnen en stuur de juiste pakketten naar de juiste mensen, zodat je de minste kosten maakt voor openstellingskosten en verzendkosten.

Dit is het klassieke "Facility Location Problem" (Probleem van de locatie van faciliteiten). Maar in dit specifieke artikel voegen de auteurs een lastige draai toe: Klantenonverenigbaarheid.

De Draai: "Vijanden" in de Buurt

Stel je voor dat sommige van je klanten rivaliserende bedrijven zijn (zoals twee concurrerende frisdrankmerken) of gevaarlijke stoffen hanteren die niet gemengd mogen worden. Je kunt deze "vijandige" klanten niet in hetzelfde magazijn onderbrengen. Als je dat wel doet, is het een ramp. Dit voegt een laag complexiteit toe die het vinden van de perfecte oplossing ongelooflijk moeilijk maakt, alsof je probeert een gigantische, verschuivende legpuzzel op te lossen waarbij sommige stukken elkaar magnetisch afstoten.

De Oplossing: De "Grote Buurt"-Zoek

De auteurs stellen een nieuwe manier voor om deze puzzel op te lossen, genaamd Large Neighborhood Search (LNS). Om te begrijpen hoe dit werkt, stel je voor dat je probeert de meubels in een woonkamer opnieuw in te delen om het er mooier uit te laten zien.

De "Vernietig"-Fase (De Rommelmaker):
In plaats van één stoel per keer te verplaatsen, pakt het algoritme een heel stuk van de kamer – zeg de bank, het tapijt en de salontafel – en gooit ze naar buiten. In de taal van het artikel is dit de Vernietig-operator. Ze hebben drie speciale manieren bedacht om te kiezen welke "meubels" (klanten en magazijnen) verwijderd moeten worden:
- Goedkoopste Faciliteiten: Het selecteren van de magazijnen die op dit moment het meest kosten om te gebruiken.
- Hybride Klanten: Een slimme mix van het selecteren van de duurste klanten om te bedienen en het vinden van de beste nieuwe plekken voor hen.
- Willekeurig: Gewoon een willekeurige groep grijpen om de boel op te schudden.
De "Reparatie"-Fase (De Expert-Architect):
Nu heb je een rommelige kamer met een gat in het midden. Je raadt niet zomaar waar je de meubels terug moet zetten. In plaats daarvan roep je een super-slimme architect (een exacte wiskundige solver genaamd Gurobi) aan om alleen naar dat specifieke gat te kijken. De architect bedenkt de absoluut beste manier om alleen die specifieke items opnieuw in te delen zodat ze perfect passen, met inachtneming van de "vijand"-regels. Dit is de Reparatie-operator.
De Lus:
De computer herhaalt dit proces duizenden keren: breek een deel van de oplossing, laat de expert dat specifieke deel herstellen en kijk of de hele kamer er beter uitziet. Als dat zo is, behoud je de verandering. Zo niet, probeer dan de volgende keer een ander stuk om te breken.

Waarom Dit Artikel Speciaal Is

De auteurs hebben deze machine niet alleen gebouwd; ze hebben hem afgesteld als een raceauto.

De Startlijn: Ze realiseerden zich dat het beginnen met een goed initieel plan belangrijk is. Ze testten verschillende manieren om de eerste "kamer" in te richten en ontdekten dat beginnen met een specifieke hebzuchtige strategie hen een voorsprong gaf.
De Acceptatieregels: Ze hebben de regels aangepast voor wanneer een nieuwe indeling geaccepteerd moet worden. Ze besloten om soms ook "gelijke" indelingen (niet alleen betere) toe te staan. Dit helpt het algoritme om uit "lokale valkuilen" te ontsnappen – situaties waarin de kamer er goed uitziet, maar het eigenlijk vastzit in een hoek en niet beter kan worden zonder een grote opschudding.
De Resultaten: Ze testten hun methode op twee enorme datasets (sommige met tot 3.000 magazijnen en 8.000 klanten). De resultaten waren indrukwekkend: hun methode versloeg alle eerdere "state-of-the-art"-methoden. Sterker nog, voor elke testcase die ze probeerden, vonden ze een nieuwe beste oplossing, wat geld bespaarde in vergelijking met alles wat anders bekend was.

De Conclusie

Beschouw dit artikel als de introductie van een nieuw, zeer efficiënt team van renovateurs. Eerdere methoden waren als mensen die proberen een huis te repareren door één baksteen per keer te verplaatsen. Deze nieuwe methode pakt een hele muur, haalt een meesterbouwer binnen om alleen die muur perfect opnieuw te ontwerpen, en zet hem dan terug. Door dit keer op keer te doen, slaagden ze erin een "huis" (een logistiek plan) te bouwen dat goedkoper en efficiënter is dan elk ander plan dat eerder is gevonden, zelfs voor de meest complexe en "vijandige" scenario's.

Technische Samenvatting: Een Verbeterde Large Neighborhood Search-benadering voor het Capaciteitsgebonden Locatieprobleem van Faciliteiten met Incompatibele Klanten

Probleemdefinitie
Dit artikel behandelt het Multi-Source Capaciteitsgebonden Locatieprobleem van Faciliteiten met Incompatibele Klanten (MS-CFLP-CI). Deze variant breidt het klassieke MS-CFLP uit door een set van incompatibele klantparen ( $I$ ) in te voeren die niet door dezelfde faciliteit kunnen worden bediend. Het probleem omvat het bepalen welke faciliteiten geopend moeten worden (met openingkosten $f_j$ ) en hoe de klantvraag ( $d_i$ ) over de geopende faciliteiten moet worden verdeeld (met verzendkosten $c_{ij}$ ) om de totale kosten te minimaliseren. De oplossing moet voldoen aan capaciteitsbeperkingen van faciliteiten ( $s_j$ ), de klantvraag volledig dekken en garanderen dat geen twee incompatibele klanten dezelfde faciliteit delen. De aanwezigheid van incompatibiliteitsbeperkingen maakt het subprobleem van het vinden van een optimale levering vanuit geopende faciliteiten NP-moeilijk, zelfs wanneer de set geopende faciliteiten vaststaat.

Methodologie
De auteurs stellen een Large Neighborhood Search (LNS)-kader voor om MS-CFLP-CI op te lossen. De kern van de aanpak bestaat uit het iteratief vernietigen van een deel van de huidige oplossing en het herstellen ervan met behulp van een exacte Mixed Integer Programming (MIP)-oplosser (Gurobi).

Oplossingsrepresentatie: Oplossingen worden weergegeven als matrices van verzonden hoeveelheden, ondersteund door hulpdatastructuren die geopende/gesloten faciliteiten en toegewezen klanten bijhouden.
Initiële Oplossing: Een heuristiek construeert een startoplossing door faciliteiten te sorteren op openingkosten, er voldoende te selecteren om de totale vraag te dekken, en een specifiek aantal extra faciliteiten ( $k=5$ ) toe te voegen om incompatibiliteitsbeperkingen te hanteren. Klanten worden toegewezen op basis van een uniforme strategie.
Vernietigingsoperatoren: Het artikel introduceert drie nieuwe vernietigingsoperatoren die specifiek zijn ontworpen voor incompatibiliteitsbeperkingen:
1. Goedkoopste Faciliteiten (CF): Selecteert een willekeurige faciliteit en haar klanten, en identificeert vervolgens andere geopende faciliteiten die de laagste gemiddelde verzendkosten bieden voor die specifieke klantgroep.
2. Hybride Klanten (HC): Een recombinatie van twee strategieën. Het selecteert een willekeurige faciliteit en haar klanten, en identificeert vervolgens "goedkoopste klanten" (die met lage verzendkosten naar de faciliteit kunnen) en "duurste klanten" (die met hoge verzendkosten kunnen). Vervolgens worden extra faciliteiten geselecteerd die de beste service bieden voor deze specifieke klantsubsets.
3. Gesloten Faciliteiten: Zowel willekeurige gesloten faciliteiten als die met de minimale kostenmaatstaf ( $Q_g$ ) worden opgenomen in het subprobleem om het openen van nieuwe faciliteiten te verkennen.
Hersteloperator: Het subprobleem dat wordt gedefinieerd door de vernietigde elementen wordt exact opgelost met Gurobi. Om de rekentijd te beheersen, omvat de herstelfase een beperking die het aantal nieuw geopende faciliteiten beperkt tot maximaal twee meer dan momenteel betrokken in het subprobleem. Een afkapwaarde (de huidige subprobleemkosten) wordt aan de oplosser gegeven om convergentie te versnellen.
Configuratie en Afstemming: De auteurs gebruiken de tool irace voor op kenmerken gebaseerde parameterafstemming, waarbij parameters zoals de subprobleemgrootte ( $\nu$ ) worden aangepast op basis van de schaal van het voorbeeld (specifiek onderscheidend tussen voorbeelden met $\le 700$ en $> 700$ faciliteiten). Het uiteindelijke algoritme, genaamd $LNS_{init,accept}$ , combineert de voorgestelde vernietigingsoperatoren met een verbeterde heuristiek voor de initiële oplossing en een acceptatiecriterium dat toestaat dat oplossingen met gelijke kosten worden geaccepteerd, wat helpt om te ontsnappen uit lokale optima.

Belangrijkste Bijdragen

Nieuw Algoritmisch Kader: Dit is de eerste toepassing van Large Neighborhood Search op het MS-CFLP-CI-probleem.
Gespecialiseerde Operatoren: Het ontwerp van vernietigingsoperatoren (CF en HC) die expliciet rekening houden met incompatibiliteitsbeperkingen, en verder gaan dan standaard heuristieken voor locatie van faciliteiten.
Hybride Exact/Heuristisch Herstel: De integratie van een exacte MIP-oplosser binnen de herstelfase, geoptimaliseerd met specifieke beperkingen om oplossingkwaliteit en looptijd in evenwicht te brengen.
Rigoureuze Analyse: Een uitgebreide ablatiestudie en statistische analyse (met behulp van Friedman- en Nemenyitesten) om de impact van individuele componenten (initialisatie, acceptatiecriteria, adaptieve gewichten) te evalueren.
Uitgebreide Benchmarking: Evaluatie op twee grootschalige datasets (wlp en cflp-ci) met tot 3.000 faciliteiten en 8.000 klanten.

Experimentele Resultaten
De voorgestelde $LNS_{init,accept}$ -methode werd getest tegen state-of-the-art metaheuristieken, waaronder MineReduce-gebaseerde Multi-Start Iterated Local Search (MR-MS-ILS), GRASP, Permutation-coded Evolutionary Algorithm (PcEA), Multi-start Greedy (MG) en Simulated Annealing (SA).

Prestaties: De voorgestelde methode presteerde significant beter dan alle bestaande methoden op beide datasets onder twee verschillende tijdslimieten ( $10\sqrt{m}$ en $m$ seconden).
Nieuwe Beste Oplossingen: De aanpak vond nieuwe beste oplossingen voor alle 80 instanties in beide datasets.
Statistische Significantie: Statistische tests bevestigden dat de verbeteringen ten opzichte van de vorige beste methode (SA) statistisch significant zijn.
Schaalbaarheid: Waar exacte oplossers (Gurobi/CPLEX) alleen instanties tot 150 faciliteiten binnen redelijke tijd tot optimaliteit konden oplossen, kon de LNS-aanpak effectief omgaan met instanties met tot 3.000 faciliteiten.
Gap-reductie: Voor de wlp-dataset bereikte de methode gap-verbeteringen variërend van -0,68% tot -1,84% ten opzichte van de best bekende oplossingen. Voor de cflp-ci-dataset varieerden de verbeteringen van -0,46% tot -2,09%.

Betekenis en Beweringen
De auteurs beweren dat hun methode de huidige state-of-the-art vertegenwoordigt voor het MS-CFLP-CI-probleem. De betekenis van het werk ligt in het vermogen om de rekenkundige complexiteit te hanteren die wordt geïntroduceerd door incompatibiliteiten van klanten, waar eerdere metaheuristieken moeite hadden om volledig te optimaliseren, met name voor grotere instanties. Het artikel stelt dat de combinatie van nieuwe vernietigingsoperatoren, een exacte herstelfase en specifieke algoritmische afstemming de methode in staat stelt om effectief middelgrote buurten te verkennen en superieure oplossingen te vinden waar SA en andere methoden stagneren. De auteurs merken bescheiden op dat, hoewel hun methode momenteel de beste is, toekomstig werk een Instance Space Analysis zou kunnen omvatten om de moeilijkheid van instanties beter te begrijpen en de aanpak uit te breiden naar andere varianten van locatie van faciliteiten.

De Draai: "Vijanden" in de Buurt

De Oplossing: De "Grote Buurt"-Zoek

Waarom Dit Artikel Speciaal Is

De Conclusie

Technische Samenvatting: Een Verbeterde Large Neighborhood Search-benadering voor het Capaciteitsgebonden Locatieprobleem van Faciliteiten met Incompatibele Klanten

Meer zoals dit