基于重力p-median模型的支線機場物資供應中心選址

雷繼超，種小雷，張世迪，于慶坤,龍小勇

(空軍工程大學 航空工程學院，陜西 西安 710038)

支線機場一般地處偏遠，存在物資供應不便、保障困難等方面的問題。一個地區中一般存在多個支線機場，因其擔負的任務不同，對物資的需求量也不盡相同，因此根據支線機場需求物資的種類和數量，建立區域機場物資供應中心是十分必要的。文獻[1-5]針對多層級設施選址問題進行了建模分析，構建了不同的算法并給出了求解方案，結果表明多層級選址模型明顯優于單層的模型。在分階段解決多層級選址問題的研究方面，文獻[6-9]通過建立多層級選址模型，運用遺傳算法對選址進行了優化，結果表明以運輸總成本為最小目標函數建立的多層級選址模型是可行的。文獻[10-13]將重力p-median模型應用到布局設施設計中，結果表明該模型的改進具有實際意義。Wang等[14]建立配送中心的選址模型，并運用改進的免疫優化算法解決配送中心選址問題。

配送中心的選址涉及到很多錯綜復雜的因素，相關研究往往只能解決小區域范圍的選址，具有局限性；并且選址往往只是選擇一個物流中心，考慮的因素相對較少，并不能解決多個機場物資供應的問題。本文從區域的角度出發，考慮了多個物流配送中心的情況，建立重力p-median模型，并采用改進的免疫優化算法對相應模型進行求解，從而確定出機場物資供應中心的最優位置。

1 問題描述

針對建立區域機場物資供應中心現階段存在的問題，解決方案的具體設想及建模目標約束要求如下。

1.1 問題方案設想

本文設想的區域層級機場物資運輸運行模式見圖1。依托區域物流運輸體系，由地區物流中心向機場物資供應中心運輸貨物，物資供應中心將不同區域的機場根據就近原則劃分為幾個物資分散區。每個供應中心保障對應區域的物資供應，通過設計三級運輸體系可以提高物資運輸效率，因此機場物資供應中心的選址在經濟發展中具有重要的意義。

圖1 機場物資保障模式Fig.1 Airport material security model

1.2 建模目標約束

機場物資供應中心選址模型的建立圍繞目標約束展開。

(1)費用約束

在選擇機場物資供應中心時，使其到地區物流中心與到機場的運輸總成本最小。

(2)距離約束

選擇各機場物資供應中心到機場運輸貨物的總距離在滿足條件時,同時需要滿足距離最短原則。

(3)容量約束

考慮選擇供應中心的物資供應量應大于機場的物資需求量，保證機場物資使用時不受供應量的限制。

(4)需求分配

要求每個機場對應一個供應中心，一個供應中心可對應多個機場。

2 選址模型建立與求解

建模的思路采用階段選址的方法，首先采用Voronoi圖確定備選點初始位置，然后重心法確定備選點的位置時，需要滿足每個組的機場與機場物資供應中心可變成本最小。為了進一步減少重心法帶來的誤差，基于重力p-median模型從備選點中選取合適的機場位置，采用改進的免疫優化算法進行求解，確定符合目標約束的選址位置。

2.1 選址備選點位置確定

由于重心法求解時精度不夠，因此首先采用Voronoi確定備選點初始位置。采用Voronoi圖對機場群進行不同區域劃分，并求出不同區域的備選位置。Voronoi圖由一組連接兩相鄰點直線的垂直平分線組成的連續多邊形組成，具有以下特點：在構網時，總是選擇最鄰近的點形成三角形且不與約束線段相交；在一個Voronoi區域內的所有點到此區域內控制點的距離比到其他任何一控制點的距離都近。因此，選擇Voronoi圖作為機場物資供應中心選址的理論基礎。Voronoi圖原理見圖2。

圖2 Voronoi 圖Fig.2 Voronoi diagram

假設二維空間上存在q(q≥2)個互異的點，其幾何表示為G={g1,g2,…,gq}∈R2,二維空間上任意一點r到點gf的歐式距離記為d(r,gf),則Voronoi圖的數學表達式為：

V(gf)={r∈R2|d(r,gf)≤d(r,gh)}

(1)

式中h=1,2,3,…,f-1,f+1,…,q。

