The Air Liquide Inventory Routing Problem is a real-world optimization problem proposed by the French company Air Liquide for the 2016 ROADEF/EURO challenge. It belongs to the class of Inventory Routing Problems, a class of problems that combines aspects of vehicle routing and inventory management. Many variants of this problem has been described in the literature due to their different structure and the different availability of information on the customer's demand. The main goal of this work is to develop problem-specific algorithmic components that will be integrated in a framework for the design of general-purpose metaheuristic algorithms and use the Irace package to find the best configuration and set of parameters for the algorithm. Some exact algorithms and powerful stochastic local search methods have been developed to solve this problem. In particular, stochastic local search methods are very promising because they can solve computationally hard problems very effectively and robustly, especially when problem size increases and exacts methods fail to find a solution in a reasonable time. Three different components to generate an initial solution have been developed and four different neighborhood operators have been defined. In order to speed-up the evaluation of a solution, a delta evaluation function has been defined. In order to consider the unfeasibility of solutions, a variant of the original objective function has been proposed. An experimental analysis has been performed on the Iridia cluster using the set of instances available for the competition. The analysis shows how the configuration found by irace outperforms a configuration chosen randomly and an ad-hoc configuration. Furthermore, a sensitivity analysis has also been performed to investigate how the parameters affect the algorithm performance.

L'"Air Liquide Inventory Routing Problem" è un problema reale presentato dalla compagnia francese Air Liquide per il 2016 ROADEF/EURO challenge. Appartiene alla classe di Inventory Routing Problems, una classe di problemi che combina aspetti di Vehicle Routing e Inventory Management. Diverse varianti di questo problema sono state affrontate data la loro diversa struttura e la diversa disponibilità di informazione riguardo la domanda dei clienti. L'obiettivo principale di questo lavoro è quello di sviluppare delle componenti algoritmiche da integrare in un framework per lo sviluppo di algoritmi metaeuristici ed usare il pacchetto Irace per trovare la configurazione e il set di parametri ideale. Alcuni algoritmi esatti e potenti algoritmi di ricerca stocastici sono stati sviluppati per risolvere questa classe di problemi. In particolare, questi ultimi sono molto efficaci perchè possono risolvere problemi computazionalmente complessi in modo efficiente e robusto, specialmente quando le istanze di tali problemi diventano molto grandi e gli algoritmi esatti non riescono a trovare una soluzione in un tempo ragionevole. Tre componenti per generare una soluzione iniziale sono stati sviluppati e quattro diversi operatori sono stati definiti. Una funzione delta è stata definita per velocizzare la valutazione di una soluzione. Una variante della funzione obiettivo originale è stata proposta per tenere in considerazione il fatto che alcune soluzioni violano i vincoli. Degli esperimenti sono stati eseguiti sul cluster dell'Iridia usando l'insieme di istanze reso disponibile per la competizione. L'analisi ha mostrato che la configurazione scelta da Irace ottiene migliori risultati rispetto ad una configurazione scelta in maniera casuale a una configurazione scelta in base alla mia esperienza del problema. Inoltre, un'analisi di sensitività è stata fatta per verificare come i parametri di un algoritmo ne influenzano le performance.

Automatic tuning and configuration of metaheuristics for the inventory routing problem

FISCARELLI, ANTONIO MARIA
2015/2016

Abstract

The Air Liquide Inventory Routing Problem is a real-world optimization problem proposed by the French company Air Liquide for the 2016 ROADEF/EURO challenge. It belongs to the class of Inventory Routing Problems, a class of problems that combines aspects of vehicle routing and inventory management. Many variants of this problem has been described in the literature due to their different structure and the different availability of information on the customer's demand. The main goal of this work is to develop problem-specific algorithmic components that will be integrated in a framework for the design of general-purpose metaheuristic algorithms and use the Irace package to find the best configuration and set of parameters for the algorithm. Some exact algorithms and powerful stochastic local search methods have been developed to solve this problem. In particular, stochastic local search methods are very promising because they can solve computationally hard problems very effectively and robustly, especially when problem size increases and exacts methods fail to find a solution in a reasonable time. Three different components to generate an initial solution have been developed and four different neighborhood operators have been defined. In order to speed-up the evaluation of a solution, a delta evaluation function has been defined. In order to consider the unfeasibility of solutions, a variant of the original objective function has been proposed. An experimental analysis has been performed on the Iridia cluster using the set of instances available for the competition. The analysis shows how the configuration found by irace outperforms a configuration chosen randomly and an ad-hoc configuration. Furthermore, a sensitivity analysis has also been performed to investigate how the parameters affect the algorithm performance.
STÜTZLE, THOMAS
PAGNOZZI, FEDERICO
ING - Scuola di Ingegneria Industriale e dell'Informazione
21-dic-2016
2015/2016
L'"Air Liquide Inventory Routing Problem" è un problema reale presentato dalla compagnia francese Air Liquide per il 2016 ROADEF/EURO challenge. Appartiene alla classe di Inventory Routing Problems, una classe di problemi che combina aspetti di Vehicle Routing e Inventory Management. Diverse varianti di questo problema sono state affrontate data la loro diversa struttura e la diversa disponibilità di informazione riguardo la domanda dei clienti. L'obiettivo principale di questo lavoro è quello di sviluppare delle componenti algoritmiche da integrare in un framework per lo sviluppo di algoritmi metaeuristici ed usare il pacchetto Irace per trovare la configurazione e il set di parametri ideale. Alcuni algoritmi esatti e potenti algoritmi di ricerca stocastici sono stati sviluppati per risolvere questa classe di problemi. In particolare, questi ultimi sono molto efficaci perchè possono risolvere problemi computazionalmente complessi in modo efficiente e robusto, specialmente quando le istanze di tali problemi diventano molto grandi e gli algoritmi esatti non riescono a trovare una soluzione in un tempo ragionevole. Tre componenti per generare una soluzione iniziale sono stati sviluppati e quattro diversi operatori sono stati definiti. Una funzione delta è stata definita per velocizzare la valutazione di una soluzione. Una variante della funzione obiettivo originale è stata proposta per tenere in considerazione il fatto che alcune soluzioni violano i vincoli. Degli esperimenti sono stati eseguiti sul cluster dell'Iridia usando l'insieme di istanze reso disponibile per la competizione. L'analisi ha mostrato che la configurazione scelta da Irace ottiene migliori risultati rispetto ad una configurazione scelta in maniera casuale a una configurazione scelta in base alla mia esperienza del problema. Inoltre, un'analisi di sensitività è stata fatta per verificare come i parametri di un algoritmo ne influenzano le performance.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
Tesi - Fiscarelli Antonio Maria.pdf

accessibile in internet per tutti

Descrizione: Tesi - Fiscarelli Antonio Maria - Matricola 820571
Dimensione 3.05 MB
Formato Adobe PDF
3.05 MB Adobe PDF Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/131954