On the Effectiveness of Set Covering Formulations for the Vehicle Routing Problem with Time Windows

Abstract

The Vehicle Routing Problem with Time Windows (VRPTW) is one of the most important problems in distribution and transportation. A classical and recently popular technique that has proven effective for solving these problems is based on formulating them as a set covering problem. The method starts by solving its linear programming relaxation, via column generation, and then uses a branch and bound strategy to find an integer solution to the set covering problem: a solution to the VRPTW. An empirically observed property is that the optimal solution value of the set covering problem is very close to its linear programming relaxation which makes the branch and bound step extremely efficient. In this paper we explain this behavior by demonstrating that for any distribution of service times, time windows, customer loads, and locations, the relative gap between fractional and integer solutions of the set covering problem becomes arbitrarily small as the number of customers increases.