申瑞玲, 霍佳震, 王 茜

?

競爭環(huán)境下截流問題的選址-價格模型

申瑞玲1, 霍佳震2, 王 茜3

(1.河南財經(jīng)政法大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河南 鄭州 450000； 2.同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海 200092; 3.河南工業(yè)大學(xué)，河南 鄭州 450000)

研究了競爭環(huán)境下考慮產(chǎn)品定價的截流設(shè)施選址問題。連鎖企業(yè)在市場上新建設(shè)施時，市場上已有屬于競爭對手的設(shè)施存在，在連鎖企業(yè)新建設(shè)施位置確定之后，兩個企業(yè)關(guān)于產(chǎn)品定價進(jìn)行雙寡頭完全信息非合作博弈。定義了效用函數(shù)，引入Huff模型，以企業(yè)利潤最大為目標(biāo)，建立雙層規(guī)劃模型，證明了模型納什均衡價格的存在性，并構(gòu)造啟發(fā)式算法對模型進(jìn)行求解。算例分析表明，該算法求解結(jié)果較為理想，可用于大中型網(wǎng)絡(luò)的規(guī)劃選址問題。

運籌學(xué)；截流設(shè)施選址；選址-價格；納什均衡；模擬退火算法

0 引言

連鎖企業(yè)在進(jìn)入某個市場時，如果市場上沒有其他企業(yè)的同類設(shè)施存在，則企業(yè)在市場上處于壟斷地位，如果市場上已有其他企業(yè)的同類設(shè)施存在，則企業(yè)在市場上展開競爭[1]。在競爭的過程中，商業(yè)企業(yè)追求的是利潤的最大化。為了獲取最大利潤，企業(yè)在進(jìn)入市場時，除了要考慮選址的地點之外，還要考慮其他一些因素，如產(chǎn)品的定價，競爭對手的反應(yīng)等

競爭選址模型最早由Hoteling[2]提出，假設(shè)消費者均勻分布在一條直線上，對兩個冰淇淋商販的選址問題進(jìn)行了研究；Hoover[3]首先對選址-價格(location-price)問題進(jìn)行了研究。此后學(xué)者們在對選址-價格模型的研究中，將產(chǎn)品定價分為兩種情況，一種是出廠價格(mill price)，企業(yè)對產(chǎn)品統(tǒng)一定價，消費者與企業(yè)設(shè)施之間的運輸成本由消費者承擔(dān)，另一種是交貨價格(delivered price)，企業(yè)與消費者之間的運輸成本由企業(yè)承擔(dān)，企業(yè)對各個區(qū)域消費者分別定價[4]。Serra和Revelle[5]假設(shè)競爭雙方對產(chǎn)品定價為出廠價格，顧客到使其支付總成本最低的設(shè)施接受服務(wù)，構(gòu)造PMAXCAP模型，研究了先進(jìn)入市場的企業(yè)會對后進(jìn)入市場的企業(yè)的決策做出反應(yīng)的情況下，后進(jìn)入市場的企業(yè)如何選址和確定價格，以使其利潤最大的問題；Perez等[6]討論了企業(yè)產(chǎn)品定價分別為出廠價格和交貨價格的情況下，納什均衡解存在的條件；Aboolian等[7]研究了先進(jìn)入市場的企業(yè)不會對其產(chǎn)品定價進(jìn)行調(diào)整，但是消費者需求存在彈性的情況下，構(gòu)造CFLUPM模型對后進(jìn)入市場的企業(yè)的選址和定價策略進(jìn)行了研究，并討論了需求彈性系數(shù)對企業(yè)決策的影響；Garcia等[4]研究了產(chǎn)品定價為交貨價格，后進(jìn)入市場的企業(yè)的候選選址點是網(wǎng)絡(luò)中的任意點和只能是網(wǎng)絡(luò)中的節(jié)點兩種情況下，后進(jìn)入市場企業(yè)的選址-定價問題，并證明了在一定情況下，先進(jìn)入市場的企業(yè)的利潤隨著后進(jìn)入市場上企業(yè)新建設(shè)設(shè)施數(shù)的增加而增加；Pelegrin等[8]研究了定價為交貨價格，且存在市場擴(kuò)張的情況下，連鎖企業(yè)如何選擇擴(kuò)建設(shè)施點并如何對產(chǎn)品定價的問題。

