Busca avançada
Ano de início
Entree


An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands

Texto completo
Autor(es):
De La Vega, Jonathan ; Gendreau, Michel ; Morabito, Reinaldo ; Munari, Pedro ; Ordonez, Fernando
Número total de Autores: 5
Tipo de documento: Artigo Científico
Fonte: European Journal of Operational Research; v. 308, n. 2, p. 20-pg., 2023-02-28.
Resumo

This paper addresses the vehicle routing problem with time windows and stochastic demands (VRPTWSD). The problem is modeled as a two-stage stochastic program with recourse, in which routes are designed in the first stage and executed in the second. A failure occurs if the load of the vehicle is insufficient to meet the observed demand of a customer, implying recourse actions to recover feasibility. We consider the classical recourse policy where reactive trips to the depot are made in case of failures and a fixed rule-based recourse policy where, in addition, preventive trips are allowed. These recourse actions delay the vehicle and may cause further failures if the arrival times on the remaining customers of the planned route do not satisfy their time windows. An additional recourse action is used to service the customers whose time windows would be violated in the planned routes. We propose an Integer L-shaped algorithm considering the mentioned recourse actions. To the best of our knowledge, this is the first tailored exact approach for the VRPTWSD. Computational experiments using 112 benchmark in-stances evaluate the performance of this algorithm as well as the quality of the stochastic problem solu-tions. The results indicate significant savings in the solutions when using the fixed rule-based policy and round-trip recourse actions instead of the classical policy. Additionally, the algorithm performed better with the fixed rule-based policy, solving to optimality all instances with up to 34 customers, and taking less time on instances that were solved to optimality with both policies.(c) 2022 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 18/01523-0 - Benders-branch-and-cut para o problema de roteamento de veículos com múltiplos entregadores e demanda estocástica
Beneficiário:Jonathan Justen de La Vega Martínez
Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Processo FAPESP: 19/23596-2 - Problemas de roteamento de veículos ricos: modelos e algoritmos para variantes determinísticas e estocásticas
Beneficiário:Pedro Augusto Munari Junior
Modalidade de apoio: Auxílio à Pesquisa - Regular
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
Processo FAPESP: 17/06434-3 - Otimização robusta dois estágios com recurso para o problema de roteamento de veículos com janelas de tempo e múltiplos entregadores
Beneficiário:Jonathan Justen de La Vega Martínez
Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado