Bologna Servizi di trasporto merci: Problemi di routing di ... · Maggio 2001 6 Daniele Vigo -...

Maggio 2001

1

Daniele Vigo - DEIS, Università di Bologna

Servizi di trasporto merci

Servizi di trasporto merci:Problemi di routing di veicoli

Daniele VigoDEIS, Università di Bologna

tel. 051/2093029 fax 2093073email: [email protected]://www.or.deis.unibo.it

VRP-TO.2D. Vigo

ProgrammaI. Introduzione alla Ricerca Operativa ed ai

problemi di routing: • Componenti del problema• Esempi di applicazioni reali

II. Vehicle routing problem• Modelli matematici e di teoria dei grafi• Algoritmi euristici

Maggio 2001

2



VRP-TO.3D. Vigo

Aspetti economici• 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

VRP-TO.4D. Vigo

Tecniche 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

Maggio 2001

3



VRP-TO.5D. Vigo

Ricerca Operativa ?• applicazione di metodi scientifici

a problemi decisionali che si presentano in strutture organizzate complesse

Matematica Informatica

Ricerca Operativa (Operations Research)Scienza della Gestione (Management Sc.)

Scienza delle Decisioni (Decision Sc.)

VRP-TO.6D. Vigo

Sistemi Organizzati• insieme di elementi legati da forme di interazione

Es. Reparto di produzione

M1 M2

M3 M4

Elementi: macchine

Interazione: flussi di materiale

Maggio 2001

4



VRP-TO.7D. Vigo

Problemi decisionali• Scelta, tra diverse alternative, della configurazione

relativa ad un insieme di decisioni che consente di ottenere dal sistema le prestazioni desiderate

Decisioni:• layout impianto• tipo di macchine• sequenza lavorazioni

Prestazioni: max produttività, min costo, …

M1 M2

M3 M4

VRP-TO.8D. Vigo

Problemi decisionali (2)• Livello Strategico (Pianificazione/Planning)

• Definizione e valutazione delle alternative• generalmente si opera in regime probabilistico• Es. layout impianto, scelta delle macchine, …

• Livello Operativo (Programmazione/Management)• Definizione della prassi operativa nell’ambito delle

scelte strategiche fatte• generalmente si opera in regime deterministico

Scelte strategiche

Scelte operative

Maggio 2001

5



VRP-TO.9D. Vigo

Sistemi e Modelli• Modello:

rappresentazione semplificata di un sistema reale,progettata per rispondere, mediante analisi sperimentali, a domande specifiche (risposta agli ingressi/decisioni).

ModelloUscite

(Prestazioni)Ingressi

(Decisioni/Controlli)

VRP-TO.10D. Vigo

Classificazione• Modello Fisico:

riproduzione in scala (similitudine o analogia) • Modello Matematico:

insieme di relazioni logico/matematiche che descrivono il comportamento del sistema

• Statico: sistema in equilibrio• Dinamico: sistema in evoluzione (nel tempo)• Analitico: descritto mediante equazioni/diseq.• Numerico: descritto mediante algoritmi di calcolo

Maggio 2001

6



VRP-TO.11D. Vigo

Modelli matematiciz = f (x1,x2, …)

• z valore delle “prestazioni” (v. dipendente)• x1,x2, …variabili decisionali (v. indipendenti)• spesso (x1,x2, …) devono assumere valori entro un

insieme specifico (regione ammissibile)• Es. 1 s = v t • Es. 2 z = max {f (x), x ∈ F}

VRP-TO.12D. Vigo

Modelli matematici (2)• Modelli Prescrittivi:

• forma di f (•) nota • valori delle x noti e controllabili dal decisore• normalmente usati a livello Operativo per la

determinazione dei valori di x che “massimizzano” z• Modelli Descrittivi:

• forma di f (•) nota • valori delle x non noti e/o non controllabili dal decisore• normalmente usati a livello Strategico per la

determinazione/stima dei valori di alcune x in funzione di altre

Maggio 2001

7



VRP-TO.13D. Vigo

Modelli e realtà• Proprietà di un modello:

• astrazione (scalabilità, generalità)• sintesi (solo le caratteristiche rilevanti)

• Un modello può migliorare il grado di comprensione della realtà:

• individuazione delle componenti importanti• relazioni di causa effetto

⇒Può migliorare le decisioni

VRP-TO.14D. Vigo

