  This paper studies robust variants of an extended model of the classical
Heterogeneous Vehicle Routing Problem (HVRP), where a mixed fleet of vehicles
with different capacities, availabilities, fixed costs and routing costs is
used to serve customers with uncertain demand. This model includes, as special
cases, all variants of the HVRP studied in the literature with fixed and
unlimited fleet sizes, accessibility restrictions at customer locations, as
well as multiple depots. Contrary to its deterministic counterpart, the goal of
the robust HVRP is to determine a minimum-cost set of routes and fleet
composition that remains feasible for all demand realizations from a
pre-specified uncertainty set. To solve this problem, we develop robust
versions of classical node- and edge-exchange neighborhoods that are commonly
used in local search and establish that efficient evaluation of the local moves
can be achieved for five popular classes of uncertainty sets. The proposed
local search is then incorporated in a modular fashion within two metaheuristic
algorithms to determine robust HVRP solutions. The quality of the metaheuristic
solutions is quantified using an integer programming model that provides lower
bounds on the optimal solution. An extensive computational study on literature
benchmarks shows that the proposed methods allow us to obtain high quality
robust solutions for different uncertainty sets and with minor additional
effort compared to deterministic solutions.
