💻 computer science

Assigning and optimising airport ground-handling operations: an rVNS metaheuristic

Questo articolo presenta una meta-euristica di ricerca nel vicinato variabile ridotta (rVNS) cooperativa per ottimizzare il complesso problema del routing e della pianificazione dei veicoli con capacità, più viaggi, finestre temporali e pause pasti (MTCVRSPTW-MB) per le operazioni di catering aeroportuale, dimostrando la sua superiore efficienza e riduzione del chilometraggio rispetto ai metodi esatti su istanze reali presso l'aeroporto internazionale di San Francisco.

Autori originali: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Pubblicato 2026-07-07

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Alexandre Dupaquis, Ronan Guivarch, Sandrine Mouysset, Daniel Ruiz, Vincent Charvillat, Frédéric Bouilhaguet

Articolo originale sotto licenza CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immaginate un aeroporto frenetico come un gigantesco puzzle ad alta posta in gioco. Da un lato, avete centinaia di aeroplani in arrivo e in partenza, ognuno dei quali deve ricevere il carico di cibo. Dall'altro lato, avete una flotta di camion e conducenti, ognuno con competenze specifiche, tempo limitato e regole rigide su quando poter fare la pausa pranzo.

L'obiettivo è semplice: nutrire ogni aereo in tempo utilizzando il minor numero di chilometri percorsi dai camion. Ma la matematica dietro tutto ciò è incredibilmente complessa. Se si cercasse di risolverlo con un normale programma informatico, sarebbe come cercare un singolo granello di sabbia specifico su una spiaggia controllandoli uno per uno: richiederebbe troppo tempo.

Questo articolo presenta un modo più intelligente e veloce per risolvere questo puzzle utilizzando un metodo chiamato rVNS (Variable Neighbourhood Search ridotta). Ecco come funziona, suddiviso in concetti quotidiani:

1. Il Problee: Il "Tetris" del cibo aeroportuale

Pensate al team di assistenza a terra dell'aeroporto come se stesse giocando a una partita di Tetris ad alta velocità.

I Blocchi: Sono i compiti (caricare un aereo, scaricare un aereo).
Gli Slot: Sono i conducenti e i camion.
Le Regole: Un conducente può guidare solo un determinato camion; un camion può trasportare solo una certa quantità di cibo; un conducente deve fare una pausa pranzo di 30 minuti tra le 4 e le 5 ore dall'inizio del turno; e un aereo deve essere nutrito entro una specifica finestra temporale.

In passato, i ricercatori hanno provato due modi per risolvere questo problema:

Il modo "Perfetto" (Metodo Esatto): Cercare di calcolare ogni singola possibilità per trovare la soluzione assoluta migliore. È come cercare di leggere ogni libro in una biblioteca per trovare la storia migliore. È accurato, ma richiede troppo tempo.
Il modo "Veloce" (Eurisitica Greedy): Fare la scelta migliore disponibile nel momento esatto in cui si presenta. È come afferrare il libro più vicino senza guardarsi intorno. È veloce, ma spesso porta a un risultato mediocre.

2. La Soluzione: Lo "Shuffle Intelligente" (rVNS)

Il nuovo metodo, rVNS, è come un maestro risolutore di puzzle che sa che, a volte, bisogna rompere una buona disposizione per crearne una migliore.

Inve invece di cercare di costruire il puzzle perfetto da zero, l'algoritmo parte da una disposizione decente e poi gioca a un gioco di "Mescolamento e Scambio" (Shuffle and Swap).

Il Mescolamento (Shuffle): Sceglie casualmente alcuni compiti (blocchi) e li rimuove dal programma, mettendoli in una "sala d'attesa".
Lo Scambio (Swap): Poi prova a reinserire quei compiti, ma questa volta cerca di incastrarli in posizioni diverse o di scambiarli con altri compiti per vedere se l'immagine complessiva migliora.

Perché "Ridotta"?
Di solito, questi algoritmi cercano di mescolare enormi blocchi del puzzle, il che è lento. Questo nuovo metodo mescola piccoli pezzi, ma lo fa molto velocemente e ripetutamente. È come uno chef che assaggia una zuppa e aggiunge un pizzico di sale, poi assaggia di nuovo, invece di provare a riscrivere l'intera ricetta ogni volta.

3. Il "Tocco Segreto": Due Strategie Diverse

L'algoritmo è abbastanza intelligente da sapere quando concentrarsi su cosa. Ha due modalità:

Modalità A (Il "Riempitivo"): Il suo obiettivo principale è garantire che nessun compito venga lasciato indietro. Mescola il programma per assicurarsi che ogni aereo venga nutrito.
Modalità B (Il "Risparmiatore di Chilometri"): Una volta assegnati la maggior parte dei compiti, cambia focus sul risparmio di carburante. Cerca modi per riorganizzare i camion in modo che percorrano meno chilometri tra un aereo e l'altro.

4. Il "Briefing di Squadra" (Parallelizzazione)

Per rendere tutto questo ancora più veloce, i ricercatori non hanno usato un solo cervello informatico; ne hanno usato un team. Immaginate un gruppo di detective che cerca di risolvere un crimine. Inve di una sola persona che controlla ogni indizio, hanno diviso il lavoro:

