带惩罚的软容量设施选址问题

郭远达 凌锐衡 马倩男 宁萌

【摘要】设施选址问题自20世纪60年代初期以来，在运筹学中一直占据着中心位置。传统设施选址问题要求所有顾客都被服务，这会造成一定的资源浪费，因此可以在模型中设置顾客的惩罚费用，以使得部分顾客不被服务（带惩罚设施选址问题）。另外，可以对模型中开设设施的容量做限制（带容量设施选址问题）。本文将结合以上两种情况建立带惩罚的软容量设施选址模型，通过原始-对偶框架得到4-近似算法，并通过程序验证算法的正确性。

【关键词】软容量设施选址问题  近似比  原始对偶算法

【基金项目】大学生创新创业训练计划项目、202006（编号：202010060119）。

【中图分类号】TP301.6   【文献标识码】A 【文章编号】2095-3089（2021）28-0194-03

一、绪论

设施选址问题的研究目标为开设设施，并且使得设施的开设费用及顾客连接到开设设施上的费用之和最小。设施选址问题是NP-难解问题[1]，除非P=NP，否则设施选址问题不存在多项式时间精确算法，因此本文将采用近似算法。

近似算法是指在多项式时间内给出优化问题的近似优化解的算法。用近似算法得到的解并不是理論上的最优解，而是可行解。目标函数值与最优值之间的比值称为近似比，称近似比为ρ的算法为ρ-近似算法。

无容量设施选址问题（uncapacitated facility location problem，简称UFLP）是设施选址问题中最经典的问题，其特点是开设设施没有容量限制。若每个设施有容量限制且可以多次开设，就称为软容量限制的设施选址问题（Soft capacitated facility location problem，简称SCFLP）。在实际运用中，有时会遇到部分顾客的服务成本很高的情形，此类顾客很难为其分配设施，这时需要加入鲁棒性设置，带惩罚的设施选址问题（facility location problem with penalties，简称FLPWP）便是其中一种。FLPWP允许部分顾客的需求不被满足，这会造成一定的惩罚费用。

本文将讨论带惩罚的软容量设施选址问题（soft capacitated facility location problem with penalties，简称

SCFLPWP）。SCFLPWP是以SCFLP和FLPWP为基础延伸出的新问题，即固定设施和顾客的数量，判断顾客是否惩罚及哪些设施开设，并统计开设设施的开设次数，在此基础上使得设施的开设费用、顾客的服务费用和惩罚费用之和最小。

二、问题描述与符号

在SCFLPWP中，F表示可选设施的集合，C表示顾客集合。我们要求任一设施i∈F可服务多个顾客，任一顾客j∈C只可被一个设施服务。设施i有容量限制，且允许顾客j的服务不被满足，此时需要支付一定的惩罚费用。SCFLPWP旨在在集合F中，选择F的子集，开设中的设施，统计开设次数，在集合C中，选择C的子集，惩罚中的顾客，找到一个映射ω：C＼→，将C＼中的顾客与开设的设施连接，使得开设费用、服务费用和惩罚费用之和最小。

为了方便描述问题和设计算法，引入以下概念和相关符号：

（1）fi为设施i的开设费用;

（2）cij为设施i为顾客j提供单位服务的连接费用;

（3）pj为顾客j未连接到任意设施i的惩罚费用，即顾客j的预算上限;

（4）μi为设施i单次开设的容量。

引入整数变量yi∈N表示设施i开设次数;引入0-1变量xij表示顾客j与设施i是否相连，若相连xij=1，否则xij=0;引入0-1变量zj表示顾客j是否惩罚，若惩罚zj=1，否则zj=0。由此可以得到SCFLPWP的整数线性规划

minfiyi+cijxij+pjzj

s.t.  zj+xij≥1 ∀j∈C

xij≤μiyi ∀i∈F，j∈C

xij≤yi ∀i∈F，j∈C （1）

zj∈{0，1} ∀j∈C

yi∈N ∀i∈F

xij∈{0，1} ∀i∈F，j∈C

在规划（1）中，第一组约束条件表示顾客两种状态：惩罚或连接;第二组约束表示对于开设yi次的设施i，其所服务的顾客总量不能超过设施总容量;第三组约束表示如果有顾客j连接到某个设施i上，则该设施i就必须开设。

三、算法设计

（一）问题转化

将规划（1）整数约束松弛为zj≥0，xij≥0，yi≥0得到SCFLPWP的对偶规划

maxαj

s.t.  αj≤βij+cij+γi ∀i∈F，j∈C

βij≤fi-μiγi ∀i∈F （2）

αj≤pj ∀j∈C

αj，βij，γi≥0 ∀i∈F，j∈C

在规划（2）中，αj表示顾客的贡献;βij表示顾客j对设施i支付的开设费用;γi 无实际意义，当γi =3fi/4μi[2]时，通过构造新的连接费用和设施费用，可以将规划（2）转变为FLPWP的对偶规划，其中设施i开设费用为fi′=fi-μiγi，为顾客j提供单位服务的连接费用为cij′=cij+γi。

