Column Generation Based Algorithms for a VRP with Time Windows and Variable Departure Times

We investigate a solution methodology for a variant of the VRP with time windows. In the examined variant, the departure time of each vehicle from the depot can be determined by the decision-maker, who aims at minimizing the overall duration of the routes, including waiting times, while respecting the maximum allowed working duration of each vehicle. In order to solve this problem with a branch-and-price methodology, we address the associated pricing problem as an elementary shortest path problem with resource constraints (ESPPRC). We propose an adapted bidirectional dynamic programming algorithm for the studied ESPPRC. The decremental state space relaxation (DSSR) technique is also implemented as an acceleration technique both to obtain ng-routes and elementary routes. Several implementation and integration strategies are considered for the DSSR and ng-route relaxation techniques. The ng-route pricing and the elementary route pricing algorithms are compared inside a column generation procedure. For both column generation procedures, the algorithmic choices are made and the values of the numerical parameters are determined using an automatic algorithm configuration tool, the irace package. Finally, we discuss how these column generation procedures can be included as a component in the development of a matheuristic.