Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen

Author(s)

De La Vega, Jonathan ; Munari, Pedro ; Morabito, Reinaldo

• Document type: Journal article
• Source: Computers & Operations Research; v. 124, p. 20-pg., 2020-12-01.

Abstract

This paper addresses the vehicle routing problem with time windows and multiple deliverymen (VRPTWMD) under uncertain demand as well as uncertain travel and service times. This variant is faced by logistics companies that deliver products to retailers located in congested urban areas, where service times are relatively long compared to travel times, and depend on the number of deliverymen assigned to each route. Differently from traditional variants, these service times show high variability, requiring an appropriate way of handling the related uncertainty. We extend two mathematical formulations to represent the VRPTWMD under uncertainty, using the robust optimization paradigm with budgeted uncertainty sets, and developed effective exact solution methods for solving each of them. The first formulation is a robust vehicle flow model solved by a tailored branch-and-cut algorithm that resorts to 1and 2-path inequalities that we show how to effectively separate. The second formulation is a set partitioning model, for which we propose a branch-price-and-cut algorithm that relies on a robust resource-constrained elementary shortest path problem. The results of computational experiments using instances from the literature and risk analysis via a Monte Carlo simulation show the importance of incorporating uncertainties in the VRPTWMD, and indicate the sensitivity of decisions as well as cost and risk to the level of uncertainty in the input data. (c) 2020 Elsevier Ltd. All rights reserved. (AU)

• FAPESP's process: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings
• Grantee: Reinaldo Morabito Neto
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 15/14582-7 - Stochastic Programming and Robust Optimization to Variants of Vehicle Routing Problem: Formulations and Exact Methods
• Grantee: Jonathan Justen de La Vega Martínez
• Support Opportunities: Scholarships in Brazil - Doctorate