Portale di Ateneo - Unibs.it

• Nuovi sviluppi nei problemi di vehicle routing
  Responsabile: SPERANZA Maria Grazia
  Università degli Studi di BRESCIA
  speranza@eco.unibs.it
   
• Algoritmi euristici innovativi per problemi di Arc Routing, con particolare riferimento a quelli capacitivi e multi-obiettivo
  Responsabile: GRANDINETTI Lucio
  Università della CALABRIA
  lugran@unical.it
   
• Logistica collaborativa: modelli e algoritmi di vehicle routing e localizzazione ottima
  Responsabile: ARBIB Claudio
  Università degli Studi de L'AQUILA
  arbib@di.univaq.it
   
• Problemi di " Vehicle Routing e Dispatching" di tipo dinamico e stocastico
  Responsabile: GHIANI Gianpaolo
  Università degli Studi del SALENTO
  gianpaolo.ghiani@unisalento.it
   
• Problemi Integrati di Vehicle Routing e Container Packing: Modelli ed Algoritmi
  Responsabile: TADEI Roberto
  Politecnico di TORINO
  roberto.tadei@polito.it

L'obiettivo del progetto è quello di apportare un significativo avanzamento rispetto allo stato dell'arte nell'ottimizzazione della logistica distributiva, fornendo alla comunità scientifica e al mondo sociale e imprenditoriale strumenti teorici, metodologici e applicativi per la comprensione e la soluzione di problemi reali nell'attuale contesto competitivo.

Lo scenario che attualmente domina i mercati è caratterizzato dalla tendenza alla crescita della competizione tra aziende che si trovano quindi nella necessità di gestire in modo ottimale ogni aspetto economico, dalla roduzione al trasporto. Le problematiche della logistica distributiva sono un tema classico della ricerca in ambito economico: quasi ogni attività di tipo economico legata alla produzione e ai servizi prevede lo spostamento di merci, materiali o persone. Il trasferimento di materiali grezzi dai fornitori alle industrie manifatturiere, la movimentazione e consegna di prodotti dai magazzini ai clienti, nonché la movimentazione di materiali internamente all'azienda, rappresentano solo alcune delle molte attività affrontate giornalmente da quasi tutte le aziende. La complessità delle reti distributive ha richiesto anche in passato un forte impegno di razionalizzazione e riorganizzazione del servizio, sia in termini di efficienza (attraverso il contenimento dei costi di esercizio), sia di efficacia (attraverso una più elevata soddisfazione della clientela). Ad oggi, tuttavia, la maggior parte della letteratura scientifica si è focalizzata su modelli statici di logistica distributiva, nei quali si intende ottimizzare in funzione di un singolo obiettivo e per i quali le informazioni necessarie sono note integralmente al momento della pianificazione dei servizi.
Questi modelli e i corrispondenti metodi di soluzione non sono però più sufficienti a risolvere in modo efficiente i problemi di logistica distributiva nell'attuale contesto competitivo. Nella maggior parte delle applicazioni reali, infatti, le aziende hanno come obiettivo la minimizzazione del costo logistico totale, o hanno l'esigenza di determinare soluzioni che meglio permettano di raggiungere il miglior compromesso fra obiettivi diversi, o si trovano ad operare in contesti fortemente dinamici dove le informazioni disponibili al pianificatore non sono completamente note a priori. Negli ultimi anni quindi l'attenzione generale si è concentrata su modelli di logistica distributiva integrata, modelli di routing multiobiettivo e modelli con diverso grado di dinamismo, sia per gli evidenti vantaggi economici derivanti dal saper progettare soluzioni efficienti per sistemi integrati anche in assenza di informazione completa, sia grazie al forte sviluppo tecnologico. Quest'ultimo, consentendo comunicazioni in tempo reale, ha posto la necessità di un completo ripensamento, sia delle principali problematiche affrontate dalle aziende, sia delle metodologie richieste per risolverle. In particolare, le nuove tecnologie di comunicazione computer-based, quali Geographical Information System (GIS), Global Positioning System (GPS) e Intelligent Vehicle-Highway System (IVHS) da una parte ed i sistemi integrati capaci di gestire, elaborare e trasferire informazioni complesse in modo automatico (sistemi di Electronic Data Interchange (EDI) e tecnologie web-based) dall'altra, hanno consentito lo sviluppo di nuove strategie distributive offrendo alle imprese (incluse le piccole e medie imprese tipiche della realtà italiana) una rilevante opportunità di miglioramento della propria competitività globale. La moderna tecnologia ha pertanto aperto nuove prospettive nella gestione dell'informazione.

