Two-stage robust optimization with recourse for the vehicle routing problem with time windows and multiple deliverymen

• Grant number: 17/06434-3
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: June 12, 2017
• End date: December 11, 2017
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Reinaldo Morabito Neto
• Grantee: Jonathan Justen de La Vega Martínez
• Supervisor: Fernando Ordonez
• 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: Universidad de Chile, Chile
• 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 use the two-stage robust linear programming methodology withrecourse to contemplate the uncertainties in the vehicle routing problem with time windows and multiple deliverymen (VRPTWMD). This problem arises in situations where customer sites are located in heavily congested centers, preventing the parking of vehicles near the delivery site. Therefore, in this situation, performing the service by more than one deliveryman is indispensable for the customer's allowed service times, since, it is expected that this service time will be reduced. Considering uncertain demand a priori, when a vehicle arrives at a customer site is possible that the customer's demand can not be met. At this point, a failure has occurred and, therefore, a recourse action must be taken. There has been different recourse actions proposed in the literature. For instance, returning to the depot from the customer's site where the failure occurred and continue with the pre-stablished route, serving the customer with anextra vehicle, among others. Regardless of the recourse used, additional costs related to transportation are incurred by the extra trips to the depot. Depending on the recourse, the second-stage decision variables used to represent it can be integer, resulting in a two-stage robust linear program with integer recourse. This problem presents several theoretical and computational challenges. For this reason, the objective ofthis research project is to propose a solution method that efficiently explore the particular structure of the two-stage robust linear program with recourse for the VRPTWMD with uncertain parameters.

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)