傳統(tǒng)的設(shè)施選址假設(shè)設(shè)施服務(wù)對象位于網(wǎng)絡(luò)中各個節(jié)點，但是對有些設(shè)施，如加油站，加氣站，ATM，便利商店等，其服務(wù)對象主要是過往的顧客流，截流設(shè)施選址問題主要對此類問題進(jìn)行研究。Hodgson[9]和Berman[10]各自提出了截流設(shè)施模型，對截流選址模型進(jìn)行了開拓性的研究；Berman和Krass[11]將空間交互作用模型引入到截流選址模型中，提出了FISIM模型，討論了消費者偏離原路徑行駛情況下的競爭環(huán)境下截流選址模型，為截流設(shè)施選址問題的研究提供了新的思路；在此基礎(chǔ)上，Wu和Lin[12]研究了競爭環(huán)境下的截流設(shè)施選址問題；楊珺等[13]研究了帶服務(wù)半徑的截流設(shè)施選址問題；胡丹丹等[14]研究了考慮顧客等待時間的截流設(shè)施選址問題；Zeng 等[15,16]研究了考慮消費者購物區(qū)位偏好的截流設(shè)施選址問題；Tanaka和Furuta[17]假設(shè)不同大小的設(shè)施吸引力不同，研究了企業(yè)同時確定選址地點和設(shè)施大小的問題。

本文對競爭環(huán)境下考慮產(chǎn)品定價的設(shè)施選址問題進(jìn)行研究。問題描述為：連鎖企業(yè)(企業(yè)A)在進(jìn)入某個市場時，市場上已有屬于競爭對手(企業(yè)B)的設(shè)施存在，在企業(yè)A確定其選址地點和產(chǎn)品定價之后，為使本企業(yè)利潤最大化，企業(yè)B對其產(chǎn)品定價進(jìn)行調(diào)整。假設(shè)兩個企業(yè)銷售完全相同的產(chǎn)品，同一企業(yè)在其各個設(shè)施點處定價相同，產(chǎn)品定價為出廠價格，消費者到設(shè)施點處購買產(chǎn)品的交通費用由消費者承擔(dān)。

1 模型建立

我們用G(N,A)表示網(wǎng)絡(luò)，其中N為網(wǎng)絡(luò)中的節(jié)點集，A為網(wǎng)絡(luò)中的邊集；P為網(wǎng)絡(luò)中非零流量的路徑集合,p∈P;Np為路徑p上的節(jié)點集合；fp為路徑p上顧客流量；E為網(wǎng)絡(luò)中企業(yè)B已有的設(shè)施點集合,k∈E;M為企業(yè)A新建設(shè)施點集合,j∈M;m為企業(yè)A擬新建設(shè)施數(shù)目；gj為企業(yè)A在j處新建設(shè)施的建設(shè)成本,j∈M;cA,cB分別表示企業(yè)A，企業(yè)B產(chǎn)品的成本價；pA,pB分別表示企業(yè)A，企業(yè)B對產(chǎn)品的定價。

在截流選址模型中，我們用dpj表示路徑p上的顧客到節(jié)點j處接受服務(wù)時偏離原路徑的距離。本文中我們定義偏離距離dpj的計算公式為：假設(shè)s,e分別是路徑p的起點和終點，若p上的顧客到j(luò)點接受服務(wù)，則偏離距離dpj=dpj+dje-dse。

根據(jù)以上分析，建立模型如下：

