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

Technischer Zusammenfassung: Ein verbesserter Large Neighborhood Search-Ansatz für das kapazitierte Standortproblem mit inkompatiblen Kunden

Problemdefinition
Diese Arbeit behandelt das Multi-Source Capacitated Facility Location Problem mit Kundeninkompatibilitäten (MS-CFLP-CI). Diese Variante erweitert das klassische MS-CFLP durch die Einführung einer Menge inkompatibler Kundenpaare ($I$), die nicht von derselben Einrichtung bedient werden können. Das Problem besteht darin, zu bestimmen, welche Einrichtungen eröffnet werden (was Eröffnungskosten $f_j$ verursacht) und wie die Kundennachfrage ($d_i$) auf die eröffneten Einrichtungen verteilt wird (was Transportkosten $c_{ij}$ verursacht), um die Gesamtkosten zu minimieren. Die Lösung muss Kapazitätsbeschränkungen der Einrichtungen ($s_j$) erfüllen, die Kundennachfrage vollständig decken und sicherstellen, dass keine zwei inkompatiblen Kunden dieselbe Einrichtung teilen. Das Vorhandensein von Inkompatibilitätsbeschränkungen macht das Teilproblem der Suche nach einer optimalen Versorgung durch eröffnete Einrichtungen NP-schwer, selbst wenn die Menge der eröffneten Einrichtungen festgelegt ist.

Methodik
Die Autoren schlagen einen Large Neighborhood Search (LNS)-Rahmen vor, um MS-CFLP-CI zu lösen. Der Kern des Ansatzes besteht darin, iterativ einen Teil der aktuellen Lösung zu zerstören und sie mithilfe eines exakten Mixed Integer Programming (MIP)-Löser (Gurobi) wiederherzustellen.

• Lösungsdarstellung: Lösungen werden als Matrizen von versendeten Mengen dargestellt, unterstützt durch Hilfsdatenstrukturen, die geöffnete/geschlossene Einrichtungen und zugewiesene Kunden verfolgen.
• Anfangslösung: Ein Heuristikverfahren konstruiert eine Startlösung, indem es Einrichtungen nach Eröffnungskosten sortiert, genügend davon auswählt, um die Gesamtnachfrage zu decken, und eine bestimmte Anzahl zusätzlicher Einrichtungen ($k=5$) hinzufügt, um Inkompatibilitätsbeschränkungen zu handhaben. Kunden werden basierend auf einer einheitlichen Strategie zugewiesen.
• Zerstörungsoperatoren: Die Arbeit stellt drei neuartige Zerstörungsoperatoren vor, die speziell für die Inkompatibilitätsbeschränkungen entwickelt wurden:
  1. Günstigste Einrichtungen (CF): Wählt eine zufällige Einrichtung und deren Kunden aus, identifiziert dann andere geöffnete Einrichtungen, die für diese spezifische Kundengruppe die niedrigsten durchschnittlichen Transportkosten bieten.
  2. Hybride Kunden (HC): Eine Rekombination zweier Strategien. Es wird eine zufällige Einrichtung und deren Kunden ausgewählt, dann werden „günstige Kunden" (jene mit niedrigen Transportkosten zur Einrichtung) und „teure Kunden" (jene mit hohen Transportkosten) identifiziert. Anschließend werden zusätzliche Einrichtungen ausgewählt, die den besten Service für diese spezifischen Kundenteilmengen bieten.
  3. Geschlossene Einrichtungen: Sowohl zufällige geschlossene Einrichtungen als auch solche mit dem minimalen Kostenmaß ($Q_g$) werden in das Teilproblem einbezogen, um das Öffnen neuer Einrichtungen zu explorieren.
• Wiederherstellungsoperator: Das durch die zerstörten Elemente definierte Teilproblem wird exakt mit Gurobi gelöst. Um die Rechenzeit zu managen, umfasst die Wiederherstellungsphase eine Beschränkung, die die Anzahl neu eröffneter Einrichtungen auf höchstens zwei mehr als die derzeit im Teilproblem involvierten Einrichtungen begrenzt. Ein Abbruchwert (die aktuelle Teilproblemkosten) wird dem Löser zur Beschleunigung der Konvergenz bereitgestellt.
• Konfiguration und Feinabstimmung: Die Autoren verwenden das Tool irace für die featurebasierte Parameteroptimierung und passen Parameter wie die Teilproblemgröße ($\nu$) an die Instanzskala an (insbesondere mit Unterscheidung zwischen Instanzen mit $\le 700$ und $> 700$ Einrichtungen). Der finale Algorithmus, bezeichnet als $LNS_{init,accept}$, kombiniert die vorgeschlagenen Zerstörungsoperatoren mit einer verbesserten Heuristik für die Anfangslösung und einem Akzeptanzkriterium, das Lösungen mit gleichen Kosten zur Akzeptanz zulässt, was das Entkommen aus lokalen Optima erleichtert.