Modelli e Ricerca Operativa (1)• Sistema “reale” di distribuzione merci

Magazzini ClientiFabbriche

Maggio 2001

8



VRP-TO.15D. Vigo

Assunzioni ed ipotesiProblema tattico di determinazione dei flussi:• staticità (Es. problema “giornaliero”):

• domanda media• non si considerano i tempi di servizio

• costi di trasporto “lineari” = cij xij

• solo vincoli di capacità: • fabbriche (produzione massima nel periodo)• magazzini (massima q.tà di merce “trattabile”)

⇒ modello di programmazione lineare

VRP-TO.16D. Vigo

Modello schematico (astratto)

F1

F2

Ma

Mb

Mc

C1

C2

C3

C4

C5

m1

m2

Capacità

c1a

c1b

Costi

ta1

Costi

d1

d2

d3

d4

d5

Domanda

ma

mb

Capacità

mc

Maggio 2001

9



VRP-TO.17D. Vigo

Modello Matematico• Variabili decisionali:

x flussi tra fabbriche e magazzini

F1

F2

Ma

Mb

Mc

C1

C2

C3

C4

C5

m1

m2

Capacità

c1a

c1b

Costi

ta1

Costi

d1

d2

d3

d4

d5

Domanda

y flussi tra magazzini e negozi

VRP-TO.18D. Vigo

Modello matematico (2)

(obiettivo)min c1a x1a + c1b x1b + … ta1 ya1 + ta2 ya2 + …

(vincoli di capacità)∀ f: x1a + x1b + … ≤ m1

∀ m: x1a + x2a + … ≤ ma

(vincoli sulla domanda) ya1 + y b1 + … ≥ d1

(bilanciamento dei flussi)x1a + x2a … = ya1 + y a2 …

F1

F2

Ma

Mb

Mc

C1

C2

C3

C4

C5

m1

m2

c1ac1b

ta1 d1

d2

d3

d4

d5

Maggio 2001

10



VRP-TO.19D. Vigo

III. Verifica del modello• Calibrazione dei parametri del modello:

• si determinano i valori dei parametri caratteristici in modo che il modello fornisca risposte (valori misurati) aderenti alla realtà

• Esperimenti sul modello e confronto dei risultati con valori osservati nella realtà

• Eventuale revisione del modello

127 1000 127 ~1000Modello

VRP-TO.20D. Vigo

IV. Determinazione delle soluzioni• Mediante un “algoritmo” si generano soluzioni

alternative (Es. diversi n) e si sceglie la “migliore” (minor costo)

• Es. pochi valori di n da “tentare”: enumerazione

C

n1 2 3 4 5 6 7 8 9

sol. “ottima”

Maggio 2001

11



VRP-TO.21D. Vigo

I sette ponti di Königsberg• Problema di Eulero (1707-1783)

Pregel

È possibile effettuare una passeggiata, ritornando al punto di partenza, dopo aver attraversato tutti i ponti una sola volta ?

VRP-TO.22D. Vigo

Modello del problema dei ponti• Rappresentazione astratta del problema:

nascita della Teoria dei Grafi• Grafo equivalente alla mappa:

Pregel B

A

C

D

Maggio 2001

12



VRP-TO.23D. Vigo

Soluzione del problema

• Esiste un percorso chiuso che attraversa tutti gli archi del grafo una ed una sola volta ?(Circuito Euleriano)

B

A

C

D

Cond. necessaria e sufficiente(Eulero, 1736): Il circuito esiste se e solo se in ogni nodo ha un numero pari di lati incidenti

⇒ Il problema di Königsbergnon ha soluzione !!

VRP-TO.24D. 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

Maggio 2001

13



VRP-TO.25D. Vigo

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

• globali • sui singoli viaggi

• Obiettivi dell’ottimizzazione

VRP-TO.26D. 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

Maggio 2001

14



VRP-TO.27D. Vigo

Rete stradale (2)

scala regionale: grafo non orientato

VRP-TO.28D. Vigo

Rete stradale (3)

scala urbana: grafo orientato

Maggio 2001

15



VRP-TO.29D. Vigo

Rete stradale (4)

Soluzioni ibride

VRP-TO.30D. 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

Maggio 2001

16



VRP-TO.31D. Vigo

Rete Stradale (6)• Proprietà di triangolarità

k

i j

