A Vehicle Routing Problem with Flexible Time Windows

In several real-world situations, time window constraints can be violated to a certain extent. In this paper we aim to assess the operational gains obtained by employing a fixed relaxation of the time window constraints. Namely, we study the Vehicle Routing Problem with Flexible Time Windows (VRPFlexTW), in which vehicles are allowed to deviate from customer time windows by a given tolerance. This flexibility enables savings in the operational costs of carriers, since customers may be served before and after the earliest and latest time window bounds, respectively. As time window violations affect customers satisfaction, they are penalized.

Our solution procedure comprises three main components: initialization, routing and scheduling. The time-oriented nearest neighbor heuristic is used in the initialization component. The routing component is handled via a tabu search algorithm, while the scheduling component is performed by solving an LP model. We validate our solution algorithm on benchmark instances and test the performance of the solution procedure with various stopping criteria values. Furthermore, we compare the solutions of the VRPTW with those of the VRPFlexTW. In many instances, we observe that the VRPFlexTW results in operational gains when compared to the VRPTW. These gains are achieved by a reduction in the total distance traveled or by a reduction in the number of vehicles used or by a reduction both in the total distance and in the number of vehicles.

We model a practical problem and develop an efficient solution frame- work to handle it. Our solution approach can effectively be used by carrier companies trying to assess the added value of allowing a certain extent of customer service flexibility. Generally, relaxing time windows improves the total cost. However, this relaxation brings some violations. This trade-off might be balanced with respect to the preferences of carrier companies and to the concerns of their customers. Further research may focus on handling uncertainties in travel times and on exploring more complex penalty func- tions.