Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows

Il paper dimostra che un metodo semplice ed esatto risolve istantaneamente le istanze di riferimento classiche del problema del commesso viaggiatore con finestre temporali, rivelando che queste non sono più rappresentative per valutare l'efficacia degli algoritmi e richiedendo cautela nella creazione di set di addestramento per il machine learning.

L'essenziale

Ecco una spiegazione semplice e creativa di questo articolo, pensata per chiunque, anche senza conoscenze tecniche di informatica o matematica.

🚚 Il Grande Inganno delle "Prove di Fuga"

Immagina di essere un allenatore di una squadra di corse di camion. Il tuo obiettivo è trovare il percorso più veloce per consegnare pacchi in diverse città, rispettando orari di consegna molto precisi (le "finestre temporali"). Questo è il Problema del Commesso Viaggiatore con Finestre Temporali.

Per decenni, gli scienziati hanno usato una serie di "prove di gara" classiche (chiamate benchmark) per vedere chi è il miglior algoritmo (il miglior "pilota" o strategia) per risolvere questo problema.

Il problema? Queste prove di gara sono diventate così prevedibili che un algoritmo molto semplice e "stupido" le sta battendo tutte, sembrando un genio, quando in realtà sta solo imbrogliando il sistema.

Ecco cosa ha scoperto l'autore, Francisco Soulignac, usando un'analogia con una caccia al tesoro.

---

1. La Caccia al Tesoro (Il Problema)

Immagina di dover visitare 50 o più case in una città.

• Ogni casa ha una finestra temporale: puoi entrare solo tra le 14:00 e le 14:30.
• Se arrivi alle 13:55, devi aspettare.
• Se arrivi alle 14:31, hai fallito.
• Devi partire da un magazzino, visitare tutte le case e tornare al magazzino il più velocemente possibile.

Ci sono due modi per misurare la vittoria:

1. TSPTW-M (Tempo di completamento): Arrivi al magazzino finale il prima possibile?
2. TSPTW-D (Durata totale): Quanto tempo è passato dal momento in cui hai lasciato il magazzino fino al ritorno?

2. La Scoperta: Il "Trucco" del Pilota Semplice

L'autore ha creato un algoritmo molto semplice (chiamato "Algorithm 2"). È come un pilota che guarda solo indietro (dal punto di arrivo verso il punto di partenza) e cerca di arrivare il più presto possibile, ignorando le complessità che gli altri algoritmi considerano.

Il risultato sorprendente?

• Su tutte le prove classiche con 50 o più case, il suo algoritmo semplice risolve il problema in meno di 10 secondi.
• È così veloce che sembra un miracolo.
• Tuttavia, se provi a usare lo stesso algoritmo su un problema con 30 case ma con finestre temporali molto "lasche" (puoi arrivare in un intervallo di tempo molto ampio), l'algoritmo crolla e non riesce a risolvere nulla.

L'analogia:
Immagina che le vecchie prove di gara siano come un labirinto con muri molto vicini e stretti. Il tuo algoritmo semplice è come un topo che sa che in quel labirinto stretto non può girare, quindi corre dritto in una direzione e vince.
Ma se il labirinto è grande e aperto (finestre temporali ampie), il topo si perde perché non ha la mappa complessa che gli altri topi (algoritmi avanzati) usano.

