基于容量限制和預(yù)算限制的網(wǎng)絡(luò)截流設(shè)施選址和設(shè)計(jì)模型

摘要：截流問(wèn)題研究的對(duì)象為路徑上行走的消費(fèi)者，其研究的問(wèn)題為如何選址使設(shè)施截得網(wǎng)絡(luò)上最大的流量。大部分截流的文獻(xiàn)假設(shè)設(shè)施容量無(wú)限制，只要在消費(fèi)者行走路徑上有一個(gè)設(shè)施即可截得路徑上的全部流量。本文的截流問(wèn)題，考慮了設(shè)施的容量限制，并可以通過(guò)一定的技術(shù)改進(jìn)容量，也考慮了路徑上流量有一定的截取比例，建立了具有容量和預(yù)算限制的截流設(shè)施選址和設(shè)計(jì)模型。

關(guān)鍵詞：截流 設(shè)施選址 容量 設(shè)計(jì)

0 引言

選址問(wèn)題為策略管理決策問(wèn)題，選址的好壞直接影響著企業(yè)的利潤(rùn)和消費(fèi)者滿意度等一系列重要問(wèn)題。從Hodgson（1981）[1]一篇文章起，在過(guò)去的近三十年時(shí)間里，大量設(shè)施選址的文獻(xiàn)關(guān)注的不是產(chǎn)生流或吸引流而是截得的流量，在提前計(jì)劃路徑上的發(fā)點(diǎn)到終點(diǎn)的流量，被路徑上的設(shè)施自愿或強(qiáng)加的截得。換言之，流量的目的不是為了獲得服務(wù)，但如果在他們提前計(jì)劃的路徑上存在一個(gè)設(shè)施，則他們會(huì)自愿的或者不可避免的中斷下來(lái)獲取服務(wù)，然后繼續(xù)前行到達(dá)目的地。因此此類問(wèn)題稱作截流的設(shè)施選址問(wèn)題。Gendreau（2000）[2]描述預(yù)防和懲罰截流問(wèn)題的公式和特征，給出了監(jiān)測(cè)站選址模型，目標(biāo)是總的危險(xiǎn)減少最大化。Uno（2008）[3]本文考慮一個(gè)新的選址問(wèn)題，防御性選址問(wèn)題（DLP）。在DLP中，決策者選址設(shè)施為了阻止他的對(duì)手到達(dá)一個(gè)重要的位置稱為中心；例如：“一個(gè)國(guó)家的一個(gè)政府部門選擇自我防御設(shè)施，為了阻止入侵者到達(dá)國(guó)家的首都”。本文的決策者和對(duì)手稱為防御者和入侵者，假設(shè)決策者考慮防御設(shè)施的選址，背景是網(wǎng)絡(luò)的。DLP被看為0-1規(guī)劃問(wèn)題，可以找到斯坦?fàn)柌窠狻＿M(jìn)一步把DLP拓展為一個(gè)多目標(biāo)DLP，如：防御者需要同時(shí)保護(hù)兩個(gè)或者多個(gè)中心。Boccia（2009）[4]總結(jié)了FIFLP的五個(gè)基本重要知識(shí)點(diǎn)：①O-D（origin-destination）路徑和相關(guān)流的知識(shí)；②連線失敗或者偏離原計(jì)劃路徑；③單一或多形式截流；④是否運(yùn)用抽樣操作的流量監(jiān)控；⑤在網(wǎng)絡(luò)結(jié)點(diǎn)還是弧上選址。Jong-Geun Kim（2012，2013）[5][6]研究了燃料補(bǔ)充設(shè)施的截流選址問(wèn)題，與一般截流問(wèn)題不同的是，文中需要補(bǔ)充燃料的車輛是否被設(shè)施服務(wù)，取決于網(wǎng)絡(luò)上的車輛，是否在行走的路徑上的站點(diǎn)或附近的站點(diǎn)停車補(bǔ)充燃料。

現(xiàn)有的截流選址問(wèn)題，基本假設(shè)設(shè)施容量是無(wú)限制的，只要在行走路徑上有設(shè)施開放，則流量全部截得。通過(guò)對(duì)實(shí)際問(wèn)題的研究發(fā)現(xiàn)，設(shè)施不可能無(wú)限制的提供服務(wù)，設(shè)施對(duì)不同路徑上的流量截得存在比例問(wèn)題。本文的截流選址模型考慮了上述問(wèn)題。

2 模型與算法

2.1 問(wèn)題描述

