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

李　蕾，鄭鵬杰

（1.青海交通職業(yè)技術(shù)學(xué)院　管理工程系，青?！∥鲗帯?10003；2.中鐵第四勘察設(shè)計(jì)院集團(tuán)有限公司　線站處，湖北　武漢　430063）

?

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

李蕾1，鄭鵬杰2

（1.青海交通職業(yè)技術(shù)學(xué)院管理工程系，青海西寧810003；2.中鐵第四勘察設(shè)計(jì)院集團(tuán)有限公司線站處，湖北武漢430063）

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

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

1　引言

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

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

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

2　問題分析

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

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

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

3.1符號及參數(shù)定義

為研究方便，定義本文模型所需符號與參數(shù)如下：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個物流中心提供運(yùn)輸服務(wù)的單位廣義費(fèi)用；xij表示第i個客戶在 j物流中心滿足的運(yùn)輸量；fj表示在 j地點(diǎn)新建物流中心的固定投資，j∈A2；δj為0-1變量，在j（j∈A2）處新建時等于1，否則為0；Wi表示第i個客戶的總運(yùn)輸需求量；R表示一個充分大的正數(shù)。

3.2上層模型

（1）目標(biāo)函數(shù)。上層目標(biāo)考慮到?jīng)Q策部門的利益，必須在決策部門投入成本允許的范圍內(nèi)進(jìn)行新建物流中心最優(yōu)選址，使得新建物流中心總成本最小，包括固定成本和變動成本，得到目標(biāo)函數(shù)如下：

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

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

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

3.3下層模型

（1）目標(biāo)函數(shù)。下層模型表示多個物流中心競爭條件下，所有客戶需求量在不同物流中心的分配問題，也是用戶最優(yōu)選擇問題，目標(biāo)是使得所有客戶的總費(fèi)用達(dá)到最低，目標(biāo)函數(shù)如下：

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

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

滿足運(yùn)輸需求量有意義，即非負(fù)約束，可得：

4　求解算法

4.1最優(yōu)解分析

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

引入拉格朗日函數(shù)，下層規(guī)劃目標(biāo)函數(shù)可以表示如下：

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

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

對式（10）和（11）進(jìn)行化簡可得一階條件為：

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

4.2Frank-wolfe算法設(shè)計(jì)

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

假設(shè)存在有限個最優(yōu)解yi，下層規(guī)劃運(yùn)輸需求分配的Frank-wolfe算法步驟如下：

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

Step2：根據(jù)目標(biāo)函數(shù)min?f（xi）Tx可知是求最小值，將初始點(diǎn)代入得到當(dāng)前最優(yōu)解yi。

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

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

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

4.3遺傳算法設(shè)計(jì)

根據(jù)上層模型是一個標(biāo)準(zhǔn)的0-1規(guī)劃問題，本文設(shè)計(jì)遺傳算法對其求解。

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

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

選擇操作具體步驟如下：

Step1：計(jì)算所有個體的適應(yīng)函數(shù)值，并排序，令i=1；

Step2：選出適應(yīng)度函數(shù)值最大的個體，直接復(fù)制到下一代；

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

4.4算法步驟

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

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

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

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

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

Step7：產(chǎn)生新一代種群，Xi+1=Xi。

Step8：置i=i+1，轉(zhuǎn)Step2。

5　算例分析

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

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

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

表1　物流中心到客戶的單位運(yùn)輸費(fèi)率（元·kg/km）

表2　物流中心到客戶的運(yùn)輸距離（km）

表3　備選物流中心建設(shè)費(fèi)用和運(yùn)營費(fèi)用（萬元）

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

表4　新建物流中心選址結(jié)果與客戶運(yùn)輸需求分配（kg）

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

根據(jù)本案例設(shè)計(jì)的迭代次數(shù)為500，依次導(dǎo)出9個不同迭代次數(shù)得到的選址結(jié)果，見表5，表中“1”表示選擇在此處新建物流中心，“0”表示不在此處新建物流中心。

表5　不同迭代次數(shù)的選址結(jié)果

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

6　結(jié)論

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

［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］王寶華，何世偉.不確定環(huán)境下物流中心選址魯棒優(yōu)化模型及算法［J］.交通運(yùn)輸系統(tǒng)工程與信息，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的多級物流中心選址動態(tài)模型分析［J］.物流技術(shù)，2011，30（10）：81-83.

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

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

［8］Bing Wang，F(xiàn)u 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-），女，青海西寧人，青海交通職業(yè)技術(shù)學(xué)院管理工程系講師，碩士，研究方向：現(xiàn)代物流發(fā)展與運(yùn)作模式；鄭鵬杰（1989-），男，湖北武漢人，中鐵第四勘察設(shè)計(jì)院集團(tuán)有限公司線站處助理工程師，碩士，研究方向：現(xiàn)代物流園區(qū)規(guī)劃與設(shè)計(jì)。