Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework

In many appointment-based logistics systems customer orders may be served within a set of consecutive periods/days (i.e. a period window). In this case, the Multi-Period Vehicle Routing Problem (MPVRP) is relevant, and its efficient solution may lead to significant operational improvements. In this paper we investigate the MPVRP with Time Windows (MPVRPTW). The latter are time intervals within each period of the period window, during which service may be provided to the customer. A general model and an exact method to solve the MPVRPTW are presented. The solution method is based on column generation. Furthermore, two novel, efficient techniques to accelerate the solution procedure of the MPVRPTW are proposed. These techniques exploit the structure of the multi-period setting in order to identify similarities within the different subproblems and, thus, avoid solving every subproblem at each iteration. The experimental study analyzed the performance of the proposed methods systematically for various problem parameters, such as geographical distribution of customers and period window patterns. In most cases, the new methods improve significantly the efficiency of convergence to the optimal solution as compared to the classical method.