考慮市場競爭條件的新建物流中心選址問題研究

李　蕾，鄭鵬杰

（1.青海交通職業技術學院　管理工程系，青海　西寧　810003；2.中鐵第四勘察設計院集團有限公司　線站處，湖北　武漢　430063）

?

考慮市場競爭條件的新建物流中心選址問題研究

李蕾1，鄭鵬杰2

（1.青海交通職業技術學院管理工程系，青海西寧810003；2.中鐵第四勘察設計院集團有限公司線站處，湖北武漢430063）

在市場競爭條件下，提出了新建物流中心的選址模型與算法，考慮原有物流中心的競爭，建立了基于市場競爭的新建物流中心選址雙層規劃模型，上層規劃為新建物流中心的總成本最小，下層規劃為客戶選擇最優且總費用最小。根據模型的特點，設計了一種基于Frank-Wolfe算法和遺傳算法相結合的迭代算法對其進行求解。最后，通過算例分析驗證了模型和算法的有效性，為新建物流中心選址提供了科學的決策方法。

物流中心；市場競爭；雙層規劃；遺傳算法；Frank-Wolfe算法；選址

1　引言

隨著現代物流的快速發展，對物流中心的功能與數量提出了更高的要求，原有的一些物流中心不能滿足現代物流發展需求，新建物流中心是現代物流發展的必要途徑。新建物流中心選址是一個復雜的系統工程，在原有物流中心基礎上，需要考慮與原有物流中心的競爭，所謂的競爭主要是指與原物流中心共同負責客戶的配送任務。

對于物流中心的選址問題，國內外研究已頗為成熟。物流中心選址最先使用的方法是重心法和物流位圖法，重心法是根據物理學原理，在平面中找到圖形的重心來確定物流中心的地址［1］。而物流位圖法是通過模擬流體力學的“位勢”來確定物流中心的地址［2］，重心法理論上可行，但難以在實際中實現，物流位圖法計算復雜性較大，運算比較麻煩。隨著計算機技術的不斷發展，物流中心選址方法也不斷完善，不確定規劃方法和雙層規劃方法等在物流中心選址中得到較好的應用，文獻［3］提出在不確定條件下，建立了隨機規劃選址模型，并給出了模型的魯棒性優化，Schuetz等提出用戶需求和短期成本都是隨機變量的物流中心選址模型，并運用拉格朗日方法進行求解［4］。文獻［5-6］運用GIS技術對多級物流中心動態選址問題進行了研究，文獻［7-8］運用雙層規劃模型研究了供應鏈選址問題，并提出雙層規劃模型更能系統的分析選址過程。

綜上所述，國內外研究學者在物流中心選址問題上研究較為豐富，但都是籠統的考慮物流中心選址，沒有進一步深入地研究物流中心選址的影響因素，尤其原有物流中心對于新建物流中心的競爭尤為重要，基于此，在市場競爭條件下，本文對新建物流中心選址問題考慮市場競爭因素，建立基于市場競爭的新建物流中心選址模型，并設計合理算法進行求解。

2　問題分析

考慮市場競爭條件下的新建物流中心選址就是將原有的物流中心和新建物流中心一起研究，不僅考慮原有物流中心的運輸費用，而且還考慮與新建物流中心的運量分擔，原有的物流中心對新建物流中心產生較大影響，新建物流中心選址問題如圖1所示。在已有物流中心1的前提下，如何選擇在2或3處新建物流中心，考慮所有的客戶需求全部滿足。

圖1　新建物流中心選址問題分析

3　數學模型

3.1符號及參數定義

