Supporto didattico ad uso esclusivo...

Corso di Trasporto merci e logistica

I problemi di I problemi di nodenode routingrouting

Supporto didattico ad uso esclusivo internoSupporto didattico ad uso esclusivo interno

a cura di: ing. Mario Cordascoa cura di: ing. Mario Cordasco

A.A. 2008-2009

Corso di Trasporto merci e Logistica

I problemi di node routingIng. Mario Cordasco

La distribuzione fisica delle merci

La logistica è l’insieme delle attività e dei servizi che permettono alle merci di essere spostate dai punti (sorgenti) in cui esse sono disponibili, alle destinazioni che le richiedono.

La distribuzione fisica comprende le attività di:

• gestione degli ordini;

• stoccaggio e movimentazione interna delle merci;

• trasporto delle merci. Voce di costo maggiore

Deve avvenire con tempi costi e livelli di servizio opportuni



I problemi di routing

Vengono definiti problemi di routing i problemi di trasporto a breve distanza.

Sono caratterizzati da spostamenti che hanno origine e destinazione collocate in un ambito territoriale locale (ambito urbano o regionale) e che possono essere effettuati nell’arco di una giornata.

Si dispone di una flotta di veicoli che partono e ritornano nello stesso punto

consegna di merci precedentemente trasportate ad un terminale locale in forma consolidata

ritiro di merci destinate ad essere successivamente consolidate in un terminale

Obiettivo: determinare le rotte che minimizzano tempi e costi della distribuzione




Una rotta può servire:

•solo punti di ritiro (pick-up);

•solo punti di consegna (delivery);

•entrambi i tipi di punti precedenti (pick-up and delivery).



P

Deposito

P

P P

P

P

Operazioni di pick-up

D

Deposito

D

D D

D

D D

Deposito

P

D P

P

D

Operazioni di delivery Operazioni di pick-up e delivery


I problemi di routing sono indicati con i termini “VehicleRouting Problem” o più semplicemente con la sigla VRP.

Esempi pratici:

•Distribuzione a supermercati.

•Distribuzione di snack e bevande a distributori.

•Distribuzione di prodotti petroliferi.

•Distribuzione prodotti finiti e raccolta materie prime.

•Trasporto di merci fra depositi.




•Raccolta rifiuti solidi urbani e smistamento verso inceneritori/discariche.

•Ritiro contenitori vuoti ed imballaggi.

•Servizi di consegna e raccolta della posta.

•Servizi di scuola-bus.

•Servizi di corriere espresso.

•Movimentazioni merci all'interno di un magazzino.

•Picking di merci da un magazzino automatizzato.




Ipotesi importanti di partenza-Siano note le caratteristiche della domanda da soddisfare,

-Siano note le posizioni dei punti che richiedono il servizio,

-Siano note le caratteristiche della flotta,

-Siano noti i periodi temporali entro cui è possibile effettuare il servizio,

-Siano noti i costi da minimizzare.

Risultati attesi-Numero di giri da effettuare,

-Veicoli assegnati ad ogni giro,

-Costo, durata temporale e lunghezza del giro,

-Successione delle fermate,

-Quantità trasportate (consegnate e/o ritirate),

-Eventuali ordini non soddisfatti.

Vincoli operativi




I vincoli operativi più comuni:

•La quantità di merce trasportata non supera la capacità dei veicoli (in peso o in volume) adibiti al trasporto;

•Se lo stesso mezzo effettua le consegne ed i ritiri;

•Incompatibilità veicolo-cliente (es.: attrezzature di scarico richieste, strade troppo piccole per raggiungere i clienti);

•Incompatibilità prodotto-veicolo (es.: prodotti che necessitano della refrigerazione, prodotti molto ingombranti);

•Layout di carico (es.: imballaggi e contenitori di diverse caratteristiche);

•La durata di una rotta non supera la durata di un turno lavorativo;

•Precedenze nelle consegne legate ad accordi commerciali;

•I clienti siano serviti in fasce orarie prestabilite (time windows).




Varianti di VRP:

Il VRP base è il problema in cui da un deposito (o impianto) centrale una flotta di veicoli deve rifornire un insieme di clienti.

Il Capacitated VRP (CVRP) è un problema di routing in cui gli veicoli sono tutti uguali e hanno una capacità massima di trasporto (in peso o in volume).

Il VRP Time Windows (VRPTW) è una generalizzazione del VRP in cui il servizio di consegna e/o raccolta merce deve essere effettuato all'interno di intervallo di tempo prestabilito durante il quale il cliente deve o può essere servito.

Nel VRP Delivery and Pickup (VRPDP) l'insieme dei clienti è partizionato in clienti di consegna ed in clienti di raccolta. Possono esserci dei vincoli di precedenza da soddisfare fra le consegne e le raccolte in un viaggio.




Classificazione

VRP

NRP ARP



TSP

ATSP STSP

CPP

RPP CCPP

URPP DRPP UCCPP DCCPP


In genere la classificazione avviene in base al tipo di circuito da compiere. Ne esistono due tipi:

Circuito hamiltoniano

Dato un grafo G = (V, A), è un ciclo orientato nel quale tutti i vertici V compaiono esattamente una volta.

Circuito euleriano

Dato un grafo G = (V, A), è un ciclo orientato nel quale tutti gli archi devono essere percorsi, anche più di una volta.

Node Routing Problem (NRP)

Traveling Salesman Problem(TSP)

Arc Routing Problem (ARP)

Chinese Postman Problem(CPP)



Traveling Salesman Problem

È un problema che venne posto per la prima volta nel 1859 dal matematico irlandese SirWilliam Rowan Hamilton.

