考慮碳排放的多產品競爭設施選址問題研究

劉偉偉 王明征 胡祥培

(1.大連理工大學經濟管理學院,遼寧大連 116024;2.哈爾濱工業大學(威海)經濟管理學院,山東威海 264209;3.浙江大學管理學院,浙江杭州 310058)

1 引言

設施選址問題研究的是企業如何選擇合適的位置開設設施,當為顧客提供產品或服務時,使其總利潤達到最大.設施選址決策作為企業的長期戰略,是企業生存根本之所在[1].經典的選址模型,例如覆蓋問題、p-中值問題和無容量設施選址問題,均基于空間壟斷的假設,即企業是市場的唯一參與者[2,3].然而,該假設在諸多實際問題中并不成立,例如加油站、超市和快遞門店等設施的選址中,在新設施進入市場之前,通常已有一個或多個競爭設施存在.由于新企業未進入市場前,該行業產品供需是平衡的.新企業一旦進入,將與對手競爭市場份額,勢必會打破原有平衡,形成新的市場均衡價格、產品交易量和生產量,達到新的平衡狀態[4].因此,在設施選址問題中考慮到競爭對手的反應尤為重要.

競爭選址,研究的即為競爭環境下的選址問題[5].20 世紀80 年代后,競爭選址逐漸成為選址領域的熱點問題,得到了較為廣泛的研究[6?8].作為競爭選址問題的一種,帶預見性的競爭是指企業在進入市場之前,已經考慮到競爭對手會緊隨其后進入市場.此類問題被描述為Stackelberg 博弈[9],即雙寡頭壟斷市場的主從博弈.在該博弈中,有兩個行動者(稱為領導者和跟隨者)相繼進行決策.領導者預料跟隨者的反應,制定自己的最優決策;跟隨者在觀測到領導者的決策之后制定自己的最優決策.Hakimi[10]首次將這個模型引入到選址領域,領導者將跟隨者的最優反應納入到決策過程中,并采取最小最大策略來維護自己的利益.Miller等[11]研究了寡頭壟斷企業的選址及市場均衡集成問題.Fischer 等[12]根據序列行動和運輸價格固定與否對雙寡頭競爭選址問題進行研究并提出兩種模型.

近年來,隨著全球對碳減排的日益關注,政府及消費者都在迫使企業減少碳排放[13].許多國家制定了政策和法律法規來約束碳排放量.廠商要想擔負起應有的社會責任、保持競爭地位,著重考慮碳排放勢在必行[14].如何實現碳減排以及評估實施碳減排對企業績效產生的影響成為當今企業普遍關注的關鍵問題之一.Wu 等[15]認為運輸是物流系統中環境污染的最大來源.Elhedhli 等[16]指出,通過策略上合理安排設施的位置,減少車輛的出行距離,可以對國家碳足跡的減少起到重要作用.由此,將碳排放約束應用于企業的選址決策中,對于低碳可持續發展,具有廣泛的現實意義.目前,諸多研究已關注碳排放[17?22],但在設施選址問題中納入環境因素的研究尚不十分豐富[23],在競爭設施選址問題中考慮碳排放的研究更是相對較少.Ghaddar 等[4]在政府的碳交易機制下研究了雙寡頭壟斷企業的競爭設施選址問題,考慮了運輸產生的碳排放,目標為企業利潤最大化,但他們針對的是單一產品.

眾所周知,顧客對服務與產品的需求往往不是單一的.隨著企業生產經營的多元化,企業已向顧客提供多種替代和/或者互補產品.由于產品之間存在著替代或者互補關系,一種產品的價格會對另一種產品的需求量產生影響,甚至當一種產品的價格高至其需求為零時,該產品仍然對其它產品的需求產生影響,所以產品的需求量不僅受到自身價格的影響,也受到其它產品價格的影響[24].企業在設施選址時考慮到產品之間的替代或者互補關系具有重要的現實意義.如何將產品之間的替代或者互補關系及政府的碳排放政策融入競爭設施選址問題中為企業制定出最優的設施選址策略,以實現利潤最大化,是本文解決的主要問題.由此,本文探討了碳交易機制下的雙寡頭壟斷企業的競爭設施選址問題,將運輸碳排放及多種產品之間的替代或互補關系考慮在內.