選擇對偶生成法生成Voronoi圖，步驟為：

步驟1：在圖上利用機場位置點構建Delaunay三角網，對各三角形進行編號，并記錄其構成的三個機場點；步驟2：利用三點畫圓找到各三角形的外接圓圓心，計算坐標；步驟3：遍歷三角形鏈表，將相鄰三角形外心連接，遍歷結束后生成以每個三角形頂點為生成元的多邊形網，即所需Voronoi圖。

根據Voronoi圖性質可將Voronoi圖內所有區域控制點選為該區域的備選點，記錄備選點坐標。以其中一個三角形機場組為例，Voronoi圖控制點求法如下：以控制點為對應三角形外接圓圓心，該點到圓心各頂點距離相等的性質求解。公式如下：

(2)

(3)

式中，(x1,y1)，(x2,y2)，(x3,y3)為機場坐標，待求坐標(x,y)為重心法求解初始坐標。

2.2 基于重力p-median模型的選址優化

2.2.1 重心法確定備選點

重心法選址是利用物理學中求解一個二維封閉圖形重心的原理來解決選址問題的方法。在平面選址問題中，將Voronoi圖三角形頂點各機場的物資需求量視為物體的重量，考慮運輸過程中的運費，求得區域重心點，即重心備選點。

重心法求解過程如下：

(4)

(5)

式中，U為運輸總距離，wl為各機場物資需求量，dl為重心備選點到第l個機場的距離。

通過求二元函數極值點得出重心備選點坐標，即令?U/?x=0,?U/?y=0求得相應解。

(6)

(7)

通過迭代得到公式(8)～(9)：

(8)

(9)

求解時需要用迭代重心法求出最優解。迭代重心法計算步驟如下：

步驟1：將式(6)～(7)聯立求得的備選點坐標代入式(8)～(9)得到需要求的坐標(x′,y′),代入公式(4)中求得費用值；步驟2：為保證得到的解是全局最優初始解，將步驟1中坐標(x′,y′)代入式(8)～(9)中，求得(x″,y″)，再次代入式(4)中，以此方法迭代求解，直到所求費用值為最小的(x*,y*)；步驟3：記錄所求坐標(x*,y*)，以待進一步求解。

2.2.2 重力p-median模型的選址建模

假設采用重心法求出物資供應中心備選點集合為P={pi|pi=(λi,φi),i=1,2,…,n)，pi為各備選點，i為數目，n為備選點總數，λi、φi為優化求解得到的坐標，本文通過建立重力p-median模型對備選點進行優化。

重力p-median模型的基本理論可以抽象描述為在n個可能的地點中選取p個地點建立機場物資供應中心，使得機場集合與備選點集合之間的相對距離之和最小，并對其進行分配。其核心問題是p-median算法。該算法的基本原理為假設一個圖的所有結點為潛在可用結點，模型優化的目標為找出一個結點的集合，使未選中的節點與已選中最近的結點的目標值達到最小。為了使得運輸總成本最小，需要考慮貨物在運輸過程中的成本，貨物運輸主要采用公路運輸方式，汽車運輸成本的主要項目有：(i)車輛直接費用：外購燃料費用、輪胎費用、公司職工工資、職工福利費用、固定資產折舊費用、固定資產修理費用、養路費用、公路運輸管理費用、車輛保險費用、事故費用、應交稅金、其他費用。(ii)運營間接費用：固定成本費用、每車每公里變動成本費用、每噸每公里變動成本。根據一般運價成本規則，運輸總成本可以表示為如下的形式:

(10)

式中，c表示物資運輸總成本，sij表示每年進行物資運輸所產生的不變成本，gij表示按照運輸每公里每噸進行折算所需要的成本，wi表示第i個機場物資需求量，tij為機場j和備選點i之間的相對距離。

建模求解的目標是使每年的物資運輸總成本達到最小，運輸總成本由可變運輸總成本和固定運輸總成本組成，由于每年的固定運輸總成本是不變的，為了簡便計算，只需要計算可變運輸總成本即可。屬于可變成本的是外購燃料費用、應交稅金、其他費用，物資運量，運輸距離；屬于不變成本的是公司職工工資、職工福利費用、固定資產折舊費用、固定資產修理費用、養路費用、公路運輸管理費用、車輛保險費用。

