Dynamic Time Window Assignment for Next-Day Service Routing

Abstract

We consider a problem where customers dynamically request next-day home service, e.g., repair or instalment. Unlike attended home delivery, customers cannot select a time window (TW), but the service provider assigns a next-day TW to each new customer if the customer can feasibly be inserted in the service route of the next day without violating the TWs of the existing customers. Otherwise, the customer service is postponed to another day (which is outside of the scope of this work). For fast service and efficient operations, the provider aims to serve many customers the next day. Thus, TWs have to be assigned to keep the flexibility of the fleet for future requests. For such anticipatory assignments, we propose a stochastic lookahead method that samples a set of future request scenarios, solves the corresponding team orienteering problems with TWs, and uses the solutions to evaluate current TW-assignment decisions. For real-time solutions of the TOP, we propose to approximate its optimal solution value with a tight upper bound. The bound is obtained by solving the linear relaxation of a set packing reformulation via column generation. We test our algorithm on Iowa City data and compare it to several benchmark policies. The results show that our method increases customer service significantly and that our relaxation is essential for effective decisions. We further show that our policy does not lead to observable discrimination against inconveniently located customers.