Optimization Online


Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen

Jonathan De La Vega (jdlvmartinez***at***gmail.com)
Pedro Munari (munari***at***dep.ufscar.br)
Reinaldo Morabito (morabito***at***ufscar.br)

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. In addition to routing and scheduling decisions, the VRPTWMD involves the choice of the number of deliverymen to be allocated to each route, as service times depend on the number of deliverymen assigned to routes. We extend two mathematical formulations to represent the VRPTWMD under uncertainty, using the robust optimization paradigm with budgeted uncertainty sets. The first robust formulation is a vehicle flow model with additional constraints obtained from the linearization of recursive equations that model all possible realizations of uncertain parameters, a technique that exhibits advantages over the dualization scheme commonly used in the literature. 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.

Keywords: vehicle routing; multiple deliverymen; uncertainty; robust optimization; branch-price-and-cut.

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )


Download: [PDF]

Entry Submitted: 09/20/2019
Entry Accepted: 09/20/2019
Entry Last Modified: 05/31/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society