確定約束條件：

(i)總目標：三級運輸總成本最小；

(ii)供應約束：從區域物流中心向各機場物資中心的供應總量總和小于其總供應能力；

(iii)需求約束：從各機場物資中心供應地向各機場供應量應滿足其需求量；

(iv)映射約束：一個機場只能與一個機場物資中心對應；

(v)分配約束：需求節點可以被指派到相應的候選節點；

(vi)個數約束：允許建立機場物資中心為r個；

(vii)0-1約束：指定相應變為為0-1變量。

重力p-median模型如公式(11)所示：

(11)

(12)

(13)

(14)

約束條件:

(15)

(16)

fij≤qj,i=1,2,…,n;j=1,2,…,m

(17)

(18)

fij,qj∈{0,1}

(19)

式中：rij表示機場i選址機場物資供應點j的概率；β表示重力模型中的距離衰減參數；m表示機場總數；Di表示機場的需求規模；Sj表示機場物資供應中心的吸引力，吸引力根據該機場的客貨吞吐量來確定；U(p)表示機場物資供應中心到機場的總距離；hij表示機場i選址機場物資供應中心j的物資需求量；Z表示機場供應中心到機場的可變運輸總成本；wj表示第j個機場物資供應中心供應量；qj表示決策變量。

目標函數(14)表示機場供應中心到機場的可變運輸總成本最小；式(15)保證一個機場只能接收最近的一個機場物資備選點的供應；式(16)保證機場物資供應中心的供應量滿足機場的需求量；式(17)保證機場可以被指派到相應的備選點；式(18)表示備選點為p個；式(19)保證控制變量fij、qj取值范圍為0或1。

2.2.3 模型求解

本文利用免疫優化算法求解重力p-median模型，該算法經過“初始種群產生—評價標準計算—種群間個體信息交換—新種群產生”的循環過程能獲得較大概率的問題最優解。

步驟如下：

步驟1：初始抗體群產生由記憶單元和保留種群組成。保留種群隨機生成，記憶單元生成方式舉例如下：設有10個備選點，用數字1～10標號表示。以0-1代碼表示是否選擇該備選點，代碼所在位置為該機場位置，圖3表示選擇備選點3、7、9為所需備選點。

圖3 單個抗體表示舉例 Fig.3 Examples of individual antibodies

步驟 2: 計算抗體與抗原間親和力，設計親和力函數 A v 如式( 20) 所示;

(20)

(21)

步驟3:選擇親和力較高的抗體形成新的抗體群，計算新抗體群中抗體濃度Cv。即計算群體中相似抗體所占比例；Sv,s為抗體間親和度，kv,s為抗體v與抗體xj中相同的位數；L為抗體長度。

(22)

(23)

(24)

步驟4：利用親和力濃度和抗體濃度組成期望繁殖概率Pv，采用輪盤賭機制的方法，對新抗體群進行選擇。

(25)

步驟5：對個體利用式(20)期望繁殖概率Pv進行選擇。

步驟6：隨機選擇變異位進行變異。

步驟7：選擇已變異的抗體中親和度高的個體組成記憶庫，將父代個體中親和度低的個體淘汰，重新生成下一代種群。

步驟8 以進化代數作為終止條件，判斷是否終止。若滿足終止條件，則終止程序，輸出結果；否則轉步驟2。

2.2.4 免疫優化算法的改進

本文提出以可變運輸總成本作為目標函數，在改進的免疫優化算法中，對親和力函數進行改進，并在程序編程過程中，考慮了各機場與機場物資供應中心的重力的因素。免疫優化算法對機場與機場物資供應中心的可變運輸總成本，和機場物資供應中心與地區物資供應中心的可變運輸成本進行優化，從備選的機場物資供應中心點中選取總的可變運輸成本最小的位置點。

3 算例分析

3.1 問題描述

為解決某地區機場物資運輸的問題，提高機場物資保障能力，需要在某地區依托地區物流中心新建機場物資供應中心。在資金允許的情況下，經過財務預算，建造機場物資供應中心所需費用，最多能夠修建3個機場。同時經過論證以后，需要3個機場能夠保證本地區的機場物資的供應。因此新建3個機場物資供應中心以滿足某地區內所有支線機場的物資供應，需要找出3個最優位置，保證可變運輸總成本達到最小。已知某地區區域物流中心和機場物資供應中心的相對位置坐標，如圖4所示。