多產品的需求-價格關系是選址決策制定的關鍵.產品之間替代或者互補關系的存在導致了需求-價格關系極其復雜,因此現有選址文獻普遍采用僅在某個區域上有定義的需求函數,如線性需求函數.Soon等[24]通過實例論證了基于該類型的需求函數制定的決策可能是次優決策,表明了基于定義于整個非負價格區域上的需求函數制定最優決策的必要性.現有文獻主要有兩種定義于整個非負價格區域上的需求函數：一種是利用單片可微函數近似需求,如Cobb-Douglas函數[25]和Logit 函數[26].該類型的函數形式上簡單易處理,卻不能反映真實市場.例如,在Cobb-Douglas 模型中會出現當其它產品價格上升,產品的需求量趨于無限大的情形;一種是利用分片光滑函數近似需求,如Boyer 等[27]和Kubler 等[28],但它們具有與第一種函數類似的不可取的特性.Soon 等[24]提出了一個分片光滑的多產品需求函數–互補需求函數,該函數能精確刻畫整個非負價格區域上的需求,且具有如單調性等從經濟管理角度可取的性質.為了制定全局最優選址決策,本文基于互補需求函數研究考慮碳排放的多產品競爭設施選址問題.目前僅有Federgruen 等[29?31]基于互補需求函數進行研究,但他們針對產品定價,不涉及設施選址.

由上述分析,本文將能夠反映市場情況的互補需求函數引入多產品競爭設施選址問題中,以此融入了多種產品之間的替代和/或者互補關系.基于互補需求函數,建立了考慮碳排放的多產品競爭設施選址模型,為雙層規劃,是強NP-hard 問題;為了有效求解該問題,利用Karush-Kuhn-Tucker 條件、大M 方法和McCormick 外逼近方法將雙層規劃轉化為有界閉集上的0-1 混合整數凹規劃,極大地降低了問題的求解難度,并提出具有全局收斂性的分支提升算法;通過對數值結果的討論分析,本文為低碳可持續環境下的企業運營提供了決策參考.

2 考慮碳排放的多產品競爭設施選址模型

2.1 問題描述

考慮兩家制造企業.企業F 已建立b(≥1)處設施生產并向n(≥1)個顧客點提供其所需的l(≥2)種產品(產品之間存在替代或者互補關系).企業L 打算進入市場與企業F 競爭市場份額,因此需要從m(≥1)處備選設施中確定開設的設施.每處潛在設施均有能力生產此l種產品,且均可將產品運輸到各個顧客需求點,運輸產品的過程中會產生碳排放.本文考慮政府的碳交易機制,即政府對企業L 和企業F 分別規定碳限額EL和EF,當碳排放量超過EL(EF)時,企業L(F)可以從碳交易市場上購買其所需的份額;當碳排放量低于EL(EF)時,企業L(F)可以將多余的份額在碳交易市場上賣出,獲取部分收益.

企業L 和企業F 之間是Stackelberg 博弈,企業L 為領導者,企業F 為追隨者.Stackelberg[32]最早引入該博弈,之后出現了諸多擴展[33,34].企業L 預測企業F 的反應,確定開設的設施、設施到顧客點的產品運輸量及產品的價格策略,以實現自身利潤最大化.企業F 在觀察到企業L 的決策后,確定已建立設施到顧客點的產品運輸量策略,以實現自身利潤最大化.

2.2 模型建立

本文假設對于任意,非線性互補問題的解唯一且∈?,該假設成立的具體條件見3.1節.

由于諸多理論模型和實證研究中普遍采用仿射結構,因此本文針對給定的需求函數dj(p)為線性需求函數的情形進行分析.線性需求函數dj(p)的具體形式為

