俞武揚(yáng), 簡(jiǎn) 悅

(杭州電子科技大學(xué) 管理學(xué)院,浙江 杭州 310018)

0 引言

競(jìng)爭(zhēng)設(shè)施選址問題(CFLP)廣泛存在于我們的日常生活中，包括購(gòu)物中心，配送中心和倉(cāng)庫(kù)等設(shè)施的選址。該問題是為了在已經(jīng)存在或即將發(fā)生競(jìng)爭(zhēng)的市場(chǎng)中，選擇一個(gè)或多個(gè)設(shè)施的位置，使得目標(biāo)函數(shù)值最優(yōu)。競(jìng)爭(zhēng)選址的問題研究的求解目標(biāo)是通常最優(yōu)化類型目標(biāo)，其中利潤(rùn)型目標(biāo)，需求型目標(biāo)和費(fèi)用型目標(biāo)是選址問題中的求解重點(diǎn)。目前已存在許多解決該問題的模型，為了貼近復(fù)雜多變的市場(chǎng)情況，逐漸衍生出許多變體，包括設(shè)施之間的預(yù)算分配，帶有預(yù)見性的競(jìng)爭(zhēng)，加入閾值等[1]。

為貼近真實(shí)的顧客選擇行為，學(xué)者們將閾值的概念引入了競(jìng)爭(zhēng)設(shè)施選址問題模型中。Serra等[2]在模型中假設(shè)為了生存，設(shè)施存在一個(gè)必須達(dá)到的需求閾值，只有捕獲的需求量達(dá)到該閾值水平時(shí)該設(shè)施才能開放，否則不能在該位點(diǎn)開設(shè)新設(shè)施。Colomé等[3]不僅考慮了需求閾值，還將概率約束加入模型中，只有當(dāng)分配給設(shè)施的總需求高于閾值的概率達(dá)到預(yù)期時(shí)，設(shè)施才能開放。Fernández等[4]提出了部分概率選擇規(guī)則，該規(guī)則假設(shè)顧客只會(huì)光顧對(duì)其吸引力達(dá)到閾值的設(shè)施。Suárez等[5]不僅考慮了吸引力閾值，還將消費(fèi)者的偏好添加到模型中，考慮了不同顧客的不同吸引力閾值。

在傳統(tǒng)的競(jìng)爭(zhēng)設(shè)施選址模型中，通常認(rèn)為設(shè)施可以被所有需求點(diǎn)感知，但在實(shí)際生活中顧客并不會(huì)光顧所有設(shè)施。Drezner等[6]提出了競(jìng)爭(zhēng)設(shè)施選址問題的覆蓋模型，假設(shè)每個(gè)競(jìng)爭(zhēng)設(shè)施都具有一個(gè)由其吸引力水平?jīng)Q定的“覆蓋范圍”，并且位于服務(wù)范圍內(nèi)的顧客將被該設(shè)施吸引。與傳統(tǒng)模型不同，此模型允許丟失一些需求。當(dāng)需求點(diǎn)不在任何設(shè)施的服務(wù)范圍內(nèi)時(shí)，需求就會(huì)丟失。Drezner等[7]使用了基于服務(wù)半徑的模型，并將預(yù)算添加到模型中。Qi等[8]發(fā)現(xiàn)當(dāng)服務(wù)半徑達(dá)到一定值時(shí)，如果服務(wù)半徑繼續(xù)增加，解決方案將保持穩(wěn)定。

