Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giuseppe Bruno » 20.Introduzione ai problemi di routing


Argomenti della lezione

  • Gli elementi di un problema di routing
  • Rappresentazione dei problemi
  • I principali modelli

Gli elementi di un problema di routing

I problemi di logistica distributiva o di routing riguardano gli aspetti organizzativi e gestionali con riferimento alla movimentazione, distribuzione e trasporto di persone e beni.

I problemi presentano caratteristiche molto diverse a partire dagli oggetti da movimentare (es: semilavorati, prodotti finiti, merci, pacchi, rifiuti, posta, persone), dai mezzi con i quali si effettua la movimentazione (es: robot, AGV, veicoli, furgoni, mezzi specializzati, navi, aerei), dai tempi necessari per l’effettuazione del servizio (es: minuti, ore, giorni) agli spazi nell’ambito dei quali si deve svolgere il servizio (es: interno di un’azienda, ambito urbano, area regionale, contesto nazionale ed internazionale).

Gli elementi di un problema di routing (segue)

Un problema di routing è caratterizzato dalla presenza di un insieme di clienti (customers) a ciascuno dei quali è associato un servizio da effettuare.

Obiettivo è la definizione di percorsi che un insieme di veicoli deve effettuare allo scopo di soddisfare i servizi richiesti.

I servizi possono essere di:

  • prelievo se un bene è prelevato dalla località in cui si trova il cliente;
  • consegna se un bene è consegnato presso la località in cui ha sede il cliente;
  • prelievo-consegna se un bene deve essere contestualmente prelevato da una località di origine e consegnato presso una località di destinazione.

Gli elementi di un problema di routing (segue)

Possibili vincoli

Nella pratica possono essere presenti diversi vincoli aggiuntivi. Esempi tipici sono vincoli di:

  • Numero e capacità dei veicoli a disposizione;
  • Vincoli temporali
    (es: vincoli sui tempi di prelievo e/o consegna, vincoli sulla durata massima dei percorsi). In questo caso bisogna considerare non solo la definizione dei percorsi ma anche la loro tempificazione (problema di routing e scheduling).

Rappresentazione dei problemi

Rappresentazione su grafo

Si consideri un grafo G=(V,A) con

V={v1,..,vn} insieme di n nodi rappresentativo di località,
A={(vi,vj): vi,vj∈V} insieme archi che identificano i possibili collegamenti tra località.

A ciascun arco è associato un costo cij che può indicare la lunghezza del collegamento, il tempo o il costo per coprirlo.

Si parla di problemi a

  • copertura dei nodi (node covering) se i servizi si intendono localizzati in corrispondenza dei nodi;
  • copertura di archi (arc covering) se i servizi si immagino distribuiti sugli archi;
  • Obiettivo: individuare un insieme di itinerari che visitino i nodi o gli archi presso i quali sono presenti i servizi.

Rappresentazione dei problemi (segue)

Rappresentazione su grafo

Se i costi cij sono tali che cij=cij ∀(vi,vj) il grafo rappresentativo è non orientato e il problema viene detto simmetrico.

In caso contrario il grafo è orientato e il problema viene detto asimmetrico.


Rappresentazione dei problemi (segue)

Rappresentazione su grafo

È sempre possibile associare ad un grafo qualsiasi un grafo completo in cui a ciascun arco (vi,vj) è attribuito il costo cij del percorso a costo minimo tra vi e vj.

Il grafo completo costruito in questo modo soddisfa anche la disuguaglianza triangolare, ovvero cijcis+csji,j,s.


I principali modelli


I principali modelli (segue)


I principali modelli (segue)

Complessità del problema

Il TSP appartiene alla classe dei problemi NP-hard per i quali, cioè, non esiste un algoritmo in grado di risolvere il problema in tempo polinomiale.

Una soluzione ammissibile è rappresentata da una permutazione

A-C-F-B-D-E-G-H

Il numero delle soluzioni è n!

I principali modelli (segue)


I principali modelli (segue)


I principali modelli (segue)


I principali modelli (segue)


I principali modelli (segue)


I principali modelli (segue)


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion