1

Problemi di routing di veicoli:1 - Introduzione

Daniele Vigo DEIS, Università di Bologna

dvigo@deis.unibo.it

VRP-Intro.2D. Vigo

Problemi di trasporto merci• Trasporto merci 10% - 25% del costo totale dei

beni di consumo• Razionalizzazione delle infrastrutture per il

trasporto ed il trattamento delle merci• Informatizzazione + Tecnologia + Tecniche di

ottimizzazione:• Sistemi di supporto alle decisioni• Risparmi 5% - 20% costi totali di trasporto

2

VRP-Intro.3D. Vigo

Strumenti di ottimizzazione• Sistemi per il supporto alle Decisioni:

• Pianificazione strategica (what if ?)• Pianificazione operativa (on-line)

• Integrazione nella realtà operativa industriale e commerciale

• Modelli ed algoritmi di ottimizzazione• tengono conto di tutte le caratteristiche dei problemi

reali• hanno tempi di calcolo compatibili con le esigenze

operative

VRP-Intro.4D. Vigo

Problemi di trasporto merciServizio di un insieme di clienti da parte di veicoli, localizzati in uno o più depositi, che effettuano i loro spostamenti utilizzando un’opportuna rete stradale

3

VRP-Intro.5D. Vigo

Componenti fondamentali• Rete stradale• Clienti• Veicoli• Depositi• Autisti• Vincoli operativi:

• globali • sui singoli viaggi

• Obiettivi dell’ottimizzazione

VRP-Intro.6D. Vigo

Rete stradale• Grafo (sparso): G=(V, A) o G=(V, E) • Vertici :

incroci, sedi di clienti, depositi V={0, 1, …, n}

• Archi : tratti stradali • orientati, non orientati: (i,j)∈A o e∈E• “costo” di transito (lunghezza, …): cij

• tempo di transito: tij

• Interazione/integrazione con cartografia e GIS

4

VRP-Intro.7D. Vigo

Rete stradale (2)

scala regionale: grafo non orientato

VRP-Intro.8D. Vigo

Rete stradale (3)

scala urbana: grafo orientato

5

VRP-Intro.9D. Vigo

Rete stradale (4)

Soluzioni ibride

VRP-Intro.10D. Vigo

Rete Stradale (5)• Grafo sparso ⇒ completo

4,31 2 3 0

4 5 6

7 8 9

3,3

3,3

5,4

6,73,3

3,24,4

5,5

n = 9, cij tij

c0,8 = 9, t0,8 = 10

6

VRP-Intro.11D. Vigo

Rete Stradale (6)• Proprietà di triangolarità

k

i j

kjiccc kjikij ,,∀+≤

8

3 6

VRP-Intro.12D. Vigo

Clienti• vertice del grafo• domanda = quantità merce consegnata e/o raccolta• finestre temporali per il servizio

• (orari di apertura, orari di accesso a ZTL)• istante desiderato di servizio + penalità di violazione

• tempi di carico/scarico della merce• sottoinsieme di veicoli utilizzabili• Servizio da parte di più veicoli (split deliveries)

7

VRP-Intro.13D. Vigo

Veicoli• flotta di dimensione fissa o variabile • flotta aziendale o di terzi• deposito di appartenenza (ritorno?)• capacità di carico (peso, volume, …)

• suddivisione in scomparti• non idoneità per determinati tipi di merci

• impossibilità al transito in alcune strade• costi (per km, ora, viaggio, …)• metodologia di carico/scarico

VRP-Intro.14D. Vigo

Autisti• dipendenti o “padroncini”• vincoli sindacali

• orario di lavoro• numero e durata pause• straordinario• …

• disponibilità nel periodo in esame

8

VRP-Intro.15D. Vigo

Depositi• uno o più depositi (vertici del grafo)• numero e tipo dei veicoli appartenenti ai depositi• pre-assegnazione di clienti ai depositi• in alcuni casi problema separabile:

un problema per ciascun deposito

VRP-Intro.16D. Vigo

Vincoli operativiDipendono da:• natura del trasporto effettuato• qualità del servizio desiderato• contratto di lavoro degli autisti

Due tipi:• Vincoli relativi ad un viaggio (locali)• Vincoli sull’insieme dei viaggi (globali)

9

VRP-Intro.17D. Vigo

Vincoli operativi per i viaggi• capacità del veicolo• massima lunghezza/durata• possibilità di mix raccolta/distribuzione• rispetto delle finestre temporali• vincoli di precedenza tra clienti:

• servizio nello stesso viaggio (pickup/delivery)• ordine prefissato se nello stesso viaggio

(linehaul/backhaul)

VRP-Intro.18D. Vigo

Vincoli globali• Numero massimo di viaggi