國(guó)內(nèi)隨著物流行業(yè)，零售行業(yè)的蓬勃發(fā)展，近些年也有學(xué)者開展了競(jìng)爭(zhēng)設(shè)施選址問題的相關(guān)研究。張曦等[9]針對(duì)企業(yè)擴(kuò)張和并購(gòu)問題進(jìn)行了深入研究，建立了利益最大以及吞并最小的雙目標(biāo)競(jìng)爭(zhēng)設(shè)施選址模型。吳國(guó)瑩[10]用logit效用函數(shù)來(lái)表示顧客選擇設(shè)施的概率，建立了以利潤(rùn)最大化為目標(biāo)的競(jìng)爭(zhēng)選址模型。肖劍[11]將費(fèi)用約束加入到目標(biāo)函數(shù)的約束條件中，并建立了DEA評(píng)價(jià)模型下的物流中心再選址模型。劉雄杰[12]探討了網(wǎng)格平面上門店選址問題的選址和設(shè)計(jì)的雙重決策問題。李蕾[13]考慮了物流中心的固定建設(shè)費(fèi)用和運(yùn)營(yíng)費(fèi)用，并建立了使新建物流中心總成本最小，所有顧客總費(fèi)用最少的雙層規(guī)劃模型。

可以發(fā)現(xiàn)基于服務(wù)半徑的模型比其它模型更貼近實(shí)際的顧客選擇行為，但是在現(xiàn)實(shí)生活中，顧客不僅會(huì)光顧便利半徑內(nèi)的設(shè)施，也同樣會(huì)光顧便利半徑以外，但有較高質(zhì)量的設(shè)施。因此，通過分析現(xiàn)實(shí)中的顧客光顧行為，本文針對(duì)這類顧客選擇行為模式，研究了考慮質(zhì)量閾值和顧客便利半徑的競(jìng)爭(zhēng)設(shè)施選址問題。

1 數(shù)學(xué)模型

1.1 模型描述

本文提出了一種新的顧客選擇規(guī)則用來(lái)描述以下顧客選擇行為：顧客不僅會(huì)光顧位于便利半徑內(nèi)的設(shè)施，同樣也會(huì)光顧在便利半徑以外，但高質(zhì)量的設(shè)施。該規(guī)則定義如下：對(duì)于位于顧客便利半徑以內(nèi)或質(zhì)量超過給定閾值的設(shè)施，顧客將根據(jù)其受到的吸引力的比例來(lái)選擇光顧這些設(shè)施。質(zhì)量閾值是否存在對(duì)顧客選擇行為的影響如圖1所示(左圖不考慮質(zhì)量閾值，右圖考慮質(zhì)量閾值)。

圖1 質(zhì)量閾值和便利半徑對(duì)顧客選擇行為的影響

在圖1中，矩形代表需求點(diǎn)，三角形代表超過質(zhì)量閾值的設(shè)施，菱形代表沒有超過質(zhì)量閾值的設(shè)施，位于顧客便利半徑以內(nèi)的區(qū)域用虛線包圍的圓圈表示。對(duì)于質(zhì)量不超過閾值的設(shè)施而言，設(shè)施的服務(wù)半徑與顧客的便利半徑一致，而質(zhì)量超過閾值的設(shè)施服務(wù)半徑可以認(rèn)為是無(wú)窮大。從圖1可知，如果僅考慮顧客的便利半徑，則顧客只會(huì)選擇光顧虛線箭頭所指的四個(gè)設(shè)施。若顧客根據(jù)便利半徑和質(zhì)量閾值來(lái)進(jìn)行選擇，同樣會(huì)選擇光顧虛線圓以外的三角形設(shè)施，即顧客會(huì)光顧實(shí)心箭頭所指的七個(gè)設(shè)施。

1.2 模型構(gòu)建

假設(shè)一家新公司計(jì)劃通過開設(shè)新設(shè)施進(jìn)入該市場(chǎng)，而該市場(chǎng)中已經(jīng)存在其他競(jìng)爭(zhēng)設(shè)施。本文基于靜態(tài)競(jìng)爭(zhēng)，假設(shè)當(dāng)前現(xiàn)有的公司未對(duì)新進(jìn)入者采取任何行動(dòng)。模型相關(guān)參數(shù)和變量設(shè)置如下：

