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

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 124, p. 20-pg., 2020-12-01.

Resumo

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)

• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 15/14582-7 - Programação Estocástica e Otimização Robusta para Variantes do Problema de Roteamento de Veículos: Formulações e Métodos Exatos
• Beneficiário: Jonathan Justen de La Vega Martínez
• Modalidade de apoio: Bolsas no Brasil - Doutorado