New Refinements for the Solution of Vehicle Routing Problems with Branch and Price
New Refinements for the Solution of Vehicle Routing Problems with Branch and Price
复制标题
带有分支和价格的车辆路径问题解决方案的新改进
DOI：
10.3138/infor.45.4.239
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Gendreau
中科院分区：
文献类型：
--
作者：
Dominique Feillet;M. Gendreau
列生成是一种众所周知的数学规划技术，它基于两个组件：一个主问题，它在一个有限的列池中选择最优列（变量），一个子问题，它向这个池提供潜在的好列，直到满足最优性标准。嵌入在Branch和Price算法中，这种解决方法在许多车辆路线问题中被证明是非常有效的，其中列表示可行的车辆路线。然后子问题通常表示为具有资源约束的最短路径问题，可以使用在实践中通常非常有效的动态规划方法来求解。在本文中，我们提出了一些新的改进，以提高在这种情况下列生成方法的能力，重点是子问题阶段。为简单起见，我们将研究限于带时间窗的车辆路径问题。我们首先介绍了约束规划领域中众所周知的有限差异搜索的概念，并展示了如何将LDS应用于动态规划。我们还讨论了如何操纵动态规划的状态图来模拟标签扩展过程中的局部搜索。最后，我们给出了一些允许在搜索过程中删除大量标签的下限。计算结果表明，这些改进在计算时间方面有相当大的影响。
Abstract Column generation is a well-known mathematical programming technique based on two components: a master problem, which selects optimal columns (variables) in a restricted pool of columns, and a subproblem that feeds this pool with potentially good columns until an optimality criterion is met. Embedded in Branch and Price algorithms, this solution approach proved to be very efficient in the context of numerous vehicle routing problems, where columns represent feasible vehicle routes. The subproblem is then usually expressed as a shortest path problem with resource constraints, which can be solved using dynamic programming methods that are generally very effective in practice. In this paper, we propose some new refinements to improve the capabilities of column generation approaches in this context, with a focus on the subproblem phase. For the sake of simplicity, we restrict our study to the case of the Vehicle Routing Problem with Time Windows. We first introduce the notion of Limited Discrepancy Search, which is well known in the field of Constraint Programming, and we show how LDS can be applied to dynamic programming. We also discuss how the state graph of dynamic programming can be manipulated in order to simulate local search during label extension. Finally, we present some lower bounds that allow removing a substantial number of labels during the search. Computational results demonstrate the considerable impact of these refinements in terms of computing time.