Continuous Facility Location with Backbone Network Costs
Continuous Facility Location with Backbone Network Costs
复制标题
具有骨干网络成本的连续设施选址
作者：
J. Carlsson;Fan Jia
我们考虑一个连续的设施选址问题，其中我们的目标是最小化三个成本的加权和：1 安装设施的固定成本，2 将设施相互连接产生的骨干网络成本，以及 3 从设施到服务区域提供服务产生的运输成本。我们首先分析该模型的限制行为，并推导设施的两种渐近最优配置：其中一种配置是经过充分研究的蜂窝启发式，另一种是阿基米德螺旋。然后，我们给出一种快速常数因子近似算法，用于找到一组设施在任何凸多边形中的放置，从而最小化上述三个成本的总和。
We consider a continuous facility location problem in which our objective is to minimize the weighted sum of three costs: 1 fixed costs from installing the facilities, 2 backbone network costs incurred from connecting the facilities to each other, and 3 transportation costs incurred from providing services from the facilities to the service region. We first analyze the limiting behavior of this model and derive the two asymptotically optimal configurations of facilities: one of these configurations is the well studied honeycomb heuristic, and the other is an Archimedean spiral. We then give a fast constant-factor approximation algorithm for finding the placement of a set of facilities in any convex polygon that minimizes the sum of the three aforementioned costs.