i,I：需求點(diǎn)的索引和集合;j,J：現(xiàn)有設(shè)施的索引和集合;Wi：需求點(diǎn)i的需求量;diu：需求點(diǎn)i到設(shè)施u的距離;Qu：設(shè)施u的質(zhì)量;δ：質(zhì)量閾值;s：新設(shè)施的數(shù)量;β：顧客的便利光顧半徑;x,X：新設(shè)施的索引和集合 (X?IJ)。

引力模型被廣泛用于競(jìng)爭(zhēng)設(shè)施選址問題，需求點(diǎn)所感知到的設(shè)施吸引力取決于設(shè)施的質(zhì)量以及它們之間的距離。因此，對(duì)于需求點(diǎn)i，設(shè)施u(可以是現(xiàn)有設(shè)施或新設(shè)施)的吸引力由下式給出：

(1)

(2)

需求點(diǎn)i訪問現(xiàn)有設(shè)施j的概率如下:

(3)

需求點(diǎn)i到訪新設(shè)施x的概率為:

(4)

為了避免分母為零的情況，在分母中加入了一個(gè)參數(shù)ε,通常ε設(shè)置為一個(gè)非常小的數(shù)字。因此考慮便利半徑和質(zhì)量閾值的競(jìng)爭(zhēng)設(shè)施選址問題可以表述為:

(5)

2 算法設(shè)計(jì)

對(duì)于小規(guī)模實(shí)例，競(jìng)爭(zhēng)設(shè)施選址問題可以使用窮舉法或商用優(yōu)化軟件如Lingo，CPLEX等來(lái)解決競(jìng)爭(zhēng)設(shè)施選址問題。但是，在大規(guī)模實(shí)例中，這一問題的求解變得極為困難。由于大多數(shù)設(shè)施選址問題都是NP-hard問題，因此近年來(lái)大量研究致力于提出解決競(jìng)爭(zhēng)設(shè)施選址問題的有效算法。

Fernández等[14]提出了兩種基于排序的算法來(lái)解決靜態(tài)設(shè)施選址問題，并證明了算法的有效性?；谂判虻碾x散優(yōu)化算法是鄰域搜索算法的一種變體，只有在鄰域搜索過程得到的解所獲得的目標(biāo)值優(yōu)于當(dāng)前解的目標(biāo)值時(shí)才接受新解。為了更好地解決靜態(tài)競(jìng)爭(zhēng)設(shè)施選址問題，本文將排序算法和傳統(tǒng)遺傳算法相結(jié)合，得到了一種基于排序的遺傳算法(RGA)。算法的符號(hào)和描述如表1所示。

表1 算法符號(hào)和描述

基于排序的遺傳算法(RGA)流程:

生成初始解集合Y0, 令Y←Y0，rk=1,?k=1,2,…|L|,Z*=0,Y*←?

While未達(dá)到迭代次數(shù):

Ynew←?

For每?jī)蓚€(gè)相鄰的染色體X1,X2∈Y//交叉算子

Ifpc>rand(0-1之間的隨機(jī)數(shù))

End If

End for

For每個(gè)解決方案X∈Y//變異算子

If pm>rand

隨機(jī)選擇x∈X,c∈C,交換x和c產(chǎn)生新解X′，

令Ynew←Ynew∪X′，Y←Y∪Ynew

End If

End for

While終止規(guī)則未滿足://基于排名的鄰域交換

For每個(gè)解決方案X∈Y

選擇候選位點(diǎn)c∈C,交換x和c生成新的X′和C′，

IfM(X′)>Mmax

Mmax←M(X′),X←X′,C←C′，rk=c←rk=c+2,rk∈X′c←rk∈X′c+1

End If

End for

IfMmax>Z*,令Z*←Mmax,Y*←X,End If

End while

(4)選擇

從Y中選擇anum個(gè)解決方案并更新Y, 即|Y|=anum

End while

步驟1是交叉操作，假設(shè)有兩個(gè)候選解X1,X2∈Y，解的長(zhǎng)度(染色體的長(zhǎng)度)等于新設(shè)施數(shù)s。隨機(jī)選擇r1,r2∈[1,s]，使r1

