A Branch-and-price Algorithm for the Multi-Vehicle Covering Tour Problem

In this paper, we propose a Branch-and-price (BP) algorithm and a Column Generation Heuristic (CGH) for the Multi-Vehicle Covering Tour Problem (m-CTP). Specific dominance and extension pruning rules are introduced to accelerate the resolution of the pricing problems. To the best of our knowledge, this is the first work dedicated to the exact resolution of m-CTP. The algorithm managed to solve about 30% of the instances in our test bed, within a 4 hour CPU time limit. Our preliminary computational experiments suggest that both the lower bounds provided by the formulation behind BP and the CGH upper bounds are of good quality.