Inventory Routing Problems with Split Deliveries

In this thesis, we study the benefit of introducing split deliveries in the Inventory Routing Problem, both when the Order-up-to level and the Maximum Level replenishment policies are applied. We first describe the problem and carry out a worst-case analysis to show the cost increase we have in the worst case by using unsplit deliveries instead of split deliveries, both for the Order-up-to level and the Maximum-Level replenishment policies. Then, we propose a mathematical formulation and solve it by implementing a branch-and-cut algorithm. Extensive computational results on benchmark instances allow us to evaluate the benefit of introducing split deliveries. A sensitivity analysis on customer demands, initial inventory levels, maximum inventory levels and distance to the depot allows us to understand the instance features that make split deliveries effective in IRPs. We also proposed new matheuristics to solve the split IRPs. The first heuristic is based on the Capacitated Concentrator Location problems, and the second uses a route-based formulation to improve upon the first. Computational experiments were done to understand the effectiveness of these matheuristics and their benefits over the exact algorithm.

In questa tesi, studiamo il beneficio dell'introduzione dello split delivery nell'Inventory Routing Problem, sia quando vengono applicate le politiche di riapprovvigionamento di tipo Order-up-to Level sia di tipo Maximum Level. Per prima cosa descriviamo il problema ed eseguiamo un'analisi del caso peggiore per mostrare l'aumento dei costi che abbiamo nel caso peggiore utilizzando soluzioni unsplit rispetto a soluzioni split delivery, sia per politiche Order-up-to Level che Maximum Level. Quindi, proponiamo una formulazione matematica e la risolviamo implementando un algoritmo branch-and-cut. Estesi risultati computazionali su istanze di benchmark consentono di valutare il vantaggio dell'introduzione dello split delivery. Un'analisi di sensibilità sulla domanda dei clienti, sui livelli iniziali di inventario, sui livelli massimi di inventario e sulla distanza dal deposito ci consente di comprendere le caratteristiche dell'istanza che rendono efficaci lo split delivery negli IRP. Sono state inoltre proposte nuove matheuristiche per risolvere gli IRP. La prima si basa sul Capacitated Concentrator Location Problem, mentre la seconda utilizza una formulazione di tipo route-based e viene utilizzata per migliorare la prima. I risultati computazionali ci consentono di comprendere l'efficacia di queste matheuristiche e i loro vantaggi rispetto al metodo esatto.