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
 
 
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