(1)

(2)

pA≥cA

(3)

upj=max(U-(pj+αdpj)αp,0)

(4)

(5)

yj∈{0,1}

(6)

maxπB(pA,pB,Y)=(pB-cB)∑p∈P∑j∈Efp×wpj

(7)pB≥cB

(8)

其中目標(biāo)函數(shù)(1)式表示企業(yè)A的總利潤，其中第一項表示企業(yè)A的總收入，第二項表示企業(yè)A的選址成本，約束條件(2)式表示企業(yè)A新建設(shè)施個數(shù)為m個，(3)表示企業(yè)A的產(chǎn)品定價pA不低于產(chǎn)品進(jìn)價cA，(4),(5)在前面已經(jīng)解釋，(6)式是0-1約束，下層目標(biāo)函數(shù)(7)式表示企業(yè)B的總利潤最大，(8)表示企業(yè)B的產(chǎn)品定價pB不低于產(chǎn)品進(jìn)價cB

2 模型解的存在性

整個決策過程可以分為兩個階段：第一階段，確定企業(yè)A選址地點。在此階段，企業(yè)A需考慮下一階段的價格博弈。第二階段，確定產(chǎn)品定價。對企業(yè)A新建設(shè)施點集合，在考慮對方策略的情況下，基于本企業(yè)利潤最大化的原則，兩個企業(yè)確定各自產(chǎn)品定價，這一決策過程可以看作是一個完全信息非合作博弈的過程，博弈的結(jié)果是雙方產(chǎn)品定價為目標(biāo)函數(shù)的納什均衡解。接下來我們將證明模型納什均衡解的存在性。

納什均衡策略是每一個參與者針對其他參與者所選策略的最優(yōu)反應(yīng)策略[18]，為了證明本模型中純策略納什均衡解的存在性，我們首先引入Debreu定理。

定理1 (Debreu) 在策略博弈中,如果每個局中人的純策略空間Si是歐氏空間上的非空緊凸子集，支付函數(shù)連續(xù)且關(guān)于Si擬凹，那么該博弈存在一個純策略納什均衡。

命題1πΑ,πΒ分別關(guān)于pΑ,pB是擬凹的。

(9)

同理可證，πB關(guān)于pB是凹函數(shù)。

根據(jù)凹函數(shù)與擬凹函數(shù)的性質(zhì)，πΑ,πB分別關(guān)于pA,pB是擬凹的。

從效用函數(shù)的定義可以看到，一定存在某個值pAmax，當(dāng)企業(yè)A的產(chǎn)品定價pA大于pAmax時，企業(yè)A對所有路徑上的顧客流效用為零，此時企業(yè)A利潤為零，因此pA的取值范圍為 [cΑ,pAmax], 同樣的，定義pB的取值范圍為[cB,pBmax] 。

命題2 問題P存在純策略納什均衡解。

證明 在此模型中，策略空間pA=[cΑ,pAmax],pB=[cB,pBmax],顯然pA,pB是有界閉凸集。由連續(xù)函數(shù)的性質(zhì)知，πΑ,πB是連續(xù)函數(shù)，根據(jù)推論1,πΑ,πB分別關(guān)于pA,pB是擬凹的，模型滿足定理1純策略納什均衡解存在的所有條件，命題得證。

3 算法設(shè)計

由于模型的目標(biāo)函數(shù)是非線性函數(shù)，且目標(biāo)函數(shù)中wpj的值只有在pA,pB,Y確定后才能確定，因此不能使用傳統(tǒng)的規(guī)劃的方法進(jìn)行求解?；诖耍覀儤?gòu)造啟發(fā)式算法進(jìn)行求解。

