A Unified Matheuristic for a Class of Vehicle Routing Problems Under Time and Demand Uncertainty

Abstract

This work address a class of VRPs under uncertain demands and travel times, considering multiple attributes such as heterogeneous fleet, multiple depots, and time windows. We assume customer demands and travel times are random variables that belong to a budgeted uncertainty set, and approach the problems under the robust optimization paradigm. To solve them, we implement a multi-start matheuristic that combines the iterated local search framework with an exact set partitioning procedure. Data structures were incorporated into the local search procedure to make movement feasibility checking more efficient. We conduct computational experiments over several sets of benchmark instances for many particular cases, such as VRPTW, HFVRP, and the classical CVRP. As also done in related works, we perform slight modifications (e.g., increase vehicle capacity, generate uncertainty sets) in each instance to account for uncertainties and properly assess performance in the robust counterparts. Overall, the results are promising, as our method achieves best-known solutions in most cases, as well as improves many of the open instances