Su un dodecaedro regolare di legno egli disegnò il nome di una città su ogni vertice e propose di individuare un cammino lungo gli spigoli che, partendo da un punto iniziale e passando per ciascuna città una ed una sola volta, permettesse poi di tornare al punto di partenza.




Definizione

Dato un grafo G = (V,A) si definisce cammino hamiltoniano un cammino c tale che

c = (v1, v2, …, vk) tale per cui:

* k è pari a |V|, cardinalità di V

* vi ≠ vj per ogni i, j

Se G è simmetrico:

Simmetric Traveling Salesman Problem (STSP)

Se G non è simmetrico:

Asimmetric Traveling Salesman Problem (ATSP)




Caratteristiche principali



Deve valere la disuguaglianza

triangolare

Il grafo deve essere connesso

Ogni nodo ha 2 archi incidenti

Grafo di partenza

Soluzione individuata


Tecniche risolutive

Un primo approccio alla risoluzione del problema, di tipo elementare, può consistere nell’individuare tutti i cicli hamiltoniani del grafo e far coincidere la soluzione con il ciclo a costo minimo.

Il numero di soluzioni cresce spaventosamente con il numero di nodi del grafo:

Ncicli = (n-1)! n (n-1)!1 12 13 24 65 246 1207 7208 5.0409 40.320

10 362.88015 87.178.291.20020 121.645.100.408.832.00025 620.448.401.733.239.000.000.00030 8.841.761.993.739.700.000.000.000.000.000

Necessità di algoritmi risolutivi in grado di

limitare i tempi di calcolo




Tecniche risolutive

Il problema così posto è di difficile soluzione e non sono noti algoritmi efficaci ed efficienti allo stesso tempo.

Essi vengono suddivisi in due grandi classi: algoritmi di tipo esatto ed algoritmi di tipo euristico.

Le tecniche euristiche vengono utilizzate :

- quando le dimensioni del problema sono eccessive,

- quando si ha la necessità di risolvere il problema in tempi rapidi,

- quando i dati di partenza del problema sono approssimati,

- quando si devono trattare problemi dinamici.




Tecniche risolutive

Algoritmi Euristici:

1. Metodi costruttivi;

2. Metodi di miglioramento;

3. Metodi a due fasi:

3. Ricerca locale.

Algoritmi Esatti:

1. Metodi Branch and Bound;

2. Metodi Branch and Cut;

3. Metodi basati sulla programmazione dinamica;

4. Metodi basati sulla formulazione Set Partitioning.




Metodo Branch and Bound

Branch = ramo, diramazione. Branching: generazione di sottoinsiemi.

Bound = confine. Bounding: scelta del limite (inferiore).

Si ricorre ad una ricerca esaustiva di tutti i cicli hamiltoniani su partizioni del grafo.




Metodo Branch and Bound

3. Si uniscono i cicli individuati per ottenere un nuovo ciclo di costo minimo

2. Si cercano i cicli hamiltoniani di costo minimo nei sottografi

1. Si divide il grafo iniziale in sottografi




Tecniche euristiche:

1. Metodi costruttivi;

2. Metodi di miglioramento;

3. Metodi a due fasi;

4. Metodi di ricerca locale;

la soluzione viene ottenuta partendo da un cammino elementare e migliorato attraverso una sequenza di soluzioni parziali fino a raggiungere una soluzione ammissibile.

la soluzione viene ottenuta migliorando un ciclo hamiltoniano già individuato.

la soluzione viene ottenuta costruendo prima un ciclo hamiltoniano e migliorando poi la soluzione individuata.

la soluzione viene ottenuta partendo da una soluzione nota ed effettuando delle trasformazioni in alcuni intorni; gli algoritmi si fermano quando viene trovata un ottimo locale.




Nodo più vicino

Parte dal nodo di riferimento.

Ad ogni iterazione aggiunge il vertice che produce il minimo incremento di costo (il nodo più vicino) e che non è stato ancora visitato.

Al termine della procedura, collegando i due estremi del percorso, si ottiene un ciclo hamiltoniano.




Nodo più vicino

È un metodo che non funziona bene; i primi archi sono brevi gli ultimi molto lunghi.

È una buona base da migliorare.

È semplice da applicare.

La soluzione individuata è in media superiore del 25% rispetto a quella esatta.




Nodo più lontano

Parte dal nodo di riferimento.

Individua il nodo più lontano da quello di riferimento, ottenendo un primo ciclo.




Nodo più lontano

Ad ogni iterazione aggiunge il vertice che è più distante dai nodi già inseriti (il nodo più lontano) e che non è stato ancora visitato.

Il vertice viene inserito in maniera tale che l’incremento del circuito parziale sia minimo.

Al termine della procedura si ottiene un ciclo hamiltoniano.




Nodo più lontano

È un metodo che non funziona bene; i primi archi sono lunghi gli ultimi molto brevi.


È semplice da applicare.

La soluzione individuata è in media superiore del 15% rispetto a quella esatta.




A

B

C

EChristofides

Parte da un albero ricoprente minimo.

Si uniscono i nodi di ordine dispari, inserendo degli archi di matching.

D

A

C

E

Nodi di ordine dispari: A C D E B DArchi di matching: A-C, D-E




E

A

C

Christofides

Il ciclo ottenuto non è hamiltoniano; si eliminano dal cammino i nodi visitati più di una volta a vantaggio di costo totale.

Al termine della procedura si ottiene un ciclo hamiltoniano.

B DCiclo ottenuto: A-B-C-D-E-C-A

E

A

C

B D




Christofides

E È un metodo basato su un algoritmo più complesso.


La soluzione individuata è in media superiore del 10-20% rispetto a quella esatta.

A

C

BD



Supporto didattico ad uso esclusivo...

Documents

Transcript of Supporto didattico ad uso esclusivo...