Francesco CARRABS | Projects

OTTIMIZZAZIONE ROBUSTA IN PROBLEMI CON VARIABILITÀ DEI TERMINI NOTI

Il Problema del Trasporto a Intervalli (ITP) è una variante del TP in cui i valori delle offerte e delle domande possono variare all’interno di intervalli specifici. Nel caso del Trasporto a Intervalli, al variare di offerta e domanda, varierà, ovviamente, anche il valore della funzione obiettivo all’ottimo. Lo studio dei valori che può assumere la funzione obiettivo al variare dei termini di offerta e domanda è noto con il nome Optimal Value Range Problem (OVRP). Mentre calcolare il miglior valore all’ottimo che può assumere la funzione obiettivo e, determinare quindi, i corrispondenti livelli di domanda ed offerta, è un problema facile, calcolare il valore peggiore all’ottimo al variare dei livelli di offerte e domande è un problema difficile (NP-Hard). L'obiettivo del nostro studio sarà quello di studiare varianti significative del problema ITP e proporre algoritmi meta-euristici per il calcolo di un lower ed upper bound al peggior valore ottimo che può assumere la funzione obiettivo. In particolare ci focalizzeremo su due varianti, una con vincoli di disuguaglianza sull’offerta e una con vincoli di uguaglianza sull’offerta. Per la variante con vincoli di disuguaglianza sull’offerta abbiamo intenzione di studiare e proporre delle proprietà sotto le quali alcuni risultati teorici proposti in letteratura ne diventano una conseguenza. L’obiettivo è di progettare e sviluppare una Iterated Local Search che sfrutta la definizione di un intorno definito a partire dalle proprietà provate. Verificheremo la possibilità di individuare nuovi casi polinomiali, in particolare nel caso della presenza del fenomeno del paradosso del trasporto. Per la variante con vincoli di uguaglianza cercheremo di provare proprietà teoriche che ci consentono di formalizzare la relazione tra le due versioni del problema che considereremo e in particolare relazioni relative al peggior valore all’ottimo che le due varianti possono assumere. Anche in questo caso cercheremo di derivare nuovi casi polinomiali in particolare in presenza del paradosso del trasporto. Per tale variante cercheremo di sviluppare un algoritmo di tipo Tabu Search che ci consenta in tempi competitivi di calcolare un lower bound al peggior valore ottimo. Per entrambe le versioni studieremo l’applicazione di algoritmi di tipo esatto. Effettueremo esperienze computazionali e confronteremo i risultati ottenuti con gli approcci presenti in letteratura.