裝備保障多配送中心連續選址模型及其算法研究

王莉莉，陳云翔，劉 闊，王 政

（1.空軍工程大學 裝備管理與安全工程學院，陜西 西安 710051；2.國網南陽供電公司，河南 南陽 473000；3.94672部隊，江蘇 南京 211100）

0 引 言

裝備配送中心是裝備保障力量的重要組成部分，平時是軍隊戰備訓練物資的儲備、供應基地，戰時擔負軍隊裝備、彈藥、器材的供應保障任務，加強裝備保障配送中心建設，提高裝備供應保障能力，對保持部隊持續作戰能力和作戰勝利起著至關重要的作用。在整個裝備供應網絡中，配送中心[1]作為裝備周轉、分揀、庫存管理和流通加工的據點，能克服裝備在運輸過程中產生的時間和空間障礙，保證裝備滿足不同作戰單位的需求。好的裝備保障配送方案，不僅能夠節約物流成本，提高裝備運輸速度，而且還可以實現裝備保障的系統化、集成化、庫存結構合理化、裝備儲備數量科學化。

由于裝備保障范圍內的路網結構密集，且配送中心選址目標區域是一個連續的平面區域[2]，可能選址位置的數量是無限的，配送中心與配送中心之間的距離一般通過在地圖上直接測量可以得到，處理方便。因此，這里推薦使用連續選址方法[3]進行裝備保障配送中心的選址。一般情況下，裝備保障配送中心選址通常是以總配送費用最少為目標函數建立選址模型，而戰爭中呈現出的高消耗性和高時效性等特點，使得裝備保障配送中心的選址不僅要滿足總配送費用最小外，還必須滿足配送時效性的要求。同時，為了減小裝備保障配送中心在戰時受攻擊的概率，實現配送中心安全、可靠的要求，裝備保障配送中心選址必須根據敵方火力的攻擊能力確定出安全性約束條件。

1 裝備保障多配送中心選址的基本程序（如圖1所示）

圖1 裝備保障多配送中心選址的基本程序[4]

2 裝備保障多配送中心連續選址模型

2.1 基本假設

給定某戰區，在此區域內分布著執行不同任務的作戰單元，要求在此區域內擬建一定數目的裝備保障配送中心，為多個需求地提供作戰物資配送服務，選址的總原則[5]是盡量使選出地址上建立的配送中心與各需求地的總配送費用最小，總配送時間最少。基本假設如下：（1）運費是運輸量、運輸距離的函數；（2）一個需求地僅有一個配送中心供應；（3）配送中心容量可以滿足需求；（4）各需求點的需求量已知；（5）需求地在整個裝備物流系統中權重不同，在配送過程中考慮先配送權重大的需求地；（6）用地理坐標求出的裝備保障配送中心和裝備器材、彈藥需求地的距離作為模型中配送中心和需求地之間的計算距離，不考慮之間實際里程。

2.2 根據費用最小確定多配送中心位置

（1）基本假設

Cyij表示裝備保障配送中心i向需求地j供應過程中的總運輸費用；（xj, yj）表示需求地j的位置坐標；（Xi,Yi）表示裝備保障配送中心i的位置坐標；dij表示裝備保障配送中心i到需求地j的距離；Dj表示需求地j的最大允許配送距離；m表示需求地數；n表示裝備保障配送中心數；q表示運輸方式數；bijq表示不同運輸方式下裝備保障配送中心i和需求地j之間單位距離、單位物資運輸費（bij1：航空運費，bij2：鐵路運費，bij3：公路運費，bij4：水運費）；wijq表示以運輸方式q將裝備從配送中心i運到需求地j的運輸量；aij表示從配送中心i到需求地j的單位距離運輸費；pj表示需求地j的需求量；Zij為0、1變量，表示需求地j是否由設置于點i的配送中心供應；y=e（x）表示約定的火力打擊范圍；（xa1, ya1）表示裝備保障配送區域的起始點坐標；（xa2, ya2）表示裝備保障配送區域的終止點坐標。

