魯棒動態設施選址問題的近似算法

吳晨晨， 王 麗， 徐春明， 徐大川

(1.南開大學 商學院,天津 300371; 2.天津理工大學 理學院,天津 300384; 3.北京工業大學 數學學院,北京 100124)

0 引言

在建立和管理實體企業中，首要任務就是要進行合理的選址。同時，選址也是事業擴展的第一步。因此設施選址的重要性顯而易見。另一方面，設施是指在生成過程賴以運行的硬件條件，常見由工廠、倉庫、車間等實體構成。而設施選址就是指合理利用科學方法選擇以上提及設施的地理位置，使其與企業整體運營體系有機結合，從而達到企業的經營目標。選址后對建成后的設施布置以及投產后的生產經營費用、產品和服務質量以及成本都有極大而長久的影響。考慮到不當的設施選址會給企業運營帶來若干不良影響，而僅靠事后加強和完善管理是無法彌補的,因此該問題引起了眾多學者的關注[21]。 在進行設施選址時，必須充分考慮到多方面因素的影響，慎重決策。除新建企業的設施選址問題以外，隨著經濟的發展，城市規模的擴大，以及地區之間的發展差異，很多企業面臨著重新選址的問題，等等。可見，設施選址是很多企業在生產運作過程中都面臨的一個重要問題。大量的成功案例證明，在選址問題上，以下原則是必要的。

(1)成本最小原則：作為經濟實體的企業，經濟利益對于企業無論何時何地都是重要的。固定費用，單個顧客的服務成本，等等都與選址有關。

(2)接近顧客原則：對于實體經濟，都需要遵循這條原則，如銀行儲蓄所、郵電局、電影院、醫院、學校、零售業的所有商店等。許多制造企業也把工廠建到消費市場附近，以降低運費和損耗。

(3)動態發展原則：選址是一項帶有戰略性的經營管理活動，因此在選址是要綜合考慮企業生產力的合理布局，市場的開拓。這樣才能在當前世界經濟越來越趨于一體化的時代背景下，增加企業的競爭力。

從解決問題的角度看，設施選址問題是起源于傳統韋伯問題 (Weber Problem)。具體地說，該問題是指在待選的地址中開設一個設施，使得事先給定的顧客連接到該設施的距離之和最小。對于此類問題只需事先將所有待選設施中的所有設施遍歷計算相應的費用得到最小的決策即為最優解。隨著社會和經濟發展，開設一個設施遠遠不夠，同時設施的建立也需要一定的成本。由此，不斷發展出了設施選址問題，其中最經典的問題為無容量的設施選址問題 (uncapacitated facility location problem，簡稱UFLP)。

無容量設施選址問題是指給定設施的集合F和顧客的集合C,設施i∈F的開設費用為fi,設施i∈F和顧客j∈C之間的連接費用(即服務成本)為cij,該問題的目標為開設一些設施，將每個顧客連接到一個開設的設施 上使得開設費用和連接費用之和最小。由于可以從集合覆蓋問題規約而來，從而設施選址問題是NP-困難的。這類問題在P≠NP的假設下，不存在有效時間的 (即多項式時間)算法。為此，處理這類問題的一個重要方法是丟棄掉對最優解的追求，找到問題的一個可控的可行解即可。這類方法稱為近似算法，即，如果算法A所得解的費用不超過α倍最優值，那么被稱為α-近似算法。UFLP的第一個常數近似比是由Shmoys等人[18]通過建立整數線性規劃，松弛整數約束，進而利用算法將分數最優解舍入為整數解，給出了3.16-近似算法。后來，許多學者不斷創造新的技巧得到更好的近似比。總體來說，設施選址問題的近似算法技巧可以分為四類，線性規劃舍入[18]，原始-對偶[11]，對偶-擬合[10]，局部搜索[1]。目前，最好的近似比是Li[15]利用綜合線性規劃舍入和對偶-擬合技巧得到的1.488-近似算法。除非P=NP，UFLP不存在近似比低于1.463的近似算法[6]。

在設施建立后服務顧客的過程中，有時會遇到某些顧客的服務成本很高的情形。因此，經常在此類問題中加入一些魯棒設置。這里介紹兩種。第一種，每個顧客都有不被服務的成本，這里稱之為懲罰費用。若選擇不服務該顧客，則需要支付相應的懲罰費用，這類問題則稱之為帶懲罰的設施選址問題(facility location problem with penalties，簡稱FLPWP)。第二種，規定可以至多不服務個顧客，這些顧客被稱為異常點(outlier)。允許異常點的設施選址問題被稱為帶異常點的設施選址問題(facility location problem with outliers，簡稱FLPWO)。

優化問題中，時常考慮異常點的設置。FLPWO由Charikar等[2]提出，在設施選址問題原始對偶技巧的基礎上得到3-近似算法。此外，異常點設置在數據挖掘中有重要的應用。Gupta等[7]利用局部搜索技巧得到了常數的近似比，但會較小的違背異常點數目限制。在此之后，不斷有學者對此問題進行討論[3,5,7,14]。

對比前述工作，本文將討論同時具有帶懲罰和異常點的動態設施選址問題(dynamic facility location problem with penalties and outliers，簡稱DFLPWPO)，利用原始對偶技巧，保持了近似比，得到3-近似算法。本文接下來將按照如下結構對魯棒動態設施選址問題的研究工作展開論述。第二部分將介紹魯棒動態設施選址問題的描述和相關的符號；第三部分將介紹原始-對偶算法；第四部分將對第二部分的算法進行分析，得到近似比為3；最后則對全文進行總結并給出研究展望。

1 問題描述與符號

為了方便描述問題和設計算法，本文引入以下概念和相關記號：

?(i,s)∈F,(j,t)∈D

(1)

在上述規劃中，第一組約束表示每個顧客-時刻對(j,t)要不連接到一個設施-時刻對，要不被懲罰，要不作為異常點；第二組約束表示如果顧客-時刻對(j,t)連接到設施-時刻對(i,s)上，則設施-時刻對一定開設；第三組約束表示異常點至多有l個。

2 算法

由于FLPWO的整數間隙是無窮，從而作為推廣模型的DFLPWPO，其整數間隙也為無窮。為處理這一問題個算法設計帶來的困難，我們借助文獻[2]中轉變實例的方法。因此，對于給定DFLPWPO的實例I，我們將其轉化為實例I′。具體轉化過程為，記(ih,sh)是最優解中開設費用最大的設施-時刻對。重新定義設施費用

因此，實例I′的整數規劃為:

?(i,s)∈F,(j,t)∈D

算法1

步驟0初始時，設置

3 分析

接下來我們分別分析顧客的連接費用和懲罰費用。

根據三角不等式，有

綜合以上引理，可以得到算法的近似比。

定理4.4算法1是DFLPWPO的3-近似算法。

4 總結和展望

本文主要討論了魯棒動態設施選址問題，將帶懲罰和帶異常點兩種變形嵌入到動態設施選址問題中，利用原始-對偶的基本框架設計得到3-近似算法。在設施選址問題仍有待解決的問題, 其中無容量設施選址問題的突破近似比上界(1.488)和近似比下界(1.463)之間的壁壘是近似算法領域里最有趣的問題之一。 此外, 是否存在基于局部搜索框架的帶異常點的設施選址問題的近似算法也是有意義的問題。