Quanto siamo lontani dal minimo dimostrato.
Fino a ieri questa era la casella vuota del sito: si sapeva fin dove il motore arriva, non quanto sia buono il piano che produce. La differenza conta, perché un piano si può sempre confrontare con un avversario scelto da noi. Su queste istanze l’avversario non lo scegliamo: sono problemi pubblici, per alcuni dei quali il minimo assoluto è dimostrato e non è opinabile. Il risultato ha due facce, e una delle due non ci fa comodo.
Campagna del 14 agosto 2026, 60 esecuzioni, 15 istanze pubbliche, cento iterazioni, limite tecnico di 300 secondi, due semi ripetuti due volte. Il metodo era bloccato prima che partisse la prima esecuzione. Tutti i file sono scaricabili.
La risposta in due righe. campagna a · 60 esecuzioni · 36 valide · 14 agosto 2026
Il motore sa mettere in fila le fermate quasi perfettamente, e sa distribuirle fra i mezzi molto peggio. Sono due mestieri diversi dentro lo stesso problema, e questa campagna li separa. Quando c’è un mezzo solo e la domanda è soltanto «in che ordine passo», il motore tocca il minimo dimostrato: su berlin52 lo trova con entrambi i semi, su eil51 e eil76 con uno dei due. Quando i mezzi sono nove o dieci e bisogna anche decidere chi va con chi, resta indietro di circa l’otto e mezzo per cento rispetto alla soluzione migliore mai trovata da chiunque su quel problema.
Un numero di riferimento onesto, prima che lo chieda qualcun altro. Sul CVRP i risolutori dedicati che vincono le competizioni stanno tipicamente entro l’uno o due per cento dal miglior noto. Un otto e mezzo per cento non è un buon numero in quella classifica. È il nostro, ed è qui perché il patto di questo sito è che i numeri si pubblicano anche quando non convengono.
Il contratto di prova
Che cosa era deciso prima di vedere i risultati.
Una misura di qualità è facile da truccare: basta scegliere le istanze dopo, o cambiare un parametro finché il numero migliora, o togliere dal conto le esecuzioni andate male. Per questo il contratto è stato scritto e bloccato prima, ed è dentro il file di configurazione scaricabile con la sua impronta.
Le quindici istanze erano scelte prima. Sette da TSPLIB e otto da CVRPLIB, elencate nella configurazione con nome, dimensione, valore di riferimento e indirizzo di provenienza. Nessuna è stata tolta dopo: le quattro che vanno fuori tempo e le due che non producono alcun piano sono in tabella come le altre.
Le istanze e i riferimenti sono scaricati dalle fonti ufficiali, con l’impronta registrata. Le istanze TSPLIB dall’università di Heidelberg, quelle CVRPLIB dalla PUC-Rio. Per ogni file il risultato registra l’indirizzo, l’ora di scaricamento e l’impronta SHA-256: significa che i valori di riferimento non li abbiamo scritti noi.
La distanza è quella del benchmark, non una nostra. Distanza euclidea intera nella forma prescritta da TSPLIB — (int)(sqrt(dx²+dy²)+0,5) — perché con qualunque altro arrotondamento gli ottimi pubblicati non sarebbero più confrontabili. Il costo minimizzato è soltanto la somma delle distanze: costo fisso per mezzo zero, costo per chilometro zero, costo per ora zero. Un solo termine, altrimenti il confronto non è con lo stesso problema.
Tutti i clienti sono obbligatori, e nessuna penale li rende scartabili. È la trappola più comune di questi confronti: se un cliente può restare non servito pagando una penale, il costo scende e lo scarto sembra migliore. Qui la penale non esiste, e il verificatore controlla che ogni cliente sia servito esattamente una volta.
Le condizioni di calcolo sono quelle delle altre prove del sito. Cento iterazioni, limite tecnico 300 secondi, semi 11 e 29, due ripetizioni ciascuno, MacBook Air M1. Il solutore è routelogic-universal-constrained-ils-v1 versione 2.0.0, invocato dal punto d’ingresso produttivo, e il risultato registra l’impronta dei quattordici file del motore su cui ogni esecuzione è girata.
TSPLIB · l’ordine delle fermate
Contro un minimo dimostrato, e non una stima.
Queste sette istanze hanno un mezzo solo. Non c’è niente da distribuire: c’è solo da decidere in che ordine passare. Il valore di riferimento non è il «migliore trovato finora»: è l’ottimo dimostrato, cioè un numero sotto il quale è matematicamente impossibile andare. Zero per cento vuol dire zero.
51 nodi · 1 mezzo
52 nodi · 1 mezzo
76 nodi · 1 mezzo
100 nodi · 1 mezzo
101 nodi · 1 mezzo
150 nodi · 1 mezzo
280 nodi · 1 mezzo
Come si legge. Dodici esecuzioni valide su tre istanze, e in quattro casi su sei il costo ottenuto coincide cifra per cifra con l’ottimo dimostrato. Lo scarto mediano è zero, il peggiore è lo 0,94% di eil51 con il seme 11. Su berlin52 il minimo esce con entrambi i semi. Non è un risultato che ci mette in classifica fra i risolutori di TSP — un programma specializzato ci arriva in una frazione di questo tempo — ma risponde alla domanda che serviva: la parte del motore che decide l’ordine delle tappe non lascia sul tavolo percentuali significative.
E poi si ferma, e si ferma presto. Da cento nodi in su, nessuna delle quattro istanze conclude entro cinque minuti: né kroA100, né eil101, né ch150, né a280, con nessuno dei due semi e in nessuna delle due ripetizioni. Sedici esecuzioni, sedici volte fuori tempo.
È lo stesso muro che aveva trovato la misura del quarto asse, visto da un’altra angolazione, e adesso ha una spiegazione precisa: il costo non dipende da quante fermate ci sono in tutto, dipende da quante ne ha ogni singolo mezzo. eil76 mette 75 fermate su un mezzo solo e ci impiega 221–234 secondi; A‑n80‑k10 ne mette 79 su dieci mezzi e chiude in 53–59. Stesso numero di fermate, quattro volte il tempo. Il motore paga la lunghezza del singolo giro, non la dimensione del problema. La misura del quarto asse dice la stessa cosa in italiano →
CVRPLIB · l’assegnazione ai mezzi
Qui il numero è peggiore, ed è il numero che conta di più.
Queste otto istanze hanno più mezzi, una portata e una domanda per cliente: sono la forma del problema vero. Il riferimento non è un ottimo dimostrato ma il miglior risultato noto, cioè il migliore che qualcuno abbia mai pubblicato su quel problema; lo scarto vero dall’ottimo è quindi al massimo quello scritto qui, mai di più.
32 nodi · 5 mezzi
44 nodi · 6 mezzi
60 nodi · 9 mezzi
80 nodi · 10 mezzi
50 nodi · 7 mezzi
76 nodi · 4 mezzi
101 nodi · 25 mezzi
200 nodi · 36 mezzi
Come si legge. Ventiquattro esecuzioni valide su sei istanze. Lo scarto mediano è l’8,46%, il peggiore il 13,77%. Il tempo non è il problema: qui il motore chiude in cinque, venti, sessanta secondi, molto sotto il tetto, e nonostante il tempo avanzi non trova di meglio. Non è una misura fermata troppo presto: è il punto in cui la ricerca si ferma da sola, con cento iterazioni. Su A‑n32‑k5 con il seme 29 tocca il miglior noto esatto, e serve a mostrare che il divario non è un difetto di formulazione del problema: quando parte bene ci arriva.
Lo scarto dipende dal seme molto più di quanto dovrebbe. Guarda B‑n50‑k7: con il seme 29 fa +2,02%, con il seme 11 fa +13,77%. Undici punti di differenza sullo stesso problema, cambiando solo il numero da cui parte il generatore casuale. Su A‑n32‑k5 la forbice è fra 0,00% e +7,91%; su A‑n44‑k6 fra +4,06% e +10,89%.
Questo dice una cosa precisa su come funziona il motore: la soluzione finale dipende molto dalla prima assegnazione dei clienti ai mezzi, e le mosse di miglioramento successive non riescono a rimediare a una partenza sfortunata. Il buon comportamento su TSPLIB conferma la lettura: una volta che i clienti sono su un mezzo, il motore li mette in fila benissimo; è la scelta di quali clienti mettere su quale mezzo che resta debole.
Ed è anche la buona notizia, se ce n’è una. Un divario che dipende dal seme è un divario che si riduce lasciando lavorare il motore più a lungo o partendo più volte. La campagna con mille iterazioni e trenta minuti per esecuzione è già programmata, ed è dichiarata qui sotto prima di essere eseguita, così il numero che uscirà non potrà essere una selezione comoda.
Due istanze non producono alcun piano, e questo è un limite vero. Su X‑n101‑k25 e X‑n200‑k36 il motore non va fuori tempo: si ferma in un ottavo di secondo dicendo che un cliente obbligatorio non può essere collocato. Non è lentezza, è una resa immediata, e il codice di errore lo dice per nome: NO_FEASIBLE_INITIAL_SOLUTION.
Il motivo si calcola, e il confine si vede. Il rapporto fra la domanda totale e la capacità complessiva della flotta dice quanto sono pieni i mezzi se tutto va bene:
Il confine sta fra il 97,4% e il 98,6%. Sotto, il motore lavora; sopra, non parte. Su X‑n101‑k25 la domanda totale è 5.147 e la capacità complessiva 5.150: tre unità di margine distribuite su venticinque mezzi. In quelle condizioni il piano esiste — qualcuno lo ha trovato, ed è il valore di riferimento — ma va costruito quasi con un incastro esatto, e la costruzione iniziale del motore non ci arriva: mette i primi clienti dove sembra conveniente e alla fine restano tre o quattro clienti che non entrano più da nessuna parte.
Che cosa significa per un’azienda vera. Che se i mezzi partono pieni al novantotto per cento e la giornata deve incastrarsi al chilo, il motore può rispondere «non ce la faccio» invece di rispondere male — il che è preferibile a un piano sbagliato, ma resta un limite e non una virtù. Sotto quella soglia, che è dove sta la grande maggioranza delle distribuzioni reali, il piano lo produce.
Chi controlla il risultato
Un secondo programma che non usa il solutore.
Uno scarto percentuale è credibile solo se il piano da cui viene è davvero un piano. Quattro controlli girano su ognuna delle 36 esecuzioni valide, dentro un programma diverso da quello che ha prodotto la soluzione, e se uno solo fallisce l’esecuzione non entra fra i risultati.
Ogni cliente servito esattamente una volta
Né saltato né contato due volte. È la trappola più comune di questi confronti: un cliente lasciato fuori abbassa il costo e migliora lo scarto. 36 esecuzioni su 36 superate, zero clienti non assegnati.
La distanza ricalcolata da zero
Il verificatore ricostruisce le distanze dalle coordinate dell’istanza con la formula del benchmark e risomma il percorso, senza guardare il totale dichiarato dal solutore. Il costo pubblicato è quello ricalcolato, non quello dichiarato.
L’obiettivo è solo la distanza
Il controllo verifica che il costo minimizzato coincida con la pura somma delle distanze, senza costi per mezzo, per ora o per chilometro. Se un termine in più entrasse nell’obiettivo, il confronto sarebbe con un problema diverso da quello del benchmark.
Lo stesso seme ridà lo stesso piano
Ogni configurazione è girata due volte. In tutte e diciotto le coppie la seconda esecuzione ha prodotto l’impronta identica alla prima, cifra per cifra: il risultato non dipende da quanto fosse carica la macchina.
Che cosa dimostra. Che i 36 scarti pubblicati vengono da piani completi, validi e ricalcolati da un programma indipendente, su istanze scaricate dalle fonti ufficiali con l’impronta registrata, con il metodo bloccato prima dell’esecuzione e con le esecuzioni fallite pubblicate insieme alle riuscite.
Che cosa non dimostra. Non dice quanto valga il motore con più tempo a disposizione: cento iterazioni sono poche, e la campagna da mille è ancora da eseguire. Non dice come si comporti sulle famiglie di istanze che qui non compaiono, né con finestre orarie o vincoli reali, perché questi benchmark non ne hanno. E non è un impegno sui tempi: su un’altra macchina i secondi sono altri.
Quello che manca ancora
La prossima campagna, dichiarata prima di essere fatta.
Quella qui sopra si chiama campagna (a). Ce n’è una seconda, con le stesse istanze e lo stesso verificatore, e cambia due parametri soli. È scritta qui adesso, prima di partire: quando i numeri usciranno, si potrà controllare che il metodo non sia cambiato per farli sembrare migliori.
Campagna (b) — mille iterazioni, mezz’ora per esecuzione
Stesse quindici istanze, stessi due semi, stesse due ripetizioni, stesso verificatore. Cambiano solo il numero di iterazioni, da cento a mille, e il limite tecnico, da 300 a 1800 secondi. Serve a rispondere a una domanda sola: lo scarto dell’8,5% è un limite del metodo o solo poco tempo di ricerca? Circa quattordici ore di calcolo.
Comportamento su rete stradale vera — non misurato
Questi benchmark usano distanze euclidee su un piano, non strade. È una condizione del confronto e non si può cambiare senza perdere i valori di riferimento, ma vuol dire che questa pagina non dice nulla su come il motore si comporti con una matrice stradale reale. Vale qui come vale per la misura di capacità.
Rifare i conti
I sette file per controllare tutto questo.
La configurazione bloccata prima dell’esecuzione, il file grezzo con tutte e 60 le righe, il registro cronologico, il caso di prova, il lettore delle istanze, il verificatore indipendente e il programma della campagna. Ognuno con la sua impronta SHA-256 dichiarata.
Il file dei risultati contiene tutte e 60 le esecuzioni, comprese le sedici fuori tempo e le otto senza piano, ognuna con esito, secondi, costo, scarto, impronta della soluzione, impronta della verifica indipendente e impronta dei quattordici file del motore. Serve a controllare che le tabelle qui sopra siano quello che è uscito e non una selezione.
Vai agli artefatti scaricabili, con le impronte e i comandi per controllarle →
Dove guardare adesso
Le altre pagine che rispondono a domande diverse.
Fin dove arriva il motore
Questa pagina dice quanto è buono il piano. L’altra dice quanto grande può essere il problema: quattro assi di crescita, con tutte e 34 le famiglie di vincoli accese insieme, e il limite basso che ne esce. Le due misure si spiegano a vicenda. Vai a capacità e limiti →
Il confronto su dati veri
Qui l’avversario è il minimo matematico su problemi inventati da altri. Nel confronto tecnico l’avversario è il giro che un’azienda faceva davvero, su cinque giornate reali. Vai al confronto tecnico →