考慮顧客便利半徑和質量閾值的競爭設施選址問題

俞武揚, 簡 悅

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

0 引言

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

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

在傳統的競爭設施選址模型中，通常認為設施可以被所有需求點感知，但在實際生活中顧客并不會光顧所有設施。Drezner等[6]提出了競爭設施選址問題的覆蓋模型，假設每個競爭設施都具有一個由其吸引力水平決定的“覆蓋范圍”，并且位于服務范圍內的顧客將被該設施吸引。與傳統模型不同，此模型允許丟失一些需求。當需求點不在任何設施的服務范圍內時，需求就會丟失。Drezner等[7]使用了基于服務半徑的模型，并將預算添加到模型中。Qi等[8]發現當服務半徑達到一定值時，如果服務半徑繼續增加，解決方案將保持穩定。

國內隨著物流行業，零售行業的蓬勃發展，近些年也有學者開展了競爭設施選址問題的相關研究。張曦等[9]針對企業擴張和并購問題進行了深入研究，建立了利益最大以及吞并最小的雙目標競爭設施選址模型。吳國瑩[10]用logit效用函數來表示顧客選擇設施的概率，建立了以利潤最大化為目標的競爭選址模型。肖劍[11]將費用約束加入到目標函數的約束條件中，并建立了DEA評價模型下的物流中心再選址模型。劉雄杰[12]探討了網格平面上門店選址問題的選址和設計的雙重決策問題。李蕾[13]考慮了物流中心的固定建設費用和運營費用，并建立了使新建物流中心總成本最小，所有顧客總費用最少的雙層規劃模型。

可以發現基于服務半徑的模型比其它模型更貼近實際的顧客選擇行為，但是在現實生活中，顧客不僅會光顧便利半徑內的設施，也同樣會光顧便利半徑以外，但有較高質量的設施。因此，通過分析現實中的顧客光顧行為，本文針對這類顧客選擇行為模式，研究了考慮質量閾值和顧客便利半徑的競爭設施選址問題。

1 數學模型

1.1 模型描述

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

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

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

1.2 模型構建

假設一家新公司計劃通過開設新設施進入該市場，而該市場中已經存在其他競爭設施。本文基于靜態競爭，假設當前現有的公司未對新進入者采取任何行動。模型相關參數和變量設置如下：

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

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

(1)

(2)

需求點i訪問現有設施j的概率如下:

(3)

需求點i到訪新設施x的概率為:

(4)

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

(5)

2 算法設計

對于小規模實例，競爭設施選址問題可以使用窮舉法或商用優化軟件如Lingo，CPLEX等來解決競爭設施選址問題。但是，在大規模實例中，這一問題的求解變得極為困難。由于大多數設施選址問題都是NP-hard問題，因此近年來大量研究致力于提出解決競爭設施選址問題的有效算法。

Fernández等[14]提出了兩種基于排序的算法來解決靜態設施選址問題，并證明了算法的有效性。基于排序的離散優化算法是鄰域搜索算法的一種變體，只有在鄰域搜索過程得到的解所獲得的目標值優于當前解的目標值時才接受新解。為了更好地解決靜態競爭設施選址問題，本文將排序算法和傳統遺傳算法相結合，得到了一種基于排序的遺傳算法(RGA)。算法的符號和描述如表1所示。

表1 算法符號和描述

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

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

While未達到迭代次數:

Ynew←?

For每兩個相鄰的染色體X1,X2∈Y//交叉算子

Ifpc>rand(0-1之間的隨機數)

End If

End for

For每個解決方案X∈Y//變異算子

If pm>rand

隨機選擇x∈X,c∈C,交換x和c產生新解X′，

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

End If

End for

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

For每個解決方案X∈Y

選擇候選位點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個解決方案并更新Y, 即|Y|=anum

End while

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

圖2 候選解的交叉過程

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

3 計算結果與分析

3.1 RGA算法的性能

本節通過測試隨機正態分布，泊松分布以及位于二維平面中的均勻分布這三種不同分布的實例來檢測算法的有效性。所有測試實例都是隨機生成，假設市場上有|J|個已有設施，一家新公司即將進入市場并開放s個新設施，除現有設施外的所有需求點所在位置都可以視為新設施的潛在位置。

首先針對小規模算例評估算法RGA的有效性，將RGA算法結果與窮舉法找到的最優結果進行比較。RGA算法的參數設置如下：染色體種群anum的數量設置為10，每代基于排名的搜索的迭代次數為100，pc=0.8,pm=0.2，并運行10代，即進行了10,000次功能評估。為了提高結果的準確性，每個算例進行了10次測試，MRGA表示RGA算法的平均結果，窮舉法最優解用Mopt表示如表2所示。

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

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

表3 GA,RDOA,RGA算法在大型實例上的結果對比

觀察表3可得,GAP1的值不超過0.6%，即RGA算法在大型實例上也能獲得較為穩定的結果。進一步觀察發現，RGA算法的性能在這三種算法中表現最優，RDOA也可以得到令人滿意的解決方案，但它的求解結果比RGA算法稍差，而傳統GA算法效果最不理想。

3.2 實例分析

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

表4 數據集中的部分參數

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

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

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

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

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

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

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

觀察圖3發現，當δ=35000時，新公司選擇在其中兩個位置放置新設施，另外一個設施放置在已有設施附近，以搶占已有設施的市場份額。同樣，當δ=40000時，新公司選擇在其中一個超過質量閾值的位點放置新設施，而其余兩個設施放置在鄰近已有設施的區域。這意味著只要有可放置的高質量位點，新的設施必會放置在超過質量閾值的位點上，以吸引全部的需求點，而那些未超過質量閾值的設施通常會選擇已有設施附近的位點以搶占更多的市場份額。

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

表7 服務半徑β對市場份額的影響(|J|=s=3)

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

4 結論

本文提出了一個考慮質量閾值和顧客便利半徑的顧客選擇行為，這是對基于便利半徑選擇行為的擴展。針對該選擇行為下的競爭設施選址問題，提出了一種改進RGA算法。通過不同規模的數值實驗研究了RDOA算法的有效性，發現RGA算法可以獲得穩定的結果，并且優于RDOA和GA算法。通過一個仿真實例研究，發現質量閾值對市場份額至關重要，只要存在超過質量閾值的設施，就可以滿足所有需求點的需求。值得注意的是，質量閾值本身并不與市場份額直接相關，而是通過控制超過閾值的設施數量來影響市場份額。