c c c i j kij ik k j≤ + ∀ , ,

8

3 6

VRP-TO.32D. 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)

Maggio 2001

17



VRP-TO.33D. 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-TO.34D. Vigo

Autisti• dipendenti o “padroncini”• vincoli sindacali

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

• disponibilità nel periodo in esame

Maggio 2001

18



VRP-TO.35D. 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-TO.36D. 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)

Maggio 2001

19



VRP-TO.37D. 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-TO.38D. 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

Maggio 2001

20



VRP-TO.39D. 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-TO.40D. 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

Maggio 2001

21



VRP-TO.41D. 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-TO.42D. 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

Maggio 2001

22



VRP-TO.43D. Vigo

TSP• Soluzione ≡ permutazione di {1, …, n}• se G completo ⇒ (n-1)! soluzioni

• 2 casi per la matrice dei costi:

TSP o STSP :simmetrica ⇒∀= jicc jiij ,

ATSP :aasimmetric ⇒∀

≠=

jicc jiij ,

VRP-TO.44D. Vigo

TSP simmetricoGrafo non orientato G(V,E):

V={1,…,n} vertici |V|=nE={e1,…,em} lati (edges) |E|=mce ≥ 0 costo lato e

SS δ (S) = ins. Lati incidenti in S

σ (S) = ins. Lati interni ad S

eα(e) β(e)

Maggio 2001

23



VRP-TO.45D. Vigo

Circuito Hamiltoniano• Cammino elementare chiuso che visita tutti i

vertici del grafo• ogni vertice deve avere grado 2• ogni vertice deve essere raggiunto • ogni “taglio” deve essere attraversato almeno 2 volte

S

VRP-TO.46D. Vigo

Modello matematico a 2 indici

=

∈

altrimenti0soluzionein lato se1

: lato ogniper e

x

Ee

e

eα(e) β(e)

Maggio 2001

24



VRP-TO.47D. Vigo

Funzione obiettivo• Minimizzare il costo degli archi scelti

∑∈

=Ee

ee xcz min

VRP-TO.48D. Vigo

i

Vincoli di grado• Ogni vertice deve avere due archi incidenti

( )Vix

iee ∈∀=∑

∈

2δ

δ(i)

Maggio 2001

25



VRP-TO.49D. Vigo

Soluzione non ammissibile

Subtour isolato

VRP-TO.50D. Vigo

Vincoli di connessione 1

( )2,2 ≥⊂∀≥∑

∈

SVSxSe

e δ

Vincoli di taglio (CUT):Ogni taglio deve essere attraversato almeno 2 volte

S

Maggio 2001

26



VRP-TO.51D. Vigo

Vincoli di connessione 2• Vincoli di Subtour elimination:

il numero di archi interni ad un sottoinsieme S selezionati deve essere minore di |S|

( )2,1 ≥⊂∀−≤∑

∈

SVSSxSe

e σ

S

VRP-TO.52D. 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

Maggio 2001

27



VRP-TO.53D. 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

VRP-TO.54D. 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

Maggio 2001

28



VRP-TO.55D. 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%

VRP-TO.56D. 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 viaggiSoluzione ottimizzata: 943 km (-17%), 12 viaggi

Maggio 2001

29



VRP-TO.57D. 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

VRP-TO.58D. 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

Maggio 2001

30



VRP-TO.59D. 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

VRP-TO.60D. 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

Maggio 2001

31



VRP-TO.61D. 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%

VRP-TO.62D. 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

Maggio 2001

32



VRP-TO.63D. Vigo

Analisi conferimenti (2)

Riempimento osservato

VRP-TO.64D. Vigo

Analisi conferimenti (3)

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

Stima

valoriosservati

Maggio 2001

33



VRP-TO.65D. 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)

VRP-TO.66D. Vigo

Sistema di gestione

Maggio 2001

34



VRP-TO.67D. Vigo

Ottimizzazione offerta

Tipi di contenitoriutilizzabili e loro caratteristiche

VRP-TO.68D. 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%)

Maggio 2001

35



VRP-TO.69D. 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%)

VRP-TO.70D. 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 %)

Maggio 2001

36



VRP-TO.71D. 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

VRP-TO.72D. 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 …

Maggio 2001

37



VRP-TO.73D. 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

VRP-TO.74D. Vigo

