• EDDA Winner 2021

EURO Doctoral Dissertation Winner 2021

The winner of the 2021 EURO Doctoral Dissertation Award is:

Alexandre Florio

The EDDA jury 2021 consisted of Hande Yaman (chair), Yves Crama, Laura Palagi, Kathrin Klamroth and Stefan Minner.

The award was presented at the closing session of the EURO 2021 Conference in Athens (Greece).

Models and Solution Methods for Stochastic Vehicle Routing Problems

This thesis investigates what is known in the transportation literature as stochastic vehicle routing problems (SVRPs). SVRPs arise whenever vehicle routes must be planned, but the full setting where routing is to take place is not known with certainty. The first studied problem is a new SVRP variant, in which the availability of customers for receiving deliveries is uncertain. This new SVRP is motivated by attended home delivery, in particular, the delivery of e-commerce orders. Next, the focus becomes the classical vehicle routing problem with stochastic demands (VRPSD). The problem is regarded under a priori optimization and optimal restocking. The first contribution is a mixed-integer linear model for the single-vehicle version, which allows solving exactly small problem instances. In addition, a heuristic method to find good quality solutions in larger instances is proposed. The VRPSD with multiple vehicles is then extensively studied. First, a state-of-the-art branch-price-and-cut algorithm for the VRPSD is introduced.

This is the first method that is able to solve instances with few customers per vehicle, which are the most relevant instances concerning the value of stochastic solution. Following that, the VRPSD is considered under probabilistic duration constraints instead of the usual capacity-based constraints. These alternate constraints are more realistic whenever routes must finish within some prescribed time limit (e.g., due to working hours regulations). Under this new set of constraints, the VRPSD becomes considerably more difficult.

The problem is solved exactly for the first time by a novel branch-and-price algorithm, which combines different strategies for evaluating route feasibility. The last contribution is a Bayesian model for the VRPSD with positively correlated demands, along with an optimal restocking policy for this case. This is an important step towards addressing one of the current challenges in stochastic routing: developing models and algorithms that can handle statistical dependence among uncertain parameters.

EURO-Online login