圖2 候選解的交叉過程

步驟(2)和(3)都是基于鄰域交換，它們之間的區(qū)別在于步驟(2)的突變具有一定的概率，并且可以接受比當(dāng)前解更差的解決方案。且步驟(2)的鄰域交換過程僅執(zhí)行一次，并且每次生成的新解都會(huì)添加到現(xiàn)有解決方案集合Y中。步驟(3)是對(duì)Y中的所有可行解執(zhí)行多次鄰域交換。只有在交換的解所獲得的目標(biāo)值更優(yōu)才接受新解，并且Y的大小不會(huì)因產(chǎn)生新的解決方案而增加。

3 計(jì)算結(jié)果與分析

3.1 RGA算法的性能

本節(jié)通過測(cè)試隨機(jī)正態(tài)分布，泊松分布以及位于二維平面中的均勻分布這三種不同分布的實(shí)例來(lái)檢測(cè)算法的有效性。所有測(cè)試實(shí)例都是隨機(jī)生成，假設(shè)市場(chǎng)上有|J|個(gè)已有設(shè)施，一家新公司即將進(jìn)入市場(chǎng)并開放s個(gè)新設(shè)施，除現(xiàn)有設(shè)施外的所有需求點(diǎn)所在位置都可以視為新設(shè)施的潛在位置。

首先針對(duì)小規(guī)模算例評(píng)估算法RGA的有效性，將RGA算法結(jié)果與窮舉法找到的最優(yōu)結(jié)果進(jìn)行比較。RGA算法的參數(shù)設(shè)置如下：染色體種群anum的數(shù)量設(shè)置為10，每代基于排名的搜索的迭代次數(shù)為100，pc=0.8,pm=0.2，并運(yùn)行10代，即進(jìn)行了10,000次功能評(píng)估。為了提高結(jié)果的準(zhǔn)確性，每個(gè)算例進(jìn)行了10次測(cè)試，MRGA表示RGA算法的平均結(jié)果，窮舉法最優(yōu)解用Mopt表示如表2所示。

表2 RGA算法的最優(yōu)性測(cè)試(β=20,δ=60,|J|=s=5)

從表2可以明顯看出，任意一種分布情況下RGA算法都可以獲得最佳解決方案。并且RGA算法可以在短時(shí)間內(nèi)(小于6秒)解決小規(guī)模實(shí)例，而當(dāng)需求點(diǎn)數(shù)為60時(shí)，窮舉法用時(shí)已達(dá)到100秒以上。

表3 GA,RDOA,RGA算法在大型實(shí)例上的結(jié)果對(duì)比

觀察表3可得,GAP1的值不超過0.6%，即RGA算法在大型實(shí)例上也能獲得較為穩(wěn)定的結(jié)果。進(jìn)一步觀察發(fā)現(xiàn)，RGA算法的性能在這三種算法中表現(xiàn)最優(yōu)，RDOA也可以得到令人滿意的解決方案，但它的求解結(jié)果比RGA算法稍差，而傳統(tǒng)GA算法效果最不理想。

3.2 實(shí)例分析

最后，本文使用了浙江省杭州市江干區(qū)九堡50個(gè)小區(qū)的真實(shí)地理數(shù)據(jù)和坐標(biāo)數(shù)據(jù)，以2020年8月小區(qū)樓盤價(jià)格和小區(qū)總戶數(shù)給出了一個(gè)仿真實(shí)例。在該實(shí)例中每個(gè)小區(qū)作為一個(gè)需求點(diǎn)，目標(biāo)是在這些小區(qū)中建立給定數(shù)量的設(shè)施，使得這些設(shè)施獲取的市場(chǎng)份額最大，其中需求量與小區(qū)總戶數(shù)成正比，設(shè)施的質(zhì)量則與小區(qū)的樓盤價(jià)格成正比。數(shù)據(jù)集的部分參數(shù)在表4中展示。

