A comparative study of branch-and-price algorithms for vehicle routing with time windows and waiting time costs

Branch-and-price is a leading methodology for solving routing problems. Several studies have investigated labeling algorithms to solve the related pricing problem, which is usually a variant of the elementary shortest path problem with resource constraints. Solving this problem efficiently is crucial, since it is a performance bottleneck for the branch-and-price procedure. Such algorithms include methods like decremental state space relaxation, ng-route relaxation, and hybrids of these two. These focus on how to treat efficiently the elementarity constraints, since they tend to make label domination difficult, which translates to more computational resources used. In this study, we investigate the performance of these methods in a branch-and-price framework. The problem under consideration is a variant of the vehicle routing problem with time windows in which waiting times have a linear cost. We first parametrize several algorithmic components. Then, we search for good parameter configurations for each algorithm with irace, a tool for automated parameter tuning that generates and runs a very high number of configurations on a set of tuning instances and uses statistical tests to determine the best performing configuration. Finally, we run all final configurations on the Solomon benchmark instances and analyze the results with statistical tests. Our results show that a class of hybrid algorithms with certain features based on ng-route relaxation outperforms all the others.