店面布局、服務(wù)窗口數(shù)量、工作人員的操作熟練程度等都會(huì)影響設(shè)施的服務(wù)容量，服務(wù)容量與基礎(chǔ)設(shè)施有關(guān)，同時(shí)也可以通過(guò)布局、規(guī)劃設(shè)計(jì)或培訓(xùn)等技術(shù)手段改進(jìn)和擴(kuò)充容量。不同的方法對(duì)設(shè)施容量改進(jìn)的效果不同，同時(shí)耗費(fèi)的成本也不同。本文研究的截流問(wèn)題，考慮了在網(wǎng)絡(luò)上開放設(shè)施時(shí)，有基礎(chǔ)的可接納服務(wù)的容量，通過(guò)一定的技術(shù)手段可以擴(kuò)充設(shè)施的服務(wù)容量，這種設(shè)施容量的改進(jìn)有上限，無(wú)論采用多先進(jìn)的技術(shù)和方法，不可能使設(shè)施容量無(wú)限制增加，因此本文設(shè)置了改進(jìn)的上限，采用不同的方法擴(kuò)充容量，其消耗的成本不同。本文將成本分為兩部分，一部分為開放設(shè)施的固定成本，一部分為擴(kuò)充設(shè)施容量所消耗的變動(dòng)成本。建立了基于容量限制和預(yù)算限制的截流選址和設(shè)施服務(wù)容量設(shè)計(jì)模型。

2.2 模型建立

符號(hào)說(shuō)明：

yik：采用第k種技術(shù)改進(jìn)i點(diǎn)的設(shè)施帶來(lái)的容量影響

fp：路徑p上的流量

αi：i點(diǎn)的建立設(shè)施的基礎(chǔ)容量

zi=1 i點(diǎn)開放一個(gè)設(shè)施0 其他

xip：i點(diǎn)的設(shè)施對(duì)路徑p上的需求截取的比例

Ci=ziαi（1+yik）

v（yik）：非減的可變成本，

wi：固定成本。

B：建立設(shè)施的成本限制

maxfpxip （1）

ST.

fpxip≤Ci （2）

v（yik）+wizi≤B （3）

yik≤ziy （4）

xip≤1 （5）

xip≤zi （6）

zi∈{0，1} （7）

xip∈{0，1} （8）

yik∈[0，y]（9）

目標(biāo)函數(shù)（1）為截得流量最大化，約束條件（2）為i點(diǎn)設(shè)施容量限制約束，約束條件（3）為預(yù)算限制約束，約束條件（4）為采用第k種技術(shù)改進(jìn)i點(diǎn)的設(shè)施帶來(lái)的容量擴(kuò)充不會(huì)超過(guò)技術(shù)上限，約束條件（5）保證路徑p上的每點(diǎn)設(shè)施截得的總需求比例不會(huì)超過(guò)1，約束條件（6）保證只有在i開放設(shè)施，才能截得路徑上的流量。約束條件（7）、（8）、（9）為變量取值范圍約束。

2.3 模型求解

所建立的模型為混合整數(shù)規(guī)劃模型，可以通過(guò)分支定界法求解模型。Lingo軟件是一款非常好的求解模型軟件，本文模型，如果給定參數(shù)的具體數(shù)值，可以通過(guò)lingo軟件，運(yùn)用分支定界法求出最優(yōu)解。

3 結(jié)語(yǔ)

本文研究的截流問(wèn)題，即考慮了設(shè)施的容量，也考慮了容量擴(kuò)張問(wèn)題，在容量擴(kuò)張中有技術(shù)瓶頸和預(yù)算限制等問(wèn)題，在這些因素的前提下，建立了具有容量和預(yù)算限制的截流選址模型。所建立的模型為基本截流問(wèn)題的擴(kuò)展模型，由于基本截流模型為NP-hard問(wèn)題，故所建立的模型為NP-hard問(wèn)題，對(duì)于小規(guī)模問(wèn)題，可以運(yùn)用分支定界求的問(wèn)題的最優(yōu)解，但如果問(wèn)題規(guī)模較大，則求最優(yōu)解不太現(xiàn)實(shí)，需設(shè)置啟發(fā)式算法求解模型的滿意解，今后將研究求解模型的啟發(fā)式算法。

參考文獻(xiàn)：

[1]Hodgson M J.The location of public facilities intermediate to the journey to work[J].European Journal of Operational Research.1981，6（2）：199-204.

[2]Gendreau M，Laporte G，Parent I.Heuristics for the location of inspection station on a network. Naval Research Logistics，2000，47（4）：287-303.

[3]Uno T，Katagiri H.Single- and multi-objective defensive location problems on a network. European Journal of Operational Research，2008，188（1）：76-84.

[4]Boccia M，Sforza A，Sterle C.Flow Intercepting Facility Location： Problems， Models and Heuristics. Journal of Mathematical Modelling and Algorithms，2009，8：35-79.

[5]Jong-Geun Kim，Michael Kuby.The deviation-flow refueling location model for optimizing a network of refueling stations[J].international journal of hydrogen energy，2012，37：5406-5420.

[6]Jong-Geun Kim，MichaelKuby.A network transformation heuristic approach for the deviation flow refueling location model[J].Computers Operations Research，2013，40：1122-

1131.

基金項(xiàng)目：國(guó)家自然科學(xué)基金（70871044，70971045）。

作者簡(jiǎn)介：

張曦（1980-）女，河北南宮人，講師，博士，主要研究方向?yàn)檫x址和網(wǎng)絡(luò)優(yōu)化。