Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen
Jonathan De La Vega (jdlvmartinezgmail.com)
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 )
Entry Submitted: 09/20/2019
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|