表4 數(shù)據(jù)集中的部分參數(shù)

在該實(shí)例中，顧客遵循具有便利半徑和質(zhì)量閾值的比例規(guī)則，已有設(shè)施位于人口最稠密的位置。本文考慮了當(dāng)β=800，δ=35000時(shí)設(shè)施數(shù)量對(duì)市場(chǎng)份額的影響。注意，只要確定參數(shù)δ，就可以確定預(yù)設(shè)質(zhì)量超過閾值的設(shè)施數(shù)量(由參數(shù)U表示)和質(zhì)量超過閾值的已有設(shè)施數(shù)量(由參數(shù)E表示)。確定新設(shè)施位置后，參數(shù)N表示超出質(zhì)量閾值的新設(shè)施數(shù)量。表5顯示了每種實(shí)例的最佳解決方案。

表5 設(shè)置不同|J|和s時(shí)的最優(yōu)解(β=800,δ=35000,U=8)

如表5所示，在僅改變新設(shè)施數(shù)量的情況下，市場(chǎng)份額隨著設(shè)施數(shù)量的增加而增加。新設(shè)施數(shù)量相同時(shí)，市場(chǎng)份額會(huì)隨著已有設(shè)施數(shù)量的增加而減小。進(jìn)一步觀察可知，新設(shè)施總會(huì)選擇超過質(zhì)量閾值的設(shè)施從而能夠吸引更多的顧客。

為了研究質(zhì)量閾值對(duì)市場(chǎng)份額的影響，令δ以步長(zhǎng)為1000從35000增長(zhǎng)到40000,分別計(jì)算新進(jìn)企業(yè)在給定質(zhì)量閾值下所獲得的市場(chǎng)份額，并與沒有質(zhì)量閾值(δ=∞)的實(shí)例進(jìn)行比較。假定現(xiàn)有設(shè)施和新設(shè)施的數(shù)量相同(|J|=s=3),距離限制β= 800,對(duì)應(yīng)于不同閾值的最佳解決方案如表6所示。

表6 質(zhì)量閾值δ對(duì)市場(chǎng)份額的影響(|J|=3,s=3, β=800)

從表6中可以看出，若模型中添加了質(zhì)量閾值，只要存在質(zhì)量超過質(zhì)量閾值的設(shè)施，所有顧客的需求就可以得到滿足，但僅考慮距離限制時(shí)，情況并非如此。值得一提的是，質(zhì)量閾值與市場(chǎng)份額沒有直接關(guān)系，而是通過影響質(zhì)量高于閾值的設(shè)施數(shù)量而間接影響市場(chǎng)份額，參數(shù)U通常隨著質(zhì)量閾值的降低而增加。當(dāng)δ=38000和39000時(shí)，即使更改參數(shù)δ，如果U的值不變，目標(biāo)函數(shù)的值也不會(huì)改變。當(dāng)δ=36000和37000時(shí)，新設(shè)施放置位點(diǎn)相同，但市場(chǎng)份額不同，表明即使設(shè)施放置地點(diǎn)相同，當(dāng)參數(shù)U改變時(shí)，目標(biāo)函數(shù)的值也會(huì)改變。圖3展示了不同質(zhì)量閾值時(shí)的最優(yōu)解。其中，三角形和正方形分別表示現(xiàn)有設(shè)施和新進(jìn)設(shè)施，未超過質(zhì)量閾值的設(shè)施所能吸引的需求位點(diǎn)在圖中用直線連接，而超過質(zhì)量閾值的設(shè)施的沒有服務(wù)半徑的約束，可以被所有需求點(diǎn)感知。

圖3 不同質(zhì)量閾值(|J|=s=3, β=800,左圖δ=35000,右圖δ=40000)