為研究方便，定義本文模型所需符號與參數如下：A=A1?A2表示所有物流中心的集合，包括原有物流中心和備選新建物流中心，其中A1=｛j：j=1,2,…,n｝表示原有物流中心的集合，A2=｛j：j=n+1,n+2,…,n+m｝表示備選新建物流中心集合；B=｛i：i=1,2,…,k｝表示所有物流中心覆蓋的客戶集合；cij表示第i個客戶由第 j個物流中心提供運輸服務的單位廣義費用；xij表示第i個客戶在 j物流中心滿足的運輸量；fj表示在 j地點新建物流中心的固定投資，j∈A2；δj為0-1變量，在j（j∈A2）處新建時等于1，否則為0；Wi表示第i個客戶的總運輸需求量；R表示一個充分大的正數。

3.2上層模型

（1）目標函數。上層目標考慮到決策部門的利益，必須在決策部門投入成本允許的范圍內進行新建物流中心最優選址，使得新建物流中心總成本最小，包括固定成本和變動成本，得到目標函數如下：

（2）約束條件。由于考慮到新建物流中心的必要性，故至少需要新建一個物流中心，得到約束條件如下：

一般情況下，決策部門在建設物流中心之前會有預算（N0），故必須在預算內進行，可得約束條件如下：

δj是一個0-1變量，約束如下：

3.3下層模型

（1）目標函數。下層模型表示多個物流中心競爭條件下，所有客戶需求量在不同物流中心的分配問題，也是用戶最優選擇問題，目標是使得所有客戶的總費用達到最低，目標函數如下：

（2）約束條件。由于所有客戶的需求量必須滿足，可得到約束條件如下：

保證所有客戶只在新建物流中心分配運輸需求，沒有建設的物流中心不分配運輸需求，可得約束條件如下：

滿足運輸需求量有意義，即非負約束，可得：

4　求解算法

4.1最優解分析

上層規劃是一個標準的0-1規劃問題，求解算法較多，本文利用遺傳算法進行求解。上層規劃實際是一個客戶需求分配問題，從式（7）可以看出，若δj=0，則xij=0，可以去掉；若δj=1，則xij≤R是肯定滿足的，也可以去掉。故下層模型中只有一個等式約束，可以通過拉格朗日方法證明最優解的存在性。

引入拉格朗日函數，下層規劃目標函數可以表示如下：

式（9）中ui表示下層規劃式（6）約束的拉格朗日乘子。

利用拉格朗日方法中的K-T條件，求解上述問題的一階條件，可得：

對式（10）和（11）進行化簡可得一階條件為：

ui可以理解為客戶i分配運輸需求到各個物流中心的最小費用，且必須滿足cij（xij）=ui。結果就是客戶i到所有分配運輸需求的物流中心費用是相等的，并且此費用小于或者等于沒有分配運輸需求的物流中心的費用。也就是說，客戶所有選址費用都是最低且相等的，故下層規劃滿足用戶最優的UE平衡，存在唯一最優解。

4.2Frank-wolfe算法設計

對于下層規劃滿足用戶最優UE平衡的運輸需求分配問題，最常用求解方法就是Frank-Wolfe算法，基本思想是：通過每次迭代將非線性規劃問題轉化為線性規劃問題，即在某個可行解xi處用泰勒公式展開，利用一階泰勒展開式逼近原來目標函數，最終轉化為線性規劃問題。

假設存在有限個最優解yi，下層規劃運輸需求分配的Frank-wolfe算法步驟如下：

Step1：初始化。選取初始可行點x0，允許誤差ε＞0，置i=0。

Step2：根據目標函數min?f（xi）Tx可知是求最小值，將初始點代入得到當前最優解yi。

(3) 方法3以及本文方法中樁間凈距與抗滑樁截面寬度、高度都相關，呈線性增函數關系。其中，b-L曲線斜率相對于a-L曲線斜率小，表明樁間凈距對抗滑樁截面寬度的變化更為敏感。

Step3：確定可行下降方向。若 ?f（xi）T（yi-xi）≠0，則?f（xi）T（yi-xi）＜0，故 可 行 下 降 方 向di=yi-xi，若則停止計算，輸出xi，否則轉到下一步。