（2）選址模型

模型的目標函數為：

2.3 根據時間最短確定多配送中心位置

（1）基本假設

Tyij表示從配送中心i向需求地j的運輸時間之和；（Xi,Yi）表示裝備調配保障配送中心i的位置坐標；dij表示裝備調配保障配送中心i到需求地j的距離；Dj表示需求地j的最大允許配送距離；m表示需求地數；n表示裝備調配保障配送中心數；q表示運輸方式數（航空，鐵路，公路，水運）；vijq表示配送中心i到需求地j每一段路程中，不同運輸方式的運輸速度；γijq表示從配送中心i到需求地j的運輸過程中，每一段路程的相對難易程度；fijq表示每種運輸方式在從配送中心i到需求地j的路程中所占的比例；λj表示需求地的權重；Zij為0、1變量，表示需求地j是否由設置于點i的配送中心供應；y=e（x）表示約定的火力打擊范圍；（xa1, ya1）表示裝備調配保障配送區域的起始點坐標；（xa2, ya2）表示裝備調配保障配送區域的終止點坐標。

（2）選址模型

模型的目標函數為：

3 裝備保障多配送中心連續選址模型的求解

配送中心的連續選址問題可以看作一個多源Weber問題。該問題假設配送中心沒有容量限制，任何一個需求地的需求量都由離它最近的配送中心滿足。Cooper[6]已證明該問題的目標函數既不是凸函數也不是凹函數，有可能存在許多局部最優解，因此對于大規模的連續選址問題，多采用啟發式算法。多配送中心連續選址不但要同時確定多個配送中心地址，還要確定每個配送中心服務分配方案，所以又稱為連續選址分配問題[7-8]。目前對連續性選址模型的求解方法[9-10]一般以重心法為基礎進行計算，但是在選址中由于存在較多局部解，用常規算法很難得到最優解，因此能夠找到一種進行全局優化的方法顯得尤為重要[11]?；谶@種考慮，以費用最小的配送中心選址模型為例，本文分兩步求解[12]選址模型，第一步，暫時不考慮時效性約束（4）和安全性約束（6），僅從節省費用的角度出發，用目標函數（1）和約束條件（2）、（3）、（5）進行選址計算，確定每個配送中心所服務的需求地集合，用服務分配矩陣來描述。第二步，考慮時效性約束條件（4）和安全性約束條件（6），用MATLAB優化函數分別對每個配送中心進行選址計算，確定最終符合經濟性、時效性和安全性約束的選址方案。

3.1 交替分配啟發式算法

根據提供的n個配送中心地址（X1,Y1）,（X2,Y2）, …,（Xn,Yn）確定離每個需求地最近的配送中心為該需求地供應裝備，形成n個配送區域，每個區域可表述為如下的需求地集合：

要求總費用最小，則對Xi、Yi求偏導，令其為0。

由式（13）可以求得區域Qi內最優配送中心地址的坐標（X*i,Y*i）。

利用式（14），假設一個初始解（x0i,y0i），把（Xki,Yki）代入式（14）、（15）和（16）中，計算出裝備保障配送中心的改善地址（Xki+1,Yki+1）。當相繼得出的解（Xki,Yki）和（Xki+1,Yki+1）充分接近時，既可停止計算，（Xki+1,Yki+1）便是i個配送中心作為單一新增配送中心的最優解。

一個有確定值的二進制數矩陣（lij）m×n就代表一種備選的服務分配方案，但是由于備選方案總共有S（n,m）種當m、n數變得較大時，備選方案的數目可能非常大，因此，構造出交替分配啟發式算法，確定裝備保障配送中心連續選址的服務分配矩陣，具體步驟如下：

（1）將n個服務對象任意分成m個組，每個組有一個配送中心負責送貨，從而初步確定服務分配矩陣S，S=（lij）m×n。

（2）按式（14）、（15）和（16）進行迭代計算，直到充分接近為止，求出配送中心的坐標，計算總配送費用。

