Benders-branch-and-cut for the vehicle routing problem with multiple deliverymen and stochastic demand

• Grant number: 18/01523-0
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: May 01, 2018
• End date: September 30, 2018
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Reinaldo Morabito Neto
• Grantee: Jonathan Justen de La Vega Martínez
• Supervisor: Michel Gendreau
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
• Institution abroad: École Polytechnique de Montréal, Canada
• Associated to the scholarship: 15/14582-7 - Stochastic Programming and Robust Optimization to Variants of Vehicle Routing Problem: Formulations and Exact Methods, BP.DR

Abstract

In this research project, we intend to improve the benders-branch-and-cut algorithm developed in BEPE project of process 2017/06434-3 to effectively solve instances of reasonable size of the vehicle routing problem with time windows, multiple deliverymen and stochastic demand. The problem was formulated as a two-stage stochastic program with recourse. In the first stage, a set of routes is defined. In the second stage, recourse decisions or contingency actions are taken in order to mitigate the impact of demand uncertainties in the routes defined a priori. An exact solution method based on the benders-branch-and-cut algorithm was proposed to solve the problem. Computational experiments were done using the well known instances of Solomon in order to evaluate the computational performance of the proposed algorithm. Computational results revealed the difficulty of the benders-branch-and-cut algorithm to solve instances of reasonable size of the problem. Indeed, the algorithm could not prove optimality within a running time of 3600 seconds for instances with more than 25 customers and 20 scenarios. For this reason, the present research project aims to improve the performance of the benders-branch-and-cut algorithm developed in BEPE project of process 2017/06434-3 to effectively solve instances of reasonable size.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

DE LA VEGA, JONATHAN; GENDREAU, MICHEL; MORABITO, REINALDO; MUNARI, PEDRO; ORDONEZ, FERNANDO. An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands. European Journal of Operational Research, v. 308, n. 2, p. 20-pg., 2023-02-28. (18/01523-0, 19/23596-2, 16/01860-1, 15/14582-7, 17/06434-3)