Self-Imposed Time Windows in Vehicle Routing Problems

We speak of Self-Imposed Time Windows (SITW) when a logistics service provider quotes a delivery time window to his customer. Once this time window is communicated, the company strives to respect it as well as possible. We incorporate these SITW within the framework of the Vehicle Routing Problem (VRP). Essential to SITW is the fact that the time window is determined by the carrier company and not by the customer. The resulting VRP-SITW is inherently different from the well-studied VRP with Time Windows (VRPTW) in that in the latter problem the time windows are exogenous constraints imposed by the customers. The second important element of the problem studied in this paper is the uncertainty in the travel times. The basic mechanism of dealing with this uncertainty is the allocation of time buffers throughout the routes, which absorb disruptions. We propose a heuristic solution approach combining an LP model and a local search heuristic. A tabu search heuristic assigns customers to vehicles and establishes the order of visit of the customers per vehicle. Detailed timing decisions are subsequently generated by the LP model, whose output also guides the local search in a feedback loop. We test our algorithm on a number of benchmark instances for the VRP and VRPTW. We highlight the costs involved in integrating SITW with the VRP and we underline the advantages to the carrier company of SITW when compared to VRPTW