We propose to improve customer satisfaction in delivery networks by dynamically reassigning time windows. Specifically, we consider delivering goods to customers within given time windows, and we improve customer satisfaction by giving the distributor the possibility to dynamically reassign the time windows of the customers when faced with uncertainty during the day. Time window reassignment in itself is not appreciated by the customer. However, being informed timely that a delivery will be made in a later time window is preferred to not being informed at all.

To the best of our knowledge, dynamically reassigning time windows to improve customer satisfaction has not been considered in the literature. In this paper, we assume that travel times and service times are stochastic, and that their value only becomes known after serving a customer or traveling an arc, respectively. This setting is relevant for, e.g., parcel delivery, retailer distribution, and repairmen scheduling.

We first consider the case where the route is fixed and we have to decide when to reassign which time window, and how much the time window is moved. We model customer satisfaction and we provide both exact and heuristic methods for reassigning time windows to maximize satisfaction. Next, we explore integrating customer satisfaction into the vehicle routing phase.

We present results comparing the optimal time window reassignment to multiple heuristics that are inspired by practice. Finally, we analyze the effect of including customer satisfaction in the vehicle routing phase.