郭遠(yuǎn)達(dá) 凌銳衡 馬倩男 寧萌

【摘要】設(shè)施選址問題自20世紀(jì)60年代初期以來，在運(yùn)籌學(xué)中一直占據(jù)著中心位置。傳統(tǒng)設(shè)施選址問題要求所有顧客都被服務(wù)，這會造成一定的資源浪費(fèi)，因此可以在模型中設(shè)置顧客的懲罰費(fèi)用，以使得部分顧客不被服務(wù)（帶懲罰設(shè)施選址問題）。另外，可以對模型中開設(shè)設(shè)施的容量做限制（帶容量設(shè)施選址問題）。本文將結(jié)合以上兩種情況建立帶懲罰的軟容量設(shè)施選址模型，通過原始-對偶框架得到4-近似算法，并通過程序驗(yàn)證算法的正確性。

【關(guān)鍵詞】軟容量設(shè)施選址問題? 近似比? 原始對偶算法

【基金項(xiàng)目】大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目、202006（編號：202010060119）。

【中圖分類號】TP301.6 ? 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2021）28-0194-03

一、緒論

設(shè)施選址問題的研究目標(biāo)為開設(shè)設(shè)施，并且使得設(shè)施的開設(shè)費(fèi)用及顧客連接到開設(shè)設(shè)施上的費(fèi)用之和最小。設(shè)施選址問題是NP-難解問題[1]，除非P=NP，否則設(shè)施選址問題不存在多項(xiàng)式時(shí)間精確算法，因此本文將采用近似算法。

近似算法是指在多項(xiàng)式時(shí)間內(nèi)給出優(yōu)化問題的近似優(yōu)化解的算法。用近似算法得到的解并不是理論上的最優(yōu)解，而是可行解。目標(biāo)函數(shù)值與最優(yōu)值之間的比值稱為近似比，稱近似比為ρ的算法為ρ-近似算法。

無容量設(shè)施選址問題（uncapacitated facility location problem，簡稱UFLP）是設(shè)施選址問題中最經(jīng)典的問題，其特點(diǎn)是開設(shè)設(shè)施沒有容量限制。若每個(gè)設(shè)施有容量限制且可以多次開設(shè)，就稱為軟容量限制的設(shè)施選址問題（Soft capacitated facility location problem，簡稱SCFLP）。在實(shí)際運(yùn)用中，有時(shí)會遇到部分顧客的服務(wù)成本很高的情形，此類顧客很難為其分配設(shè)施，這時(shí)需要加入魯棒性設(shè)置，帶懲罰的設(shè)施選址問題（facility location problem with penalties，簡稱FLPWP）便是其中一種。FLPWP允許部分顧客的需求不被滿足，這會造成一定的懲罰費(fèi)用。

本文將討論帶懲罰的軟容量設(shè)施選址問題（soft capacitated facility location problem with penalties，簡稱

SCFLPWP）。SCFLPWP是以SCFLP和FLPWP為基礎(chǔ)延伸出的新問題，即固定設(shè)施和顧客的數(shù)量，判斷顧客是否懲罰及哪些設(shè)施開設(shè)，并統(tǒng)計(jì)開設(shè)設(shè)施的開設(shè)次數(shù)，在此基礎(chǔ)上使得設(shè)施的開設(shè)費(fèi)用、顧客的服務(wù)費(fèi)用和懲罰費(fèi)用之和最小。

二、問題描述與符號

在SCFLPWP中，F(xiàn)表示可選設(shè)施的集合，C表示顧客集合。我們要求任一設(shè)施i∈F可服務(wù)多個(gè)顧客，任一顧客j∈C只可被一個(gè)設(shè)施服務(wù)。設(shè)施i有容量限制，且允許顧客j的服務(wù)不被滿足，此時(shí)需要支付一定的懲罰費(fèi)用。SCFLPWP旨在在集合F中，選擇F的子集，開設(shè)中的設(shè)施，統(tǒng)計(jì)開設(shè)次數(shù)，在集合C中，選擇C的子集，懲罰中的顧客，找到一個(gè)映射ω：C＼→，將C＼中的顧客與開設(shè)的設(shè)施連接，使得開設(shè)費(fèi)用、服務(wù)費(fèi)用和懲罰費(fèi)用之和最小。

為了方便描述問題和設(shè)計(jì)算法，引入以下概念和相關(guān)符號：

（1）fi為設(shè)施i的開設(shè)費(fèi)用;

