Robust optimization for the vehicle routing problem with multiple deliverymen

Author(s)

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

Affiliation

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

• Document type: Journal article
• Source: CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH; v. 27, n. 4, p. 905-936, DEC 2019.
• Web of Science Citations: 2

Abstract

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)

• FAPESP's process: 13/07375-0 - CeMEAI - Center for Mathematical Sciences Applied to Industry
• Grantee: Francisco Louzada Neto
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
• 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