（4）重復第2和3兩步運算過程，直到所有服務對象都劃歸到為總配送費用最少的裝備保障配送中心負責供貨為止。此時，方案最佳，各配送中心地址為最優地址，總配送費用最小。

3.2 考慮時效性和安全性約束的模型求解

本文同時考慮經濟性、時效性和安全性的選址模型是一個有約束非線性規劃的問題，可以借助MATLAB優化工具箱中的fmincon（）函數進行選址計算。

目標函數：

時效性約束：

安全性約束：

選址坐標的上下限：

fmincon（）函數調用格式[13]為：［x,fval］=fmincon（@fun,x0,A,b,Aeq,beq,bl,ul,@con,@eon）

x是輸出的選址結果，fval是輸出目標函數值，即最小配送費用。fun是用MATLAB語言編寫的目標函數M文件，con是用MATLAB語言編寫的時效性約束M文件，eon是用MATLAB語言編寫的安全性約束M文件。bu、ul分別是配送中心坐標取值的上限下限，A、b、Aeq、beq為空集。x0為初始可行解。初始可行解是尋優搜索的起點位置，本文把它定位在配送區域中心位置，令：

最后，把上述M文件和輸入參數一起代入fmincon（）函數中，很快輸出選址結果［X,Y ］，如果無解，則應該增加配送中心數量，以滿足裝備保障配送的時效性和安全性要求。

4 結論

本文結合我軍裝備保障的現狀以及未來擔負的主要作戰任務和可能的作戰環境，對裝備保障多配送中心的連續選址問題進行了分析與討論，以經濟性為目標函數，以時效性和安全性為約束條件，給出了裝備保障多個配送中心連續選址模型。由于多配送中心連續選址不但要同時確定多個配送中心地址，還要確定每個配送中心服務分配方案，所以，本文利用交替分配啟發式算法對模型進行求解，把多個配送中心連續選址問題轉化為單個配送中心連續選址問題，最后再運用MATLAB優化工具箱中的fmincon（）函數對每個配送中心的地址進行計算，得到最優配送中心地址。本文提出的算法已為我軍某作戰方向的裝備器材彈藥配送網絡規劃所借鑒，能夠有效解決裝備保障選址中的時效性和安全性約束問題，結果符合實際要求。

[1] 汝宜紅，田源，徐杰.配送中心規劃[M].北京：北方交通大學出版社，2002:10-46.

[2] Chen P C,Hansen P,Jaumard B,et al.Solution of the multisource Weber and conditional Weber problems by d.-c.programming[J].Operation Research,1998,46(4):548-566.

[3] Goldengorin B,Ghosh D,Sierksma G.Branch and peg algorithms for the simple plant location problem[J].Computer&Operations Research,2003,30(7):967-981.

[4] 甘應愛.運籌學[M].（修訂版）.北京：清華大學出版社，2000:2-38.

[5] 劉志勇.空軍裝備保障配送中心選址研究[D].西安：空軍工程大學，2003:18-20.

[6] Cooper L.Location-allocation problem[J].Operation Research,1963,11(1):331-343.

[7] 宋柏.物流系統多個倉庫的定點決策方法[J].集裝箱化，2000(10):9-12.

[8] 郭曉峰，鄭隸華，葉耀華.基于最優配送線路的選址方法研究[J].物流技術，2001,109(4):28-30.

[9] Drezner T.Location of multiple retail facilities whit limited budget constraints-in continuous space[J].Journal of Retailing and Consumer Services,2000(3):173-184.

[10] 龔延成，郭曉汾，蔡團結,等.物流配送點選址模型及其算法研究[J].中國公路學報，2003,16(2):123-126.

[11] 姜大立，楊西龍.易腐物品配送中心連續選址模型及其遺傳算法[J].系統工程理論與實踐，2003(2):62-67.

[12] 龔延成.帶時效性約束的配送中心多源選址問題研究[J].數學的實踐與認識，2007,37(11):27-31.

[13] 蘇金明，阮沈勇.MATLAB6.1實用指南[M].北京：電子工業出版社，2002.