Logic-based Benders decomposition for the heterogeneous fixed fleet vehicle routing problem with time windows

Autor(es)

Fachini, Ramon Faganello ^[1] ; Armentano, Vinicius Amaral ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Fac Elect & Comp Engn, BR-13083852 Campinas, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: COMPUTERS & INDUSTRIAL ENGINEERING; v. 148, OCT 2020.
• Citações Web of Science: 0

Resumo

This paper presents exact algorithms based on logic-based Benders decomposition and a variant, called branch- and-check, for the heterogeneous fixed fleet vehicle routing problem with time windows. The objective is to service, at the minimal cost, a set of geographically dispersed customers within their time windows by a limited and capacitated fleet of heterogeneous vehicles. The proposed algorithms decompose the problem into a generalized assignment master problem and independent traveling salesman subproblems with time windows. Valid optimality and feasibility cuts are devised to guarantee the convergence of the algorithms, which include enhancements to solve the master problem and the subproblems. Extensive computational experiments on 216 benchmark instances illustrate the effectiveness of the suggested approaches. Instances with up to 100 customers are solved to proven optimality and the results indicate that the best proposed algorithm is competitive with state-of-the-art methods. (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: 16/06566-4 - Algoritmos Ótimos para o Problema de Roteamento de Veículos com Frota Heterogênea, Janelas de Tempo Flexíveis e Tempos de Viagem Estocásticos
• Beneficiário: Vinicius Amaral Armentano
• Modalidade de apoio: Bolsas no Exterior - Pesquisa