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={v₁,..,v_n} insieme di n nodi rappresentativo di località,
A={(v_i,v_j): v_i,v_j∈V} insieme archi che identificano i possibili collegamenti tra località.

A ciascun arco è associato un costo c_ij 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.

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)