• Logistics
• Lower bound
• Operational research
• Optimal Restocking
• Stochastic VRP

Questo lavoro di tesi discute un Vehicle Routing Problem with Stochastic Demands (VRPSD) dove le richieste dei clienti seguono una distribuzione di probabilità di Poisson.
L'approccio utilizzato è il metodo a priori, in cui in una prima fase si risolve un classico Capacitated Vehicle Routing Problem (CVRP) e in una seconda fase si stimano i costi di ricorso basandosi sulla soluzione della prima fase. Nel progetto saranno trattati due tipi principali di politiche di ricorso: il Detour To Depot (DTD) e l'Optimal Restocking (OR). Il metodo a priori vieni qui risolto con un integer L-shaped method che utilizza feasibility cuts per garantire che la soluzione soddisfi tutti i vincoli del problema e optimality cuts per migliorare il valore della funzione obiettivo del VRP escludendo le soluzioni infeasible. Questo metodo utilizza anche lower bounding functionals per approssimare il costo di ricorso. Di seguito, vengono presentati diversi nuovi lower bounds sul costo di ricorso. Questi lower bounds rafforzano le lower bounding functionals e accelerano significativamente il processo di risoluzione. Infine, verranno esaminati i risultati computazionali e verranno fatte alcune considerazioni finali.

This thesis work discusses a Vehicle Routing Problem with Stochastic Demands (VRPSD) where customers demands follow a Poisson probability distribution. The approach used is the a priori method where in the first stage a classic Capacitated Vehicle Routing Problem (CVRP) is solved and then in the second stage the recourse costs will be estimated relying on the first stage solution. Two main types of recourse policies will be treated in the project: the detour to depot and the optimal restocking. The a priori method is solved here with an integer L-shaped method that uses feasibility cuts to ensure that the solution satisfies all the problem constraints and optimality cuts to improve the objective function value of the VRP by excluding infeasible solutions. This method uses also lower bounding functionals to approximate the recourse cost. Following, several new lower bounds on the recourse cost are presented. The lower bounds strengthen the lower bounding functionals and significantly speed up the resolution process. Finally, the computational experiments will be examinated and some final considerations.