Come Nigin costruisce e confronta un piano di consegna.
La domanda «quali consegne a quale mezzo, e in quale ordine» ha un nome nella ricerca operativa: Vehicle Routing Problem, cioè problema di instradamento dei veicoli. Viene studiata dal 1959. Nigin applica quel quadro ai tuoi dati, ai tuoi mezzi e alle regole che dichiari.
In questa pagina capisci come viene prodotto e documentato il confronto, e perché lo stesso calcolo, sugli stessi dati, deve poter dare lo stesso risultato.
Il confronto misura ciò che emerge nel perimetro analizzato. Non dimostra automaticamente l'ottimo globale e non garantisce un miglioramento.
01 — Il problema
Un piano operativo può funzionare senza essere stato confrontato con un'alternativa calcolata.
Molte aziende consegnano ogni giorno con esperienza, fogli di calcolo, gestionale, mappe, regole interne e conoscenza degli autisti. Tutto questo ha valore ed è necessario per definire dati e vincoli realistici.
Esperienza
Rappresenta eccezioni, consuetudini e conoscenza operativa. È necessaria per definire dati e vincoli realistici, ma da sola non quantifica il delta rispetto a un'alternativa.
Calcolo
Costruisce e valuta piani alternativi sotto gli stessi ordini, provider, criteri e vincoli dichiarati.
Decisione
Spetta all'azienda sulla base del confronto documentato, dei limiti dichiarati e dell'applicabilità operativa.
Funzionare non equivale a essere stato confrontato. Senza un confronto controllato non è possibile attribuire con precisione il delta tecnico alla diversa assegnazione o sequenza. L'effetto economico richiede inoltre costi e assunzioni separati.
02 — La storia
Questa matematica non nasce oggi.
Alcune tappe della disciplina. Non è una cronologia completa né esaustiva: è una selezione di riferimenti utili a inquadrare il problema. Il testo di ogni tappa è riportato per esteso qui sotto, e non dipende dall'interazione.
The Truck Dispatching Problem
Uno dei lavori fondativi del Vehicle Routing Problem, formulato nel contesto della distribuzione di carburante.
- 1959Dantzig e Ramser — The Truck Dispatching ProblemUno dei lavori fondativi del Vehicle Routing Problem, formulato nel contesto della distribuzione di carburante.
- 1964Clarke e Wright — Savings AlgorithmUna delle prime euristiche costruttive ampiamente utilizzate: unisce percorsi quando l'unione produce un risparmio.
- Sviluppo successivoRicerca localeMetodi che partono da una soluzione e la migliorano con modifiche locali, per esempio scambiando archi del percorso.
- Sviluppo successivoMetaeuristicheStrategie di livello superiore che guidano la ricerca tra più soluzioni e possono aiutare a uscire da ottimi locali.
- OggiSistemi moderniSistemi che combinano un solver, un modello di vincoli, i dati operativi dell'azienda e metriche calcolate da provider di routing.
03 — Il VRP
Il problema riguarda assegnazione, sequenza e vincoli.
Un VRP stabilisce quali mezzi servono quali ordini e in quale sequenza, sotto capacità, tempi, compatibilità e altre regole configurate. Il risultato deve indicare anche eventuali ordini non serviti, esclusioni, warning e infeasibilità.
Assegnazione e sequenza possono influire su distanza, durata stimata, utilizzo dei mezzi e fattibilità. Restano elementi distinti la scelta degli ordini da includere, l'assegnazione ai mezzi, l'ordine delle fermate, gli orari, i carichi, i vincoli e l'obiettivo.
L'obiettivo non è necessariamente soltanto minimizzare i chilometri: può includere durata, costi dichiarati, uso dei mezzi, penalità e ordini non assegnati, secondo la configurazione. Non ogni obiettivo è attivo in ogni esecuzione.
04 — La combinatoria
Perché l'enumerazione completa diventa impraticabile.
Un esempio combinatorio semplificato
Il cursore conta i punti totali, di cui il primo è il deposito fisso. Con n punti totali le sequenze cicliche distinte sono (n − 1)! / 2.
Scritto per esteso, con le fermate cliente al posto dei punti totali:
Con 10 fermate cliente: 10! / 2 = 1.814.400 sequenze
Con 14 fermate cliente: 14! / 2 = 43.589.145.600 sequenze
Ipotesi del calcolo, tutte necessarie. Il deposito è fisso; è considerato un solo mezzo; ogni fermata viene visitata una volta; i percorsi inversi sono considerati equivalenti; il modello è simmetrico. Si tratta di un esempio combinatorio semplificato: un VRP reale con più mezzi, vincoli, ordini opzionali o costi asimmetrici ha uno spazio delle soluzioni differente. Questi numeri non sono il conteggio universale di ogni VRP.
L'enumerazione completa diventa rapidamente impraticabile e non rappresenta il metodo usato dal solver produttivo. Il solver non enumera necessariamente tutte le alternative: esplora selettivamente lo spazio secondo l'obiettivo e i vincoli configurati.
05 — Scelta locale e piano complessivo
Una scelta locale non valuta automaticamente il piano complessivo.
Nearest neighbor sceglie ogni volta la fermata più vicina secondo il criterio adottato. Può essere utile come costruzione iniziale, ma non valuta necessariamente assegnazione, vincoli ed effetto complessivo sul piano.
Illustrazione didattica, non esecuzione del solver produttivo e non benchmark
Nearest neighbor
Riordino della sequenza
Sceglie il punto successivo più vicino, una decisione alla volta. Può produrre attraversamenti e rientri lunghi.
Valuta la sequenza nel suo insieme e confronta alternative, sulla stessa istanza e con lo stesso criterio di distanza.
Che cosa mostrano davvero queste due illustrazioni. I punti sono generati nel browser su un piano astratto, con distanze geometriche e non stradali. Rappresentano una sola sequenza chiusa, un solo mezzo e nessun vincolo: non mostrano assegnazione tra mezzi, capacità, finestre o fattibilità. L'istanza viene inoltre selezionata fra alcune generate, per rendere visibile la differenza fra i due percorsi. Non sono un'esecuzione del motore produttivo, non sono una misura di prestazione e non sono un benchmark. Con le preferenze di riduzione del movimento attive non vengono disegnate: il testo di questa sezione resta l'informazione principale.
06 — Euristiche e metaeuristiche
Una buona regola pratica non è una prova di efficienza.
Euristica
Metodo pratico che costruisce o migliora una soluzione senza enumerare necessariamente tutto lo spazio. Esempi: nearest neighbor, savings, sweep, 2-opt.
Metaeuristica
Strategia generale che guida la ricerca tra più soluzioni e può aiutare a uscire da ottimi locali. Esempi: ILS, Tabu Search, Simulated Annealing, ALNS.
ILS
Iterated Local Search è una metaeuristica che alterna ricerca locale e perturbazioni, conservando la migliore soluzione trovata.
ILS è una strategia euristica nota nella letteratura e può essere utilizzata come componente di ricerca. Non coincide, da sola, con l'intero motore produttivo Nigin. Il motore produttivo è un motore VRP vincolato che orchestra assegnazione, sequenza, fattibilità e confronto di scenario: la ricerca è uno dei suoi componenti, accanto alla compilazione del problema, all'applicazione dei vincoli e a una verifica interna di fattibilità separata dal ciclo di ricerca.
07 — Il confine del metodo
Migliore soluzione trovata non significa ottimo globale.
Il motore utilizza ricerca euristica: esplora selettivamente soluzioni alternative e conserva i risultati migliori trovati secondo l'obiettivo configurato. Non costituisce una prova automatica di ottimo globale.
Che cosa il risultato dichiara
- La migliore soluzione trovata fra quelle esplorate
- Sotto l'obiettivo e i vincoli effettivamente configurati
- Nel perimetro e con i dati dichiarati
Che cosa non dichiara
- Che non esista una soluzione migliore
- L'ottimo globale del problema
- Un risultato trasferibile ad altri perimetri
Il risultato deve essere letto insieme a versione del motore, configurazione, provider, obiettivo, vincoli attivati, ordini serviti e non serviti, warning, assunzioni e limiti. Il report documenta i campi effettivamente previsti dal formato e dal perimetro concordato, non necessariamente ogni parametro interno dell'esecuzione.
08 — Come leggere ogni numero
Nel report, ogni numero dichiara che cosa è.
Un chilometro rilevato da un odometro, un chilometro calcolato da un provider di routing e un euro stimato non hanno la stessa forza. Per questo ogni valore appartiene a una categoria dichiarata.
| Categoria | Significato e limite |
|---|---|
| 1 · Dato osservato o fornito | Valore proveniente direttamente dai dati aziendali o da una misurazione dichiarata: ordini, fermate, mezzo assegnato, sequenza, orari registrati, chilometri da odometro quando disponibili. La provenienza deve essere indicata. Un dato fornito dal cliente non diventa automaticamente verificato da Nigin. |
| 2 · Metrica di routing calcolata | Distanza o durata prodotta dal provider sulla rappresentazione digitale della rete, con profilo e configurazione dichiarati. La durata è una stima del provider. La distanza di routing non è automaticamente una distanza realmente percorsa. |
| 3 · Metrica derivata | Valore ottenuto mediante una formula dichiarata, per esempio differenza assoluta o percentuale rispetto alla baseline. |
| 4 · Assunzione | Parametro fornito dal cliente o concordato per il calcolo: capacità, costo orario, consumo, tempo di servizio, frequenza o altra ipotesi. Deve essere distinta da una misurazione. |
| 5 · Stima economica | Valore in euro calcolato applicando assunzioni economiche a un risultato tecnico. Non equivale a un risparmio realizzato. |
| 6 · Proiezione | Estensione di una misura o stima a un periodo più lungo. È valida soltanto sotto le ipotesi dichiarate e non dimostra che ordini, traffico, costi o operatività restino costanti. |
Una stessa grandezza, come i chilometri della baseline, può avere natura diversa a seconda della provenienza: odometro osservato, traccia GPS, ricostruzione tramite routing o altro dato fornito. La categoria segue la provenienza, non il nome della grandezza.
09 — L'architettura del metodo
Dai dati al confronto documentato.
Questa è la vista metodologica: i blocchi concettuali di cui si compone il metodo. Non è una versione alternativa del percorso tecnico dei dati, descritto passo per passo in Come funziona, né delle fasi operative del pilota.
- Dati e baselineOrdini, mezzi, depositi, sequenze, quantità e regole disponibili. I dati strutturati possono avere formati diversi; il CSV è uno dei possibili.
- NormalizzazioneControllo dei campi, interpretazione delle regole, unità, assunzioni e dati mancanti.
- RoutingCostruzione delle matrici di distanza e durata tramite il provider configurato.
- Motore VRP vincolatoAssegnazione, sequenza, obiettivo e vincoli.
- VerificaFattibilità, ordini serviti e non serviti, warning e limiti.
- ConfrontoBaseline e scenario sotto criteri comparabili.
- OutputReport e artefatti previsti dal perimetro.
L'esito è un confronto documentato fra due piani sul medesimo perimetro, non un benchmark fra prodotti o fra aziende.
10 — Il confronto equo
La baseline deve essere ricostruibile.
La baseline indica quali ordini sono stati assegnati a ciascun mezzo e in quale sequenza, per quanto disponibile nei dati. Assunzioni, dati mancanti, esclusioni e correzioni vengono dichiarati.
Quando distanza e durata sono ricalcolate, baseline e scenario devono usare lo stesso provider, lo stesso profilo, gli stessi endpoint e gli stessi criteri di misura.
Il confronto deve distinguere ordini sottoposti all'analisi, ordini serviti, ordini non serviti, ordini esclusi, ordini non fattibili, mezzi utilizzati e vincoli applicati.
Non viene presentata come miglioramento equivalente una soluzione che serve meno ordini, cambia il deposito, usa mezzi aggiuntivi, modifica i dati di domanda, ignora vincoli o usa un provider differente: ogni differenza di questo tipo va dichiarata.
11 — Provider e motore
Routing sulla rete digitale, non semplice distanza in linea d'aria.
HERE e OSRM calcolano percorsi e matrici sulla rappresentazione digitale della rete. Nigin usa queste metriche per costruire e confrontare piani. Il risultato dipende da dati cartografici, profilo, configurazione, data e capacità del provider.
HERE / OSRM
Calcola percorsi, distanze e durate stimate sulla rete digitale disponibile. Non misura direttamente la realtà fisica e non decide l'assegnazione o la sequenza.
Motore VRP vincolato
Usa matrici e dati operativi per cercare assegnazioni e sequenze fattibili sotto i vincoli configurati. Cerca una soluzione migliore secondo l'obiettivo configurato; non dichiara un ordine ottimale.
La metafora corrente — il provider come strumento di misura, il motore come strumento di decisione — è utile ma imprecisa: il provider stima, non misura sul campo, e il motore propone, non decide al posto dell'azienda.
Integrato, configurato, disponibile, usato: quattro stati distinti
| Provider | Stato verificato |
|---|---|
| HERE | HERE è supportato dall'orchestrazione del routing. Nell'esecuzione tecnica documentata più sotto è stato selezionato, interrogato e ha restituito il risultato registrato. Ciò non equivale a dichiararlo disponibile o attivo in ogni esecuzione futura: le funzioni effettivamente utilizzabili dipendono dal servizio attivato, dai limiti e dai dati del provider. |
| OSRM | OSRM è supportato per il calcolo di percorsi e matrici su dati OpenStreetMap; nell'esecuzione tecnica documentata non è stato interrogato. Profilo, dataset, aggiornamento e infrastruttura incidono sul risultato. Il traffico live non è una funzione nativa standard di OSRM. |
Fallback. Il flusso distingue provider richiesto, provider effettivamente usato, eventuale fallback, motivo del fallback e ricorso a una modalità geometrica. Queste informazioni sono presenti nel record tecnico dell'esecuzione. Un fallback geometrico non equivale a routing stradale. Baseline e scenario devono essere confrontati sotto la stessa modalità di routing, salvo differenza esplicitamente documentata, e risultati prodotti con provider diversi non sono direttamente confrontabili senza dichiararlo.
12 — Un'esecuzione documentata
Demo tecnica interna su dati dimostrativi.
Esecuzione interna su un file dimostrativo, utilizzata per documentare il percorso di calcolo configurato. Non è un caso cliente, non rappresenta un risultato tipico e non dimostra l'ottimo globale.
File dimostrativo · calcolo su rete tramite provider HERE
● road-based-hereAritmetica per esteso: 13,09 − 10,43 = 2,66 km; 2,66 / 13,09 × 100 = 20,32%; il valore registrato nel record è arrotondato all'intero, −20%.
Che cosa documenta e che cosa no. Documenta che il percorso di calcolo su rete tramite il provider HERE è stato eseguito su un file dimostrativo, senza fallback, con i depositi bloccati. Il sequenziamento è stato prodotto da un componente locale di riordino di una singola sequenza: non è un'esecuzione del motore VRP vincolato con assegnazione multi-mezzo e catalogo dei vincoli, e non va letta come tale. Non è un caso cliente, non è un risultato tipico, non è una prova generale del motore.
13 — Risultato tecnico ed effetto economico
Il metodo produce un confronto tecnico. L'effetto economico richiede assunzioni ulteriori.
Una distanza inferiore o una durata stimata inferiore non equivalgono automaticamente a un risparmio economico realizzato.
Costi dei mezzi, personale, carburante, pedaggi, contratti e applicazione operativa restano elementi distinti, e le assunzioni economiche vengono dichiarate separatamente dal risultato tecnico.
Validazione tecnica interna e riproducibile nel perimetro dichiarato. Non è una certificazione esterna, una certificazione ISO o una prova di ottimo globale. Il superamento dei controlli interni previsti non rende il motore certificato, formalmente provato, sempre corretto o infallibile.
Dalla teoria ai tuoi numeri
Vediamo se il confronto ha senso sul tuo caso.
Si parte da un contatto: capiamo insieme quali dati esistono, quali regole possono essere formalizzate e quale perimetro ha senso analizzare.