Sintesi Tecnica: Un Metaeuristica Ibrida per il Problema del Veicolo Capacitato con Vincoli di Famiglia (F-CVRP)

Definizione del Problema

Il documento affronta il Problema del Veicolo Capacitato con Vincoli di Famiglia (F-CVRP), una generalizzazione del Probleola del Commesso Viaggiatore con Vincoli di Famiglia (FTSP) e del classico Problema del Veicolo Capacitato (CVRP). Nell'F-CVRP, una flotta omogenea di $K$ veicoli con capacità $Q$ parte da un unico deposito per servire un insieme di clienti suddivisi in famiglie. A differenza dello standard CVRP dove ogni cliente deve essere visitato, l'F-CVRP richiede che un numero specifico di membri ($v_l$) per ogni famiglia $l$ venga visitato, mentre i restanti membri di quella famiglia possono rimanere non visitati. L'obiettivo è minimizzare il costo totale del percorso rispettando i vincoli di capacità del veicolo e soddisfacendo i requisiti esatti di visita per ogni famiglia.

Man mano che le istanze del problema scalano, i metodi esatti diventano computazionalmente proibitivi. Di conseguenza, il documento si concentra sullo sviluppo di un'euristica veloce e di alta qualità capace di fornire soluzioni entro budget temporali ristretti, fungendo sia da risolutore autonomo sia da fornitore di limiti primali per framework esatti.

Metodologia: La Metaeuristica Ibrida ILS+SP

Gli autori propongono ILS+SP, una metaeuristica ibrida che combina un framework di Ricerca Locale Iterata (ILS) con una fase di post-ottimizzazione basata sulla Partizione di Insiemi (SP). L'algoritmo opera come segue:

1. Nucleo di Ricerca Locale Iterata (ILS)

La ricerca è guidata da un framework ILS che mantiene un pool di percorsi ($P$) e traccia la migliore soluzione ammissibile trovata ($s^*$).

• Soluzione Iniziale: Generata tramite un'euristica di Inserimento Parallelo Migliore (BPI), che costruisce $K$ percorsi inserendo iterativamente i clienti per minimizzare l'incremento dei costi, garantendo il rispetto dei conteggi delle visite per famiglia.
• Ricerca Locale (RVND): La ricerca locale impiega una strategia di Discesa a Vicinato Variabile Casuale (RVND). Essa esplora un portfolio di nove vicinati:
  • Inter-percorso (5): Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
  • Intra-percorso (3): Scambio (Exchange), Reinserimento (Reinsertion), Or-opt2.
  • Specializzato (1): MemberRelocate, un operatore specifico del problema che rimuove un cliente visitato e inserisce un membro non visitato della stessa famiglia nella migliore posizione tra tutti i percorsi.
  • Tutti i vicinati preservano i vincoli strutturali dei conteggi delle visite familiari e del numero di percorsi attivi ($K$).
• Criterio di Accettazione: A differenza della ricerca locale standard, l'algoritmo accetta mosse peggiorative basandosi su un criterio di Simulated Annealing (SA) con uno schema di raffreddamento basato sul tempo. Ciò consente alla ricerca di uscire dai minimi locali.
• Perturbazione: Per diversificare la ricerca, l'algoritmo applica una delle tre perturbazioni casuali (RandomSwap, RandomShift o RandomMemberRelocate) alla soluzione corrente prima di rientrare nella ricerca locale.
• Gestione delle Penalità: Le violazioni di capacità sono gestite tramite un coefficiente di penalità dinamico ($\theta$) nella funzione obiettivo, che viene regolato in base alla fattibilità della soluzione corrente per guidare la ricerca verso regioni ammissibili.

2. Post-Ottimizzazione tramite Partizione di Insiemi (SP)

Al termine del budget temporale, l'algoritmo esegue un passaggio di ottimizzazione finale. Esso formula un problema di Partizione di Insiemi (SP) sui percorsi capaci di rispettare la capacità ($P$) raccolti durante l'intero processo di ricerca.

• Il modello SP seleziona un sottoinsieme di percorsi per minimizzare il costo totale soddisfacendo i requisiti di visita delle famiglie e utilizzando esattamente $K$ percorsi.
• Poiché il pool $P$ contiene i percorsi che compongono la migliore soluzione trovata finora ($s^*$), la soluzione ottimale dell'SP è garantita essere almeno altrettanto buona di $s^*$.

Contributi Chiave

Il documento evidenzia quattro contributi primari che distinguono questo lavoro dallo stato dell'arte esistente (nello specifico l'ILS di Bernardino e Paias, 2024):

1. Ibridazione con la Partizione di Insiemi: L'introduzione di una fase di post-ottimizzazione SP per ri-ottimizzare il pool di percorsi, un componente matheuristic assente negli approcci precedenti.
2. Ricerca Locale Potenziata: L'implementazione del vicinato MemberRelocate, che inserisce in modo ottimale i membri familiari non visitati nella migliore posizione tra tutti i percorsi, anziché limitarsi a scambiarli in loco.
3. Esplorazione del Vicinato Randomizzata: L'uso di RVND per randomizzare l'ordine di esplorazione dei vicinati, contrastando con l'ordine fisso utilizzato nella letteratura precedente.
4. Accettazione tramite Simulated Annealing: L'adozione di un criterio SA per accettare soluzioni peggiorative, sostituendo l'accettazione rigorosa basata solo sul miglioramento dei metodi precedenti, migliorando così l'equilibrio tra intensificazione e diversificazione.

Risultati Computazionali

Gli autori hanno valutato l'ILS+SP su due set di benchmark:

1. Benchmark Standard (144 istanze): Derivato dal set di Augerat et al. (1995), contenente istanze con più di 50 clienti.
   • Performance: Il metodo ha vinto o pareggiato su ogni istanza contro lo stato dell'arte euristico di Bernardino e Paias (2024).
   • Riduzione del Gap: Il gap medio rispetto alla Migliore Soluzione Nota (BKS) è stato ridotto dall'1,84% (miglior risultato precedente) allo 0,01%.
2. Benchmark di Scalabilità (120 istanze): Un nuovo set di istanze più grandi (fino a 142 clienti) derivato dal CVRP Set X (Uchoa et al., 2017).
   • Performance: L'algoritmo ha ottenuto un gap medio dello 0,47% con un tempo di esecuzione medio di 37 secondi, dimostrando scalabilità verso dimensioni del problema più grandi.

Significato e Rivendicazioni

Il documento posiziona l'ILS+SP come una soluzione robusta e scalabile per l'F-CVRP. Gli autori affermano che, integrando una post-ottimizzazione matheuristic (SP) con un sofisticato framework ILS caratterizzato da vicinati specifici del problema e accettazione SA, il metodo supera significativamente le euristiche esistenti. I risultati suggeriscono che l'approccio non è solo capace di eguagliare o migliorare le migliori soluzioni note per i benchmark stabiliti, ma scala anche efficacementamente verso istanze più grandi e complesse, rendendolo uno strumento prezioso sia per l'applicazione autonoma che per l'integrazione in framework di soluzione esatti.