Step4：進行一維搜索。從xi出發做一維搜索，尋找到最佳步長 αi，滿足 minf［xi+α（yi-xi）］，其中 0≤α≤1，令xi+1=xi+αi（yi-xi），i=i+1，轉到Step2。

4.3遺傳算法設計

根據上層模型是一個標準的0-1規劃問題，本文設計遺傳算法對其求解。

（1）遺傳操作設計。根據0-1整數規劃模型特點，設計一種0-1編碼。染色體的基因由數字0或1組成，種群大小一般選擇30-100之間。本文上層所求的目標函數是求總費用最小，故可以直接采用目標函數作為適應度函數。遺傳算法采用隨機單點交叉策略，變異操作就是根據變異概率選取其中一條染色體，然后隨機選取其中一個基因點位置進行變異，使其基因值“1”或“0”互換。

（2）復制操作方法。選擇操作主要是將適應函數值較大的個體遺傳到下一代，淘汰適應度值小的個體，本文主要采用輪盤賭和錦標賽相結合。首先，利用錦標賽規則，把每一次迭代過程中適應函數值最大的父代保留遺傳到下一代。然后，利用輪盤賭原理，以隨機概率的形式選擇遺傳下一代，概率是由個體適應度函數值與所有個體適應度函數值之比確定，選擇遺傳到下一代的概率pi由式（18）得到：

選擇操作具體步驟如下：

Step1：計算所有個體的適應函數值，并排序，令i=1；

Step2：選出適應度函數值最大的個體，直接復制到下一代；

Step4：若i≥m-1，程序終止；否則轉到下一步；

4.4算法步驟

根據本文設計的Frank-wolfe算法和遺傳算法的結合，具體算法步驟如下，其中i表示迭代次數，Gen表示遺傳算法最大迭代次數，Xi表示第i代種群。

Step1：種群初始化。隨機生成m個初始種群Xi（新建物流中心選址結果），并置i=0。

Step2：將初始解Xi代入到下層模型，利用Frank-wolfe算法計算下層，獲得當前最優解（客戶在各個物流中心的需求分配）。

Step5：對種群Xi進行交叉操作，并淘汰不符合條件的染色體。

Step6：對種群Xi進行變異操作，并淘汰不符合條件的染色體。

Step7：產生新一代種群，Xi+1=Xi。

Step8：置i=i+1，轉Step2。

5　算例分析

如圖2所示，某大型公司需要在B區域新建至少一個物流中心，備選點主要有1，2和3三個地方，而此區域里原有一個物流中心4，所有物流中心需要滿足6個客戶的運輸需求。

已知六個客戶運輸需求量依次為7 000kg、15 000kg、13 000kg、10 000kg、9 000kg和8 500kg。各個物流中心到所有客戶之間的單位運輸費率與距離見表1和表2，備選物流中心建設和運營費用見表3。

圖2　考慮市場競爭的新建物流中心選址案例

表1　物流中心到客戶的單位運輸費率（元·kg/km）

表2　物流中心到客戶的運輸距離（km）

表3　備選物流中心建設費用和運營費用（萬元）

此外，本案例中Frank-wolfe算法中的參數ε=0.01，遺傳算法中的種群大小為50，交叉概率為0.9，變異概率為0.05，最大迭代次數為500代，利用C++編程計算，在計算到435代左右趨于穩定，上層模型的總費用為13 477.587，得到的選址結果和用戶運輸需求分配結果見表4。

表4　新建物流中心選址結果與客戶運輸需求分配（kg）

從表4的結果中可以看出，新建物流中心的選址結果是在1處新建一個物流中心，同時由物流中心1和4共同承擔所有客戶的運輸需求任務。

根據本案例設計的迭代次數為500，依次導出9個不同迭代次數得到的選址結果，見表5，表中“1”表示選擇在此處新建物流中心，“0”表示不在此處新建物流中心。