• per tipologia veicoli• per deposito

• Bilanciamento del carico di lavoro• Aggregazione dei viaggi in giornate lavorative

• massimizzazione della produttività• sosta minima tra un viaggio ed il successivo

10

VRP-Intro.19D. Vigo

Obiettivi

• Minimizzare: costo globale dei viaggi + costi fissi per veicoli ed autisti

• Minimizzare numero veicoli e/o autisti• Bilanciare viaggi• Minimizzare penalità associate al mancato o

parziale servizio di clienti

obiettivi in contrasto tra loro

costo viaggio = somma costi degli archi

VRP-Intro.20D. Vigo

Altre caratteristiche• servizio su più giorni• più viaggi nello stesso giorno per i veicoli• più richieste per ciascun cliente• conoscenza a priori della domanda parziale o nulla

(problemi stocastici, dinamici, on-line)• dipendenza dal tempo del costo degli archi o

presenza di perturbazioni stocastiche

11

VRP-Intro.21D. Vigo

Problema del Commesso Viaggiatore (TSP)• caso particolare:

• 1 deposito• 1 veicolo di capacità illimitata• minimizzare il costo per servire tutti i clienti

Circuito a costo minimo

passante per tutti i vertici

Circuito Hamiltoniano

VRP-Intro.22D. Vigo

Applicazioni del TSP• percorsi di rappresentanti, manutentori …• sequenza di perforazione di un circuito stampato

• plotting di disegni (minimizzare il percorso a vuoto della penna)

• Sequenziamento di decolli ed atterraggi

12

VRP-Intro.23D. Vigo

Vehicle Routing Problem (VRP)• Ciascun viaggio è eseguito da un veicolo che:

• parte da un deposito • serve alcuni clienti• ritorna al deposito di partenza

Circuito passante per il deposito

VRP-Intro.24D. Vigo

Vehicle Routing Problem (VRP)• Determinare un insieme di viaggi in modo da:

• servire (se possibile) tutti i clienti• rispettare i vincoli operativi per ogni viaggio• minimizzare un’assegnata funzione costo

13

VRP-Intro.25D. Vigo

Applicazioni del VRP (1)• consegna di prodotti:

alimentari, petroliferi, farmaceutici, giornali, latte, pizza, posta, …

• raccolta di prodotti:latte, vuoti (bottiglie, bombole), posta …

• consegna/raccolta di prodotti:corrieri espressi, consegne ai supermercati e raccolta dai fornitori

VRP-Intro.26D. Vigo

Applicazioni del VRP (2)• raccolta di rifiuti solidi urbani• pulizia delle strade (spazzaneve, potatura alberi, …)• trasporto persone / portatori di handicap• minibus “a richiesta”• autobus per servizi scolastici• viaggi di rappresentanti, controllori, postini,

manutentori ...

risparmio medio sui costi: 5%-20%

14

VRP-Intro.27D. Vigo

Consegna prodotti a negozi• distribuzione giornaliera salumi a livello regionale• 5 veicoli, circa 400 negozi• 2-3 viaggi al giorno per ciascun veicolo• 30-40 consegne per viaggio• finestre temporali: {8-12, 15-17}, {8-12}

• Soluzione manuale: 1138 km, 14 viaggi• Soluzione ottimizzata: 943 km (-17%), 12 viaggi

VRP-Intro.28D. Vigo

Grande distribuzione• Distribuzione di prodotti a punti vendita su scala

macro-regionale:• 3 magazzini multiprodotto (Generi Vari, Ortofrutta,

Salumi e Latticini)• 300 punti-vendita (fino a 6 visite settimanali)• molti carichi completi (GV)• finestre temporali (30’– 4ore) • tempi di carico-scarico diversificati sui clienti• flotta eterogenea (fino a 6 tipi di veicoli)• viaggi di tipo “network”: DepA → DepB → DepA

15

VRP-Intro.29D. Vigo

Risultati (1)• Generi vari : giornata “tipo”

44 pdv, 613 pallets (1-5 pdv per viaggio)

89-96%66-94%Utilizzo veicolo (carico/capacità)

119h124hTempo totale

3537n. Viaggi

Route+Attuale

VRP-Intro.30D. Vigo

Risultati (2)• Ortofrutta : giornata “tipo”

48 pdv, 298 pallets (2-8 pdv per viaggio)

91-94%66-86%Utilizzo veicolo (carico/capacità)

83h92hTempo totale

1621n. Viaggi

Route+Attuale

16

VRP-Intro.31D. Vigo

Raccolta di rifiuti solidi urbani• punti di raccolta (cassonetti/campane)

sensi unici e cassonetti sui due lati: grafo orientatoMolti cassonetti: domanda associata agli archi

