The Research into the Vehicle Routing Problem with Self-Imposed Time Windows

Small-package carrier companies transport goods to customers. In this article we will focus on companies who provide a time window for delivery to its customers. The company strives to respect this selected time windows as well as possible. The self-imposed time window (SITW) has an important aspect that it is selected by the company and not by the customer. We include this self-imposed time window into the Vehicle Routing Problem (VRP). The VRP-SITW is different from the VRP with time windows (VRPTW), because in the latter problem the time windows are chosen by the customer itself. Another main aspect of this article is the incorporation of uncertainty in the travel times. Disruptions may occur in the routes and we account for this by allocating buffers. We used a two-stage solution approach with a tabu search heuristic and a linear programming problem as introduced by Jabali et al. (2015). In the first stage the routing and the ordering of the customers within a route is done by using the tabu search procedure. The second stage generates the schedules of the time windows using the linear programming problem. In this article we test the algorithm on a number of benchmark instances. We indicate the costs involved in including the SITW in the VRP and in addition to this, highlight the advantages of the VRP-SITW over the VRPTW. Lastly, we make some alterations in the algorithm to test the influence on the final obtained costs.