The Robust Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is a classical
problem of routing a fleet of vehicles from a center
to service a set of customers at minimum cost. VRP
has been studied over several decades due to its
numerous applications in the industry. Such real
life routing problems contain a high degree
of uncertainty. Most of the current methods to
address uncertainty in VRP either require strong
assumptions or increase the complexity of the
model significantly. Robust optimization has
recently emerged, increasingly in this decade, as a
novel approach to model uncertainty: optimize
against the worst-case scenario. This study
contributes to the literature by proposing a routing
model that uses robust optimization with simple
assumptions to model uncertainty in demand and
travel times without increasing the complexity of
the formulation. We adapt this model for a real life
courier delivery problem with stochastic service
times and time windows (via robust optimization),
and withprobabilistic customers (via a recourse
action). We then develop a heuristic for this large
scale problem and obtain improved solutions than
used in practice at a leading company in the
industry.