Roberto Baldacci

L'attività di ricerca svolta da Roberto Baldacci riguarda problemi di Ottimizzazione Combinatoria, sviluppando e sperimentando algoritmi esatti ed euristici per la loro risoluzione e studiando questioni teoriche legate a tale risoluzione. In particolare, tale attività ha riguardato e riguarda:

• Metodi matematici per problemi di Travelling Salesman con vincoli aggiuntivi;
• Metodi matematici per problemi di Vehicle Routing in presenza di vincoli reali;
• Procedure di lower bound ed algoritmi euristici per problemi di Car Pooling;
• Algoritmi per problemi di localizzazione di mediani su grafi con vincoli di capacità;
• Procedure di lower bound ed algoritmi esatti ed euristici per problemi di disegno di reti di telecomunicazioni;
• Algoritmi euristici ed esatti per problemi di “Packing” multi-dimensionali;
• Algoritmi esatti ed euristici per problemi di gestione del rischio e del portafoglio;
• Procedure di lower bound ed algoritmi esatti per problemi di Capacitated Arc Routing.

L'attività di ricerca riguarda i problemi di Ottimizzazione Combinatoria, lo sviluppo e la sperimentazione di algoritmi esatti ed euristici per la loro risoluzione e lo studio di questioni teoriche legate a tale risoluzione.

In particolare, l'attività di ricerca è caratterizzata da un importante filone di ricerca nell'ambito della Ricerca Operativa, costituito dai problemi di instradamento (routing) su grafi. I problemi di routing su grafi ricoprono un ruolo fondamentale sia per la loro importanza teorica sia per la loro importanza pratica. In tale ambito, sono stati studiati e vengono attualmente studiati sia algoritmi di risoluzione esatta ed euristica per diversi problemi di routing fra i quali: il Vehicle Routing Problem, Il Car Pooling Problem, il Capacitaed Arc Routing Problem, etc. Di seguito viene riportata una breve descrizione degli argomenti di ricerca più rilevanti fra le principali linee di ricerca.

Il Vehicle Routing Problem (VRP)

Il VRP è un ben noto problema di ottimizzazione combinatoria che ha molte applicazioni pratiche nella gestione di reti di distribuzione. La risoluzione ottima di questo problema è da molti anni oggetto di ricerca ed esistono centinaia (forse migliaia) di articoli scientifici che descrivono metodi di risoluzione di varianti del VRP. Tuttavia, nonostante la ricerca sviluppata, non esiste alcun algoritmo in grado di risolvere ogni problema di VRP. Esistono algoritmi e procedure che risolvono in modo appropriato certe classi di VRP, tuttavia, queste procedure non risolvono in modo adeguato o non producono alcuna soluzione per problemi diversi da quelli per cui sono state disegnate.

Tutti i metodi esatti per il VRP considerano un problema base che compare in ogni problema di routing. Questo problema centrale viene denominato "Capacitated Vehicle Routing Problem" (CVRP). Il CVRP consiste nel disegnare i viaggi per un insieme di veicoli omogenei localizzati in un deposito centrale al fine di rifornire un insieme di clienti a cui deve essere consegnata un quantitativo noto a priori di merce. L'obiettivo è di minimizzare la somma dei costi dei viaggi. Ogni viaggio inizia e finisce al deposito e contiene un sottoinsieme dei clienti. In ogni soluzione ammissibile per il CVRP, tutti i clienti sono serviti e la somma dei quantitativi dei clienti di un viaggio non deve superare la capacità del veicolo. Nella formulazione più semplice del CVRP non esistono limiti inferiori o superiori sulla durata di un viaggio e, quindi, non viene in alcun modo considerato il problema del bilanciamento del carico di lavoro fra gli autisti dei veicoli della flotta.

Oggetto della ricerca per quanto riguarda il VRP è lo sviluppo di algoritmi esatti ed euristici che siano per la sua risoluzione che siano inoltre in grado di incorporare le complessità che caratterizzano i problemi reali.

Car Pooling Problem (CPP)

Il Car Pooling è un servizio di mobilità alternativo al trasporto pubblico gestito direttamente da aziende pubbliche o private di grosse dimensioni al fine di organizzare in modo efficiente gli spostamenti da e verso l'azienda stessa. I principali benefici di tale servizio sono la riduzione del numero di automezzi impiegati negli spostamenti, la diminuzione delle emissioni inquinanti e del traffico stradale. Il tipo di servizio proposto dipende strettamente dal tipo di azienda che offre il servizio. All'interno del servizio Car Pooling si possono identificare diverse varianti applicative in cui la possibilità di utilizzare Internet per il supporto alle transazioni del servizio è cruciale per il successo del servizio. Infatti la complessità dei problemi impedisce la possibilità di generare soluzioni dettagliate in tempo reale, come ad esempio durante una telefonata. Quindi le modalità di utilizzo di un servizio di questo tipo prevedono l'accettazione di richieste da parte degli utenti, con un controllo in tempo reale di aspetti generali di fattibilità della richiesta e quindi un invio differito di e-mail o altro tipo di messaggio per comunicare il dettaglio della soluzione relativo all'utente specifico.

Durante le diverse attività di ricerca svolte sul CPP, sono state individuate quattro versioni del CPP di rilevante interesse applicativo: Daily Car Pooling Problem (D-CPP), Selective Car Pooling Problem (S-CPP), Long-term Car Pooling Problem (L-CPP),  Daily Car Pooling Problem con Pickup e Delivery (DPD-CPP).

