Skip to main content

MSBE Group presents a research seminar from Pedro Munari on vehicle routing under uncertainty (joint work with Alfredo Moreno, Jonathan De La Vega, Douglas Alem, Jacek Gondzio and Reinaldo Morabito)

Friday 13 July 2018
Conference Room, 4th Floor
Dr Pedro Munari; Federal University of Sao Carlos, Brazil


In real-world settings, vehicle routing is typically subject to different sources of uncertainty regarding demands, customer availability, travel times, among others. Designing routes without taking uncertainty into account might result in route plans that become infeasible or too costly in practice. In this talk, we review the main approaches for incorporating uncertainty into the vehicle routing problem (VRP), focusing on the main challenges and benefits that they offer. In addition, we present a novel formulation and an exact solution method based on robust optimization (RO) for the VRP with time windows, considering that demand and travel times are uncertain and belong to budgeted uncertainty sets. The formulation is compact and derived from the incorporation of dynamic programming recursive equations into a standard deterministic model.

This strategy, which has never been used to obtain RO counterparts, is appealing because one does not need to formulate the adversary robust problem, thus avoiding the classical dualization scheme commonly used in the RO literature. The exact method is a branch-price-and-cut algorithm based on a set partitioning formulation of the problem, which relies on a robust resource constrained elementary shortest path problem to generate routes that are robust regarding both demands and travel times. Computational experiments show that the proposed model yields robust optimal solutions within reasonable running times regardless of the budgets of uncertainty and deviations. We also assess the trade-off between robustness and performance using a Monte Carlo simulation and illustrate the importance of providing robust routes towards a reliable decision-making process in practice.

Coffee/tea and biscuits available from 13:45.

Further Information