模擬退火算法[19]模擬金屬的退火過程，它從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，在解空間中隨機(jī)搜尋目標(biāo)函數(shù)的全局最優(yōu)解，為了避免陷入局部最優(yōu)解，算法使用雙向搜索技術(shù)，若新求得的解優(yōu)于當(dāng)前解，則接受新求得的解為當(dāng)前解，否則，以一定的概率接受新求得的解為當(dāng)前解。模擬退火算法已在理論上被證明是一種以概率1收斂于全局最優(yōu)解。研究表明，較高質(zhì)量的初始解不僅可以提高模擬退火算法的收斂速度，而且提高算法最終解的質(zhì)量。本文中我們使用貪婪算法所求得的解為模擬退火算法的初始解。

具體算法如下：算法分為兩個階段，第一階段使用貪婪算法對問題進(jìn)行求解，將貪婪算法求得的問題的解作為問題的初始解，在第二階段使用模擬退火算法對其進(jìn)行優(yōu)化，具體步驟如下：

第一階段：貪婪算法求解問題初始解：

Step 1M0←Φ,k←1;

Step 4Mk←Mk-1∪{j*},k←k+1;

Step 5 如果k=m或者N-E-Mk=Φ, 終止計算；否則，轉(zhuǎn)入Step 2.

第二階段：模擬退火算法：

Step 3 :k←k+1,tk+1←α×tk. 若滿足終止條件，則終止計算，否則轉(zhuǎn)入Step 2.

注1：模擬退火算法包含一個內(nèi)循環(huán)過程和一個外循環(huán)過程，本文中，我們將外循環(huán)的終止條件設(shè)置為溫度t降到指定溫度，內(nèi)循環(huán)終止條件為迭代次數(shù)達(dá)到事先給定的值，內(nèi)循環(huán)中Mk的鄰域由交換Mk中任意兩個元素的位置得到。

注2：納什均衡解的求解。雖然我們在第三部分證明了模型納什均衡解的存在性，但是卻很難求得其解析解。這是因為，給定企業(yè)A的選址點，則兩個企業(yè)的價格均衡解需由求解以下非線性方程組得到：

由于各個方程組里各個等式的高度非線性性，要求得方程組的解析解幾乎是不可能的，因此本文中我們使用Serra和Revelle[4]提出的price-search算法進(jìn)行求解。

4 算例分析

4.1 小規(guī)模算例

我們隨機(jī)生成節(jié)點數(shù)為10,15,20，路徑數(shù)為20,30,40的隨機(jī)網(wǎng)絡(luò)，企業(yè)B已有的設(shè)施數(shù)目為1,2，企業(yè)A擬新建設(shè)施數(shù)目m=2,3，對每組情況，隨機(jī)生成30組算例。每組算例中，路徑p上的顧客流fp～N(100,30),企業(yè)A在各個節(jié)點處的選址成本gj∈[400,500],兩個企業(yè)的產(chǎn)品成本cA=cB∈[4.5,5],效用函數(shù)中參數(shù)U∈ [8,10],α,αp∈ [0,1]。

為了檢驗本文所提啟發(fā)式算法的有效性，我們將本文所提算法的試驗結(jié)果與枚舉算法的計算結(jié)果進(jìn)行比較。但是，在枚舉算法求解的過程中，對算法得到的任何一個問題的可行解，使用price-search 算法求解兩個企業(yè)的納什均衡價格。因為在求解的過程中使用了price-search 算法，枚舉算法求得的問題的解不一定是模型的最優(yōu)解，但是算法給了我們一個模型解的上界，用于檢驗本文所提算法的有效性。兩種算法結(jié)果的比較如表1 所示。從表1可以看出，本文所提算法的計算結(jié)果與枚舉算法的計算結(jié)果基本一致，算法是有效的。

表1 本文算法與枚舉算法計算結(jié)果比較

4.2 大規(guī)模算例

圖1 示例網(wǎng)絡(luò)