（2）cij為設(shè)施i為顧客j提供單位服務(wù)的連接費(fèi)用;

（3）pj為顧客j未連接到任意設(shè)施i的懲罰費(fèi)用，即顧客j的預(yù)算上限;

（4）μi為設(shè)施i單次開設(shè)的容量。

引入整數(shù)變量yi∈N表示設(shè)施i開設(shè)次數(shù);引入0-1變量xij表示顧客j與設(shè)施i是否相連，若相連xij=1，否則xij=0;引入0-1變量zj表示顧客j是否懲罰，若懲罰zj=1，否則zj=0。由此可以得到SCFLPWP的整數(shù)線性規(guī)劃

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

在規(guī)劃（1）中，第一組約束條件表示顧客兩種狀態(tài)：懲罰或連接;第二組約束表示對于開設(shè)yi次的設(shè)施i，其所服務(wù)的顧客總量不能超過設(shè)施總?cè)萘?第三組約束表示如果有顧客j連接到某個(gè)設(shè)施i上，則該設(shè)施i就必須開設(shè)。

三、算法設(shè)計(jì)

（一）問題轉(zhuǎn)化

將規(guī)劃（1）整數(shù)約束松弛為zj≥0，xij≥0，yi≥0得到SCFLPWP的對偶規(guī)劃

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

在規(guī)劃（2）中，αj表示顧客的貢獻(xiàn);βij表示顧客j對設(shè)施i支付的開設(shè)費(fèi)用;γi 無實(shí)際意義，當(dāng)γi =3fi/4μi[2]時(shí)，通過構(gòu)造新的連接費(fèi)用和設(shè)施費(fèi)用，可以將規(guī)劃（2）轉(zhuǎn)變?yōu)镕LPWP的對偶規(guī)劃，其中設(shè)施i開設(shè)費(fèi)用為fi′=fi-μiγi，為顧客j提供單位服務(wù)的連接費(fèi)用為cij′=cij+γi。

（二）算法步驟

在FLPWP對偶規(guī)劃（2）中，若將約束條件αj≤pj，?j∈C除去，則FLPWP對偶規(guī)劃就轉(zhuǎn)變?yōu)閁FLP的對偶規(guī)劃。參考Jain和Varizani[2]的UFLP原始對偶3-近似算法，我們發(fā)現(xiàn)只需在此算法的基礎(chǔ)上增加判斷顧客是否被懲罰的處理過程，就可以得到SCFLPWP的原始對偶近似算法。算法整體步驟簡述如下：

1.步驟1? 構(gòu)造對偶可行解

確定臨時(shí)懲罰的顧客：?j∈C，αj隨時(shí)間同步增長，當(dāng)αj=pj時(shí)，就將顧客j臨時(shí)懲罰。

確定臨時(shí)開設(shè)的設(shè)施：?i∈F，j∈C，αj隨時(shí)間同步增長，當(dāng)αj=cij′時(shí)，若設(shè)施i未臨時(shí)開設(shè)，βij開始與時(shí)間同步增長。當(dāng)βij=fi′時(shí)，設(shè)施i的開設(shè)費(fèi)用被完全支付，將設(shè)施i臨時(shí)開設(shè)。

確定顧客與設(shè)施的臨時(shí)連接情況：臨時(shí)被懲罰的顧客不連接任何設(shè)施;?i∈F，j∈C，對于αj≥cij′的顧客j，若設(shè)施i臨時(shí)開設(shè)，且顧客j未被懲罰則將顧客j與設(shè)施i連接。

2.步驟2? 構(gòu)造原始整數(shù)可行解

確定最終開設(shè)設(shè)施集合：選擇關(guān)閉一些臨時(shí)開設(shè)的設(shè)施，保證每個(gè)顧客至多對一個(gè)開設(shè)設(shè)施有貢獻(xiàn)，對于因這些設(shè)施關(guān)閉而沒有連接的顧客，將其重新連接到最近的開設(shè)設(shè)施上，則剩余開設(shè)設(shè)施集合即為。

確定最終懲罰的顧客集合：若臨時(shí)懲罰的顧客中有?i∈，βij>0的顧客j，就將其放棄懲罰并與設(shè)施i連接，則剩余懲罰顧客集合即為。

確定設(shè)施i∈開設(shè)次數(shù)yi：統(tǒng)計(jì)每個(gè)開設(shè)的設(shè)施需服務(wù)的顧客數(shù)量，并計(jì)算設(shè)施開設(shè)次數(shù)yi=

