论文部分内容阅读
无容量设施选址问题(Uncapacitated Facility Location Problem(UFLP)在许多文献中被广泛研究．由于UFLP是NP-困难的，设计具有较好性能比的高效近似算法是重要的研究手段.两阶段随机设施选址问题(Two Stage Stochastic Facility Location Problem(SFLP)和带惩罚的设施选址问题(Facility Location Problem with Penalties(FLPWP)都是UFLP的重要变形.
本论文中，我们研究带次模惩罚的两阶段随机设施选址问题(Two Stage Stochastic Facility Location Problem with Submodular Penalties(SFLPSP). SFLPSP按下述方式构造成一个两阶段随机模型：第一阶段，用户的信息是未知的；场景出现的概率和概率的分布在第二阶段给出.同一设施在不同阶段和场景的开放费用是不同的．在第一阶段开放的设施可以服务所有场景的用户，在第二阶段某一场景开放的设施只能服务该场景的用户．在每个场景中，某些用户可以不被服务，但是产生次模惩罚费用.我们需要确定每个场景中被相应场景开放的设施或者第一阶段开放的设施服务的用户集合.不被服务的用户集产生相应次模惩罚费用.我们的目标是使得包括设施开放费用，连接费用以及惩罚费用的总费用最小.
结合UFLP, SFLP和FLPSP的原始对偶技巧，我们给出了SFLPSP的原始对偶3-近似算法.