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

Riepilogo Tecnico: Un Approccio di Ricerca in Grande Vicinato Potenziato per il Problema di Localizzazione di Impianti con Capacità e Clienti Incompatibili

Definizione del Problema
Questo articolo affronta il Problema di Localizzazione di Impianti con Capacità e Clienti Incompatibili a Sorgenti Multiple (MS-CFLP-CI). Questa variante estende il classico MS-CFLP introducendo un insieme di coppie di clienti incompatibili ($I$) che non possono essere serviti dallo stesso impianto. Il problema consiste nel determinare quali impianti aprire (sostenendo costi di apertura $f_j$) e come distribuire la domanda dei clienti ($d_i$) tra gli impianti aperti (sostenendo costi di spedizione $c_{ij}$) per minimizzare il costo totale. La soluzione deve soddisfare i vincoli di capacità degli impianti ($s_j$), soddisfare completamente la domanda dei clienti e garantire che nessun due clienti incompatibili condividano un impianto. La presenza di vincoli di incompatibilità rende il sottoproblema di trovare l'approvvigionamento ottimale dagli impianti aperti NP-difficile, anche quando l'insieme degli impianti aperti è fissato.

Metodologia
Gli autori propongono un framework di Ricerca in Grande Vicinato (LNS) per risolvere il MS-CFLP-CI. Il nucleo dell'approccio consiste nel distruggere iterativamente una porzione della soluzione corrente e ripararla utilizzando un solver esatto di Programmazione Intera Mista (MIP) (Gurobi).

• Rappresentazione della Soluzione: Le soluzioni sono rappresentate come matrici di quantità spedite, supportate da strutture dati ausiliarie che tracciano gli impianti aperti/chiusi e i clienti assegnati.
• Soluzione Iniziale: Un'euristica costruisce una soluzione di partenza ordinando gli impianti in base al costo di apertura, selezionandone un numero sufficiente a soddisfare la domanda totale e aggiungendo un numero specifico di impianti extra ($k=5$) per gestire i vincoli di incompatibilità. I clienti vengono assegnati in base a una strategia uniforme.
• Operatori di Distruzione: L'articolo introduce tre nuovi operatori di distruzione progettati specificamente per i vincoli di incompatibilità:
  1. Impianti più Economici (CF): Seleziona un impianto casuale e i suoi clienti, quindi identifica altri impianti aperti che offrono il costo medio di spedizione più basso per quel specifico gruppo di clienti.
  2. Clienti Ibridi (HC): Una ricombinazione di due strategie. Seleziona un impianto casuale e i suoi clienti, quindi identifica "clienti economici" (quelli con bassi costi di spedizione verso l'impianto) e "clienti costosi" (quelli con alti costi di spedizione). Successivamente, seleziona impianti aggiuntivi che offrono il miglior servizio per questi specifici sottoinsiemi di clienti.
  3. Impianti Chiusi: Sia gli impianti chiusi casuali sia quelli con la misura di costo minima ($Q_g$) sono inclusi nel sottoproblema per esplorare l'apertura di nuovi impianti.
• Operatore di Riparazione: Il sottoproblema definito dagli elementi distrutti viene risolto esattamente utilizzando Gurobi. Per gestire il tempo computazionale, la fase di riparazione include un vincolo che limita il numero di nuovi impianti aperti a al massimo due in più rispetto a quelli attualmente coinvolti nel sottoproblema. Un valore di cutoff (il costo corrente del sottoproblema) viene fornito al solver per accelerare la convergenza.
• Configurazione e Taratura: Gli autori impiegano lo strumento irace per la taratura dei parametri basata sulle caratteristiche, regolando parametri come la dimensione del sottoproblema ($\nu$) in base alla scala dell'istanza (in particolare distinguendo tra istanze con $\le 700$ e $> 700$ impianti). L'algoritmo finale, denominato $LNS_{init,accept}$, combina gli operatori di distruzione proposti con un'euristica migliorata per la soluzione iniziale e un criterio di accettazione che permette di accettare soluzioni con costo uguale, facilitando la fuga dagli ottimi locali.

Principali Contributi

• Nuovo Framework Algoritmico: Questa è la prima applicazione della Ricerca in Grande Vicinato al problema MS-CFLP-CI.
• Operatori Specializzati: La progettazione di operatori di distruzione (CF e HC) che tengono esplicitamente conto dei vincoli di incompatibilità, andando oltre le euristiche standard per la localizzazione degli impianti.
• Riparazione Ibrida Esatta/Euristica: L'integrazione di un solver MIP esatto all'interno della fase di riparazione, ottimizzata con vincoli specifici per bilanciare la qualità della soluzione e il tempo di esecuzione.
• Analisi Rigorosa: Uno studio di ablazione completo e un'analisi statistica (utilizzando i test di Friedman e Nemenyi) per valutare l'impatto dei singoli componenti (inizializzazione, criteri di accettazione, pesi adattivi).
• Benchmarking Estensivo: Valutazione su due dataset su larga scala (wlp e cflp-ci) contenenti fino a 3.000 impianti e 8.000 clienti.

Risultati Sperimentali
Il metodo proposto $LNS_{init,accept}$ è stato testato contro metaeuristiche all'avanguardia, tra cui Ricerca Locale Iterata Multi-Avvio basata su MineReduce (MR-MS-ILS), GRASP, Algoritmo Evolutivo con Codifica a Permutazione (PcEA), Multi-start Greedy (MG) e Ricottura Simulata (SA).

• Prestazioni: Il metodo proposto ha superato significativamente tutti i metodi esistenti su entrambi i dataset sotto due diversi limiti di tempo ($10\sqrt{m}$ e $m$ secondi).
• Nuove Soluzioni Migliori: L'approccio ha trovato nuove soluzioni migliori per tutte le 80 istanze in entrambi i dataset.
• Significatività Statistica: I test statistici hanno confermato che i miglioramenti rispetto al metodo precedente migliore (SA) sono statisticamente significativi.
• Scalabilità: Mentre i solver esatti (Gurobi/CPLEX) potevano risolvere solo istanze fino a 150 impianti all'ottimalità in tempi ragionevoli, l'approccio LNS ha gestito efficacemente istanze fino a 3.000 impianti.
• Riduzione del Gap: Per il dataset wlp, il metodo ha ottenuto miglioramenti del gap che vanno da -0,68% a -1,84% rispetto alle soluzioni migliori note. Per il dataset cflp-ci, i miglioramenti sono variati da -0,46% a -2,09%.

Significato e Affermazioni
Gli autori affermano che il loro metodo rappresenta lo stato dell'arte attuale per il problema MS-CFLP-CI. Il significato del lavoro risiede nella sua capacità di gestire la complessità computazionale introdotta dalle incompatibilità dei clienti, che le precedenti metaeuristiche faticavano a ottimizzare completamente, in particolare per istanze più grandi. L'articolo afferma che la combinazione di operatori di distruzione innovativi, una fase di riparazione esatta e una taratura algoritmica specifica permette al metodo di esplorare efficacemente vicinati di dimensioni medie, trovando soluzioni superiori dove SA e altri metodi ristagnano. Gli autori notano con modestia che, sebbene il loro metodo sia attualmente il migliore, il lavoro futuro potrebbe coinvolgere l'Analisi dello Spazio delle Istanze per comprendere meglio la difficoltà delle istanze e estendere l'approccio ad altre varianti del problema di localizzazione degli impianti.