Abstract :
[en] The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known extension of the Vehicle Routing Problem, one of the oldest and most studied problems in combinatorial optimization. The VRPTW consists in finding an optimal set of routes for a fleet of vehicles based in a single depot in order to service a set of customers. Each customer is associated with a time window, which specifies the earliest and the latest possible service start times. Time windows are a natural feature of a number of applications, such as postal deliveries, grocery deliveries, or school bus routing.
In addition to the VRPTW, we consider a variant of this problem where the aim is to minimize the total route duration, instead of just the total travel time. Thus, the waiting times that are incurred by vehicles before they can service a customer are taken into account in the objective function of the problem. This aspect is relevant in applications where waiting times bear an implicit cost, such as when the vehicles are rented by the distribution company, or when they consume energy during idle times, as in the case of refrigerated trucks delivering perishable goods.
Branch-and-Price (BP) is one of the most effective and commonly used exact 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. Being able to solve this subproblem efficiently is crucial, since it is a major bottleneck for the performance of the BP procedure. Each of these methods uses a certain strategy to relax the elementarity constraints of the pricing problem in order to accelerate its solution. In this study, we investigate the performances of several such methods within a BP framework.
In order to perform rigorous comparisons, we first parametrize several algorithmic components. Then, we search for good parameter configurations for each algorithm with a tool for automated parameter tuning. Finally, we run the best configuration found for each algorithm on benchmark instances and analyze the results with statistical tests. Our results show in particular that a class of hybrid algorithms, where multiple customer sets are used to control the relaxation of the elementarity conditions, rather than a single one, outperforms all the others.
