线性开设费用在线设施选址问题的算法研究

魏露

摘   要：设施选址问题是组合优化问题的经典问题，是NP-困难问题，一般设计近似算法进行求解。文章研究的线性开设费用的在线设施选址问题是在线设施选址问题的變形问题。利用对偶拟合的技巧，给出了竞争比为4Hn的在线算法，其中n为出现的顾客个数。

关键词：在线;设施选址;线性开设费用;竞争比

1    问题描述

线性开设费用的在线设施选址问题可描述为：给定设施集F，顾客集D，任意设施i∈F，开设费用为fi;任意顾客j∈D，服务需求量为dj，通常考虑dj=1的情形。设施i∈F为顾客j∈D提供一个单位服务量的费用为cij，称为连接费用。假定连接费用cij是可度量的，即满足（1）非负性cij≥0。（2）对称性cij=cji。（3）三角不等式cij≤cik+cki。目标是选择F的子集，开设中的设施，确定函数，依据函数将D中顾客连接到相应的设施上，在保证满足D中所有顾客需求的前提下，使开设费用和连接费用总和达到最小[1]。

2    算法

将对偶规划中的变量υjt看作是顾客（j，t）对总费用的贡献，假设存在算法得到的解的费用为R，变量υjt的值满足，若对于任意的O，有，其中，γ≥1是常数，那么该算法的近似比最多为γ。因为对于每一个在最优解中开设的设施i以及在最优解中连接到它上的顾客集合P，有，将该式对最优解中的设施求和得到，算法得到解的费用不超过最优解费用的γ倍，故算法的近似比为γ。也可以从原始对偶的角度来解释近似比，不等式，表明如果将变量υjt一致放缩γ倍可以得到对偶问题的一个可行解且费用为，这个费用也是该问题最优值的下界，这种方法称为对偶拟合（Dual Fitting，DF）。

顾客的到达时间是未知的，当顾客到达时必须有开设的设施为其提供服务，并且一旦顾客连接到某个开设的设施上后，不能再改连其他设施上。根据这样的思想设计算法，对每一个出现的顾客设置一个对偶变量υjt（可能是对偶不可行的），用Dt表示时刻t出现的顾客的集合，X表示已经开设的设施的集合，且最初为空集。对于每一个先前出现的顾客（j，t）肯定已经连接到X中某个开设的设施上，那么它对未开设的设施的预算为[C（X， j）-cij]，其中C（X， j）表示顾客j到集合X中的设施最近的距离，即;对于当前出现的顾客，它对未开设设施的预算为（υjt-cij）。用Si表示设施i当前服务的顾客集合。由于设置的对偶变量可能是不可行的，所以为了对算法的竞争比进行分析，利用对偶拟合的技巧将对偶变量一致缩小某一系数使得新的对偶变量可行。

4    结语

在线设施选址问题有机器广泛的应用，线性开设费用的在线设施选址问题是其变形问题。本文根据问题的特殊性利用对偶拟合的技巧设计了竞争比为4Hn的算法，并且对算法进行了理论分析证明了竞争比。

本文只考虑了线性开设费用的在线设施选址问题，但在实际的生产和管理中，所遇到的问题会受到很多条件的约束，这使得设施选址问题存在大量的变形问题，例如在线的凹设施选址问题等。

[参考文献]

[1]Hochbaum D S.Heuristics for the fixed cost median problem[J].Mathematical Programming，1982（1）：148-162.

[2]Guha S，Khuller S.Greedy strikes back：improved facility location algorithms[J].Jo-urnal of Algorithms，1999（31）：228-248.

[3]徐大川，张家伟.设施选址问题的近似算法[M].北京：科学出版社，2013.