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

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

0 引言

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

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

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

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

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

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

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

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

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

1 問題描述與符號

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

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

(1)

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

2 算法

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

因此，實例I′的整數(shù)規(guī)劃為:

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

算法1

步驟0初始時，設(shè)置

3 分析

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

根據(jù)三角不等式，有

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

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

4 總結(jié)和展望

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