Robust optimization for the vehicle routing problem with multiple deliverymen

Autor(es)

De La Vega, Jonathan ^[1] ; Munari, Pedro ^[1] ; Morabito, Reinaldo ^[1]

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

^[1] Univ Fed Sao Carlos, Dept Prod Engn, Rodovia Washington Luis Km 235, BR-13565905 Sao Carlos, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH; v. 27, n. 4, p. 905-936, DEC 2019.
• Citações Web of Science: 2

Resumo

This paper addresses the vehicle routing problem with time windows and multiple deliverymen in which the customer demands are uncertain and belong to a predetermined polytope. In addition to the routing decisions, this problem attempts to define the number of deliverymen used to service to the customers on each route. A new mathematical formulation is presented for the deterministic counterpart based on auxiliary variables that define the assignment of customers to routes. Building on this formulation, we apply a static robust optimization approach to obtain a robust counterpart formulation that captures the random nature of customer demand. Due to the difficulty in solving this formulation, we propose a constructive heuristic to generate a robust solution, which is used as a starting point for solving the robust counterpart formulation. The heuristic is an extension of Solomon's heuristic I1. Computational results using problem instances from the literature and risk analysis via Monte-Carlo simulation indicate the potential of static robust optimization to address the trade-off between cost and risk. The results also reveal that the proposed approach provides good results even without exact knowledge of some probabilistic measure of the customer demand. (AU)

• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• 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