觀察圖3發(fā)現(xiàn)，當(dāng)δ=35000時(shí)，新公司選擇在其中兩個(gè)位置放置新設(shè)施，另外一個(gè)設(shè)施放置在已有設(shè)施附近，以搶占已有設(shè)施的市場(chǎng)份額。同樣，當(dāng)δ=40000時(shí)，新公司選擇在其中一個(gè)超過質(zhì)量閾值的位點(diǎn)放置新設(shè)施，而其余兩個(gè)設(shè)施放置在鄰近已有設(shè)施的區(qū)域。這意味著只要有可放置的高質(zhì)量位點(diǎn)，新的設(shè)施必會(huì)放置在超過質(zhì)量閾值的位點(diǎn)上，以吸引全部的需求點(diǎn)，而那些未超過質(zhì)量閾值的設(shè)施通常會(huì)選擇已有設(shè)施附近的位點(diǎn)以搶占更多的市場(chǎng)份額。

下面研究在設(shè)置不同參數(shù)δ時(shí)，新公司的市場(chǎng)份額如何隨著不同的便利半徑而變化?？紤]了以下三種情況：δ=35000(U=8,E=1)，δ=40000(U=2,E=0)和δ=∞，市場(chǎng)份額隨參數(shù)β的變化如表7所示。

表7 服務(wù)半徑β對(duì)市場(chǎng)份額的影響(|J|=s=3)

分析模型可知，參數(shù)δ影響超過質(zhì)量閾值的設(shè)施數(shù)量，參數(shù)β影響不超過質(zhì)量閾值設(shè)施的服務(wù)半徑。觀察表7發(fā)現(xiàn)，當(dāng)δ=35000時(shí)，隨著β的增加，新設(shè)施獲取的市場(chǎng)份額先減小后增大，這是因?yàn)殡S著覆蓋半徑的增加，現(xiàn)有的未超過質(zhì)量閾值的設(shè)施吸引了更多的客戶，這導(dǎo)致新進(jìn)入公司的市場(chǎng)份額下降，進(jìn)一步增加覆蓋半徑后，新進(jìn)公司可以獲得更多需求，其獲得的市場(chǎng)份額開始上升。當(dāng)δ=40000時(shí)，由于不存在超過質(zhì)量閾值的已有設(shè)施，市場(chǎng)份額隨覆蓋半徑的變化規(guī)律與δ=35000時(shí)相同，但其所獲得的市場(chǎng)份額明顯高于δ=35000時(shí)的情形。而當(dāng)δ=∞，即不存在質(zhì)量閾值時(shí)，新設(shè)施獲得的市場(chǎng)份額會(huì)隨著覆蓋半徑的增加明顯增大。這是由于不存在質(zhì)量閾值時(shí)，所有設(shè)施的服務(wù)范圍都由服務(wù)半徑β決定，增加β能夠增大設(shè)施吸引的需求量，從而使得設(shè)施獲得的市場(chǎng)份額增大。

4 結(jié)論

本文提出了一個(gè)考慮質(zhì)量閾值和顧客便利半徑的顧客選擇行為，這是對(duì)基于便利半徑選擇行為的擴(kuò)展。針對(duì)該選擇行為下的競(jìng)爭(zhēng)設(shè)施選址問題，提出了一種改進(jìn)RGA算法。通過不同規(guī)模的數(shù)值實(shí)驗(yàn)研究了RDOA算法的有效性，發(fā)現(xiàn)RGA算法可以獲得穩(wěn)定的結(jié)果，并且優(yōu)于RDOA和GA算法。通過一個(gè)仿真實(shí)例研究，發(fā)現(xiàn)質(zhì)量閾值對(duì)市場(chǎng)份額至關(guān)重要，只要存在超過質(zhì)量閾值的設(shè)施，就可以滿足所有需求點(diǎn)的需求。值得注意的是，質(zhì)量閾值本身并不與市場(chǎng)份額直接相關(guān)，而是通過控制超過閾值的設(shè)施數(shù)量來(lái)影響市場(chǎng)份額。