Il Team di Detective 1 lavora sulla tabella di marcia del turno mattutino.
Il Team di Detective 2 lavora sulla tabella di marcia del turno pomeridiano.
Ogni 10 secondi, si riuniscono per un briefing, condividono le loro migliori idee e combinano i loro risultati.

Questo assicura che non rimangano bloccati in un "vicolo cieco" (un ottimo locale) dove pensano di aver trovato la soluzione migliore, ma in realtà ne hanno persa una superiore.

5. I Risultati: Più Veloci, Migliori e Più Fluidi

Quando hanno testato questo nuovo metodo con dati reali dell'aeroporto internazionale di San Francisco (SFO):

Tasso di Successo: I vecchi metodi riuscivano ad assegnare circa l'80-89% dei compiti. Il nuovo metodo rVNS ha assegnato dal 99% al 99,8% dei compiti. Quasi mai lascia un aereo senza cibo.
Risparmio di Carburante: Poiché riorganizza lo schema in modo più efficiente, i camion hanno percorso circa il 20% - 30% di chilometri in meno rispetto a prima.
Velocità: Ha trovato queste soluzioni quasi perfette in meno di un minuto, il che è sufficiente per essere utilizzato nelle operazioni in tempo reale.

Riassunto

In breve, questo articolo presenta un nuovo algoritmo di "mescolamento intelligente" che aiuta i gestori aeroportuali ad assegnare i compiti di consegna del cibo a conducenti e camion. Dividendo il problema in parti più piccole, mescolandole casualmente per trovare incastri migliori e utilizzando un team di computer che lavorano insieme, il sistema assicura che quasi ogni aereo venga nutrito, percorrendo allo stesso tempo molti meno chilometri rispetto ai metodi precedenti. Trasforma un puzzle caotico e impossibile da risolvere in una routine quotidiana gestibile ed efficiente.

Sintesi Tecnica: Assegnazione e Ottimizzazione delle Operazioni di Ground-Handling Aeroportuale tramite rVNS

Definizione del Problema
Lo studio affronta la complessa ottimizzazione combinatoria delle operazioni di ground-handling aeroportuale, concentrandosi specificamente sui servizi di catering. Il problema centrale è modellato come il Multi-Trip Capacitated Vehicle Routing and Scheduling Problem with Time Windows and Meal Breaks (MTCVRSPTW-MB), esteso per accogliere una flotta eterogenea di camion e conducenti con diverse qualifiche e modelli di carico.

L'obiettivo è duplice:

Primario: Massimizzare il numero di compiti di catering (carico/scarico aeromobili) assegnati ai conducenti e ai camion disponibili.
Secondario: Minimizzare il chilometraggio totale richiesto per eseguire tali compiti.

Il problema è vincolato da rigide regole operative, tra cui:

