A Comparative Study of Branch-And Algorithms for Vehicle Routing With Time Windows and Waiting Time Costs

Abstract

Branch-and-price is one of the most commonly used methodologies for solving routing problems. In recent years, several studies have investigated advanced labeling algorithms to solve the related pricing problem, which is usually a variant of the elementary shortest path problem with resource constraints. Such algorithms include efficient techniques such as decremental state space relaxation, ng-route relaxation, and several hybridizations of these two relaxation methods. In this study, we compare the performance of these labeling algorithms in a branch-and-price framework when applied to the vehicle routing problem with time windows and a variant of this problem in which waiting times have a linear cost. For the latter problem, we also propose an appropriate label structure with associated resource extension functions and dominance rules. We perform these comparisons by using a rigorous methodology, which consists of parameterizing several features of these algorithms, obtaining a good parameter configuration for each algorithm, and analyzing the performance of these configurations on benchmark instances. In order to obtain good configurations, we make use of irace, which is a tool for automated parameter tuning, while statistical tests are used for performance comparisons. Our results show that a class of hybrid algorithms with certain features based on ng-route relaxation outperforms all the others.