Trasporti: flussi, giri di consegna e algoritmo dei risparmi

Il trasporto è spesso la voce più grande dei costi logistici. Le decisioni vanno dalla scelta del modo (strada, ferrovia, mare, aria) alla pianificazione dei flussi tra origini e destinazioni, fino al giro quotidiano di un furgone che consegna a trenta clienti. In questa lezione vediamo il problema dei trasporti come programmazione lineare, il problema del commesso viaggiatore e la sua difficoltà, l’algoritmo dei risparmi con la dimostrazione del risparmio e un esempio, e le economie del carico completo.

Il problema dei trasporti

Si hanno stabilimenti con capacità , clienti con domande e costi unitari per spedire da a . Si cercano le quantità che minimizzano il costo totale:

È un problema di programmazione lineare con una struttura speciale: se capacità e domande sono intere, esiste sempre una soluzione ottima intera, e algoritmi dedicati la trovano molto in fretta anche con migliaia di origini e destinazioni.

Il giro di consegne

Un furgone parte dal deposito, visita un insieme di clienti e torna: in che ordine? È il problema del commesso viaggiatore (TSP). Con clienti i giri possibili sono : con 20 clienti più di , impossibili da enumerare. Il problema è NP-difficile: non si conosce un algoritmo che lo risolva esattamente in tempo polinomiale. Si usano allora:

• algoritmi esatti con tecniche di taglio, che risolvono istanze di migliaia di punti in tempi accettabili;
• euristiche costruttive (il vicino più prossimo: andare sempre al cliente non visitato più vicino), veloci ma con giri del 20-25 % più lunghi dell’ottimo;
• euristiche di miglioramento (2-opt: togliere due archi che si incrociano e ricollegare i percorsi senza incrocio), che si avvicinano all’ottimo di pochi punti percentuali.

L’algoritmo dei risparmi

Con più veicoli di capacità limitata (problema di instradamento dei veicoli, VRP) l’euristica classica è quella dei risparmi di Clarke e Wright (1964). Si parte servendo ogni cliente con un viaggio separato, andata e ritorno dal deposito, e si uniscono i giri a coppie.

Teorema. Unire in un solo giro i viaggi verso i clienti e fa risparmiare

dove sono le distanze e 0 è il deposito.

Dimostrazione. Separati, i due viaggi percorrono . Il giro unico 0, , , 0 percorre . La differenza è . Per la disuguaglianza triangolare , quindi il risparmio non è mai negativo. ∎

Esempio. Con , , km: separati 44 km, uniti 27 km, risparmio . L’algoritmo calcola i risparmi di tutte le coppie, li ordina dal più grande, e unisce i giri corrispondenti se i due clienti sono agli estremi di giri diversi e il carico unito non supera la capacità del veicolo. I clienti lontani dal deposito e vicini tra loro hanno risparmi grandi e finiscono nello stesso giro, che è proprio ciò che l’intuizione suggerisce. Il risultato è in genere entro il 5-10 % dell’ottimo, e si migliora con le euristiche locali.

I sistemi reali aggiungono finestre temporali (il cliente riceve solo dalle 8 alle 12), tempi di scarico, limiti di orario degli autisti, traffico variabile durante il giorno; i programmi di pianificazione dei giri usano metaeuristiche e calcolano le soluzioni in pochi minuti ogni mattina.

Le economie del carico

Il costo di un viaggio dipende poco da quanto è pieno il mezzo: autista, carburante, pedaggi e ammortamento si pagano comunque. Il costo per unità trasportata è quindi circa , con il costo fisso del viaggio, il carico e un piccolo costo variabile per unità: decresce con il carico. Da qui le strategie di consolidamento: raggruppare piccole spedizioni in carichi completi (piattaforme di consolidamento, trasporto groupage), programmare le consegne in giorni fissi per zona, evitare i viaggi di ritorno a vuoto cercando carichi di ritorno. Le stesse economie valgono per le emissioni (lezione sulla sostenibilità).