  Next-day delivery logistics services are redefining the industry by
increasingly focusing on customer service. A challenge each logistics service
provider faces is to jointly optimize time window assignment and vehicle
routing for such next-day delivery services. To do so in a cost-efficient and
customer-centric fashion, real-life uncertainty such as stochastic travel times
need to be incorporated in the optimization process. This paper focuses on the
canonical optimization problem within this context; the Time Window Assignment
Traveling Salesperson Problem with Stochastic Travel Times (TWATSP-ST). It
belongs to the class of two-stage stochastic mixed-integer programming problems
with continuous recourse. We introduce Two-Step Benders Decomposition with
Scenario Clustering (TBDS) as a general exact solution methodology for solving
such stochastic programs to optimality. The method combines and generalizes
Benders dual decomposition, partial Benders decomposition, and Scenario
Clustering techniques and does so within a novel two-step decomposition along
the binary and continuous first-stage decisions. Extensive experiments show
that TBDS is superior to state-of-the-art approaches in the literature. It
solves TWATSP-ST instances with up to 25 customers to optimality. It provides
better lower and upper bounds that lead to faster convergence than related
methods. For example, Benders dual decomposition cannot optimally solve
instances of 10 customers. We use TBDS to analyze the structure of the optimal
solutions. By increasing routing costs only slightly, customer service can be
improved tremendously, driven by smartly alternating between high- and
low-variance travel arcs to reduce the impact of delay propagation throughout
the executed vehicle route.