表5　不同迭代次數的選址結果

從表5可以得知，隨著迭代次數的增加，上層模型的總費用隨之減少，新建物流中心選址結果也在不斷變化，從350代開始選址結果不再變化，但是上層模型的總費用還在不斷減少，說明所有用戶的運輸分配還在變化，到450代時得到的結果和最終結果一致，且后50代迭代不再發生變化，說明算法已經收斂到最優解。

6　結論

本文考慮原有物流中心對新建物流中心產生市場競爭的條件下，對新建物流中心的選址和所有用戶的運輸需求分配進行研究，建立了基于市場競爭的新建物流中心選址的雙層規劃模型，設定新建物流中心的固定建設費用和運營費用為約束條件，設計了Frank-wolfe算法和遺傳算法相結合的迭代算法對模型進行求解，并對雙層規劃模型的最優解進行討論與證明。通過設計一個簡單算例，驗證了本文模型和算法的有效性，也為新建物流中心選址問題提供了一個新的思路與方法，具有較強的實踐意義。但本文只考慮了兩級配送模式，沒有考慮多級配送，有待進一步研究。

［1］NozickL K.The fixedcharge facility location problemwithcoverage restriction［J］.TransportationResearch part E，2001，37，（4）：281-296.

［2］Klose A，Drexl A.Facility location models for distribution system design［J］. European Journal of Operational Research，2005，162（1）：4-29.

［3］王寶華，何世偉.不確定環境下物流中心選址魯棒優化模型及算法［J］.交通運輸系統工程與信息，2009，9（2）：69-74.

［4］Schuetz P，Stougie L，Tomasgard A.Stochasticfacility location with general long-run costs and convex short-run costs［J］.Computersamp;Operations Research，2008，35（9）：2 988-3 000.

［5］李振宇，楊松林.基于GIS的多級物流中心選址動態模型分析［J］.物流技術，2011，30（10）：81-83.

［6］李新運，唐保國，梁立魁.基于GIS和粒子群算法的兩級物流配送中心選址優化方法及應用［J］.物流技術，2012，31（1）：78-82.

［7］高國飛，張星臣，徐彬，等.雙層規劃模型在供應鏈選址中的應用［J］.物流技術，2008，（8）：86-88.

［8］Bing Wang，Fu Xiao-kang，Chen Ting-gui.Modeling supply chain facility location problem and its solution using a genetic algorithm［J］.Journal of Software，2014，9（9）：99-103.

Study on Location Problem of Newly-built Logistics Centers with Market Competition Consideration

Li Lei1，Zheng Pengjie2
（1. Department of Management Engineering， Qinghai Communications Technical College， Xining 810003；2. Rail-line Administration Station， China Railway Siyuan Survey Design Group Co.， Ltd.， Wuhan 430063， China）

In this paper， we proposed the model and algorithm for the location allocation of a newly built logistics center under themarket competition circumstances， and then considering the competition from the original logistics center， established a duo-level locationallocation model， the aim of the upper level programming being to minimizing the total cost of the logistics center and that of the lower levelprogramming being optimal customer selection and minimal total expenses. Then according to the characteristics of the model， we designedan iterative algorithm that combined that Frank- Wolfe algorithm and the genetic algorithm for the solution of the model， and at the end，through a numerical analysis， demonstrated the validity of the model and algorithm.

logistics center； market competition； duo-level programming； genetic algorithm； Frank-Wolfe algorithm； location allocation

F252；F224

A

1005-152X（2016）01-0076-04

10.3969/j.issn.1005-152X.2016.01.020

2015-12-12

李蕾（1984-），女，青海西寧人，青海交通職業技術學院管理工程系講師，碩士，研究方向：現代物流發展與運作模式；鄭鵬杰（1989-），男，湖北武漢人，中鐵第四勘察設計院集團有限公司線站處助理工程師，碩士，研究方向：現代物流園區規劃與設計。