Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen. (December 2020)

• Record Type: Journal Article
• Authors: De La Vega, Jonathan; Munari, Pedro; Morabito, Reinaldo
• Is Part Of: Computers & operations research. Volume 124(2020)
• Publication Date: 2020-12
• Subjects: Routing -- Multiple deliverymen -- Uncertainty -- Robust optimization -- Branch-price-and-cut; 00-01 -- 99-00; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.105062
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The robust vehicle routing problem with multiple deliverymen is addressed. We devise a branch-and-cut (BC) algorithm to solve a robust vehicle flow model. We develop a branch-price-and-cut (BPC) algorithm to solve a set-partitioning model. The BC algorithm found new optimal solutions and improved bounds for problem benchmark instances. The BPC algorithm obtained a good performance in instances with up to 50 customers. Abstract: 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 1- and 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.