。

四、近似比理論分析

引入0-1變量Yi表示設(shè)施i是否開設(shè)，若設(shè)施i開設(shè)則Yi=1，否則Yi=0。將γi=3fi/4μi，帶入cij′和fi′中，則可得到FLPWP的設(shè)施開設(shè)費(fèi)′=fi′Yi=fiYi/4，顧客設(shè)施連接費(fèi)′=cij′xij=cij+3fi/4μixij，顧客懲罰費(fèi)′=pjzj=αj。結(jié)合Jain和Varizani[2]的UFLP原始對偶算法近似比為3，可知3′+′≤3αj，則3′+′+′≤3αj+αj≤3αj。

SCFLPWP的設(shè)施開設(shè)費(fèi)=fiyi、設(shè)施顧客連接費(fèi)=cijxij、顧客懲罰費(fèi)=pjzj，則SCFLPWP的總費(fèi)用Cost=fiyi+cijxij+pjzj，由yi=

，yi≤Yi+

得

3′+′+′

=fiYi

++cijxij+pjzj

≥fiyi+cijxij+pjzj

=++

又因?yàn)?+≤3′+′+′≤3αj，則Cost=++≤4αj。綜上所述，算法是SCFLPWP的4-近似算法。

五、數(shù)值實(shí)驗(yàn)

用計(jì)算機(jī)模擬實(shí)際情況來驗(yàn)證SCFLPWP算法的有效性。實(shí)驗(yàn)軟件為：Matlab2020a;Lingo;系統(tǒng)為Windows 10.64位操作系統(tǒng)。

（一）案例1

用計(jì)算機(jī)模擬出一個(gè)范圍是到的矩形區(qū)域，在這個(gè)區(qū)域內(nèi)隨機(jī)散布著一定數(shù)量的可選設(shè)施和300個(gè)顧客。每個(gè)設(shè)施有隨機(jī)設(shè)定的設(shè)施成本費(fèi)和容量上限，每位顧客有隨機(jī)的懲罰費(fèi)用，實(shí)驗(yàn)要求確定出一個(gè)或數(shù)個(gè)設(shè)施開設(shè)且連接盡可能多的顧客。我們使用matlab和lingo軟件程序模擬此過程，并選取不同的可選設(shè)施數(shù)量，設(shè)置多組數(shù)據(jù)對比。從我們得到的結(jié)果來看，近似比沒有明顯規(guī)律，低于理論近似比4。除此之外，隨著可選設(shè)施數(shù)的增加，受懲罰的顧客是逐步遞減的;在顧客數(shù)不變，可選設(shè)施數(shù)逐步遞增的情況下，SCFLPWP算法所得到的開設(shè)設(shè)施數(shù)大致不變，而由lingo程序所得到的全局最優(yōu)解中開設(shè)設(shè)施數(shù)則是逐步遞增的。

（二）案例2

為橫向?qū)Ρ劝咐?，我們構(gòu)建了案例2。在案例1的基礎(chǔ)上，固定可選設(shè)施的數(shù)量為20，并在同樣的區(qū)域上隨機(jī)分布一定數(shù)量的顧客，其余條件不變。通過對比發(fā)現(xiàn)，近似比仍低于4，說明SCFLPWP算法有很高的準(zhǔn)確性。與案例1不同的是：隨著顧客數(shù)量的上升，最終開設(shè)費(fèi)用也在逐步遞增，但最終開設(shè)設(shè)施數(shù)卻是遞減的。

值得一提的是，在現(xiàn)實(shí)中，往往不可以直接按全局最優(yōu)解開設(shè)設(shè)施，因?yàn)槟承┰O(shè)施很可能受自然或人為因素的影響無法真正開設(shè)。在求解時(shí)，SCFLPWP算法具有極大的靈活性，得到的局部最優(yōu)解也可以為相關(guān)從業(yè)人員提供參考。

六、總結(jié)

本文主要討論了帶懲罰的軟容量設(shè)施選址問題，其理論依據(jù)是將無容量設(shè)施選址問題變形后，利用原始對偶的框架得到了4-近似算法，并通過理論論證和計(jì)算機(jī)程序進(jìn)行了檢驗(yàn)。是否能利用其他方法得到更好的近似比依舊是一個(gè)值得我們深入探究的問題。

參考文獻(xiàn)：

[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.