  We study the demand-robust fleet size vehicle routing problem with time
windows and compatibility constraints. Unlike traditional robust optimization,
which considers uncertainty in the data, demand-robust optimization considers
uncertainty in which constraints must be satisfied. This paper is the first to
solve a practical demand-robust optimization problem at large scale. We present
an MILP formulation and also propose a heuristic that maps the problem to set
cover in polynomial time. We show that under modest assumptions the relative
difference in time complexity from a standard branch-and-bound algorithm to the
proposed heuristic scales exponentially with the size of the problem. We
evaluate our heuristic using a simulation case study on the Solomon benchmark
instances for a variety of practical problem sizes, and compare with Gurobi.
The empirical approximation ratio remains below 2.0.