如圖1所示，網(wǎng)絡(luò)中節(jié)點數(shù)為60，路徑數(shù)為150，各個路徑上的需求量服從均值為1000，方差為300 的正態(tài)分布，企業(yè)B已在節(jié)點14,48,57處各有一個設(shè)施，企業(yè)A擬新建設(shè)施個數(shù)為5，兩個企業(yè)產(chǎn)品成本價均為8，消費者偏離原路徑行駛單位距離的成本為0.25，各潛在設(shè)施點的選址成本均為1000。

我們用Matlab進(jìn)行編碼，在Intel Core i3-350M處理器，2G內(nèi)存的計算機(jī)上進(jìn)行仿真實驗，其中模擬退火算法初始溫度為4000度，降溫系數(shù)0.99，終止溫度400度，內(nèi)循環(huán)每次迭代步長為10，企業(yè)A新建設(shè)施個數(shù)分別為1,2,3,4,5的情況下，對示例網(wǎng)絡(luò)進(jìn)行了仿真實驗，實驗結(jié)果如表2所示。

表2 算法運算結(jié)果

從表2可以看到，隨著企業(yè)A新建設(shè)施數(shù)的增加，企業(yè)A對產(chǎn)品的定價逐步增高，企業(yè)B產(chǎn)品定價逐漸降低。從目標(biāo)函數(shù)的定義可以看到，其他因素不變的情況下，某個企業(yè)產(chǎn)品價格的提高會造成兩方面的影響，一是其單位產(chǎn)品利潤的提高，二是企業(yè)市場占有率的降低，如何權(quán)衡利弊，制定合適的價格以獲取最大利潤，是一個非常復(fù)雜的問題。從表1 的結(jié)果來看，當(dāng)企業(yè)在市場上的設(shè)施數(shù)低于競爭對手時，企業(yè)應(yīng)選擇較低的價格以吸引盡可能多的顧客，提高總體利潤，當(dāng)企業(yè)在市場上的設(shè)施數(shù)大于競爭對手時，企業(yè)在市場占有率上已有先天優(yōu)勢，應(yīng)適當(dāng)提高其產(chǎn)品售價，以使總體利潤最大。

5 結(jié)論

新的企業(yè)的進(jìn)入必然打破市場上原有的平衡，并影響市場上已存在的企業(yè)的利潤。處于資金等因素的限制，先進(jìn)入市場的企業(yè)在無法對其設(shè)施位置進(jìn)行調(diào)整的情況下，為了追逐利潤的最大化，必然對其產(chǎn)品價格進(jìn)行調(diào)整。本文以此為背景，通過構(gòu)造效用函數(shù)，引入Huff模型，提出了競爭環(huán)境下截流問題的選址-價格模型，證明了雙方納什均衡解的存在性和唯一性，構(gòu)造啟發(fā)式算法對模型進(jìn)行求解，并將啟發(fā)式算法的計算結(jié)果與枚舉算法的計算結(jié)果進(jìn)行了比較，證明了本文所提算法的有效性。下一步，我們將對消費者具有多種需求情況下的選址問題進(jìn)行研究。

[1] Saidani N, Chu F, Chen H X. Competitive facility location and design with reactions of competitors already in the market[J]. European Journal of Operational Research, 2012, 219: 9-17.

[2] Hotelling H. Stability in competition[J]. The Economic Journal, 1929, 39(153): 41-57.

[3] Hoover E M. Spatial price discrimination[J]. The Review of Economic Studies, 1937, 4(3): 182-191.

[4] Garcia M D,Pelegrin B P,Fernandez P. Location strategy for a firm under competitive delivered prices[J]. The Annals of Regional Science, 2011, 47: 1-23.

[5] Serra D, Revelle C. Competitive location and pricing on networks[J]. Geographical Analysis, 1999, 31(1): 109-129.

[6] Perez M D G,Hernandez P F,Pelegrin B P. On price competition in location-price models with spatially separated markets[J]. Top, 2004, 12(2): 351-374.