L'obiettivo della ricerca è quello di sviluppare nuove metodologie matematiche da cui dedurre algoritmi esatti ed euristici di soluzione dei problemi di Car pooling e distribuzione merci door-to-door sopra descritti. A questo fine si intende investigare l'impiego di formulazioni matematiche specifiche per ciascun problema al fine di ottenere algoritmi di tipo branch and cut sfruttando la struttura poliedrale tipica di ciascun problema.

Disegno di reti di telecomunicazioni

L'attività di ricerca riguarda lo studio di fattibilità e convenienza di una dorsale ottica composta da sottoreti di diversa topologia (anello, maglia) e tecnologia mista (ottica, elettrica). In particolare, viene considerato il problema del cablaggio con rete ottica di un area urbana di media dimensione al fine di coprire utenti residenziali e business. L'obiettivo e' quello di identificare gli anelli e le diramazioni (rete primaria e secondaria) che minimizzano il costo totale di connessione. Il problema appartiene alla classe dei problemi NP-hard. Questa considerazione e le dimensioni dei problemi reali, rendono proibitivo l'utilizzo di metodi esatti per la sua risoluzione. Di conseguenza, la ricerca si concentra sul disegno di metodologie di tipo euristico per la sua risoluzione.

Algoritmi euristici ed esatti per problemi di ``Packing'' multi-dimensionali

Questa linea di ricerca ha come obiettivo lo studio e la realizzazione di nuovi algoritmi di soluzione per problemi di cutting e packing che si presentano nelle applicazioni reali. Il problema del cutting consiste nel determinare le modalità di taglio di una o più superfici, nel rispetto di un insieme di vincoli, per ottenere un insieme di pezzi di dimensione e quantità definita a priori, minimizzando o massimizzando una funzione obiettivo dipendente dalla specifica applicazione. A esempio si vuole massimizzare la quantità di materiale utilizzata dai pezzi tagliati da una singola superficie oppure minimizzare il numero di pelli da impiegare per produrre un certo insieme di capi di abbigliamento.

Il problema del packing dal punto di vista matematico è del tutto analogo al problema del cutting. I due problemi si differenziano solo nella definizione di alcuni vincoli riguardanti gli aspetti operativi del corrispondente problema reale. A esempio nel caricamento di container è necessario considerare anche vincoli di portata in peso e l'allocazione degli oggetti deve tenere conto dell'ordine e delle modalità di caricamento.

A tutt'oggi i lavori riguardanti il cutting e il packing presentati in letteratura descrivono per lo più tecniche euristiche, mentre i pochi metodi esatti proposti sono in grado di risolvere solo delle versioni molto semplificate del problema e di dimensioni assai ridotte.

In questa ricerca si prenderà in considerazione il problema del taglio di pelli nell'industria dell'arredamento e dell'abbigliamento, in quanto costituisce uno dei problemi di cutting più difficili e generali, noto in letteratura con il nome di Lay Planning o Nesting Problem.

Il nesting problem consiste nel tagliare una o più superfici master di forma irregolare (per esempio, pelle di animale) in un certo numero di pezzi anch'essi di forma irregolare (in gergo tecnico dette dime). Le superfici master a disposizione sono di dimensioni diverse e possono incorporare dei difetti, alcuni dei quali possono essere accettati in certi pezzi, mentre altri devono essere evitati. Quindi, il taglio deve essere effettuato tenendo conto delle eventuali zone di difetto sulla superficie master, della qualità richiesta per il particolare pezzo, della tecnologia impiegata nella fase di taglio e di eventuali richieste del designer. Inoltre, il prodotto finito generalmente necessità di più pelli per essere completato, per cui più di una pelle alla volta deve essere presa in considerazione durante il calcolo della soluzione. L'obiettivo è la minimizzazione dello scarto, in particolare si vuole massimizzare l'utilizzo della pelle di alta qualità.

L'obiettivo della ricerca è quello di sviluppare nuove metodologie basate su modelli di ottimizzazione combinatoria e approcci euristici da cui dedurre algoritmi euristici di soluzione in grado di gestire problemi con vincoli e dimensioni reali. Sarà considerato sia il problema del taglio di una singola superficie master che il taglio simultaneo di più superfici master per allocate tutti i pezzi a disposizione. A questo fine si intende investigare alcune possibili formulazioni matematiche del problema di tipo set packing che possano consentire il calcolo di lower bound al valore della soluzione ottima e possibilmente la costruzione di una procedura di tipo branch and bound per risolvere esattamente versioni semplificate del problema ed euristicamente le istanze più complesse.

Un ulteriore obiettivo della ricerca è lo sviluppo di altri metodi euristici di tipo costruttivo per calcolare delle soluzioni di buona qualità con tempi di calcolo ridotti.

Ottimizzazione del portafoglio

La diversificazione dei portafogli attraverso un'appropriata gestione delle attività e delle passività è riconosciuta come un importante aspetto dalla maggior parte delle istituzioni. La definizione delle strategie di investimento è diventata sempre più difficile da quando il mercato dei derivati è cresciuto, rendendo più complessi i portafogli. Le istituzioni richiedono una metodologia più flessibile per la gestione del portafoglio, che sia in grado di adattarsi alle diverse situazioni che si possono riscontrare sul mercato finanziario. Tipicamente la costruzione di un generico portafoglio è caratterizzata dallo stesso problema di pianificazione finanziaria: investire il capitale iniziale in un dato insieme di asset e periodicamente ribilanciare il capitale investito in modo tale che il portafoglio soddisfi determinati obiettivi.