论文标题
弯曲者的网络设计覆盖问题的分解
Benders decomposition for Network Design Covering Problems
论文作者
论文摘要
我们考虑了两个网络设计问题的覆盖变体。我们将获得一组原点/目的地对，称为O/D对，如果网络中存在一个从原点到目的地的路径，则每个这样的O/D对都涵盖，其长度不大于给定阈值。在第一个问题（称为最大覆盖网络设计问题）中，必须确定一个网络，该网络最大程度地提高了对网络设计成本的预算限制，对所涵盖的O/D成对的总满足需求。在第二个问题（称为部分覆盖网络设计问题）中，设计成本将最小化，而下限设置为涵盖的总需求。提出配方后，我们开发了一种弯曲者分解方法来解决问题。此外，我们考虑了几种稳定方法来确定弯曲器的切割，以及在主问题中添加剪切不平等。我们还考虑在方法中添加初始解决方案的影响。计算实验显示了这些不同方面的效率。
We consider two covering variants of the network design problem. We are given a set of origin/destination pairs, called O/D pairs, and each such O/D pair is covered if there exists a path in the network from the origin to the destination whose length is not larger than a given threshold. In the first problem, called the Maximal Covering Network Design problem, one must determine a network that maximizes the total fulfilled demand of the covered O/D pairs subject to a budget constraint on the design costs of the network. In the second problem, called the Partial Covering Network Design problem, the design cost is minimized while a lower bound is set on the total demand covered. After presenting formulations, we develop a Benders decomposition approach to solve the problems. Further, we consider several stabilization methods to determine Benders cuts as well as the addition of cut-set inequalities to the master problem. We also consider the impact of adding an initial solution to our methods. Computational experiments show the efficiency of these different aspects.
