Allocazione delle spedizioni da più stabilimenti o magazzini a più clienti o punti di distribuzione — quanto su ciascuna tratta affinché il costo totale di trasporto sia minimo, le capacità non siano superate, le domande siano soddisfatte. Il problema fondante della programmazione lineare: Hitchcock (1941) e Koopmans (1947).
In breve
Ti suona familiare?
- Spediamo settimanalmente da 3-8 stabilimenti o magazzini regionali a 20-100 clienti; quale stabilimento spedisce a quale cliente lo decide di solito l'abitudine o la regola 'stabilimento più vicino'.
- Gestiamo una cooperativa di raccolta del latte; flusso giornaliero da 50-200 aziende agricole a 3-6 impianti di lavorazione — quale azienda va a quale impianto viene dalla storia.
- Abbiamo una catena tessile materia-prima-laboratorio; spediamo filato e tessuto da un magazzino centrale a 30-80 laboratori contoterzisti — la matrice dei costi non viene aggiornata da 5 anni.
- Quando apre un nuovo stabilimento o magazzino, o entra un nuovo cliente, non ricalcoliamo le quote — proseguiamo con l'allocazione vecchia.
- Il prezzo del carburante o i contratti di trasporto sono cambiati, ma le quantità per coppia stabilimento-cliente sono rimaste uguali.
- Il costo totale del trasporto vale 10-20 % del budget annuo; la domanda 'cosa risparmieremmo se ridisegnassimo i flussi' è senza risposta da anni.
- Stiamo valutando un ampliamento di capacità di stabilimento; la domanda 'cosa porta 1 tonnellata in più in risparmio di trasporto' non ha risposta numerica.
Perché è importante
Come si risolve
Profondità tecnica
Come si risolve
Profondità tecnicaIn una frase: Data la matrice di costo unitario per coppie stabilimento-cliente, le capacità degli stabilimenti e la domanda dei clienti, un solver di programmazione lineare calcola in secondi quanto (x_ij) spedire da ogni stabilimento a ogni cliente — costo totale di trasporto minimo, nessun cliente scoperto, nessuno stabilimento in eccesso.
Questo problema compare nella letteratura di Ricerca Operativa (disciplina che usa matematica e informatica per risolvere decisioni di business) come Problema di Trasporto o Problema di Hitchcock, uno degli esempi fondanti della programmazione lineare. Soluzione in tre fasi:
1. Modellazione. Dati di input: origini (m stabilimenti o magazzini — ciascuno con capacità settimanale s_i in tonnellate o pallet), destinazioni (n clienti o punti di distribuzione — ciascuno con domanda settimanale d_j), matrice dei costi (c_ij — costo unitario di trasporto da stabilimento i a cliente j, TRY per tonnellata o pallet). Variabile decisionale x_ij — quantità da spedire da stabilimento i a cliente j. Vincoli: spedizione totale di ciascuno stabilimento ≤ capacità (somma su j di x_ij ≤ s_i), ricezione di ciascun cliente ≥ domanda (somma su i di x_ij ≥ d_j), tutte le x_ij ≥ 0. Obiettivo: minimizzare il costo totale di trasporto. Problema bilanciato: offerta totale uguale a domanda totale; problema non bilanciato: offerta > domanda (capacità inattiva) o offerta < domanda (sotto-produzione), risolto aggiungendo un’origine o destinazione fittizia (dummy).
2. Decisione guidata dal solver. Essendo un LP puro (Linear Programming — minimizzare un obiettivo lineare sotto vincoli lineari), i solver LP moderni risolvono migliaia di coppie origine-destinazione in secondi. Metodi classici: Metodo del Simplesso (sviluppato all’inizio degli anni 1950 per questo problema — l’algoritmo LP canonico che trova l’ottimo muovendosi di vertice in vertice); Simplex di Rete (la struttura di grafo bipartito lo rende 5-10× più veloce); Regola dell’angolo nord-ovest per soluzione iniziale ammissibile, combinata con MODI (Distribuzione Modificata) / Stepping-Stone per il miglioramento (metodo didattico manuale); Metodo di Approssimazione di Vogel (VAM) per un punto di partenza più intelligente. In pratica: media scala (5-50 origini × 50-500 destinazioni) istantanea su solver LP aperti, grande scala (centinaia-migliaia) in minuti con simplex di rete o metodi di punto interno. Il Problema di Assegnazione è caso speciale — uguale numero di origini e destinazioni, ciascuna origine a una destinazione (capacità = domanda = 1, x_ij in {0,1}); il metodo ungherese è il solver classico per questo caso.
3. Integrazione di campo. Output in due tabelle: la matrice dei flussi primale (quantità settimanale per coppia stabilimento-cliente — il piano principale del team operativo) e le variabili duali (prezzi-ombra per ogni origine e destinazione). I valori duali sono input diretto per le decisioni di investimento: ‘se la capacità dello stabilimento i sale di 1 tonnellata, di quanto cala il costo totale di trasporto?’ si legge direttamente dal duale. Pratica di campo: ri-risoluzione settimanale o mensile; variazione del prezzo del carburante, nuovo cliente/stabilimento, finestre di manutenzione capacità come trigger. Comitato trimestrale: flussi realizzati vs piano, analisi di capacità marginale, aggiornamento matrice dei costi.
Alternative
Manuale + foglio di calcolo (flussi tradizionali)
GratuitoNessuna licenza
Per chi: Piccola scala (≤3 stabilimenti, ≤20 clienti), domanda stabile
- + Costo software zero
- + Si adatta all'abitudine del team operativo
- + Modifica immediata (deviazione telefonica)
- − Flussi non ottimi — tipicamente 10-20 % di costo di trasporto in più
- − Senza matrice dei costi aggiornata gli shock del carburante non rientrano
- − Capacità marginale (per investimenti) non analizzabile
- − All'aggiunta di stabilimento/cliente nessuna ri-disegno
Foglio di calcolo con add-in LP
GratuitoZero o licenza bassa (nel pacchetto Office)
Per chi: Media scala (3-8 stabilimenti, 20-100 clienti), decisione mensile periodica
- + Interfaccia usabile dal team operativo
- + Scala sufficiente per il problema classico
- + Curva di apprendimento bassa
- − Lento o irrisolvibile su matrici grandi (200+ destinazioni)
- − Visualizzazione dei duali debole — nessun report dei prezzi-ombra
- − Nessun modulo di domanda stocastica
- − Controllo di versione debole
Software locale di pianificazione della supply chain
AziendaleLicenza 200K-1M TRY + 60K-300K TRY/anno manutenzione (prezzi SMB regionali)
Per chi: Operatore medio-grande (5-15 stabilimenti, 100-500 clienti)
- + Interfaccia e supporto in lingua locale
- + Integrazione ERP semplice
- + Modelli locali di contratto di trasporto
- − Solver LP solitamente integrato — performance da testare
- − Analisi dei duali limitata
- − Estensioni accademiche (multi-periodo, stocastiche) limitate
Piattaforma internazionale di pianificazione
AziendaleLicenza 500K-3M EUR + 150K-700K EUR/anno manutenzione
Per chi: Grande operatore (15+ stabilimenti, 500+ clienti, multi-paese)
- + Solver LP/MIP maturo, scalabile
- + Analisi duale ricca, prezzi-ombra, confronto di scenari
- + Estensioni multi-periodo e stocastiche
- − Licenza alta e rollout lungo (12-24 mesi)
- − La personalizzazione alla normativa locale allunga il progetto
- − Formazione del team è un programma ampio
Sviluppo proprietario su solver LP open source
Open SourceLicenza gratis; 8-16 settimane di sviluppo interno o 400K-1,2M TRY di consulenza
Per chi: Operatore con team tecnico, vuole plug-in ERP
- + Nessuna licenza
- + Problema classico di trasporto ben definito in letteratura open
- + Estensioni multi-periodo, stocastiche, di flusso di rete aperte
- − Servono esperienza OR interna e team dati
- − Va costruita l'interfaccia operativa
- − Manutenzione in capo all'operatore
Raccomandazione
Chiedi nell'incontro
- Quale solver alimenta il problema di trasporto — simplesso puro, simplex di rete, punto interno? Tempo tipico per 100 origini × 500 destinazioni?
- È supportato il bilanciamento automatico (origine/destinazione fittizia) per problemi non bilanciati? Viene prodotto il report di capacità inattiva?
- Le variabili duali (prezzi-ombra) sono presentate come tabella separata? Si può autogenerare lo scenario 'capacità dello stabilimento i sale di 1 tonnellata'?
- Quando la matrice dei costi viene aggiornata (carburante, nuovo contratto), il trigger di ri-risoluzione è automatico o manuale?
- È supportata la pianificazione multi-periodo (orizzonte settimanale o mensile)? È modellato il riporto di magazzino tra periodi?
- Esiste un modulo dedicato al caso speciale Problema di Assegnazione (origini = destinazioni, decisione binaria)? Metodo ungherese supportato?
- Come produrrebbe il pilota, in 8-12 settimane di dati reali, un report di risparmio rispetto al flusso manuale precedente?
- Se chiudiamo il contratto, in quale formato standard possiamo esportare definizioni origine-destinazione, storia della matrice dei costi e archivio delle soluzioni?
Dettagli tecnici
Nota editoriale
Sul piano operativo questo problema si chiama “piano dei flussi”, “ripartizione delle spedizioni” o “matrice stabilimento-cliente”. Il nome accademico è Problema di Trasporto, in alcune fonti anche Problema di Hitchcock o Problema di Hitchcock-Koopmans. Frank Hitchcock definì il problema in forma numerica nel suo articolo del MIT del 1941; Tjalling Koopmans scrisse nel 1947 una formulazione economica indipendente (citata nel Premio Nobel per l’Economia del 1975); George Dantzig nel 1951 sviluppò il metodo Simplex specificamente attorno a questo problema. È il problema fondante della programmazione lineare e l’antenato della generazione successiva — TSP, VRP, vehicle routing — che ne è derivata.
La distinzione con VRP (#002, #069) è critica: VRP è vehicle routing — un giro deposito-cliente-cliente-deposito, in che ordine ogni mezzo visita quali clienti. Il problema di trasporto è allocazione di flusso: quante unità ciascun stabilimento spedisce a ciascun cliente; non c’è rotta, solo quantità. I due sono complementari — prima il problema di trasporto decide il flusso settimanale, poi VRP decide il routing giornaliero. Operano in sequenza nella stessa catena. Distinzione dalla localizzazione (#010): la localizzazione è la decisione di aprire un nuovo stabilimento/magazzino (con costo fisso di apertura); il problema di trasporto è allocazione di flusso tra impianti esistenti (nessun costo di apertura). Distinzione da p-mediana (#074): p-mediana sceglie un numero fisso di impianti, il problema di trasporto prende gli impianti esistenti come dati.
Il punto più spesso trascurato: variabili duali e prezzi-ombra. I flussi primali (quante tonnellate ogni stabilimento spedisce a ciascun cliente) sono l’output che il professionista legge; le variabili duali assegnano un prezzo-ombra a ogni origine e destinazione — “se la capacità dello stabilimento i sale di 1 tonnellata, di quanto cala il costo totale di trasporto?”, “se la domanda del cliente j sale di 1 tonnellata, di quanto sale il costo totale?” trovano risposta esatta. Input diretto per le decisioni di investimento: quale stabilimento guadagna di più dall’espansione, quale cliente ha costo marginale di trasporto maggiore. Il professionista in genere usa solo i primali e non legge i duali — perdita critica per la prioritizzazione degli investimenti in capacità. Secondo punto trascurato: il problema non bilanciato. Nella realtà raramente la capacità totale è esattamente uguale alla domanda totale (sovra o sotto-produzione). Il solver aggiunge un’origine o destinazione fittizia — quella riga o colonna è il report di capacità inattiva; se trascurato, non si capisce a cosa corrisponde la capacità inattiva.
Percorso passo-passo per una PMI
Fase 1 — Prima misurare, poi pianificare. Almeno 6-12 mesi di dati: quantità mensile spedita per coppia stabilimento-cliente, costo unitario di trasporto (distanza + tipo di mezzo + contratto), capacità settimanale di stabilimento, domanda settimanale di cliente. Costruire la matrice dei costi come tabella separata — righe stabilimenti, colonne clienti, celle TRY/tonnellata. Critico: il prezzo del carburante è cambiato negli ultimi 12 mesi — la matrice è stata aggiornata? In caso negativo, già il primo run LP mostra 5-10 % di risparmio.
Fase 2 — Estrarre il capitale di conoscenza. Elencare quali stabilimenti sono fisicamente impossibili per quali clienti (distanza, compatibilità di prodotto, vincolo contrattuale) — questi vincoli entrano nel modello come ‘celle proibite’ (costo alto). Capacità di stabilimento: capacità sostenuta reale o con finestre di manutenzione? Domanda di cliente: stabile o stagionale?
Fase 3 — Pilota. 8-12 settimane. Costruire il modello LP per una sotto-regione (es. una linea di prodotto o un set regionale di clienti), far girare il solver e confrontare il risultato in parallelo con l’allocazione manuale attuale. La decisione resta al pianificatore; l’LP dà un suggerimento. Criterio di successo scritto prima del pilota: costo totale di trasporto in calo almeno del 10 %, report di capacità inattiva o domanda insoddisfatta chiaro. Richiedere la tabella delle variabili duali come output separato — oro per investimenti in capacità.
Fase 4 — Rollout. In 6-12 mesi estendere a tutte le linee e le regioni. Passare a ri-risoluzione mensile — carburante, nuovo cliente, manutenzione come trigger. Comitato trimestrale: flussi realizzati vs piano, report dei duali (prezzo-ombra), data di aggiornamento della matrice dei costi.
Rischi — cosa può andare storto
- La capacità di stabilimento varia in tempo reale. Il modello LP statico fissa la capacità settimanale o mensile; manutenzione, perdita turno, interruzioni di materia prima la muovono giornalmente. Soluzione: cadenza di ri-risoluzione più breve (settimanale) più margine di sicurezza sotto la capacità media.
- La matrice dei costi non viene aggiornata. Il carburante è cresciuto del 20 % ma la matrice è ferma a numeri di 2 anni fa — l’LP ottimizza una matrice obsoleta e perde denaro nella realtà. Soluzione: aggiornare ogni 3 mesi (carburante + contratto + costo del mezzo).
- Le richieste speciali del cliente non sono modellate. Alcuni clienti hanno finestra oraria, vincolo di formato pacco o regola di mix di prodotto — il problema di trasporto puro non li porta; vanno passati al VRP o alla pianificazione. Un flusso tecnicamente corretto LP può essere operativamente impraticabile.
- Dipendenza da un singolo fornitore (lock-in WMS/TMS). Se il software conserva definizioni origine-destinazione, matrice dei costi e archivio delle soluzioni in formato proprietario, uscire significa perdere la memoria dei flussi dell’operatore. Clausola contrattuale: ’esportazione annuale dello storico della matrice di flusso e della matrice dei costi in formato standard’."
Visione tecnica del metodo di soluzione
| Approccio | Scala tipica | Tempo di soluzione | Garanzia di ottimo? |
|---|---|---|---|
| Regola dell’angolo nord-ovest | Soluzione iniziale manuale, qualsiasi scala | minuti (manuale) | No — solo soluzione iniziale |
| Metodo di Approssimazione di Vogel (VAM) | Start più intelligente | minuti-secondi | No — quasi-ottimo |
| MODI / Stepping-Stone (manuale) | Piccolo (≤10 × ≤10) | ore | Sì (se applicato correttamente) |
| Simplesso (generale) | Medio (≤500 × ≤500) | secondi | Sì |
| Simplex di Rete | Grande (migliaia di origini/destinazioni) | secondi-minuti | Sì |
| Metodo di punto interno | Molto grande | minuti | Sì (tolleranza numerica) |
| Metodo ungherese (assegnazione) | Matrice quadrata | veloce | Sì (caso speciale) |
Scelta della funzione obiettivo:
- Obiettivo 1 — Costo totale di trasporto minimo: Classico. FMCG, catene materia-prima-laboratorio.
- Obiettivo 2 — Distanza o carburante minimo: Operazioni a focus CO₂ o intensive in carburante.
- Obiettivo 3 — Tempo di servizio ponderato minimo: Distribuzione rapida (alimentare, catena del freddo).
- Obiettivo 4 — Mix ponderato: trasporto + servizio + penalità: Portafoglio con penali contrattuali sui ritardi.
Il Problema di Assegnazione è caso speciale del trasporto: numero di origini = destinazioni, ogni origine a esattamente una destinazione (capacità = domanda = 1, x_ij binaria). Assegnazione personale-attività, macchina-ordine, nave-banchina (sotto-strato del BAP in #026), problemi di matching tra nodi hanno questa forma. Il metodo ungherese (Kuhn 1955) risolve l’assegnazione in O(n³) — molto più veloce del simplesso generale sugli stessi dati, ma solo per il caso speciale di assegnazione.
Estensione multi-periodo: x_ijt — quantità da stabilimento i a cliente j nel periodo t; capacità e domanda proprie per periodo, con costo di magazzino inter-periodo. Cresce nella pianificazione produzione-distribuzione multi-periodo — tiene il problema di trasporto al centro, aggiunge strati di lot-sizing e magazzino.
Estensione stocastica: d_j è variabile aleatoria; la soluzione fornisce un’allocazione che non sfora la capacità in nessuno scenario e minimizza il costo atteso — LP stocastico o MIP basato su scenari.
Riferimenti accademici
Elencati nel blocco sources di questa pagina. Hitchcock (1941) e Koopmans (1947) sono i due articoli fondanti; Dantzig (1951) sviluppò il metodo Simplex proprio attraverso questo problema. Bazaraa-Jarvis-Sherali (2010) e Murty (1992) sono riferimenti moderni da libro di testo. INFORMS e l’archivio dell’European Journal of Operational Research portano molti casi di applicazione in supply chain e reti produzione-distribuzione.
Fonti
- Hitchcock, F. L. (1941). The distribution of a product from several sources to numerous localities. Journal of Mathematics and Physics, 20(1-4), 224-230. Fonte fondante del problema.
- Koopmans, T. C. (1947). Optimum utilization of the transportation system. Econometrica, 17 (Supplement). Tra le citazioni del Premio Nobel per l’Economia 1975.
- Dantzig, G. B. (1951). Application of the Simplex Method to a transportation problem. In Activity Analysis of Production and Allocation, Wiley.
- Bazaraa, M. S., Jarvis, J. J. e Sherali, H. D. (2010). Linear Programming and Network Flows (4ª ed.). Wiley. Libro di testo standard.
- Murty, K. G. (1992). Network Programming. Prentice Hall. Riferimento classico sulla programmazione di rete.
- INFORMS Interfaces — casi di applicazione di LP e supply chain in reti produzione-distribuzione. informs.org/Publications/Interfaces
Glossario
- Problema di Trasporto
- Allocazione delle spedizioni da m origini a capacità fissa a n destinazioni a domanda fissa, minimizzando il costo unitario totale di trasporto — il problema fondante della programmazione lineare.
- Regola dell'Angolo Nord-Ovest
- L'euristica classica più semplice per generare una soluzione iniziale di base ammissibile del problema di trasporto: partire dall'angolo in alto a sinistra della matrice dei costi, assegnare il più possibile alla cella corrente e spostarsi a destra o in basso fino a esaurire offerta e domanda.
- MIP
- Modello di ottimizzazione in cui alcune variabili decisionali devono essere numeri interi (es. numero di camion, numero di turni).
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.
Da un nodo all'altro — come calcolo il cammino minimo su un grafo pesato?
Per PMI che devono calcolare il percorso più rapido o più breve tra due punti: squadre di servizio sul campo con 10-50 veicoli (idraulici, elettricisti, riparazione elettrodomestici), operatori urbani di corriere/pacchi o centrali operative che coordinano interventi di emergenza. Ogni giorno arrivano centinaia di domande 'come vado adesso più veloce da A a B?'; la risposta cambia con traffico, chiusure stradali e tipo di mezzo. Un percorso sbagliato costa al tecnico uno-due interventi saltati nella giornata, al corriere una consegna in ritardo e all'azienda un cliente. Una pianificazione manuale o a occhio lascia tipicamente 20-60 minuti sprecati per veicolo al giorno rispetto a un calcolo basato sulla rete.
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.