We consider a robust variant of the vehicle routing problem with heterogeneous time windows
(RVRP-HTW) with a focus on delay-resistant solutions. Here, customers have different availability
time windows for every vehicle and must be provided with a preferably tight appointment window
for the planned service. Different vehicles are a possibility to model different days on which one
physical vehicle can serve a customer. This is the main reason why different time windows for
different vehicles are of high practical relevance. To ensure that the appointment windows are
adhered to as much as possible, we introduce a new objective function that penalizes delays. Our
novel approach allows us to find solutions that are robust with respect to uncertainties in travel and
service times limited by a budget polytope. We present a set-partitioning model, the solution of
which is based on column generation and employs a labeling algorithm that integrates robustness
into the calculations and is adapted to our problem-specific constraints. In a Monte-Carlo simulation
on real-life data, we evaluate this method in terms of runtime and solution quality. Our solutions
show very good performance, even if the data is more uncertain than assumed for the optimization,
incurring only marginal extra travel time compared to a naive deterministic planning scheme.