Vincoli dei Conducenti: Turni di lavoro, pause pasto obbligatorie di 30 minuti (che avvengono 4–5 ore dopo l'inizio del turno) e requisiti di qualifica per specifici tipi di aeromobili e compagnie aeree.
Vincoli dei Camion: Limiti di capacità, tipi specifici di camion (14FT, 16FT, 22FT) e disponibilità giornaliera limitata.
Vincoli dei Compiti: Finestre temporali per l'esecuzione, compatibilità tra camion/conducente e il volo/compagnia aerea specifica, e requisiti di volume.
Vincoli di Missione: Regole che governano le missioni multi-task, come il divieto di scarichi domestici dopo carichi internazionali nella stessa missione, la garanzia di tempo di percorrenza sufficiente tra i compiti e l'obbligo per tutte le missioni di iniziare e terminare presso l'unità di catering principale.

Lo studio utilizza dati reali dell'Aeroporto Internazionale di San Francisco (SFO) per marzo 2023, che coinvolgono circa 350 compiti giornalieri, 80 conducenti e 40 camion. Un requisito critico è che le soluzioni debbano essere generate entro un minuto per essere operativamente sostenibili.

Metodologia
Gli autori propongono una ricerca tabu a vicinato variabile ridotta cooperativa (rVNS) meta euristica. Questo approccio è stato selezionato rispetto alla classica Variable Neighborhood Search (VNS) e alla Adaptive Large Neighborhood Search (ALNS) per bilanciare l'efficienza computazionale con la qualità della soluzione.

I componenti chiave della metodologia includono:

Framework Reduced VNS (rVNS):
- A differenza della VNS classica che varia le dimensioni dei passi, la rVNS impiega un passo fisso e piccolo.
- L'algoritmo opera attraverso un ciclo di decostruzione e ricostruzione: rimuove un numero fisso di compiti ( $n$ ) dalla soluzione corrente e tenta di riassegnarli casualmente.
- Per compensare il passo fisso, l'algoritmo sfrutta l'alta simmetria del problema di pianificazione. Esplorando soluzioni "equivalenti" (diversi programmi con punteggi identici) attraverso scambi casuali, la ricerca diversifica senza necessitare di passi ampi e computazionalmente costosi.
Struttura Algoritmica:
- Decomposizione (Dicotomia del Problema): Il programma giornaliero è suddiviso in due sottoproblemi (Mattina e Pomeriggio) basati sulle sovrapposizioni dei turni dei conducenti, consentendo l'elaborazione in parallelo.
- Euristica di Warm-Start: La rVNS è inizializzata con una soluzione generata da un'euristica greedy che dà priorità ai compiti con meno conducenti qualificati e pause pasto obbligatorie. Ciò evita che la ricerca parta da un ottimo locale povero.
- Randomizzazione a Doppio Obiettivo: L'algoritmo alterna due strategie di randomizzazione basate sulla convergenza dell'obiettivo:
  - Focus Primario: Rimuove compiti con posizioni temporali simili per creare spazio per i compiti non assegnati.
  - Focus Secondario: Rimuove compiti che contribuiscono in modo significativo al chilometraggio totale.
- Euristica di Sequenziamento: Un'euristica veloce (Algoritmo 3) verifica se un compito può essere inserito nella sequenza di un conducente senza violare i vincoli, fondamentale per mantenere la velocità durante la fase di ricostruzione.
- Parallelizzazione Cooperativa: Una strategia multi-start viene eseguita su 8 core (4 per sottoproblema). Ogni 10 secondi, le unità parallele condividono i risultati e ripartono dalla soluzione migliore attuale per ridurre la varianza ed evitare ottimi locali.
Funzione Obiettivo:
La funzione obiettivo totale $F$ è una somma pesata che dà priorità all'assegnazione dei compiti, seguita dalla riduzione del chilometraggio e, infine, dall'efficienza della missione:
$F = 10^6 \sum a_i + 10^3 \sum (x_i + y_i) + \sum e_i$
Dove $a_i$ rappresenta i compiti non assegnati, $x_i$ e $y_i$ rappresentano le distanze percorse ed $e_i$ conta l'inizio delle missioni.

Risultati Chiave
Lo studio confronta la rVNS proposta con un'Euristica Greedy e una Matheuristica (precedentemente sviluppata in [1]) utilizzando due dataset (S1: compiti meno numerosi e più vincolati; S2: compiti numerosi e meno vincolati).

Assegnazione dei Compiti: La rVNS supera significativamente i metodi precedenti. Mentre gli approcci Greedy e della Matheuristica assegnavano circa l'80–89% dei compiti, la rVNS ha raggiunto tassi di assegnazione del 99,0% - 99,8% in entrambi i dataset.
Riduzione del Chilometraggio: La rVNS ha ridotto il chilometraggio totale della flotta di circa il 30% per il dataset S1 e del 20% per il dataset S2 rispetto alla Matheuristica.
Stabilità e Convergenza:
- La rVNS parallelizzata ha dimostrato una maggiore coerenza rispetto alla versione sequenziale, con una deviazione standard nel chilometraggio del 2–3% rispetto al 4–6% dell'approccio sequenziale.
- Velocità di Convergenza: Per il dataset più piccolo (S1), l'obiettivo primario (conteggio compiti) è confluito rapidamente (entro ~1 secondo), mentre l'ottimizzazione del chilometraggio ha continuato a migliorare fino a un minuto. Per il dataset più grande (S2), l'obiettivo primario ha richiesto ~10 secondi per la convergenza, con rendimenti decrescenti dopo un minuto.
Tempo di Esecuzione: Tutte le soluzioni sono state generate entro la finestra richiesta di un minuto (specificamente ~55–60 secondi inclusi i tempi di overhead).

Significatività e Rivendicazioni
Il documento sostiene che la meta euristica rVNS offre una soluzione robusta e flessibile per il ground-handling aeroportuale che supera i precedenti baselines esatti ed euristici. La sua principale significatività risiede in:

Sostenibilità Operativa: Risolve un problema altamente vincolato e multi-obiettivo entro il rigoroso limite di un minuto richiesto per la gestione in tempo reale.
Ottimizzazione Duale: Bilancia con successo il massimizzare il completamento dei compiti con la minimizzazione dei costi operativi (chilometraggio), una caratteristica non pienamente ottimizzata nei lavori precedenti.
Flessibilità: Gli autori notano che la struttura dell'algoritmo consente l'integrazione di nuovi vincoli o obiettivi, come la gestione della ricarica dei veicoli elettrici o le operazioni multi-deposito.
Applicazione nel Mondo Reale: Lo studio dimostra che l'algoritmo può gestire la complessità dei dati reali (inclusi i finestrini temporali scorrevoli e le flotte eterogenee) meglio dei modelli precedenti, fornendo uno strumento che gli operatori di ground-handling possono usare per assegnare automaticamente centinaia di compiti giornalieri.

Gli autori rimangono modesti riguardo all'ottimalità assoluta, riconoscendo che, sebbene l'algoritmo non garantisca un ottimo globale, converge costantemente a soluzioni che sono superiori ai metodi esistenti sia in termini di velocità che di qualità. Evidenziano inoltre il potenziale per future applicazioni in scenari di riassegnazione in tempo reale dove i compiti ritardati devono essere riprogrammati dinamicamente.