（二）算法步骤

在FLPWP对偶规划（2）中，若将约束条件αj≤pj，∀j∈C除去，则FLPWP对偶规划就转变为UFLP的对偶规划。参考Jain和Varizani[2]的UFLP原始对偶3-近似算法，我们发现只需在此算法的基础上增加判断顾客是否被惩罚的处理过程，就可以得到SCFLPWP的原始对偶近似算法。算法整体步骤简述如下：

1.步骤1  构造对偶可行解

确定临时惩罚的顾客：∀j∈C，αj随时间同步增长，当αj=pj时，就将顾客j临时惩罚。

确定临时开设的设施：∀i∈F，j∈C，αj随时间同步增长，当αj=cij′时，若设施i未临时开设，βij开始与时间同步增长。当βij=fi′时，设施i的开设费用被完全支付，将设施i临时开设。

确定顾客与设施的临时连接情况：临时被惩罚的顾客不连接任何设施;∀i∈F，j∈C，对于αj≥cij′的顾客j，若设施i临时开设，且顾客j未被惩罚则将顾客j与设施i连接。

2.步骤2  构造原始整数可行解

确定最终开设设施集合：选择关闭一些临时开设的设施，保证每个顾客至多对一个开设设施有贡献，对于因这些设施关闭而没有连接的顾客，将其重新连接到最近的开设设施上，则剩余开设设施集合即为。

确定最终惩罚的顾客集合：若临时惩罚的顾客中有∀i∈，βij>0的顾客j，就将其放弃惩罚并与设施i连接，则剩余惩罚顾客集合即为。

确定设施i∈开设次数yi：统计每个开设的设施需服务的顾客数量，并计算设施开设次数yi=

。

四、近似比理论分析

引入0-1变量Yi表示设施i是否开设，若设施i开设则Yi=1，否则Yi=0。将γi=3fi/4μi，带入cij′和fi′中，则可得到FLPWP的设施开设费′=fi′Yi=fiYi/4，顾客设施连接费′=cij′xij=cij+3fi/4μixij，顾客惩罚费′=pjzj=αj。结合Jain和Varizani[2]的UFLP原始对偶算法近似比为3，可知3′+′≤3αj，则3′+′+′≤3αj+αj≤3αj。

SCFLPWP的设施开设费=fiyi、设施顾客连接费=cijxij、顾客惩罚费=pjzj，则SCFLPWP的总费用Cost=fiyi+cijxij+pjzj，由yi=

，yi≤Yi+

得

3′+′+′

=fiYi

++cijxij+pjzj

≥fiyi+cijxij+pjzj

=++

又因为++≤3′+′+′≤3αj，则Cost=++≤4αj。综上所述，算法是SCFLPWP的4-近似算法。

五、数值实验

用计算机模拟实际情况来验证SCFLPWP算法的有效性。实验软件为：Matlab2020a;Lingo;系统为Windows 10.64位操作系统。

（一）案例1

用计算机模拟出一个范围是到的矩形区域，在这个区域内随机散布着一定数量的可选设施和300个顾客。每个设施有随机设定的设施成本费和容量上限，每位顾客有随机的惩罚费用，实验要求确定出一个或数个设施开设且连接尽可能多的顾客。我们使用matlab和lingo软件程序模拟此过程，并选取不同的可選设施数量，设置多组数据对比。从我们得到的结果来看，近似比没有明显规律，低于理论近似比4。除此之外，随着可选设施数的增加，受惩罚的顾客是逐步递减的;在顾客数不变，可选设施数逐步递增的情况下，SCFLPWP算法所得到的开设设施数大致不变，而由lingo程序所得到的全局最优解中开设设施数则是逐步递增的。

（二）案例2

为横向对比案例1，我们构建了案例2。在案例1的基础上，固定可选设施的数量为20，并在同样的区域上随机分布一定数量的顾客，其余条件不变。通过对比发现，近似比仍低于4，说明SCFLPWP算法有很高的准确性。与案例1不同的是：随着顾客数量的上升，最终开设费用也在逐步递增，但最终开设设施数却是递减的。

值得一提的是，在现实中，往往不可以直接按全局最优解开设设施，因为某些设施很可能受自然或人为因素的影响无法真正开设。在求解时，SCFLPWP算法具有极大的灵活性，得到的局部最优解也可以为相关从业人员提供参考。

六、总结

本文主要讨论了带惩罚的软容量设施选址问题，其理论依据是将无容量设施选址问题变形后，利用原始对偶的框架得到了4-近似算法，并通过理论论证和计算机程序进行了检验。是否能利用其他方法得到更好的近似比依旧是一个值得我们深入探究的问题。

参考文献：

[1]Shmoys D B ， Tardos V ， Aardal K . Approximation Algorithms for Facility Location Problems[C].Twenty-ninth Acm Symposium on Theory of Computing. ACM， 1997.

[2]Jain K ， Vazirani V V . Approximation algorithms for metric facility location and k -Median problems using the primal⁃dual schema and Lagrangian relaxation[J]. Journal of the Acm， 2001，48（2）：274-296.