Hauptbeiträge

• Neuartiger algorithmischer Rahmen: Dies ist die erste Anwendung von Large Neighborhood Search auf das MS-CFLP-CI-Problem.
• Spezialisierte Operatoren: Die Gestaltung von Zerstörungsoperatoren (CF und HC), die Inkompatibilitätsbeschränkungen explizit berücksichtigen und über Standardheuristiken für Standortprobleme hinausgehen.
• Hybride exakte/heuristische Wiederherstellung: Die Integration eines exakten MIP-Lösers in die Wiederherstellungsphase, optimiert mit spezifischen Beschränkungen, um eine Balance zwischen Lösungsqualität und Laufzeit zu erreichen.
• Rigorose Analyse: Eine umfassende Ablationsstudie und statistische Analyse (unter Verwendung von Friedman- und Nemenyi-Tests), um den Einfluss einzelner Komponenten (Initialisierung, Akzeptanzkriterien, adaptive Gewichte) zu bewerten.
• Umfangreiches Benchmarking: Evaluation auf zwei großskaligen Datensätzen (wlp und cflp-ci) mit bis zu 3.000 Einrichtungen und 8.000 Kunden.

Experimentelle Ergebnisse
Die vorgeschlagene Methode $LNS_{init,accept}$ wurde gegen State-of-the-Art-Metaheuristiken getestet, darunter MineReduce-basierter Multi-Start Iterated Local Search (MR-MS-ILS), GRASP, Permutation-codierter Evolutionärer Algorithmus (PcEA), Multi-start Greedy (MG) und Simulated Annealing (SA).

• Leistung: Die vorgeschlagene Methode übertraf auf beiden Datensätzen unter zwei verschiedenen Zeitlimits ($10\sqrt{m}$ und $m$ Sekunden) signifikant alle bestehenden Methoden.
• Neue beste Lösungen: Der Ansatz fand für alle 80 Instanzen über beide Datensätze hinweg neue beste Lösungen.
• Statistische Signifikanz: Statistische Tests bestätigten, dass die Verbesserungen gegenüber der vorherigen besten Methode (SA) statistisch signifikant sind.
• Skalierbarkeit: Während exakte Löser (Gurobi/CPLEX) Instanzen bis zu 150 Einrichtungen innerhalb einer angemessenen Zeit nur bis zur Optimalität lösen konnten, bewältigte der LNS-Ansatz effektiv Instanzen mit bis zu 3.000 Einrichtungen.
• Gap-Reduktion: Für den wlp-Datensatz erzielte die Methode Gap-Verbesserungen im Bereich von -0,68 % bis -1,84 % gegenüber den besten bekannten Lösungen. Für den cflp-ci-Datensatz lagen die Verbesserungen im Bereich von -0,46 % bis -2,09 %.

Bedeutung und Behauptungen
Die Autoren behaupten, dass ihre Methode den aktuellen State-of-the-Art für das MS-CFLP-CI-Problem darstellt. Die Bedeutung der Arbeit liegt in ihrer Fähigkeit, die durch Kundeninkompatibilitäten eingeführte rechnerische Komplexität zu bewältigen, mit der frühere Metaheuristiken Schwierigkeiten hatten, insbesondere bei größeren Instanzen, diese vollständig zu optimieren. Die Arbeit behauptet, dass die Kombination aus neuartigen Zerstörungsoperatoren, einer exakten Wiederherstellungsphase und spezifischer algorithmischer Feinabstimmung es der Methode ermöglicht, mittelgroße Nachbarschaften effektiv zu explorieren und überlegene Lösungen zu finden, wo SA und andere Methoden stagnieren. Die Autoren vermerken bescheiden, dass ihre Methode zwar derzeit die beste ist, zukünftige Arbeiten jedoch eine Instanzraum-Analyse beinhalten könnten, um die Instanzschwierigkeit besser zu verstehen, sowie die Erweiterung des Ansatzes auf andere Varianten des Standortproblems.