3. Perché è un Problema? (L'Inganno)

Il punto centrale dell'articolo è un avvertimento:

"Non fidatevi ciecamente di questi risultati!"

Molti ricercatori e aziende stanno usando queste vecchie prove di gara per:

1. Valutare i nuovi algoritmi: Se un nuovo algoritmo batte i record su queste prove, sembra un genio. Ma potrebbe essere solo perché ha imparato a sfruttare i "buchi" di queste prove specifiche, non perché è davvero intelligente.
2. Addestrare l'Intelligenza Artificiale: Molti sistemi di Machine Learning (AI) vengono addestrati su dati generati con le stesse regole di queste vecchie prove. Se l'AI impara a risolvere solo questi labirinti "stretti", fallirà miseramente nel mondo reale, dove le cose sono più caotiche e le finestre temporali più ampie.

È come se un pilota di F1 si allenasse solo su un circuito con curve a 90 gradi fisse. Quando arriverebbe su una pista reale con curve imprevedibili, crollerebbe.

4. Cosa Suggerisce l'Autore?

L'autore ci dice che dobbiamo smettere di usare solo queste vecchie prove. Dobbiamo creare nuove sfide:

• Finestre temporali più "lasche": Come quelle del mondo reale, dove hai più flessibilità.
• Problemi più piccoli ma difficili: A volte, un problema con meno case ma con regole più rigide è molto più difficile da risolvere di uno con mille case ma regole facili.

In Sintesi

• Il Messaggio: Le vecchie "prove di gara" per il problema dei viaggiatori sono diventate obsolete e facili.
• Il Rischio: Chi usa queste prove per testare nuove tecnologie (specialmente l'Intelligenza Artificiale) rischia di ottenere risultati falsi e ottimistici.
• La Soluzione: Dobbiamo creare nuovi test più difficili e realistici, simili a come il traffico reale è imprevedibile, per vedere chi è davvero bravo a guidare.

Conclusione: Non farti abbagliare dai tempi di 10 secondi su vecchi test. Se un algoritmo sembra troppo bello per essere vero su questi dati specifici, probabilmente sta solo "imparando a memoria" il percorso, non sta davvero pensando.

Sommario tecnico

Ecco un riassunto tecnico dettagliato del paper "Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows" di Francisco J. Soulignac, tradotto e strutturato in italiano.

1. Il Problema: TSPTW e le sue Varianti

Il paper affronta il Problema del Commesso Viaggiatore con Finestre Temporali (TSPTW - Traveling Salesman Problem with Time Windows). In questo problema, un veicolo deve visitare un insieme di clienti entro finestre temporali predefinite $[a(v), b(v)]$, partendo e tornando a un deposito. Il veicolo può arrivare in anticipo e attendere, ma non può arrivare in ritardo.

L'autore distingue tre varianti principali in base alla funzione obiettivo:

• TSPTW-M (Makespan): Minimizzare il tempo di completamento del percorso (tempo di ritorno al deposito).
• TSPTW-D (Duration): Minimizzare la durata totale del percorso (tempo tra partenza e ritorno, includendo i tempi di attesa).
• TSPTW-TT (Total Travel Time): Minimizzare solo il tempo di viaggio, escludendo i tempi di attesa.

Il lavoro si concentra principalmente sulle varianti M e D, analizzando l'efficacia degli attuali algoritmi esatti su un set di benchmark classici.

2. Metodologia: Un Risolutore Semplice ed Esatto

L'autore propone un metodo esatto semplice basato su una ricerca informata in avanti (Best-First Search) eseguita in direzione inversa (dal deposito finale verso l'inizio).

Algoritmo Principale (per TSPTW-M)

L'algoritmo (Algoritmo 1) esplora un albero di percorsi parziali partendo dal nodo finale ($n+1$) e aggiungendo nodi in testa al percorso.

• Strategia di Potatura (Pruning):
  • Utilizza una funzione di "nodi irraggiungibili" ($U$) calcolata preventivamente tramite cammini minimi tra tutte le coppie di nodi. Se un nodo non può essere raggiunto prima di una certa soglia temporale, il ramo viene scartato.
  • Dominio: Un percorso parziale $R$ viene scartato se esiste un altro percorso $Q$ con lo stesso set di nodi visitati che offre un'uscita più favorevole (partenza più tarda o arrivo più precoce) rispetto a un limite superiore ($ub$) dato.
• Euristiche: La ricerca privilegia i percorsi che permettono di arrivare al deposito finale il prima possibile, massimizzando la possibilità di attendere ai clienti precedenti senza violare le finestre temporali.
• Risoluzione TSPTW-D (Algoritmo 3): Per la variante durata, l'autore utilizza un approccio a "finestra scorrevole". Esegue ripetutamente il risolutore TSPTW-M su diversi tempi di partenza, aggiornando dinamicamente il limite superiore basato sulla migliore soluzione trovata finora.

3. Contributi Chiave

Il contributo principale del paper non è tanto l'algoritmo in sé (che è concettualmente semplice), quanto la scoperta di un bias critico nei benchmark classici:

1. Inadeguatezza dei Benchmark Classici: Gli istanti classici (50+ clienti) compilati da López-Ibáñez e Blum (2023), che includono set come Lan, Dum, Gen, Ohl, DaS, sono risolvibili in meno di 10 secondi da questo algoritmo semplice.
2. Bias Strutturale: Questi benchmark sono generati con finestre temporali "strette" (basate su percorsi di vicinato) che creano uno spazio di ricerca con una struttura molto definita e ridotta. Questo permette a metodi esatti semplici di eccellere, ingannando la valutazione delle prestazioni.
3. Risultati Contrari alle Aspettative: L'algoritmo proposto risolve istanze grandi (fino a 400 clienti) in pochi secondi, ma fallisce su istanze più piccole (es. 30-40 clienti) se le finestre temporali sono "lasche" (loose), come quelle presenti nei benchmark recenti di Fontaine (2024) e Rifki et al. (2020).
4. Implicazioni per il Machine Learning: Molti dataset di training per algoritmi di ML sono generati con procedure simili a quelle dei benchmark classici. Questo porta a modelli che sembrano performanti ma che potrebbero non generalizzare su problemi reali o istanze più difficili.

4. Risultati Computazionali

L'autore ha testato il suo algoritmo (implementato in C++20) su 1337 istanze totali.

• Sul TSPTW-M:

  • L'algoritmo risolve tutte le istanze classiche con 50+ clienti in meno di 10 secondi ciascuna.
  • Risolve anche le 4 istanze che rimanevano aperte negli studi precedenti (Fontaine et al., 2023).
  • Tuttavia, fallisce su 7 istanze classiche con meno di 50 clienti (dove la memoria si esaurisce) e non risolve alcuna istanza dei benchmark "difficili" (Rif) con finestre temporali lasche ($\beta \in \{0, 0.25\}$).
  • Confronto con lo stato dell'arte (Ler22, Rud23, Fon24): Il metodo proposto è nettamente superiore sui benchmark classici grandi, ma inferiore su quelli con finestre lasche.

• Sul TSPTW-D:

  • Utilizzando il risolutore M come pre-processing, l'algoritmo risolve tutte tranne una delle istanze classiche con 50+ clienti in meno di 30 minuti.
  • Risolve anche le 14 istanze precedentemente irrisolte da Lera-Romero et al. (2022).
  • Anche qui, la facilità di risoluzione è attribuibile alla struttura specifica dei benchmark classici.

5. Significato e Conclusioni

Il paper conclude con un avvertimento severo per la comunità di ricerca:

• Non usare i benchmark classici come unici test: Le istanze classiche (Lan, Dum, Gen, Ohl, DaS) non sono più rappresentative per valutare l'efficienza dei risolutori TSPTW-M e TSPTW-D. La loro struttura permette di ottenere risultati "straordinari" con algoritmi semplici, creando un falso senso di progresso.
• Necessità di Benchmark più Difficili: Per una valutazione corretta, è necessario utilizzare istanze con finestre temporali più lasche (controllate dal parametro $\beta$), come quelle proposte da Fontaine (2024) e Rifki & Solnon (2025). Queste istanze sono più difficili e rivelano le vere capacità degli algoritmi.
• Attenzione per il Machine Learning: I dataset di training generati con procedure simili ai benchmark classici rischiano di produrre modelli che soffrono di overfitting su strutture facili. Si raccomanda di generare dataset con livelli di difficoltà variabili.
• Domanda aperta: Resta incerto se le istanze classiche rappresentino realmente i problemi del mondo reale. Se i problemi reali hanno finestre strette (come in alcuni contesti di stacker crane), l'algoritmo proposto potrebbe essere utile come passo di pre-filtraggio; altrimenti, la ricerca deve spostarsi verso istanze più robuste.

In sintesi, il paper smaschera una vulnerabilità nella metodologia di valutazione attuale, spingendo per un cambio di paradigma verso benchmark che testino la robustezza degli algoritmi su istanze con vincoli temporali meno restrittivi.