Riassunto analitico
Questa tesi di dottorato è incentrata sullo sviluppo di algoritmi esatti ed euristici per risolvere problemi logistici relativi al vehicle routing, allo scheduling e alla localizzazione di servizi. La tesi è strutturata in un breve capitolo introduttivo, cinque capitoli di ricerca, e una breve conclusione. La prima parte della ricerca è focalizzata su un nuovo problema di bin packing con vincoli di precedenza che generalizza alcuni problemi della letteratura, tra cui il problema di bilanciamento delle linee di montaggio. Per risolvere il problema, proponiamo un semplice e efficace algoritmo di Iterated Local Search (ILS) che integra in modo innovativo procedure costruttive e strutture di vicinato per guidare la ricerca alle soluzioni ottime locali. La seconda parte è dedicata al problema di localizzazione di p centri con vincoli di capacità, che consiste nella selezione di p impianti da un gruppo di candidati per servire un numero di clienti, al fine di minimizzare la distanza massima tra un cliente e l'impianto a cui è associato e nel rispetto di vincoli di capacità. Il problema è risolto mediante algoritmi di ricerca che, iterativamente, cercano la distanza ottimale risolvendo sotto-problemi più semplici ad ogni iterazione. Inoltre, presentiamo diverse formulazioni matematiche per i sotto-problemi e li miglioriamo attraverso varie disuguaglianze valide, tra cui una basata sulla disgiunzione 0-1 e sulla soluzione dei problemi di subset sum. La terza parte presenta un problema di instradamento di veicoli basato su un problema pratico di distribuzione affrontato da un’azienda italiana responsabile della consegna di farmaci alle aziende sanitarie. Questo problema si caratterizza per la grande quantità di dettagli e vincoli, tra cui le consegne periodiche (multi-period), l'esistenza di depositi multipli (di due tipi diversi), l'incompatibilità tra alcuni veicoli ed alcuni clienti, la presenza di finestre temporali ed altri. Il problema è risolto mediante algoritmi euristici basati sul ILS e su large neighborhood search. Esperimenti computazionali sono eseguiti su istanze realistiche fornite dall'azienda, nonché su istanze artificiali, per dimostrare l'efficienza degli algoritmi proposti. Le ultime due ricerche sviluppate nella tesi sono incentrate sul pollution-routing problem (PRP), che è una variante del problema d'instradamento di veicoli che considera la minimizzazione delle emissioni di CO2 nella funzione obiettivo. Il primo studio risolve il PRP con un algoritmo di ottimizzazione dei tempi di partenza e delle velocità per minimizzare il costo di un percorso fisso. Inoltre, è presentata una prova dell'ottimalità per l'algoritmo proposto. Gli esperimenti computazionali condotti su istanze della letteratura mostrano il contributo della flessibilità nella scelta dei tempi di partenza sulla riduzione delle emissioni di CO2. Nel secondo contributo sul PRP, viene affrontata una versione bi-obiettivo del problema, in cui due obiettivi contrastanti, ovvero i costi di viaggio e le emissioni di CO2, sono minimizzati mediante un metodo euristico di ricerca locale di Pareto. Esperimenti computazionali sulle istanze di riferimento esistenti mostrano che l'approccio proposto porta a risultati migliori rispetto a quelli ottenuti con metodi multi-obiettivo standard. In conclusione, la tesi mostra come moderni algoritmi, sia esatti che euristici, possano essere usati per ottimizzare in modo efficiente problemi di produzione e di logistica che appaiono in ambiti diversi.
|
Abstract
This Ph.D thesis is focused on the development of exact and heuristic algorithms to solve logistic problems related with vehicle routing, scheduling, and facility location. The thesis is structured in a brief introductory chapter, five research chapters, and a brief conclusion. The first part is focused on a new bin packing problem with precedence constraints that generalizes classical problems from the literature, including the well-known simple assembly line balancing problem. To solve the problem, we propose a simple and effective iterated local search (ILS) algorithm that integrates in an innovative way constructive procedures and neighborhood structures to guide the search to local optimal solutions. The second part of the thesis is dedicated to the capacitated p-center problem, that consists in selecting p facilities from a set of candidates to service a number of customers, subject to facility capacity constraints, with the aim of minimizing the maximum distance between a customer and its associated facility. We solve the problem by means of search algorithms that iteratively seek the optimal distance by solving tailored sub-problems. In addition, we present different mathematical formulations for the sub-problems and improve them by means of several valid inequalities, including an effective one based on 0-1 disjunction and the solution of subset sum problems. The third part of the thesis presents a rich vehicle routing problem based on a practical distribution problem faced by an Italian company in charge of delivering pharmaceutical products to healthcare facilities. This problem is characterized by its huge number of features and constraints, including multi-period demands, multi-depots, vehicle-customer incompatibilities, time-window constraints, and many others. The problem is solved by means of heuristic algorithms based on ILS and large neighborhood search. Computational experiments are performed on realistic instances provided by the company, as well as on artificial instances, in order to show the efficiency of the proposed algorithms. The last two researches of the thesis are focused on the Pollution-Routing Problem (PRP), which is a variant of the vehicle routing problem that considers CO2 emissions in the objective function. The first study on the PRP proposes a speed and departure time optimization algorithm to minimize the cost of a fixed route. In addition, a proof of optimality for the proposed algorithm is presented, and computational experiments conducted on benchmark instances from the literature show the contribution of the flexible departure times on the reduction of the CO2 emissions. In the second contribution on the PRP, a bi-objective version of the problem is addressed. Two conflicting objectives, namely, traveling costs and CO2 emissions, are minimized by means of a two-phase pareto local search heuristic. Extensive computational experiments over existing benchmarks instances show that the proposed approach leads to better results when compared with those obtained by standard multi-objective methods. As a concluding remark, the thesis shows how modern exact and heuristic algorithms can be used to efficiently optimize production and logistic problems arising in different fields.
|