Le imprese necessitano quindi di nuovi strumenti di supporto alle decisioni per una efficiente ed efficace organizzazione e gestione della logistica distributiva. Assumono sempre più rilevante importanza tutte le tematiche legate alla minimizzazione dei costi e alla riorganizzazione dei sistemi logistico-distributivi verso forme caratterizzate da procedure decisionali in tempo reale. In particolare, è di cruciale importanza lo studio e la messa a punto di nuovi modelli e di più adeguate metodologie risolutive in grado di gestire problemi complessi, sia per la necessità di gestire in maniera congiunta le diverse problematiche di trasporto, i costi di mantenimento a scorta e i costi di produzione (saranno richieste nuove metodologie che consentano l'ottimizzazione delle intere catene di fornitura in strutture logistiche a rete ed in ambiti cooperativi), sia per la mancanza d'informazione (saranno richiesti strumenti teorici e computazionali che permettano di valutare differenti strategie, di prevederne i risultati e gli eventuali vantaggi).

Il presente progetto si pone come obiettivo finale quello di formulare modelli e implementare algoritmi per l'ottimizzazione dei processi distributivi e la razionalizzazione delle strutture dedicate al trasporto. L'obiettivo è quello di garantire consistenti risparmi sui costi totali e un miglioramento notevole della qualità del servizio, soprattutto nei termini in cui i modelli e gli algoritmi proposti siano in grado di incorporare le numerose caratteristiche operative dei problemi reali, fornendo soluzioni più soddisfacenti e compatibili con le esigenze operative delle aziende.

Il progetto è nato con l'idea di integrare le competenze delle cinque unità operative coinvolte, con il fine di sfruttare al meglio la specificità e la complementarietà delle stesse su problemi così complessi e innovativi. Da un lato quindi, ogni unità operativa svilupperà la corrispondente categoria di problemi in cui il progetto è articolato, al fine di utilizzare al meglio le competenze specifiche. Dall'altro lato, sono previste forme di integrazione e collaborazione fra le unità operative, al fine di sfruttare al meglio l'esistente complementarietà delle stesse. Le unità operative inoltre usufruiranno della importante collaborazione di numerosi ricercatori di fama internazionale nell'area dell'ottimizzazione, dei trasporti, della logistica e del supply chain management. Tali collaborazioni sono avviate da tempo e hanno già avuto ricadute in termini di numerose pubblicazioni su riviste internazionali di alto livello.

All'inizio del progetto, è previsto un incontro di tutte le unità operative al fine di definire l'articolazione del progetto, il coordinamento delle attività svolte e i tempi di realizzazione di ogni fase. Ogni fase verrà svolta in collaborazione fra le unità operative. La comunicazione sarà facilitata dalla creazione di un forum per lo scambio di informazioni. Ogni fase verrà conclusa con un incontro tra le unità operative, al fine di consolidare le conoscenze acquisite, coordinare l'attività e formalizzare i requisiti per le fasi successive. A conclusione dell'attività di ricerca, verrà organizzato un workshop al fine di illustrare e disseminare i risultati ottenuti.

Descriviamo ora ciascuna unità operativa e il corrispondente ruolo in funzione degli obiettivi previsti.

L'Unità operativa di Cosenza possiede competenze nel campo della definizione di modelli e metodi per affrontare problemi di grande interesse pratico che sorgono nel settore della logistica, con particolare riferimento alla gestione dei sistemi di distribuzione, come testimoniato dai diversi lavori pubblicati su riviste nazionali ed internazionali. In particolare, i docenti ed i ricercatori coinvolti hanno maturato una buona esperienza nella definizione di algoritmi euristici, con particolare riferimento a quelli basati sull'Ant Colony. Le attività dell'Unità operativa, nell'ambito del presente progetto, sono rivolte alla trattazione di temi di ricerca strettamente connessi a quelli affrontati dalle unità operative di Brescia, L'Aquila e Lecce. In particolare, come quest'ultime, anche l'Unità operativa di Cosenza focalizzerà la propria attenzione nella definizione di algoritmi euristici ad hoc per la risoluzione di problemi di vehicle routing, con l'obiettivo di minimizzare il costo totale di trasporto. Tuttavia, l'attività si posiziona, rispetto all'intero progetto, come complementare dal punto di vista della specifica tematica considerata. Infatti, oltre a minimizzare il costo totale delle rotte, si procederà all'ottimizzazione di altri due obiettivi: costo della rotta più lunga e, in alcuni contesti, numero di rotte aperte. Di conseguenza, l'attività dell'Unità operativa si integra perfettamente nel focus generale del progetto. Inoltre, le competenze acquisite nell'ambito dello sviluppo di approcci metaeuristici di tipo Ant-Colony e nel campo della programmazione multiobiettivo forniscono ulteriore valore aggiunto al progetto, come ampiamente documentato nel modello B. Infine, l'Unità operativa sfrutterà le sinergie aperte con le altre unità operative afferenti al progetto, al fine di estendere la propria metodologia ad altri framework operativi, che rientrano, comunque, nella classe più generale dei problemi di vehicle routing. Un esempio potrebbe essere quello di estendere gli approcci metaeuristici definiti per risolvere problemi di instradamento dei veicoli sugli archi con vincoli operativi di capacità e di tipo multiobiettivo. L'Unità operativa di Cosenza svilupperà il proprio progetto anche in collaborazione con centri di ricerca di università straniere, come, ad esempio, il Centre for Research on Transportation (Centre de recherche sur les transports -CRT) dell'università di Montrèal (Quebec, Canada) a cui afferiscono ricercatori di fama internazionale nel settore specifico dei trasporti, come G. Laporte e J.F. Cordeau.

L'Unità operativa di Lecce è composta da ricercatori che collaborano fra di loro da tempo, come testimoniato dalle pubblicazioni congiunte. L'Unità operativa si è affermata a livello internazionale per le competenze e i risultati ottenuti nel settore dei modelli e delle tecniche di ottimizzazione applicati alla logistica. La padronanza delle tecniche dell'ottimizzazione si combina con una approfondita conoscenza dei problemi di logistica, e in particolare di quelli di trasporto. L'Unità operativa è inoltre molto sensibile agli sviluppi più innovativi del settore. Si occuperà dello sviluppo di strategie esatte ed approssimate per problemi di Vehicle Routing di tipo dinamico e stocastico nonché dello sviluppo di metaeuristiche per problemi di General Routing a larghissima scala. Il ruolo dell'Unità operativa sarà focalizzato su temi complementari rispetto a quelli studiati dall'Unità operativa di Brescia. Diverse saranno le assunzioni sul grado di dinamismo dei problemi e sulle modalità secondo cui le informazioni vengono rese disponibili. Dal punto di vista delle competenze acquisite e dei risultati ottenuti, l'Unità operativa di Lecce è perfettamente integrata con quella di Brescia, con cui condivide il contesto applicativo, l'approccio culturalmente aperto agli aspetti più innovativi nel settore, i rapporti internazionali. Per quanto riguarda le tecniche algoritmiche, le competenze dell'Unità operativa di Lecce sono prevalentemente ma non esclusivamente focalizzate sui metodi esatti, vicine a quelle dell'Unità operativa di L'Aquila e complementari a quelle di Brescia, più orientata agli approcci approssimati, analizzati, dove possibile, con tecniche di tipo worst case. Grazie alle competenze acquisite, l'Unità operativa di Lecce porterà contributi significativi nel settore dei problemi di routing e dispatching dinamici e stocastici, attraverso la collaborazione con le altre unità operative del progetto e le collaborazioni internazionali da tempo attive nel settore. La forte vicinanza culturale all'Unità operativa di Brescia apre, attraverso questo progetto, l'opportunità di concrete collaborazioni e sinergie. L'Unità operativa di Lecce collaborerà inoltre con diversi ricercatori stranieri operanti nell'area dell'ottimizzazione discreta, dell'ottimizzazione stocastica, dei trasporti, della logistica e della gestione di supply chain. Tali collaborazioni coinvolgono Jean Francois Cordeau, Gilbert Laporte, Panos M. Pardalos, Mauricio G.C. Resende, Barrett Thomas.

I risultati attesi da questa ricerca possono essere sintetizzati nei seguenti punti:

1. Modelli di base: individuazione di poche tipologie di modelli che contengano in nuce le caratteristiche fondamentali di innovazione/difficoltà inerenti:

• Il trade-off tra obiettivi contrastanti, come la minimizzazione della distanza totale percorsa, la massimizzazione del profitto raccolto, la minimizzazione del numero di veicoli utilizzati;
• L'integrazione tra problematiche di routing e di inventory in un ambiente dinamico e/o incerto;
• L'interazione tra operatori diversi in problemi di routing multi-livello, in cui il trasporto da origine a destinazione richiede il passaggio attraverso uno o più depositi intermedi.

Lo studio dei problemi in questi contesti è solo nella sua fase iniziale ed è ancora necessario comprendere a fondo quali sono gli aspetti comuni e quali sono gli aspetti distintivi dei singoli casi, distinguendo tra modelli deterministici e stocastici, mono e multiobiettivo, integrati (cioè che raccolgano le tre funzioni produzione-trasporto-magazzino) e elementari. Riteniamo importante contribuire alla definizione di un framework modellistico che possa fungere da riferimento per studi futuri.

2. Analisi delle proprietà strutturali dei modelli selezionati.

• Individuazione e analisi di casi particolari risolvibili in tempo polinomiale, come problemi su un singolo cammino, su una stella, con un solo veicolo, ecc. L'analisi di casi molto idealizzati può condurre a osservazioni utili per affrontare e risolvere modelli più realistici. Inoltre, soluzioni ottime ottenute su modelli idealizzati possono a volte condurre a buone soluzioni per i casi reali, facilmente comunicabili al decisore finale. In questo ambito si colloca l'analisi del caso peggiore e la individuazione di criteri decisionali ottimali. Questa operazione non è sempre semplice, ma è di fondamentale importanza per poter misurare il valore dell'informazione mancante al momento della decisione. La comprensione dei punti deboli di una strategia decisionale è fondamentale per svilupparne dei raffinamenti in grado di migliorare le prestazioni nel caso medio o nel caso di maggiori informazioni disponibili (ad esempio informazioni di tipo empirico o statistico).
• Caratterizzazione delle soluzioni ottime, anche in relazione a tecniche di tipo poliedrale. Lo studio delle caratteristiche generali di una soluzione ottima può portare alla definizione di tipologie di disuguaglianze valide che non sono necessarie nella formulazione originale del problema ma che, restringendo lo spazio di ricerca, possono migliorare sensibilmente l'efficienza dei metodi di risoluzione esatta.
• Caratterizzazione della frontiera efficiente per i modelli di tipo multiobiettivo: analisi della complessità dell'insieme delle soluzioni Pareto ottime e ricerca di risultati di sensitività che possano aiutare nella generazione delle soluzioni non-dominate tramite riottimizzazione di soluzioni già ottenute, a fronte di piccole variazioni nei parametri.

3. Metodi esatti: le analisi strutturali considerate al punto precedente saranno utilizzate nella progettazione di metodi risolutivi ad-hoc. In un contesto complesso e dinamico qual è quello oggetto di questo studio, i metodi esatti, che in generale possono richiedere tempi di risoluzione molto lunghi, non sono sempre lo strumento ideale per il supporto alle decisioni sul campo. Tuttavia, essi sono indispensabili in fase di benchmark per identificare le tipologie di istanze più complesse e per valutare le prestazioni dei metodi approssimati. I metodi esatti sviluppati saranno varianti delle tecniche branch-and-bound, branch-and-cut o branch-and-price, adattate ai casi specifici. Inoltre si studieranno tecniche di tipo parametrico per la generazione della frontirea efficiente per problemi multiobiettivo o comunque per la generazione di soluzioni alternative anche per problemi monoobiettivo e che, organizzate in opportune lookup tables, possano supportare un decisore finale nelle sue scelte.

4. Metodi euristici: i problemi di routing affrontati nella realtà hanno spesso caratteristiche e dimensioni che rendono impraticabile l'utilizzo di metodi esatti. Ciò può essere particolarmente sentito in un ambito dinamico, in cui l'aggiornamento continuo dell'informazione disponibile porta alla necessità di rivedere in tempi brevi le proprie decisioni. In particolare, risulterà cruciale lo sviluppo di tecniche di riottimizzazione (per esempio per adattare un tour già stabilito a fronte dell'aggiunta o della rimozione di un cliente). Lo spettro di approcci cui si può attingere è vasto. Nel nostro studio daremo particolare attenzione a tecniche di tipo Tabu Search e Variable Neighborhood Search. Inoltre, nel caso di problemi multiobiettivo, faremo uso di algoritmi di Ant colony optimization per la generazione di una popolazione di soluzioni rappresentative della frontiera efficiente. Le tecniche ricordate si sono infatti dimostrate efficaci nella recente letteratura sul routing.

