Covering problems are well-studied in the domain of Operations Research, and, more specifically, in Location Science. When the location space is a network, the most frequent assumption is to consider the candidate facility locations, the points to be covered, or both, to be discrete sets. In this work, we study the set-covering location problem when both candidate locations and demand points are continuous sets on a network. This variant has received little attention, and the scarce existing approaches have focused on particular cases, such as tree networks and integer covering radius. Here we study the general problem and present a Mixed Integer Linear Programming formulation (MILP) for networks with edges' lengths no greater than the covering radius. The model does not lose generality, as any edge not satisfying this condition can be partitioned into subedges of appropriate lengths without changing the problem. We propose a preprocessing algorithm to reduce the size of the MILP, and devise tight big-$M$ constants and valid inequalities to strengthen our formulations. Moreover, a second MILP is proposed, which admits edges' lengths greater than the covering radius. As opposed to existing formulations of the problem (including the first MILP proposed herein), the number of variables and constraints of this second model does not depend on the lengths of the network's edges. This second model represents a scalable approach that particularly suits real-world networks, whose edges are usually greater than the covering radius. Our computational experiments show the strengths and limitations of our exact approach on both real-world and random networks. Our formulations are also tested against an existing exact method.
翻译:在业务研究领域,更具体地说,在位置科学领域,对覆盖的问题进行了深入的研究。当位置空间是一个网络时,最经常的假设是考虑候选设施的位置,所覆盖的点或两者都是离散的组合。在这项工作中,当候选地点和需求点都是网络上连续的组合时,我们研究覆盖设定的定位问题。这个变量没有得到多少注意,现有办法很少集中在特定案例中,例如树网络和覆盖半径的整数。在这里,我们研究一般问题,为边缘长度不大于覆盖半径的网络提供混合的内径线设计(MILP) 。模型不会失去普遍性,因为任何不能满足这一条件的边缘可以在不改变问题的情况下被分割成适当长度的子层。我们提出一个预处理算法,以缩小MILP的规模, 并设计紧凑大- M 值的第二模型, 以及有效的不平等来强化我们的配方。此外,第二个MILP 提议采用比覆盖范围网络的长度要长得多。 模型中的第一边是覆盖网络的长度, 包括我们目前准确的变量的长度。