VRP-Intro.32D. Vigo

Raccolta di rifiuti solidi urbani

• Frequenza di svuotamento variabile (1-6 v/sett.) • 1-2 viaggi giornalieri per ogni veicolo • 30-50 punti di raccolta per viaggio• finestre temporali per alcune zone (ZTL, mercato…)• riconfigurazione postazioni/frequenze• Es. 1: Valle del Senio (BO) extraurb. (~2000 cass/s):

• 1 viaggio in meno, durata/percorrenza –19%, svuot –30%• Es. 2: Forli’ 2 zone urbane (~1500 cass/s):

• 2 viaggi in meno, durata/percorrenza –12%, svuot –24%

17

VRP-Intro.33D. Vigo

Analisi conferimenti• Gestione delle rilevazioni periodiche dei

conferimenti in peso e/o volume• Sensori di peso sui veicoli• Software di raccolta dati su palmari• Tracking dei viaggi e dei tempi di servizio

VRP-Intro.34D. Vigo

Analisi conferimenti (2)

Riempimento osservato

18

VRP-Intro.35D. Vigo

Analisi conferimenti (3)

Dai dati storici sui conferimenti si ricavano le leggi di conferimento nel tempo

Stima

valoriosservati

VRP-Intro.36D. Vigo

Ottimizzazione dell’offerta• Nota la domanda:

• Definizione delle frequenze di servizio ottimali per i punti di conferimento

• Definizione delle capacità ottimali delle postazioni (n. e tipo contenitori) assegnata la frequenza di servizio

• Allo scopo di:• Potenziamento dell’offerta (stagionalità)• Minimizzazione dei costi di servizio (n. di svuotamenti)• Ottimizzazione del parco contenitori (acquisto,

ricollocazione, gestione)

19

VRP-Intro.37D. Vigo

Sistema di gestione

VRP-Intro.38D. Vigo

Ottimizzazione offerta

Tipi di contenitoriutilizzabili e loro caratteristiche

20

VRP-Intro.39D. Vigo

Risultati (1)• Valle del Senio, Imola (BO), 2001:

1. Situazione iniziale: 275 cassonetti, 827 svuot./sett (1-3 volte/sett)

2. Ottimizzazione frequenze di servizio:275 cassonetti, 697 svuot./sett (- 15% sui costi)

3. Riconfigurazione postazioni ed ottimizzazione frequenze di servizio:283 cassonetti, 658 svuot./sett (- 21%)

VRP-Intro.40D. Vigo

Risultati (2)• Valle del Santerno, Imola (BO):

1. Situazione iniziale (marzo–aprile, 2000): 325 cassonetti, 786 svuot./sett (9 viaggi)costo medio per cassonetto 80.022 Lire

2. Riconfigurazione postazioni ed ott. frequenze (marzo–aprile 2001)325 cassonetti, 657 svuot./sett (5 viaggi)costo medio per cassonetto 60.216 Lire (–15%)

21

VRP-Intro.41D. Vigo

Risultati (3)• Forlì, due zone urbane, 2001:

1. Situazione iniziale:308 cassonetti, 1540 svuotamenti/sett

2. Riconfigurazione punti conferimento275 cassonetti (- 11%)

3. Ottimizzazione frequenze di servizio:1100 svuotamenti (- 28.6 %)

VRP-Intro.42D. Vigo

Pianificazione dei viaggi• Modello flessibile in grado di incorporare le più

diverse condizioni operative:• Flotte di veicoli eterogenei• Depositi e discariche multiple• Capacità dei veicoli (peso e/o volume)• Finestre temporali per il servizio (orari di accesso, zone

a traffico limitato, mercati …)• Durata e bilanciamento dei viaggi

22

VRP-Intro.43D. Vigo

Pianificazione dei viaggi (2)• Profili di servizio diversificati:

• es. 2 v./sett. lun–gio (3gg+4gg) o lun–ven (4gg+3gg)

• Viaggi aggregati per comune o zona• Compatibilità tra veicoli e punti o strade• Velocità dipendente dal tipo di veicolo e strada• Orizzonte di pianificazione di uno o più giorni • Incertezza sulla domanda, sui tempi di viaggio …

VRP-Intro.44D. Vigo

Trasporto urbano PRCM• Persone a ridotta capacità motoria:

• Carrozzella, accompagnatore, …

• Pickup e Delivery, Ist. des. di serv. + penalità…• Flotta eterogenea: auto, taxi, pulmini, …• Compatibilità con i veicoli e max tempo a bordoEsempio: Bologna 1994, (~ 1500 trip/sett)

• Veicoli usati (–57%, taxi da 108 a 42)• Percorrenza –11%• Qualità del servizio molto migliore