表1 符號說明Table 1 Symbol description

基于以上介紹,企業F 的利潤最大化模型為(aF)

企業L 的利潤最大化模型為(aL)

企業L 和F 的優化模型構成雙層規劃模型,上層是企業L 的優化模型(aL),下層是企業F 的優化模型(aF),這即為本文所建立的考慮碳排放的多產品競爭設施選址模型.上層模型(aL)為帶均衡約束的0-1 混合整數二次規劃,下層模型(aF)為帶均衡約束的二次規劃,且兩個模型的目標函數中均含有非線性程度高的雙線性函數,求解異常復雜,為強NP-hard 問題[37].

3 模型分析

為了提出有效的求解算法,本節對雙層規劃模型進行分析.3.1 節將雙層規劃等價轉化為單層規劃;3.2節利用大M 方法將均衡約束等價轉化為線性約束;3.3 節通過利用McCormick 外逼近方法將目標函數中的雙線性函數線性化,將模型轉化為有界閉集上的0-1 混合整數凹規劃.

3.1 雙層規劃到單層規劃的等價轉化

企業F 的最優決策,即模型(aF)的最優解可由Karush-Kuhn-Tucker(KKT)條件刻畫,即

其中變量ρjk和σqk分別為對應于約束(2)和約束(3)的對偶變量.

由此,雙層規劃模型可以轉化為如下單層規劃模型(b)

若dj(p)為線性函數,則線性互補問題存在唯一解(即均衡約束(17)有唯一解)的充分必要條件是Aj是P矩陣[24].由此,本文余下部分假定為P矩陣1.

將模型(b)中的約束(6)和約束(13)替換為式(16)～式(18),得到如下等價模型(c)

將雙層規劃轉化為單層規劃,求解難度在一定程度上有所降低,但此等價模型包含更多的均衡約束,即式(12),式(14),式(17)～式(18),且其目標函數中有雙線性函數,仍為強NP-hard 問題[38],求解難度仍不低.

3.2 均衡約束的等價轉化

帶均衡約束的優化問題一般難以求解,因為其可行域非凸甚至不連通.現實生活中,由于顧客對產品的需求量是有限的,所以(?k ∈K)有上界.本節利用大M 方法[4],通過引入統一的系數M 及二進制變量,分別將均衡約束(12),約束(14),約束(17)～約束(18)等價轉化為線性約束,得到如下模型(d)

相比模型(b)的等價模型(c),模型(d)中不再含有均衡約束,結構更加明確,為帶線性約束的0-1 混合整數二次規劃.由于均衡約束的等價轉化,則模型(c)與模型(d)是等價的.因此,可用求解模型(d)取代求解模型(b).注意到模型(d)的約束均為線性約束,則其約束集已為有界閉集,進一步分析模型(d)的目標函數,有下面的結論.

命題1模型(d)的目標函數不是凹函數.

命題1 的證明見附錄.

為便于模型分析,將dj(p)的具體形式代入約束(16),約束(23)和約束(26)中,得到如下等價模型(e)

3.3 混合整數非凹規劃到凹規劃的轉化

