On the effectiveness of set covering formulations for the vehicle routing problem with time windows
成果类型：
Article
署名作者：
Bramel, J; SimchiLevi, D
署名单位：
Northwestern University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.2.295
发表日期：
1997
页码：
295-301
关键词：
摘要：
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.