Politecnico di Torino (logo)

A two-step optimization approach for a stochastic multi-stage capacitated vehicle routing problem

Chiara Vercellino

A two-step optimization approach for a stochastic multi-stage capacitated vehicle routing problem.

Rel. Paolo Brandimarte. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Matematica, 2020

PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (2MB) | Preview

The subject of this thesis is the multi-period Capacitated Vehicle Routing Problem with stochastic customers’ demands over time, which deals with finding the best routes to deliver goods to customers starting from a depot with a limited number of available vehicles. The customers’ demands are revealed dynamically in each daily period and each day a subset of all pending orders has to be selected for the daily deliveries. Then, the selected orders are the input data for the deterministic Capacitated Vehicle Routing Problem. The works of this thesis aim to optimize the convenience of the routes used for the deliveries and they are realized by two optimization steps: firstly, a policy to select the daily orders among the pending ones is developed and then, a meta-heuristic based solver is used to optimize the daily routes. The definition of the problem is based on the real-world case study of a furniture deliveries company and it consists of a mixed-integer linear optimization problem that models the daily Capacitated Vehicle Routing Problem. Starting from the specifications of the real-world problem, a simulation approach has been developed to evaluate the performances of both the customers’ selection policy and the Capacitated Vehicle Routing solver. The results of the simulations confirm that the combination of the policy and the solver significantly reduces the deliveries’ costs.

Relators: Paolo Brandimarte
Academic year: 2020/21
Publication type: Electronic
Number of Pages: 62
Corso di laurea: Corso di laurea magistrale in Ingegneria Matematica
Classe di laurea: New organization > Master science > LM-44 - MATHEMATICAL MODELLING FOR ENGINEERING
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/15598
Modify record (reserved for operators) Modify record (reserved for operators)