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

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.