Trovare il cammino di peso totale minimo tra due nodi su un grafo pesato — nelle varianti single-source single-destination, single-source all-destinations o all-pairs. Problema fondazionale grafo-OR; algoritmi classici: Dijkstra, Bellman-Ford, Floyd-Warshall. L'algoritmo OR più invocato nell'industria moderna.
In breve
Ti suona familiare?
- Siamo un operatore nazionale di routing pacchi — per 5.000-50.000 pacchi/giorno servono rotte di tempo minimo dal deposito centrale agli indirizzi dei clienti; serve ottimizzazione multi-criterio tra tempo, distanza e carburante.
- Operiamo un servizio urbano sul campo con 10-50 veicoli (idraulica, elettricità, riparazione elettrodomestici, HVAC); calcoliamo i tempi cliente-cliente e vogliamo un motore di calcolo consapevole del traffico.
- Siamo un centro comunale di gestione del traffico; vogliamo un ponte tra dati di congestione in tempo reale e la rete cartografica statica per fornire cammino minimo consapevole del traffico per i servizi di emergenza (ambulanza, vigili del fuoco, polizia).
- Siamo pianificatori di rete dorsale di telecomunicazioni; calcoliamo il cammino di inoltro pacchetti a minore latenza tra due switch (o due POP); protocolli di routing come OSPF (Open Shortest Path First) eseguono questo calcolo sotto.
- Siamo pianificatori di supply chain; in una rete fabbrica-porto-deposito-cliente serve il costo di flusso minimo tra ogni coppia di nodi (all-pairs shortest path) — tra opzioni di trasporto multi-modale.
- Operiamo un'autostrada o una società di trasporti; per il routing su lunga distanza eseguiamo un cammino minimo a tre criteri (carburante + pedaggio + ore di guida); il grafo statico non basta, cerchiamo cammino minimo tempo-dipendente.
- Il team software ha iniziato con un'implementazione diretta di Dijkstra, ma le query in tempo reale su grafi grandi (1M+ nodi, rete stradale nazionale) sono troppo lente — valutiamo soluzioni basate su pre-processing (contraction hierarchies).
Perché è importante
Come si risolve
Profondità tecnica
Come si risolve
Profondità tecnicaIn una frase: Dati nodi (incroci) + archi pesati (distanza/tempo), usa Dijkstra quando gli archi sono non negativi (ad ogni passo scegli il vicino più vicino e aggiorna le distanze dei vicini), Bellman-Ford quando sono possibili archi negativi, Floyd-Warshall quando serve una matrice di distanze all-pairs — ciascuno garantisce l’ottimo.
Questo problema è studiato nella letteratura di Ricerca Operativa (disciplina che usa matematica e informatica per risolvere decisioni di business) come Shortest Path Problem (SPP — problema del cammino minimo) — il problema grafo-OR fondazionale, con 60+ anni di maturità. Tre varianti principali: single-source single-destination (un punto-punto), single-source all-destinations (da una sorgente a tutti i destini), all-pairs (ogni coppia). Gli algoritmi classici fondazionali risalgono agli anni 50-60: Dijkstra per grafi a pesi non negativi, Bellman-Ford per archi negativi, Floyd-Warshall per all-pairs; le moderne contraction hierarchies basate su pre-processing raggiungono tempi di query sub-millisecondo su reti viarie a scala nazionale. Tre fasi:
1. Modellazione. Dati in ingresso: (a) struttura del grafo — insieme nodi V (incroci, ubicazioni, switch), insieme archi E (strade, collegamenti), pesi w(u,v) (distanza, tempo, costo, latenza), grafo orientato (senso unico) o non orientato (doppio senso), pesi non negativi o possibilmente negativi, con o senza cicli negativi, (b) tipo di query — singolo punto-punto (sorgente s, destinazione t), single-source all-destinations (sorgente s, destinazione V), all-pairs (ogni coppia i,j), (c) dinamicità — pesi statici, tempo-dipendenti (traffico variabile con l’ora del giorno) o con aggiornamenti in tempo reale (chiusure per incidenti, meteo), (d) multi-criterio — mono-obiettivo (solo tempo) o multi-obiettivo (tempo + distanza + carburante + pedaggio); multi-obiettivo con cammini Pareto-ottimi o somma pesata, (e) vincoli — divieti per tipo di strada (camion non può entrare in alcune strade, ambulanza esente), finestre orarie (orario lavorativo), capacità (carico da trasportare). Variabili decisionali: sequenza di archi sul grafo (s → … → t), variabile per arco “in cammino o no”. Obiettivo: somma minima dei pesi.
2. Decisione guidata dal solver. La scelta dell’algoritmo dipende da grafo e tipo di query:
(a) Dijkstra — archi non negativi, single-source. Greedy (in ogni passo scegli la migliore opzione locale): a ogni passo estrarre il nodo non visitato con la minima distanza tentativa da una coda di priorità e aggiornare le distanze dei suoi vicini. Implementazione binary heap O((V+E)logV), Fibonacci heap O(E + V logV). In pratica: single-source single-destination / single-source all-destinations, grafi statici piccolo-medi (1K-100K nodi).
(b) Bellman-Ford — supporta archi negativi. Rilassamento (re-check di ogni arco per “c’è ora un cammino più breve?”) su tutti gli archi V-1 volte. Complessità O(VE). Rilevamento di ciclo negativo: se all’iterazione V c’è ancora un aggiornamento, esiste un ciclo negativo e il cammino minimo è indefinito. Uso: grafi con archi negativi (arbitraggio finanziario, contro-flusso in reti di flusso), protocolli di routing distance-vector.
(c) Floyd-Warshall — all-pairs, grafo piccolo. Programmazione dinamica: O(V³) tempo, O(V²) memoria. In pratica: V ≤ 1.000 nodi, quando serve all-pairs. Supporta archi negativi (senza cicli).
(d) A — punto-punto guidato da euristica.* Variante diretta all’obiettivo di Dijkstra; un’euristica h(v) (per es. distanza euclidea / cerchio massimo) guida le priorità dei nodi. Hart, Nilsson e Raphael (1968). In pratica: single-source single-destination su reti stradali geografiche, pathfinding su mappe di gioco. In media più rapido di Dijkstra; se l’euristica è ammissibile (h ≤ distanza vera) l’ottimo è garantito.
(e) Ricerca bidirezionale. Eseguire Dijkstra/A* in avanti dalla sorgente e all’indietro dall’obiettivo; fermarsi quando le due ricerche si incontrano. Tipicamente 2-4x più rapido del Dijkstra unidirezionale.
(f) Contraction Hierarchies (Geisberger et al. 2008) — moderno basato su pre-processing per reti stradali nazionali. Il grafo è pre-processato una volta (i nodi sono ‘contratti’ in ordine gerarchico, aggiungendo scorciatoie); ogni query successiva è risposta in tempo sub-millisecondo. Approccio standard sul campo per navigazione in tempo reale su reti stradali nazionali (10M+ archi). ALT (A*, Landmarks, Triangle inequality), Transit Node Routing e Hub Labels sono altri metodi moderni basati su pre-processing.
(g) Cammino minimo tempo-dipendente — consapevole del traffico. I pesi degli archi sono funzioni del tempo w(u,v,t); il tempo di percorrenza dipende dall’ora di partenza t. Dijkstra statico si generalizza; se la proprietà FIFO è valida (partenza più tardi — arrivo non prima), il problema è polinomiale. In pratica: un motore di routing alimentato da dati di previsione del traffico.
(h) Cammino minimo stocastico. Pesi degli archi come variabili aleatorie (per es. distribuzione del traffico); cammino minimo in valore atteso o aggiustato per rischio (CVaR); Polychronopoulos-Tsitsiklis (1996).
3. Integrazione sul campo. Output a tre livelli: (a) operativo — visualizzazione della rotta indirizzo a indirizzo nell’app mobile dell’autista / rotta di consegna pacchi / app del tecnico sul campo, integrata con la navigazione, (b) pianificazione — la matrice del cammino minimo è chiamata come subroutine sotto l’ottimizzazione VRP/TSP nel software giornaliero di pianificazione rotte, (c) strategico / analitico — analisi di rete supply chain, rapporti di colli di bottiglia di rete telco, matrice all-pairs di distanza / tempo per il supporto alle decisioni. Integrazione upstream: ERP (indirizzi degli ordini), TMS (sistema di gestione trasporti), servizio mappe (geocoding + dati rete stradale), servizio dati di traffico (previsione in tempo reale), dati GPS di tracciamento flotta. Comitato operativo trimestrale: volume di query di cammino minimo, tempo medio di query, deviazione della previsione di traffico (reale vs piano), tasso di cambio rotta (trigger di ricalcolo).
Alternative
Manuale + servizio di mappe + esperienza dell'autista
GratuitoServizio mappe in fascia gratuita, costo di sviluppo zero
Per chi: Operazione piccola (1-10 veicoli/giorno), 10-50 fermate/veicolo, rotte statiche note
- + Zero investimento software
- + Conoscenza di campo dell'autista pesa
- + Risposta telefonica al traffico in tempo reale
- − Nessuna garanzia di ottimo, rotta intuitiva gonfia la distanza del 15-30%
- − Nessun calcolo multi-criterio (tempo + carburante + pedaggio)
- − Nessuna acquisizione dati — la performance non si misura
- − Oltre 10 veicoli la capacità del pianificatore è superata
API di servizio mappe + integrazione interna
cloudPrezzo per query; €0,003-0,01/query, a 50K pacchi/giorno €2K-7K/mese
Per chi: Operazione media (50-500 veicoli, 50K-500K fermate/giorno), query consapevoli del traffico
- + Dati di traffico maturi integrati
- + Geocoding indirizzi integrato
- + API facile da consumare, tempo di sviluppo breve
- − Costo per query caro a volumi alti
- − Algoritmo a scatola nera, controllo limitato
- − Lock-in con il fornitore (contratto del servizio mappe)
- − Non scala per query all-pairs / matrice grande
Motore open-source di rete stradale + server propri
Open SourceLicenza gratuita; sviluppo interno + server 6-12 settimane o €80K-250K consulenza + €15K-50K/anno infrastruttura
Per chi: Operazione con team tecnico, alto volume di query (1M+/giorno), vincoli specializzati (divieti per tipo di strada per camion)
- + Nessun costo di licenza, nessuna tariffa per query
- + Scelta dell'algoritmo sotto controllo proprio (Dijkstra, A*, contraction hierarchies)
- + Vincoli specializzati (accesso camion, esenzione ambulanza) incorporabili
- + Sovranità del dato in azienda
- + 30+ tesi TR (YÖK) come implementazioni di riferimento
- − Dati rete stradale (qualità OpenStreetMap) richiedono aggiornamenti periodici
- − I dati di traffico richiedono un fornitore separato
- − Specialista OR interno + team infrastruttura indispensabili
- − Da prototipo accademico a produzione: 3-6 mesi
Piattaforma internazionale di routing / TMS
Aziendale€300K-2M licenza + €100K-500K/anno manutenzione
Per chi: Grande operazione (500+ veicoli, multi-sede, 1M+ fermate/giorno), integrazione TMS completa
- + Modulo maturo di cammino minimo + VRP integrato
- + Multi-criterio (tempo + costo + carburante + pedaggio) standard
- + Varianti tempo-dipendenti + stocastiche supportate
- + Servizio di traffico nel pacchetto
- − Licenza alta + lunga (12-24 mesi) implementazione
- − La calibrazione locale della rete stradale allunga il progetto
- − Algoritmo a scatola nera — controllo limitato dei parametri di pre-processing
- − Alto rischio di lock-in con singolo fornitore
Raccomandazione
Chiedi nell'incontro
- Quale approccio usa l'algoritmo di cammino minimo — Dijkstra (binary heap, Fibonacci heap), A*, ricerca bidirezionale, contraction hierarchies, ALT? Qual è il tempo medio di query su rete stradale nazionale (10M+ archi)?
- Sono supportati archi negativi (Bellman-Ford)? C'è rilevamento di cicli negativi? In quali scenari (arbitraggio finanziario, contro-flusso) si ricorre a Bellman-Ford?
- È supportato cammino minimo tempo-dipendente (consapevole del traffico)? Da quale fonte arrivano i dati di traffico, con quale frequenza (5-min, 15-min, oraria)? La proprietà FIFO è garantita?
- Da dove vengono i dati di rete stradale (OpenStreetMap, servizio mappe commerciale, inventario stradale nazionale)? Qual è il ciclo di aggiornamento? Come sono modellati i tipi di strada (autostrada, strada divisa, urbana, accesso pesante) come vincoli?
- È supportato all-pairs shortest path (Floyd-Warshall, Johnson), fino a quale scala (quanti nodi)? Come si produce la matrice all-pairs per l'analisi di rete supply chain?
- È supportata l'ottimizzazione multi-criterio (tempo + distanza + carburante + pedaggio) — somma pesata o cammini Pareto-ottimi? L'utente può regolare i parametri multi-obiettivo?
- In un pilota con dati operativi reali (8-12 settimane), quale rapporto di risparmio si può produrre rispetto alla rotta manuale / sistema esistente — carburante, tempo di consegna, ore autista, tasso di cambio rotta?
- Se il contratto finisce, in quale formato standard (GeoJSON, GraphML, CSV) possiamo esportare i dati di rete stradale, i dati di calibrazione del traffico, lo storico delle query e l'archivio delle rotte?
Dettagli tecnici
Nota dell’editore
Nel linguaggio comune questo problema si chiama “percorso più breve”, “calcolo rotta” o “navigazione”. Nella letteratura accademica il nome canonico è Shortest Path Problem (SPP), il problema grafo-OR fondazionale. Edsger Dijkstra (1959), in un articolo di due pagine su Numerische Mathematik, definì un algoritmo polinomiale per grafi a pesi non negativi — questo articolo è tra i più citati in informatica. Richard Bellman (1958), su Quarterly of Applied Mathematics, introdusse Bellman-Ford con supporto agli archi negativi. Robert Floyd (1962), su Communications of the ACM algoritmo 97 (articolo di un paragrafo), sviluppò all-pairs Floyd-Warshall. Ahuja, Magnanti e Orlin (1993) Network Flows è il manuale canonico. Gli approcci moderni basati su pre-processing (Geisberger et al. 2008 — contraction hierarchies) consegnano tempi di query sub-millisecondo su reti stradali nazionali.
Differenza con #068 (TSP): TSP è il problema tour su tutti i nodi — visitare ciascuno degli N nodi esattamente una volta e tornare all’inizio, NP-difficile, il problema fondazionale dell’ottimizzazione combinatoria. Shortest path è punto-punto singolo o single-source all-destinations — polinomiale (Dijkstra O((V+E)logV), Bellman-Ford O(VE), Floyd-Warshall O(V³)). Il gap di complessità è grande: per un grafo di 1.000 nodi Dijkstra finisce in millisecondi, TSP gira ore-giorni. TSP chiama shortest path come subroutine: la matrice di distanze a coppie è calcolata con shortest path, poi TSP risolve il tour sopra.
Differenza con #069 (CVRP): CVRP è routing di flotta con capacità — più veicoli, vincolati in capacità, clienti serviti collettivamente. CVRP chiama shortest path come subroutine: distanze cliente-cliente e deposito-cliente calcolate con shortest path, poi CVRP risolve l’assegnazione veicolo-cliente + sequenza. In questo stack shortest path ricopre il ruolo “riempi la matrice dei pesi del grafo” e CVRP il ruolo “assegnazione + sequenziamento”.
Differenza con #002 (VRPTW): VRPTW è routing di flotta con finestre temporali — più veicoli, vincoli di capacità + finestre. Anche VRPTW chiama shortest path come subroutine. Se si incorpora cammino minimo tempo-dipendente in VRPTW, si ottiene routing di flotta consapevole del traffico.
Punto più trascurato sul campo: rilevamento di archi o cicli negativi. Il praticante usa Dijkstra in ogni caso; ma se c’è un costo negativo (per es. sconto su una connessione, ritorno di capitale, rimborso per contro-flusso, un arco logaritmico negativo in un ciclo di arbitraggio valutario) Dijkstra non è ottimo — restituisce un risultato silenziosamente errato. Serve Bellman-Ford. Se c’è un ciclo negativo il cammino minimo è indefinito (il ciclo si può percorrere indefinitamente, riducendo la somma a ogni giro). In molti scenari di arbitraggio finanziario / flusso di rete / contro-flusso questo bug è silenzioso. Bellman-Ford rileva un ciclo negativo se all’iterazione V c’è ancora un aggiornamento.
Secondo punto trascurato: scelta della complessità algoritmica. Il praticante dice “Dijkstra funziona ovunque”; ma su una rete stradale nazionale (10M+ archi) una singola query classica di Dijkstra dura secondi — inaccettabile per la navigazione in tempo reale. Gli approcci moderni basati su pre-processing (contraction hierarchies — Geisberger et al. 2008, Transit Node Routing, Hub Labels) consegnano tempi di query sub-millisecondo; il pre-processing è un costo una-tantum (ore-giorni) ma ogni query successiva è rapida. Terzo punto trascurato: ipotesi di grafo statico. Il traffico cambia in tempo reale; il cammino minimo su grafo statico segna “ottimo per le 14:00” ma crolla nell’ora di punta delle 17:00. Cammino minimo tempo-dipendente (peso dell’arco in funzione del tempo) o ricalcolo rolling-horizon è indispensabile.
Percorso passo passo per PMI
Fase 1 — Misura prima, pianifica dopo. Almeno 6 mesi di dati di query / rotte: volume giornaliero (quante query A-B, quante all-pairs), tempo medio di query, deviazione previsione traffico (tempo pianificato vs reale), tasso di cambio rotta (trigger di ricalcolo). Inventario rete stradale: sorgente (servizio mappe, OpenStreetMap, inventario proprio), qualità (copertura, freschezza, tipo di peso — distanza / tempo / costo), tipo di strada (autostrada, divisa, urbana, accesso pesante). Sorgente dati di traffico: nessuna / nel pacchetto del servizio mappe / fornitore separato / dati GPS della propria flotta.
Fase 2 — Costruisci la matrice degli algoritmi. Profilo delle query: prevalentemente punto-punto singolo, single-source all-destinations, analisi all-pairs? Scenari ad archi / cicli negativi (arbitraggio finanziario, contro-flusso)? Scala del grafo: 1K, 10K, 100K, 1M, 10M+ nodi? Requisito di tempo di query: sub-millisecondo (navigazione in tempo reale), secondi (pianificazione), minuti (analisi strategica)? Scegli l’algoritmo da questa matrice: Dijkstra (piccolo-medio, non negativo), Bellman-Ford (archi negativi), Floyd-Warshall (all-pairs piccolo), A* (rete stradale geografica), contraction hierarchies (nazionale in tempo reale).
Fase 3 — Pilota. 8-12 settimane. Esegui il nuovo motore di cammino minimo su un sottoinsieme dell’operazione (per es. la regione più carica o il segmento di clienti con più query); la decisione resta al pianificatore / autista, il motore raccomanda. Criterio di successo scritto in anticipo: nella regione pilota carburante -10% minimo, tempo di consegna -15% minimo, il tempo di query soddisfa il requisito tempo reale.
Fase 4 — Rollout. 6-12 mesi per estendere all’operazione completa + integrazione con servizio traffico + ricalcolo rolling-horizon. Comitato operativo trimestrale: volume di query di cammino minimo, tempo medio di query, deviazione previsione traffico, tasso di cambio rotta, rapporto colli di bottiglia (analisi all-pairs).
Rischi — cosa può andare storto
Deviazione previsione traffico (rischio del grafo statico). Il cammino minimo su grafo statico non riflette le condizioni reali di traffico; il rischio più critico. Nelle ore di punta la rotta “ottima” calcolata impiega di più nella realtà. Soluzione: cammino minimo tempo-dipendente (peso in funzione del tempo) + servizio dati di traffico (aggiornamento 5-15 minuti) + ricalcolo rolling-horizon (ogni 15-30 minuti o evento-driven — incidente, chiusura).
Ritardo aggiornamenti in tempo reale. Se i dati di chiusura strada, incidente o evento di traffico arrivano in ritardo al motore, questo raccomanda una strada chiusa a sua insaputa — l’autista va, torna indietro, doppio costo. Soluzione: ricalcolo event-driven, notifica evento di traffico in tempo reale nell’app autista, suggerimento di rotta alternativa.
Chiusura / divieto strada sconosciuto. Se i dati (statici) di rete stradale non vengono aggiornati periodicamente, nuovi cantieri, chiusure stagionali e divieti per pesanti sono ignorati; il motore produce rotte non fattibili. Soluzione: ciclo di aggiornamento rete stradale 3-6 mesi, feedback di campo dell’autista (un report “strada chiusa” nell’app), strato di rete stradale specifico per camion nel routing di carichi pesanti.
Lock-in con software di routing / servizio mappe singolo. Senza clausola contrattuale di “esportazione annuale in formato standard (GeoJSON, GraphML, CSV) di dati di rete stradale, dati di calibrazione del traffico, storico delle query e archivio delle rotte”, uscire dal sistema significa perdere anni di dati operativi e memoria di calibrazione. Il contratto deve coprire esplicitamente la sovranità dei dati di rete stradale, l’esportazione dei parametri di calibrazione del traffico e l’output in formato standard per l’API di query.
Metodo di soluzione — visione tecnica
| Approccio | Scala tipica | Tempo di soluzione | Archi negativi? |
|---|---|---|---|
| Dijkstra ingenuo (O(V²)) | Piccolo, V ≤ 1.000 | millisecondi | No |
| Dijkstra binary heap (O((V+E)logV)) | Medio, V ≤ 100K | ms-secondi | No |
| Dijkstra Fibonacci heap (O(E + VlogV)) | Medio-grande, V ≤ 1M | secondi | No |
| Bellman-Ford (O(VE)) | Piccolo-medio, archi negativi | secondi-minuti | Sì, rileva ciclo negativo |
| Floyd-Warshall (O(V³)) | All-pairs piccolo, V ≤ 1.000 | secondi-minuti | Sì (senza ciclo) |
| Johnson (O(V² logV + VE)) | All-pairs medio, sparso | minuti | Sì |
| A* (guidato da euristica) | Rete stradale geografica, punto-punto | ms-secondi | No |
| Dijkstra/A* bidirezionale | Punto-punto, grafo grande | ms-secondi | No |
| Contraction Hierarchies | Rete stradale nazionale | sub-millisecondo (pre-processing ore) | No |
| Dijkstra tempo-dipendente | Rete stradale consapevole del traffico | ms-secondi | No |
Scelta della funzione obiettivo:
- Obiettivo 1 — Tempo totale minimo: Focalizzato sulla velocità; tipico per navigazione, emergenze, consegna pacchi.
- Obiettivo 2 — Distanza totale minima: Focalizzato su carburante + usura veicolo; tipico per lunga percorrenza.
- Obiettivo 3 — Costo totale minimo: Somma pesata di carburante + pedaggio + ore di guida.
- Obiettivo 4 — Multi-criterio (Pareto-ottimo): Compromesso tra tempo + costo + carburante; il decisore sceglie sul fronte Pareto.
Multi-obiettivo: somma pesata (più comune) o gerarchico (prima tempo, poi costo, poi carburante) o cammini Pareto-ottimi (supporto avanzato alle decisioni).
Varianti del cammino minimo — scegli per campo:
- Dijkstra classico (1959): Archi non negativi, single-source, fondazionale.
- Bellman-Ford (1958): Supporta archi negativi, rileva cicli negativi, routing distance-vector.
- Floyd-Warshall (1962): All-pairs, grafo piccolo, programmazione dinamica.
- A (Hart-Nilsson-Raphael 1968):* Punto-punto guidato da euristica, reti stradali geografiche.
- Contraction Hierarchies: Rete stradale nazionale, basato su pre-processing, tempo reale.
- Cammino minimo tempo-dipendente: Consapevole del traffico, peso come funzione del tempo.
- Cammino minimo stocastico (Polychronopoulos-Tsitsiklis 1996): Pesi incerti, aggiustato per rischio.
- Cammino minimo con vincoli di risorsa (RCSP): Vincoli aggiuntivi (carburante, finestre); appare come sottoproblema di pricing nel VRP via column generation.
Fonti accademiche
Elencate nel frontmatter della pagina sotto sources.
Fonti
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. Articolo fondazionale di due pagine; tra i più citati in informatica.
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. Riferimento fondazionale di Bellman-Ford per grafi ad archi negativi.
- Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5(6), 345. Sorgente canonica di un paragrafo del Floyd-Warshall all-pairs.
- Ahuja, R. K., Magnanti, T. L. e Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Manuale canonico di flussi di rete e cammino minimo.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. e Stein, C. (2009). Introduction to Algorithms (3ª ed.). MIT Press. Riferimento didattico per Dijkstra / Bellman-Ford / Floyd-Warshall.
- Geisberger, R., Sanders, P., Schultes, D. e Delling, D. (2008). Contraction hierarchies: Faster and simpler hierarchical routing in road networks. Experimental Algorithms (WEA 2008), LNCS 5038, 319-333. Algoritmo moderno basato su pre-processing per reti stradali nazionali.
- Hart, P. E., Nilsson, N. J. e Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. Articolo fondazionale dell’algoritmo A*.
- YÖK Thesis Center — parole chiave: ’en kısa yol’ o ‘Dijkstra’ o ‘graf algoritması’ — 30+ tesi dall’accademia TR. tez.yok.gov.tr
Glossario
- Shortest Path Problem
- Problema fondazionale grafo-OR di trovare il cammino di peso totale minimo tra due nodi su un grafo pesato (single-source single-destination, single-source all-destinations o all-pairs); algoritmi polinomiali Dijkstra (1959), Bellman-Ford (1958), Floyd-Warshall (1962).
- Dijkstra Algorithm
- Algoritmo polinomiale di Edsger Dijkstra (1959) per cammini minimi single-source su grafi a pesi non negativi; greedy — estrae il nodo non visitato a minima distanza tentativa da una coda di priorità e rilassa i suoi vicini; O((V+E) log V) con binary heap.
- MIP
- Modello di ottimizzazione in cui alcune variabili decisionali devono essere numeri interi (es. numero di camion, numero di turni).
- VRP
- La decisione su quali veicoli, partendo da uno o più depositi, visitano quali clienti e in che ordine.
Problemi correlati
Cosa entra in un camion o container, e in che ordine si carica?
Dato un camion, container o veicolo merci di dimensioni fisse, quale disposizione di scatole (o pallet) con dimensioni, pesi e regole di impilamento diversi dà il più alto tasso di utilizzo? Il nome matematico è Three-Dimensional Bin Packing Problem (3D-BPP), oppure nella variante pratica Container Loading Problem (CLP). I metodi che risolvono contemporaneamente volume, limiti di peso, regole di impilamento, distribuzione del peso (bilanciamento) e sequenza di consegna (multi-drop) sono studiati dagli anni '90. Anche un miglioramento del 5% nell'utilizzo aumenta in modo concreto le consegne per veicolo per una PMI.
Dove Apro il Nuovo Magazzino?
Un distributore, un operatore di e-commerce o un produttore pmi prevede di aprire 1–5 nuovi magazzini, filiali o centri di distribuzione nei prossimi 2–5 anni. La decisione: in quale città o regione, quanti siti, di quali dimensioni, e quali magazzini esistenti trasferiscono quale volume di clienti o ordini al nuovo sito. Una localizzazione sbagliata significa 5–10 anni di alti costi di trasporto, consegne in ritardo e perdita di clienti; una buona localizzazione vale 300.000–1,5 milioni di EUR di risparmio annuo nello stesso periodo. Quando la decisione viene presa a sensazione (per esempio 'accanto allo stabilimento, gli operai abitano vicino'), raramente colpisce l'ottimo — perché costo di trasporto, affitto, tasse, costo del lavoro e tempo di servizio sono vincoli da bilanciare insieme.