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

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

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

0 引 言

裝備配送中心是裝備保障力量的重要組成部分，平時(shí)是軍隊(duì)?wèi)?zhàn)備訓(xùn)練物資的儲(chǔ)備、供應(yīng)基地，戰(zhàn)時(shí)擔(dān)負(fù)軍隊(duì)裝備、彈藥、器材的供應(yīng)保障任務(wù)，加強(qiáng)裝備保障配送中心建設(shè)，提高裝備供應(yīng)保障能力，對保持部隊(duì)持續(xù)作戰(zhàn)能力和作戰(zhàn)勝利起著至關(guān)重要的作用。在整個(gè)裝備供應(yīng)網(wǎng)絡(luò)中，配送中心[1]作為裝備周轉(zhuǎn)、分揀、庫存管理和流通加工的據(jù)點(diǎn)，能克服裝備在運(yùn)輸過程中產(chǎn)生的時(shí)間和空間障礙，保證裝備滿足不同作戰(zhàn)單位的需求。好的裝備保障配送方案，不僅能夠節(jié)約物流成本，提高裝備運(yùn)輸速度，而且還可以實(shí)現(xiàn)裝備保障的系統(tǒng)化、集成化、庫存結(jié)構(gòu)合理化、裝備儲(chǔ)備數(shù)量科學(xué)化。

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

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

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

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

2.1 基本假設(shè)

給定某戰(zhàn)區(qū)，在此區(qū)域內(nèi)分布著執(zhí)行不同任務(wù)的作戰(zhàn)單元，要求在此區(qū)域內(nèi)擬建一定數(shù)目的裝備保障配送中心，為多個(gè)需求地提供作戰(zhàn)物資配送服務(wù)，選址的總原則[5]是盡量使選出地址上建立的配送中心與各需求地的總配送費(fèi)用最小，總配送時(shí)間最少?；炯僭O(shè)如下：（1）運(yùn)費(fèi)是運(yùn)輸量、運(yùn)輸距離的函數(shù)；（2）一個(gè)需求地僅有一個(gè)配送中心供應(yīng)；（3）配送中心容量可以滿足需求；（4）各需求點(diǎn)的需求量已知；（5）需求地在整個(gè)裝備物流系統(tǒng)中權(quán)重不同，在配送過程中考慮先配送權(quán)重大的需求地；（6）用地理坐標(biāo)求出的裝備保障配送中心和裝備器材、彈藥需求地的距離作為模型中配送中心和需求地之間的計(jì)算距離，不考慮之間實(shí)際里程。

2.2 根據(jù)費(fèi)用最小確定多配送中心位置

（1）基本假設(shè)

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

（2）選址模型

模型的目標(biāo)函數(shù)為：

2.3 根據(jù)時(shí)間最短確定多配送中心位置

（1）基本假設(shè)

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

（2）選址模型

模型的目標(biāo)函數(shù)為：

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

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

3.1 交替分配啟發(fā)式算法

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

要求總費(fèi)用最小，則對Xi、Yi求偏導(dǎo)，令其為0。

由式（13）可以求得區(qū)域Qi內(nèi)最優(yōu)配送中心地址的坐標(biāo)（X*i,Y*i）。

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

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

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

（2）按式（14）、（15）和（16）進(jìn)行迭代計(jì)算，直到充分接近為止，求出配送中心的坐標(biāo)，計(jì)算總配送費(fèi)用。

（4）重復(fù)第2和3兩步運(yùn)算過程，直到所有服務(wù)對象都劃歸到為總配送費(fèi)用最少的裝備保障配送中心負(fù)責(zé)供貨為止。此時(shí)，方案最佳，各配送中心地址為最優(yōu)地址，總配送費(fèi)用最小。

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

本文同時(shí)考慮經(jīng)濟(jì)性、時(shí)效性和安全性的選址模型是一個(gè)有約束非線性規(guī)劃的問題，可以借助MATLAB優(yōu)化工具箱中的fmincon（）函數(shù)進(jìn)行選址計(jì)算。

目標(biāo)函數(shù)：

時(shí)效性約束：

安全性約束：

選址坐標(biāo)的上下限：

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

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

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

4 結(jié)論

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

[1] 汝宜紅，田源，徐杰.配送中心規(guī)劃[M].北京：北方交通大學(xué)出版社，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] 甘應(yīng)愛.運(yùn)籌學(xué)[M].（修訂版）.北京：清華大學(xué)出版社，2000:2-38.

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

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

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

[8] 郭曉峰，鄭隸華，葉耀華.基于最優(yōu)配送線路的選址方法研究[J].物流技術(shù)，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] 龔延成，郭曉汾，蔡團(tuán)結(jié),等.物流配送點(diǎn)選址模型及其算法研究[J].中國公路學(xué)報(bào)，2003,16(2):123-126.

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

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

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