引理1滿足Lx≤x≤Ux(Lx

確定的包絡wxy.

與模型(e)相比,模型(f)目標函數中非線性項僅有. 此時進一步分析模型(f),有下列結論.

定理1模型(f)的目標函數為凹函數.

證明目標函數中的非線性項為二次項,其余項均為線性項.由于此二次函數是凹函數,從而目標函數為凹函數2雖然均導致模型(e)目標函數非凹,但當 被其McCormick 包絡代替后,模型(f)的目標函數已變為凹函數. 因此本節僅對 線性化而未再對線性化.. 證畢.

通過上述分析,求解帶均衡約束的0-1 混合整數二次規劃(b),取而代之地求解有界閉集上的0-1 混合整數凹規劃(f)即可,這極大程度地降低了問題的求解難度.

4 分支提升算法

相比原問題,模型(f)由于約束及引入的0-1 變量的增多,其規模更大.針對大規模0-1 混合整數凹規劃(f),本節在分支定界的過程中通過不斷更新McCormick 不等式產生更緊的外逼近來提升求解效率,由此稱所提出的算法為分支提升算法.

4.1 分支和剪枝規則

為方便起見,本文求解與凹規劃(f)等價的凸規劃,記為(f′),其目標函數為模型(f)的相反數.記向量,i ∈I,j ∈J,q ∈Q,k ∈K及Ψ={ψ:Lψ≤ψ≤Uψ},其中Lψ和Uψ分別表示ψ各分量的下界和上界所組成的列向量.記向量?=(z1,z2,...,zm),及Φ=[0,1]m,由于?的各分量均為0-1 變量,所以其下界均為0,上界均為1.

從求解模型(f′)的連續松弛問題（即拋棄整數要求）開始.如果松弛問題不可行,則原問題不可行.否則,選擇一個變量進行分支,產生兩個子問題.在算法進行過程中,不斷求解子問題,并通過分支添加新的子問題.當不再產生子問題時,算法終止.令LPR(Ψκ,Φκ)表示子問題的連續松弛,分別為其最優解和最優函數值,其中κ代表當前結點,Ψκ和Φκ代表當前可行解空間.

為保證求解的精確性,不僅對整數變量進行分支,還對連續變量進行分支,分支過程如下:若??的值為分數,對其進行分支,即

類似地,對連續變量x?在值處進行分支,即

在分支過程中,交替選擇整數變量和連續變量進行分支.之所以如此操作,是因為整數變量代表的選址決策與連續變量代表的定價與運輸量決策之間相互影響.分支變量的類型一旦確定,再從中隨機選擇一個變量進行分支.為了產生更緊的外逼近,每次對連續變量進行分支后,均在子問題中更新McCormick 不等式(34)～式(37).

4.2 算法步驟

基于上述表示,本節具體描述分支提升算法:

證明(f′)的下界和上界分別由松弛問題LPR(Ψκ,Φκ)和NLP(Ψκ,)的最優值給定.在可行解空間上找不到更好的解保證了剪枝規則(即情形1～情形3)的合理性.為保證求解的準確性,對整數變量和連續變量均進行分支.由于整數變量的數量是有限的,則對整數變量進行的分支即為有限步.在對連續變量進行分支時,通過在子問題中更新McCormick 不等式,由此得到更緊的外逼近.則在有限步之后,(f′)與原問題之間的間隙一定小于給定的精度ε.因此,分支提升算法會在有限步之后收斂至最優解. 證畢.

5 算例仿真

5.1 數據選取

本文在主頻3.4 GHz 的Intel i7 處理器,8 GB 的運行內存和64 位的操作系統下運行所有算例,在MATLAB 2014a 環境下執行求解的算法.針對兩種可替代產品,假設企業L 的備選設施、企業F 的已建立設施以及顧客點均隨機生成于(75×75)km2的區域上,利用歐幾里得范數衡量設施與顧客需求點之間的距離.精度ε=10?6,M=1010.算例參數見表2,其中部分參數參考文獻[4].

表2 模型參數Table 2 Model parameters

5.2 選址結果及分析

由表3,線性需求函數情形下,企業L 開設兩處設施,并均提供產品1 和產品2,利潤為19 963元;互補需求函數情形下,企業L 僅開設設施1且僅提供產品2,利潤為22 501 元,比線性需求函數情形下的利潤增加了12.7%.究其原因,對比表3 中的數據發現,兩種需求函數情形下產品2 的價格均為380 元,產品1 的價格在互補需求和線性需求函數情形下分別為160 元和128 元.這意味著產品1價格的升高導致產品2的需求增加,而產品2 銷量增加所帶來的收益要高于線性需求函數兩處設施同時銷售產品1 的收益.發現d2(p1,p2)=2 400+30p1?20p2<0,即企業L 的最優決策在線性需求函數限定的價格區域之外取到.企業F 在兩種情形下的供應策略在互補需求情形下的利潤同樣高于線性需求函數情形下的利潤.因此,對產品價格進行限制進行會導致企業部分利潤的流失,取到“次優”決策.進一步表明,企業在制定最優決策時考慮互補需求函數的必要性,即本文所提模型的合理性和有效性.

表3 最優選址、定價及供應量策略Table 3 Optimal location,price and quantity strategies

5.3 碳限額及碳交易對企業決策的影響分析

企業L 在最優選址決策下的碳排放量為85.4 kg.以企業L 為例評估碳限額對企業決策的影響.為了闡明碳限額的影響,考慮禁止碳交易和允許碳交易兩種情形.將企業L 的碳限額由80 kg 開始依次減少20 kg 直至0,企業F 的碳限額仍保持在80 kg.對比禁止碳交易和允許碳交易兩種情形下的結果,見表4.

表4 禁止碳交易和允許碳交易情形下企業決策結果對比Table 4 Comparison decision results under prohibiting carbon trading and allowing carbon trading

由表4,若政府禁止碳交易,碳限額的減少雖然會使企業碳排放量減少,但企業利潤也會同步減少,這并不利于企業的發展.若政府允許碳交易,當政府給定的碳限額不足時,企業總會從碳交易市場上購買所需的碳使總量達到85.4 kg.有趣地是,企業并不會為此付出過高的代價,甚至當政府給定的碳限額為0 時,企業僅犧牲大約3.63%的利潤即可獲得額外所需的碳.由此表明,碳交易機制的實施對于企業的可持續經營以及整個國家碳足跡的減少起到了一定的作用,因為企業總會從碳交易市場上購買其它企業多余的碳滿足自身生產活動,但只需犧牲微博的利潤即可,這在一定程度上也減輕了企業對碳排放政策實施的擔憂.

5.4 算法有效性分析

為了評估分支提升算法在處理大型選址算例上的表現,本節將分支提升算法與He 等[40]近期提出的一種分支定界算法在處理較大規模算例的時間作比較,結果見表5.

表5 分支提升算法和分支定界算法運行時間對比Table 5 Comparing the computational time of branch-and-refine algorithm and branch-and-bound algorithm

第1 列代表備選設施的數量;第2 列代表已建立設施的數量;第3 列代表顧客點的數量;第4 列和第5列分別表示分支提升算法和分支定界算法的求解時間.由表5,隨著算例規模的增大,即備選設施數量、已建立設施數量和顧客點數量的增多,求解算例所耗時間增加.但相比分支定界算法,本文所提的分支提升方法仍具有優勢.

6 結束語

在綠色低碳可持續背景下,隨著現代經濟的迅速發展和企業經營的多元化,制造多種替代和/或互補產品的企業在制定選址決策時預測競爭對手的反應至關重要.本文將政府的碳交易機制和產品之間的替代或者互補關系融入競爭設施選址問題中,建立了考慮碳排放的多產品競爭設施選址模型.針對模型特征,將其轉化為有界閉集上的0-1 混合整數凹規劃,并提出具有全局收斂性的分支提升算法.算例仿真結果表明企業總會從碳交易市場上購買其它企業多余的碳滿足自身生產活動,但只需犧牲微薄的利潤即可,這在一定程度上減輕了企業對碳排放政策實施的擔憂,對于企業的可持續經營以及整個國家碳足跡的減少起到了一定的作用.本文假定顧客的購買意愿僅受到產品價格的影響,實際上消費者在購買產品時會關注產品的綠色水平,后續的研究將進一步在設施選址問題中考慮消費者的環境偏好.

附錄 命題1 的證明

一個矩陣是半正定矩陣的充要條件是該矩陣的所有主子式非負.顯然,該矩陣并不是半正定矩陣,因為存在負的主子式,如第1 行,第2mn+1 行和第1 行,第2mn+1 列構成的主子式.所以模型(d)的目標函數并不是凹函數.

證畢.