选址求解器

伪代码

这个问题在两项方向相反的成本之间权衡：开设站点要花钱，但每多开一个站点，通往客户的路程就更短。精确表述是一个整数规划；实践中则采用带局部改进的贪心启发式。

// 精确（小规模）：枚举站点的每个子集
最优 = 无穷大
对候选站点的每个非空子集 S:
    代价 = S 中各 f 的 开设成本[f] 之和
    对每个客户 c:
        代价 += S 中各 f 的 服务成本[f][c] 的最小值
    最优 = min(最优, 代价)

// 贪心（大规模）：开设能省下最多的那个站点
S = {}
重复:
    f* = 使总代价下降最多的未开设站点
    若开设 f* 不能降低总代价: 停止
    S = S + {f*}

// 之后：用交换、开设与关闭做局部搜索

关键在于客户总是被分配给对他们而言最便宜的已开设站点，因此唯一真正的自由度就是开设哪一个子集。这把一个看似连续的问题变成了在子集上的组合问题，而这也正是它 NP 困难的原因：共有 2 的 n 次方个子集，而且没有已知办法能在多项式时间内遍历它们。

分步示例演算

在三个候选站点和四个客户的情形下决定开设哪些站点，把所有子集都比一遍。

示例图: 开设成本：F1 为 10，F2 为 8，F3 为 6。各客户的服务成本：F1 服务 C1 与 C2 分别为 2 和 3，但服务 C3 与 C4 各需 9；F2 服务 C3 与 C4 分别为 2 和 3，但服务 C1 与 C2 需 8 和 7；F3 服务这四个客户各需 5。

1. 只开设 F1. 开设成本 10，加上服务成本 2 + 3 + 9 + 9，合计 33。F1 对它附近那两个客户极好，对另外两个则糟糕透顶。
2. 只开设 F2. 开设成本 8，加上 8 + 7 + 2 + 3，合计 28。它是 F1 的镜像。
3. 同时开设 F1 与 F2. 开设成本 10 + 8 = 18，此时每个客户都挑自己最好的选择：服务成本 2 + 3 + 2 + 3 = 10，合计 28。服务成本已经无可挑剔，但支付两次开设成本把好处全吃掉了。
4. 只开设 F3. 开设成本 6，加上服务成本 5 + 5 + 5 + 5 = 20，合计 26。F3 对任何一个具体客户都不是最优选择，却依然胜出。
5. 三个全开. 开设成本 10 + 8 + 6 = 24，加上 2 + 3 + 2 + 3 = 10，合计 34。多开站点反而更糟。

最优方案是只开设 F3，总代价为 26。这一点值得停下来体会：F3 不是任何一个客户的首选站点，然而最优子集恰恰就是它。一个把每个客户分配给其服务成本最低站点的启发式，会开设 F1 与 F2 并得到 28。真正起作用的只有开设成本与服务成本之间的权衡，而逐个客户去推理捕捉不到这一点。

复杂度及其来源

时间: NP 困难；精确解为 O(2^n · n · m) · 空间: O(n · m)

设有 n 个候选站点和 m 个客户，精确枚举要测试全部 2 的 n 次方个非空子集，并对每个子集把 m 个客户各以 O(n) 的代价分配到最便宜的已开设站点，因此是 O(2 的 n 次方乘以 n 乘以 m)。这只在大约 20 到 25 个站点以内才可行。该问题是 NP 困难的，因此不预期存在精确的多项式算法。好消息是无容量限制的版本是可近似的：基于线性规划舍入与局部搜索，存在近似比约为 1.5 的常数因子算法，这与图着色形成鲜明对照，后者没有任何像样的近似算法。每一步开设能带来最大节省的站点这种贪心做法具有对数级保证，实践中表现也不错。

何时使用设施选址，何时不宜

选哪个版本取决于站点是否有容量上限，以及客户有多少。

常见陷阱

• 在决定开设哪些站点之前就分配客户. 一旦开设集合确定，分配就是平凡的：每个客户去往对他最便宜的已开设站点。反过来推理、先给每个客户挑最中意的站点，会导致开得过多，正如例子中这种思路给出 28 而最优是 26。
• 以为多开站点总是有帮助. 例子中把三个全开要花 34，比只开 F3 的 26 更糟。每开一个站点都会增加一笔固定成本，它必须靠服务成本的节省来摊平，而这往往做不到。
• 在存在容量上限时却忽视它. 无容量版本允许一个站点服务所有客户。如果现实中存在需求上限，那么无容量下的最优解可能根本不可行，此时需要的是带容量的表述。
• 在真实成本并非欧氏距离时仍用欧氏距离. 服务成本往往包含行车时间、通行费、时间窗或分区费率。用直线距离来替代会改变问题本身，往往也会改变答案。
• 在需求会波动时把结果当成定论. 选址是依据一份需求预测做出的长期决策。在动工之前，值得检验一下在别的需求情形下这个最优子集是否依然最优。

常见问题

什么是选址问题？

给定一组带开设成本的候选地点，以及一组客户及其从各地点获得服务的成本，该问题要确定开设哪些站点，使开设成本与服务成本之和最小。它可用来刻画仓库选址、服务器部署、门店网络规划以及数据中心选点。

选址问题为什么困难？

因为一旦决定开设哪些站点，客户分配就是平凡的，于是整个问题收缩为「选择一个站点子集」。有 n 个候选就有 2 的 n 次方个子集，而且没有已知办法在多项式时间内搜遍它们。该问题是 NP 困难的，不过无容量版本确实允许常数因子的近似。

有容量与无容量的选址有什么区别？

无容量时，一个已开设的站点可以服务任意多的客户。有容量时，每个站点都有需求上限，因此客户可能被迫去往更贵的站点，只因最近的那个已经满了。带容量的版本要难得多，其解在结构上也不同。

多开站点总能降低成本吗？

不能。每开一个站点都会增加一笔固定成本，只有当服务成本的节省超过它时才划算。在上面的例子中，三个站点全开要花 34，而只开一个只要 26。固定成本与可变成本之间的这种权衡正是该问题的核心。

选址问题与 K-均值有什么区别？

K-均值把点划分为 k 个簇并最小化簇内距离，既没有开设成本，k 也是事先给定的。选址问题则要决定开设多少个以及开设哪些站点，在开设成本与服务成本之间做权衡。K-均值是聚类问题，选址则是一个经济决策问题。