ON THE EFFECTIVENESS OF SET COVERING FORMULATIONS FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS

The Vehicle Routing Problem with Time Windows (VRPTW) is one of the mo st important problems in distribution and transportation. A classical and recently popular technique that has proven effective for solving t hese problems is based on formulating them as a set covering problem. The method starts by solving its linear programming relaxation, via co lumn 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 o f the set covering problem is very close to its linear programming rel axation which makes the branch and bound step extremely efficient. In this paper we explain this behavior by demonstrating that for any dist ribution 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.