VRP con vincoli di capacità• n clienti (vertici 1, …, n)• 1 deposito (vertice 0), V= {0,1,…,n}• solo consegne di un unico tipo d i ni = 1, ,K

D S d S Vii S

( ) = ∀ ⊆∈∑

domanda completamente soddisfatta K veicoli identici (capacità C )1 solo viaggio per veicolosolo vincoli di capacità

d0 0=

Maggio 2001

38



VRP-TO.75D. Vigo

VRP con vincoli di capacità (2)• Kmin = numero minimo di veicoli

per servire tutti i clienti

minmin /)( KKCVDK ≥⇒≥v(S) = numero minimo di veicoli per

servire tutti i clienti in S

})0{\(min VvK =Grafo completo orientato (ACVRP) o non orientato (CVRP)

c i j A c i Vij ii≥ ∀ ∈ = +∞ ∀ ∈0 ( , ) ,minimizzazione del costo totale dei viaggi

VRP-TO.76D. Vigo

Problema ACVRP

• determinare K circuiti semplici (viaggi) di costo totale minimo tali che:• ogni circuito passa per il vertice 0 (deposito)• ogni cliente è visitato da un solo circuito• la somma delle domande dei vertici visitati da un circuito

non supera C• ACVRP e CVRP sono NP-hard

(la determinazione della soluzione ottima richiede nel caso peggiore tempi di calcolo esponenziali in n)

• TSP caso particolare: C > D(V), K = Kmin = 1

Maggio 2001

39



VRP-TO.77D. Vigo

Modello matematico a 2 indici

=

∈

altrimenti0soluzionein ),( arco se1

:),( arco ogniper ji

x

Aji

ij

( ) SSvVS

servireper veicolidi n.minimo: dato

=⊆

i j

VRP-TO.78D. Vigo

Funzione obiettivo

z c xij ijj Vi V

=∈∈∑∑min

Maggio 2001

40



VRP-TO.79D. Vigo

Vincoli di grado per i clienti

{ }0\ 1 VjxVi

ij ∈∀=∑∈

jj

ii{ }0\ 1 VixVj

ij ∈∀=∑∈

VRP-TO.80D. Vigo

Vincoli di grado per il deposito

x Kii V

0∈∑ =

x Kjj V

0∈∑ =

00

00

2=K

Maggio 2001

41



VRP-TO.81D. Vigo

Soluzione non ammissibile (1)

53

2

3

622

3

2

K = 3, C = 10

Subtour isolato dal deposito

S

VRP-TO.82D. Vigo

5

3

2

3

622

3

2


K = 3, C = 10

Route sovraccarica

Maggio 2001

42



VRP-TO.83D. Vigo

Connessione e capacità

( )

{ }

x v S

S V S

ijj Si S ∈∉∑∑ ≥

∀ ⊆ ≠ ∅ \ ,0

S v S: ( ) = 2

Capacity-cut constraints

VRP-TO.84D. Vigo

5

3

2

3

622

3

2

K = 3, C = 10


Maggio 2001

43



VRP-TO.85D. Vigo

{ }0\ 1 VjxxVi

jiVi

ij ∈∀== ∑∑∈∈

x x Kii V

ii V

0 0∈ ∈∑ ∑= =

( ) { }x v S V Sijj Si S ∈∉∑∑ ≥ ∀ ⊆ ≠ ∅ S \ ,0

{ }x i , j Vi j ∈ ∀ ∈0 1,

Modello ACVRP

z c xij ijj Vi V

=∈∈∑∑min

VRP-TO.86D. Vigo

Algoritmi esatti per il VRP• algoritmi “Branch & Bound”• algoritmi “Branch & Cut”

• in grado di risolvere problemi con:• vincoli di capacità e/o durata massima• n < 50 (alcuni problemi n = 100)

• per problemi con vincoli e dimensioni reali si usano Algoritmi euristici

Maggio 2001

44



VRP-TO.87D. Vigo

Algoritmi euristici per il VRP• tutti i vincoli operativi dei problemi reali• soluzioni ammissibili di buona qualità

(2%-3% dall’ottimo)• tempi di calcolo limitati (pochi minuti su PC)• vengono presentati gli algoritmi euristici

nel caso di grafi non orientati• algoritmi costruttivi e di ricerca locale

VRP-TO.88D. Vigo

Algoritmi costruttivi per il VRP• vengono costruiti uno o più viaggi inserendo ad

ogni iterazione un cliente in uno dei viaggi in costruzione

• inizializzazione dei viaggi• criteri di espansione dei viaggi:

• quale cliente inserire ?• dove (viaggio, posizione) inserirlo ?

• Modalità di costruzione dei viaggi:• sequenziali (un viaggio alla volta)• paralleli (più viaggi alla volta)

Maggio 2001

45



VRP-TO.89D. Vigo

Inizializzazione dei viaggi

• scelta del pivot:• lontano dal deposito• elevato “grado di difficoltà”

• grado di difficoltà d(i) del cliente i:• domanda elevata• finestre temporali strette• pochi veicoli utilizzabili• priorità elevata• pochi clienti vicini non ancora serviti

p

ciascun viaggio inizializzato con un solo cliente (pivot) p: (deposito, p, deposito)

VRP-TO.90D. Vigo

Criteri di espansione dei viaggi• scelta del cliente i (non ancora servito) che deve

essere inserito nell’iterazione attuale in uno dei viaggi in costruzione:

• scelta del viaggio• vincoli statici: capacità, utilizzabilità, …

• scelta della posizione nel viaggio• vincoli dinamici: finestre temporali, durata massima,

precedenze, …

• criterio del saving (risparmio)• criterio dell’extramileage (aumento percorrenza)

Maggio 2001

46



VRP-TO.91D. Vigo

Criteri di espansionetra dep e 2

5

3

2

3

622

3

2

K = 3, C= 10

1

2

3

4

5

9

67

8

tra 3 e deptra 2 e 3

VRP-TO.92D. Vigo

Criterio del “saving”• saving dei clienti i e j (max):

risparmio ottenibile servendoli nello stesso viaggio e non in due viaggi separati

ijji cccjis −+= 00),(

i

j

i

j(s(i,j) = – ∞ se (i,j) non ammissibile)

Maggio 2001

47



VRP-TO.93D. Vigo

Criterio dell’ “extramileage”• extramileage di h rispetto ad i e j (min):

aumento del costo del viaggio coonseguenteall’inserzione di h tra i e j

ijhjih cccjhim −+=),,(

(m(i,h,j)= +∞ se non ammissibile)

i

j

hi

j

h

VRP-TO.94D. Vigo

Costruzione dei viaggiMetodi sequenziali• si costruisce un viaggio alla volta• ad ogni iterazione si sceglie il “miglior cliente”

non servito e lo si inserisce nella “miglior posizione” all’interno del viaggio

• si termina il viaggio attuale quando non si possono inserire altri clienti

• non si può valutare se è meglio inserire un cliente nel viaggio attuale o aspettare per inserirlo in uno dei viaggi successivi

Maggio 2001

48



VRP-TO.95D. Vigo

Metodo sequenziale (extramileage)viaggio 1

5

3

2

3

622

3

2

K = 3, C= 10

1

2

3

4

5

9

67

8

cliente 9cliente 3

pivot 1

VRP-TO.96D. Vigo


cliente 6pivot 8

5

3

2

3

622

3

2

K = 3, C= 10

1

2

3

4

5

9

67

8

cliente 7cliente 2

Maggio 2001

49



VRP-TO.97D. Vigo


cliente 5pivot 4

5

3

2

3

622

3

2

K = 3, C= 10

1

2

3

4

5

9

67

8

VRP-TO.98D. Vigo

Metodo sequenziale (pivot diversi)viaggio 1pivot 2

5

3

2

3

622

3

2

K = 3, C= 10

1

2

3

4

5

9

67

8

viaggio 2pivot 8viaggio 3pivot 5

Maggio 2001

50



VRP-TO.99D. Vigo

Costruzione dei viaggiMetodi paralleli• si costruiscono m viaggi alla volta• i viaggi vengono costruiti simultaneamente,

scegliendo ad ogni iterazione il “miglior cliente” non servito ed inserendolo nella “miglior posizione” del “migliore viaggio” tra gli m attuali

• quando gli m viaggi attuali sono terminati, si itera il procedimento considerando m nuovi viaggi

VRP-TO.100D. Vigo

Metodo parallelo (extramileage)

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

viaggio 1viaggio 1m = 2m = 2 pivot 1pivot 1

viaggio 2viaggio 2pivot 8pivot 8

cliente 9cliente 9

Maggio 2001

51



VRP-TO.101D. Vigo




55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

cliente 3cliente 3cliente 2cliente 2

VRP-TO.102D. Vigo




55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

cliente 6cliente 6cliente 6cliente 6cliente 7cliente 7

viaggio 3viaggio 3

cliente 4cliente 4pivot 5pivot 5

cliente 7cliente 7

Maggio 2001

52



VRP-TO.103D. Vigo

Costruzione dei viaggi• i metodi paralleli richiedono tempi di esecuzione

maggiori di quelli corrispondenti ai metodi sequenziali

• i metodi paralleli ottengono in generale soluzioni migliori di quelle ottenibili con i metodi sequenziali

• nei metodi sequenziali gli ultimi viaggi raccolgono in generale clienti lontani tra loro

VRP-TO.104D. Vigo

Algoritmi Cluster-first-route-second• si suddividono i clienti in sottoinsiemi

ammissibili:uno per ogni viaggio

• per ciascun sottoinsieme si determina l’itinerario (circuito a costo minimo passante per il deposito e i clienti)

Maggio 2001

53



VRP-TO.105D. Vigo

Cluster-first-route-second (1)

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

VRP-TO.106D. Vigo

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

Cluster-first-route-second (2)

Maggio 2001

54



VRP-TO.107D. Vigo

Algoritmi Route-first-cluster-second• si determina un circuito a costo minimo

complessivo per tutti i clienti• si suddivide il circuito in pezzi ammissibili

(viaggi)

VRP-TO.108D. Vigo

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

vertice iniziale 1vertice iniziale 1

Route-first-cluster-second (1)

Maggio 2001

55



VRP-TO.109D. Vigo

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

vertice iniziale 2vertice iniziale 2

Route-first-cluster-second (2)

VRP-TO.110D. Vigo

Algoritmo di Clarke-Wright1. calcola il saving s(i,j) per ogni coppia (i,j)2. ordina le coppie (i,j) per s(i,j) decrescenti3. ogni cliente servito da solo in un viaggio4. considera la prossima coppia (i,j)5. se i e j sono estremi di viaggi parziali e se i

due viaggi possono essere uniti: inserisci l’arco (i,j) in soluzione

6. se esistono coppie non esaminate ripeti 47. completa i viaggi collegandoli con il deposito

Maggio 2001

56



VRP-TO.111D. Vigo

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

ijji cccjis −+= 00),((7,8) NO(1,2) NO(3,4) NO(5,6) NO

Algoritmo di Clarke-Wright

VRP-TO.112D. Vigo

Algoritmi di ricerca locale

• esplorazione di un intorno di una soluzione S:insieme di soluzioni ottenibili da S mediante le seguenti “mosse”1. spostamento di un cliente2. scambio tra due clienti3. scambio tra due coppie di archi• nello stesso viaggio, in viaggi diversi

• si esegue la mossa che minimizza il costo• se non si ottengono miglioramenti STOP

Maggio 2001

57



VRP-TO.113D. Vigo

Spostamento di un cliente

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

cliente 6

VRP-TO.114D. Vigo

Spostamento di un cliente

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

cliente 6

Maggio 2001

58



VRP-TO.115D. Vigo

Scambio tra due clienti

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

clienti 7 e 2

VRP-TO.116D. Vigo

Scambio tra due clienti

55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

clienti 7 e 2

Maggio 2001

59



VRP-TO.117D. Vigo

Scambio tra due coppie di archi

archi (6,8), (7,9)55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

VRP-TO.118D. Vigo

Scambio tra due coppie di archi

archi (6,8), (7,9)55

33

22

33

662222

33

22

K = 3, C= 10

11

22

33

44

55

99

6677

88

Maggio 2001

60



VRP-TO.119D. Vigo

Algoritmi “Tabu Search”• si esegue la mossa migliore che cambia la

soluzione attuale S, anche se la nuova soluzione S’ ha un costo globale maggiore

• per evitare di “ripassare” per le stesse soluzioni si memorizza una lista delle ultime m soluzioni esplorate che quindi risultano “tabu” (le mosse che portano alle soluzioni tabu vengono proibite)

Bologna Servizi di trasporto merci: Problemi di routing di ... · Maggio 2001 6 Daniele Vigo -...

Documents

Transcript of Bologna Servizi di trasporto merci: Problemi di routing di ... · Maggio 2001 6 Daniele Vigo -...