Le tecniche risolutive messe a punto, esatte e approssimate, avranno come risultato finale la produzione di un software di ottimizzazione. Le potenzialità applicative della ricerca sono essenzialmente riconducibili all'utilizzo di questo software come strumento di decisione per i problemi analizzati, e più in generale come strumento di simulazione per confrontare differenti organizzazioni del servizio, permettendo un'analisi costi-benefici per differenti gradi di dinamismo e integrazione del sistema di trasporto fra cui un'azienda è chiamata a scegliere. In particolare, le aziende che risulteranno più direttamente interessate ai risultati della ricerca saranno di tre tipi.
Il primo è costituito da quelle aziende che devono reagire molto velocemente alle richieste del mercato: aziende di consegna espresso che devono valutare in tempo reale la fattibilità e la convenienza di accettare un ordine con certi vincoli temporali e aziende che, operando su una piazza in cui sono presenti anche aziende concorrenti, devono decidere in tempi brevi sull'opportunità di aggiudicarsi un servizio richiesto da un cliente.
Il secondo tipo è quello delle aziende che devono pianificare le date di svolgimento di un insieme di consegne noto, ma incompleto.
Il terzo è il caso di aziende che debbano stabilire la convenienza di un'eventuale integrazione con i propri clienti o fornitori per l'ottimizzazione dei costi di produzione, distribuzione e mantenimento a scorta della merce.