[7] Aboolian R, Berman O, Krass D. Optimizing pricing an location decisions for competitive service facilities charging uniform price[J]. Journal of Operational Research Society, 2008, 59: 1506-1519.

[8] Pelegrin B,Fernandez P,Perez M D G. On the location of new facilities for chain expansion under delivered pricing[J]. Omega, 2012,40: 149-158.

[9] Hodgson M J. A flow-capturing location-allocation model[J]. Geographical Analysis, 1990, 22: 270-279.

[10] Berman O, Larson R C, Fouska N. Optimal location of discretionary service facilities[J]. Transportation Science, 1992, 26:201-211.

[11] Berman O, Krass D. Flow intercepting spatial interaction model: a new approach to optimal location of competitive facilities[J], Location Science, 1998, 6:41- 65.

[12] Wu T H, Lin J N. Solving the competitive discretionary service facility location problem[J]. European Journal of Operational Research, 2003, 144: 366-378.

[13] 楊珺，張敏，陳新.一類帶服務(wù)半徑的服務(wù)站截流選址-分配問題[J].系統(tǒng)工程理論與實踐,2006,26(1):117-122.

[14] 胡丹丹，楊超.在競爭環(huán)境中的擁塞設(shè)施截流選址問題[J].系統(tǒng)工程理論與實踐，2010,30(1)：68-72.

[15] Zeng, W, Castillo I, Hodgson M J. A generalized model for locating facilities on a network with flow-based demand[J]. Networks and Spatial Economics, 2010, 10: 579- 611.

[16] Zeng W, Hodgson M J, Castillo I. The pickup problem: consumers’ locational preferences in flow interception[J]. Geographical Analysis, 2009, 41: 107-126.

[17] Tanak K, Furuta T. A hierarchical flow capturing location problem with demand attraction based on facility size, and its lagrangian relaxation solution method[J]. Geographical Analysis, 2012, 44:15-28.

[18] 羅伯特·吉本斯著，高峰譯.博弈論基礎(chǔ)[M].北京：中國社會科學(xué)出版社，1999.

[19] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220: 671- 680.

[20] Al-eraidah O, Krishnamurthy A, Malmbrog C J. A two-stage simulated annealing procedure for block layout problems[J]. International Journal of Production Research, 2006, 44(20): 4417- 4429

Optimizing Location and Pricing Policies in Competitive Flow Interception Problem

SHENG Rui-ling1, HUO Jia-zhen2, WANG Qian3

(1.SchoolofMathematicsandInformationScience,HenanUniversityofEconomicsandLaw,Zhengzhou450000,China; 2.SchoolofEconomicsandManagement,TongjiUniversity,Shanghai200092,China; 3.HenanUniversityofTechnology,Zhengzhou450000,China)

We present the model of optimizing the location and pricing for a firm entering a competitive market in a flow interception problem. The entering firm charges uniform mill price and aims at finding the locations and price to optimize its overall profit. The competitor, on the other hand, can react by adjusting its price with the objective of maximizing its own profit. We define the utility functions, and a probability of customers on each path patronizing the facility is described by a Huff-like model. A heuristic algorithm is presented. We also analyze the benefit of the entering firm gains considering the competitor’s reaction.

operations research; flow-interception facility location; location-pricing; Nash equilibrium; simulated annealing algorithm

2013- 06- 20

國家自然基金資助項目(71102071,71002020，11371122)；國家自然科學(xué)基金重大項目資助(71090404/71090400)；河南省社科規(guī)劃基金資助項目(2014BZHD10)

申瑞玲，女，河南長葛人，博士研究生，研究方向：運營管理，設(shè)施選址；霍佳震，男，安徽蕪湖人，博士，教授，博士生導(dǎo)師，研究方向：運營管理，供應(yīng)鏈管理；王茜，女，河南鄭州人，博士研究生，研究方向：企業(yè)管理。

O221.2

A

1007-3221(2015)04- 0122- 06