圖4 區域機場及物流中心位置圖 Fig.4 Location map of regional airports and logistics centers

假設某地區不同機場所需年均物資量數據及機場相對坐標如表1所示。

表1 重心坐標計算表Table1 Table of center of gravity coordinate calculation

3.2 基于Voronoi圖確定備選方案

利用Voronoi圖對該區域機場群進行劃分，得到不同機場組。在圖上作出對偶元Delaunay三角網及每個三角形對應中垂線，形成以每一三角形頂點為生成元的多邊形網，生成Voronoi圖見圖5。

圖5 機場區域Voronoi圖Fig.5 Voronoi diagram of airport area

采用式(2)～(3)計算各重三角形內切圓圓心點坐標，為重心法初始坐標，將初始坐標記錄于表2備選點坐標。

表2 備選點坐標表Table 2 Alternate point coordinate

將所求的備選點坐標作為重心法求解的初始坐標，代入式(8～9)，進行多次迭代求解，直到所求得坐標使得式(14)取得最小值，將所求得坐標記錄于表3。

表3 重心備選點坐標Table 3 Barycenter alternate point coordinate

3.3 建立重力p-median模型求解分配方案

3.2中求出的備選點個數為9個，則本節問題變為從9個備選點中選擇3個，并分配給機場。從區域物流中心向機場物資供應中心發送貨物，由3個機場物資供應中心向9個機場運輸貨物。

本文依據2.2中p-median模型進行選址建模處理，對1.2中建模目標約束進行求解。具體約束條件如下：

(26)

(27)

(28)

(29)

fji≤qj,(i=1,2,…,9;j=1,2,…,10)

(30)

(31)

fji,qj∈{0,1},(i=1,2,…,9;j=1,2,…,10)

(32)

式中，T表示地區物流中心總運輸量，d0i表示地區物流中心到物資中心i的距離，wi表示第i個物資中心接收物資量；dij表示第j個物資中心到第i個機場的距離。

3.4 算法求解重力p-median模型

針對本文運用的改進的免疫優化算法，采用Matlab編程。在計算中取種群規模為50，記憶庫容量為10，迭代次數為100，交叉概率為0.5，變異概率為0.4，多樣性評價參數為0.95，將相關數據代入后得到最優選址結果及相應分配方案，見圖6。圖7為免疫算法收斂曲線。

注：0點代表地區物流中心;1～9 代表機場; f、g、h 代表機場物資供應中心。圖6 物資供應中心位置點及分配方案Fig.6 Location and distribution plan of material supply center

圖7 免疫算法收斂曲線Fig.7 Immune algorithm convergence curve

改進的免疫優化算法得出的結果能夠避免出現局部最優的情況，可以有效地避免算法早熟的現象，保證了機場與機場物資供應中心的可變運輸成本和機場物資供應中心與地區物流中心的可變運輸總成本達到最小。由圖7可知，在40代以后種群的最優適應度和平均適應度接近平穩。由圖6可知，最優選址方案為f(562.39，414.96),g(424, 478)，h(169.56, 301.02)。機場物資供應中心f負責機場 1,2,8,9 物資的供應，機場g負責機場3、4 的供應，機場物資供應中心h負責機場 5、6、7 的供應。機場物資供應中心位置及對應機場如表4所示。

表4 重力p-median模型計算結果Table 4 Calculation result of the gravity p-median model

4 結論

本文采用重力p-median模型在某地區選出最優的3個配送點，得出以下結論：

(1)考慮了機場物資供應中心的吸引力，地區物流中心-支線機場物資供應中心-機場三者的運輸費率等實際因素，保證了優化結果與實際相符合。

(2)運用了改進的免疫優化算法，優化了目標函數，從地區物流中心-支線機場物流中心-機場三者之間的對應關系出發，進行優化。與以往單純只考慮配送中心與需求點的關系相比，保證了可變運輸總成本最小，也使得運輸總成本最小。

(3)從優化后的結果可以看出，從3個點選出的其中1個點實際上是其中1個機場的位置，說明了此機場吸引力較大，物資需求量較大，因此機場物流中心選在此位置，既減少了運輸距離，降低了成本，又提高了運輸效率。