朱 昱 張 健 杜 波 王 磊 張 詩(shī)

(1.解放軍后勤學(xué)院 北京 100858)(2.海軍裝備部飛機(jī)辦公室 北京 100071)(3.海軍裝備部綜合計(jì)劃部 北京 100841)(4.海軍航空工程學(xué)院 煙臺(tái) 264001)

?

艦船保障物資優(yōu)化分配方法研究*

朱 昱1張 健2杜 波3王 磊4張 詩(shī)4

(1.解放軍后勤學(xué)院 北京 100858)(2.海軍裝備部飛機(jī)辦公室 北京 100071)(3.海軍裝備部綜合計(jì)劃部 北京 100841)(4.海軍航空工程學(xué)院 煙臺(tái) 264001)

論文針對(duì)實(shí)際應(yīng)用中艦船保障物資分配的需求,提出了動(dòng)態(tài)態(tài)勢(shì)物資分配優(yōu)化方法,建立了動(dòng)態(tài)態(tài)勢(shì)物資分配優(yōu)化數(shù)學(xué)模型,即混合0-1整數(shù)規(guī)劃模型并提供了求解策略。同時(shí)利用項(xiàng)目管理方法,提出了保障物資分配項(xiàng)目實(shí)施方案的優(yōu)化流程。

艦船保障物資; 優(yōu)化分配; 方法研究

Class Number TP393

1 引言

艦船保障物資優(yōu)化分配方法通常采用固定態(tài)勢(shì)物資分配優(yōu)化方法。事實(shí)上,在艦船保障物資優(yōu)化分配中,經(jīng)常出現(xiàn)保障物資供應(yīng)點(diǎn)位置固定,但作戰(zhàn)單位位置不確定的情況。本文針對(duì)這一類(lèi)動(dòng)態(tài)態(tài)勢(shì)物資優(yōu)化分配問(wèn)題,建立相應(yīng)的優(yōu)化模型并進(jìn)行求解,得到其最優(yōu)解或準(zhǔn)最優(yōu)解,達(dá)到優(yōu)化艦船物資分配的目的。

2 固定態(tài)勢(shì)物資分配優(yōu)化方法

艦船保障物資優(yōu)化分配需要綜合考慮作戰(zhàn)單位需求程度的優(yōu)先級(jí)、作戰(zhàn)單位的可到達(dá)性等多方面問(wèn)題。固定態(tài)勢(shì)物資分配優(yōu)化方法(即單供應(yīng)點(diǎn)多作戰(zhàn)單位物資分配優(yōu)化方法和多供應(yīng)點(diǎn)多作戰(zhàn)單位物資分配優(yōu)化方法)作為一種物資分配形式在和平時(shí)期使用得較為廣泛。

2.1 單供應(yīng)點(diǎn)多作戰(zhàn)單位分配策略

單供應(yīng)點(diǎn)多作戰(zhàn)單位是常見(jiàn)的一種物資分配形式(其結(jié)構(gòu)圖如圖1所示)[1～2]。適用于和平時(shí)期艦船保障物資的分配,其分配原則一方面主要是按照作戰(zhàn)單位的需求迫切程度由急到緩進(jìn)行分配(如圖2所示)[3～4]。另一方面對(duì)于同一作戰(zhàn)單位,需比較該單位物資需求量和供應(yīng)點(diǎn)剩余的物資量:如果前者小于后者,表示剩余物資量充足,作戰(zhàn)單位的需求將全部得到滿(mǎn)足;如果前者大于后者,表示剩余物資量不足,此時(shí)應(yīng)使用基于最小方差原則的資源公平分配模型,使得單位資源滿(mǎn)足需求的偏差最小化。

圖1 單供應(yīng)點(diǎn)多作戰(zhàn)單位分配結(jié)構(gòu)圖

圖2 基于需求迫切程度優(yōu)先的分配示意圖

2.2 多供應(yīng)點(diǎn)多作戰(zhàn)單位分配策略

多供應(yīng)點(diǎn)多作戰(zhàn)單位的分配方式可在較短的時(shí)間內(nèi)完成物資的分配,具有較高的分配效率,特別是在艦船保障物資優(yōu)化的分配過(guò)程中,保障基地有多個(gè)供應(yīng)點(diǎn),且前方有多個(gè)作戰(zhàn)單位,任一供應(yīng)點(diǎn)到任一作戰(zhàn)單位的距離是已知的,要求盡量縮短各供應(yīng)點(diǎn)到各作戰(zhàn)單位配送的時(shí)間,使得各個(gè)作戰(zhàn)單位得到物資的總體滿(mǎn)意度最大[5～6]。其結(jié)構(gòu)示意圖和分配示意圖分別如圖3、圖4所示[7～8]。

圖3 多供應(yīng)點(diǎn)多作戰(zhàn)單位分配結(jié)構(gòu)圖

圖4 多供應(yīng)點(diǎn)多作戰(zhàn)單位分配示意圖

在和平時(shí)期,固定態(tài)勢(shì)物資分配優(yōu)化方法是一種較為常用的分配方法。但在實(shí)際使用上,經(jīng)常出現(xiàn)保障物資供應(yīng)點(diǎn)位置固定,但作戰(zhàn)單位位置不確定的情況。特別是戰(zhàn)時(shí),如幾艘不同的艦船分別在不同海域執(zhí)行任務(wù),由于任務(wù)要求,需要靠碼頭進(jìn)行物資補(bǔ)給,由于返航時(shí)間不盡相同,艦船選擇停靠的碼頭也不一定相同,這對(duì)物資分配優(yōu)化提出了新的需求。

3 動(dòng)態(tài)態(tài)勢(shì)物資分配優(yōu)化方法

3.1 動(dòng)態(tài)態(tài)勢(shì)物資分配優(yōu)化模型

3.1.1 物資分配路徑模型建立

針對(duì)具體問(wèn)題,首先建立供應(yīng)點(diǎn)和保障點(diǎn)路徑模型。

圖5 供應(yīng)點(diǎn)和保障點(diǎn)路徑模型

1) 供應(yīng)點(diǎn)與供應(yīng)點(diǎn)之間車(chē)輛運(yùn)輸時(shí)間

表1 供應(yīng)點(diǎn)與供應(yīng)點(diǎn)之間車(chē)輛運(yùn)輸時(shí)間

2) 供應(yīng)點(diǎn)與補(bǔ)給點(diǎn)之間的車(chē)輛運(yùn)輸時(shí)間

表2 供應(yīng)點(diǎn)與補(bǔ)給點(diǎn)之間的車(chē)輛運(yùn)輸時(shí)間

3) 補(bǔ)給點(diǎn)與補(bǔ)給點(diǎn)之間的航行時(shí)間

表3 補(bǔ)給點(diǎn)與補(bǔ)給點(diǎn)之間的航行時(shí)間

4) 艦船與補(bǔ)給點(diǎn)1之間最短航行時(shí)間

艦船與補(bǔ)給點(diǎn)1之間的最短航行時(shí)間為:T4,11,T4,12,…,T4,1n,…,T4,1N。

以上航行時(shí)間和車(chē)輛行駛時(shí)間均視為已知量。

3.1.2 庫(kù)存模型及需求模型建立

1) 庫(kù)存模型

表4 供應(yīng)點(diǎn)庫(kù)存模型

2) 需求模型

表5 各艦船需求模型

3) 供應(yīng)點(diǎn)與補(bǔ)給點(diǎn)之間對(duì)應(yīng)關(guān)系模型

表6 供應(yīng)點(diǎn)與補(bǔ)給點(diǎn)之間對(duì)應(yīng)關(guān)系模型

各供應(yīng)點(diǎn)物資庫(kù)存和各艦船需求均視為已知量。Fkm=1表示第k個(gè)補(bǔ)給點(diǎn)的物資由第m個(gè)供給點(diǎn)供給;Fkm=0表示第k個(gè)補(bǔ)給點(diǎn)的物資不由第m個(gè)供給點(diǎn)供給。

3.1.3 定義優(yōu)化變量

在動(dòng)態(tài)態(tài)勢(shì)物資分配優(yōu)化分配問(wèn)題中,優(yōu)化的目標(biāo)是獲得最優(yōu)的艦船選擇補(bǔ)給點(diǎn)(碼頭)方案和各供應(yīng)點(diǎn)之間的物資調(diào)配方案,因此定義如下的優(yōu)化變量:

1) 艦船選擇補(bǔ)給點(diǎn)(碼頭)方案優(yōu)化變量

對(duì)于艦船n,定義向量

(1)

定義相應(yīng)約束條件,即xn1,xn2,…,xnk,…,xnK只能取0或1,且

(2)

其中xnk=1表示艦船n選擇第k個(gè)補(bǔ)給點(diǎn)進(jìn)行靠碼頭補(bǔ)給;反之xnk=0表示艦船n不選擇第k個(gè)補(bǔ)給點(diǎn)進(jìn)行靠碼頭補(bǔ)給。

對(duì)于N個(gè)艦船,可以定義N個(gè)類(lèi)似的向量X1,X2,…,Xn,…,XN及N組約束條件:

(3)

特別地,當(dāng)補(bǔ)給點(diǎn)數(shù)量只有2個(gè)時(shí),上述定義可以簡(jiǎn)化:艦船n只用一個(gè)未知數(shù)x即可表示對(duì)補(bǔ)給點(diǎn)的選擇結(jié)果,如x取0表示選擇補(bǔ)給點(diǎn)1,取1表示選擇補(bǔ)給點(diǎn)2。

2) 各供應(yīng)點(diǎn)之間物資調(diào)配方案優(yōu)化變量

對(duì)于供應(yīng)點(diǎn)m,定義矩陣

(4)

其中,矩陣元素ym,i,1表示第m個(gè)供應(yīng)點(diǎn)從第1個(gè)供應(yīng)點(diǎn)調(diào)配的第i種物資的數(shù)量,ym,i,2表示第m個(gè)供應(yīng)點(diǎn)從第2個(gè)供應(yīng)點(diǎn)調(diào)配的第i種物資的數(shù)量,其余類(lèi)似。

上述矩陣元素的取值可以認(rèn)為只取整數(shù)(假定物資都以整數(shù)為單位),并且不能超過(guò)庫(kù)存,即有如下約束條件:

0≤ym,1,1≤S11,0≤ym,1,2≤S21,…,0≤ym,I,M≤SMI

(5)

相應(yīng)地,對(duì)于M個(gè)供應(yīng)點(diǎn),可以定義M個(gè)矩陣Y1,Y2,…,YM,用于表示各供應(yīng)點(diǎn)物資調(diào)配數(shù)量,相應(yīng)地有M組約束條件:

0≤y1,1,1≤S11,0≤y1,1,2≤S21,…,0≤y1,I,M≤SMI

0≤y2,1,1≤S11,0≤y2,1,2≤S21,…,0≤y2,I,M≤SMI

…

0≤yM,1,1≤S11,0≤yM,1,2≤S21,…,0≤yM,I,M≤SMI

(6)

3.1.4 各補(bǔ)給點(diǎn)物資需求及各供給點(diǎn)需要提供的物資總量計(jì)算

根據(jù)艦船選擇補(bǔ)給點(diǎn)(碼頭)方案優(yōu)化變量X1,X2,…,Xn,…XN和表5所示的各艦船需求數(shù)據(jù),可以計(jì)算得到每個(gè)補(bǔ)給點(diǎn)的物資需求。

第k個(gè)補(bǔ)給點(diǎn)對(duì)第i種物資的總需求為

(7)

從而第k個(gè)補(bǔ)給點(diǎn)對(duì)各種物資的總需求Rk1,Rk2,…,RkI也可以計(jì)算得到。

由于補(bǔ)給點(diǎn)和供給點(diǎn)之間的對(duì)應(yīng)關(guān)系已經(jīng)確定,故與第k個(gè)補(bǔ)給點(diǎn)對(duì)應(yīng)的供給點(diǎn)的物資總需求也可以確定。

(8)

故第m個(gè)供應(yīng)點(diǎn)需要提供各種物資的總量RFm1,RFm2,…,RFmI也可以計(jì)算得到。

3.1.5 供應(yīng)點(diǎn)之間物資調(diào)配約束條件

當(dāng)?shù)趍個(gè)供應(yīng)點(diǎn)的第i種物資庫(kù)存滿(mǎn)足對(duì)應(yīng)的補(bǔ)給點(diǎn)需求時(shí),不需要從其它供應(yīng)點(diǎn)進(jìn)行物資調(diào)配,只有第m個(gè)供應(yīng)點(diǎn)的第i種物資庫(kù)存不滿(mǎn)足對(duì)應(yīng)的補(bǔ)給點(diǎn)需求時(shí),才需要從其它供給點(diǎn)進(jìn)行物資調(diào)配,因此有如下約束條件:

(9)

對(duì)于I種物資,有I組約束條件,即

…

(10)

對(duì)于M個(gè)供應(yīng)點(diǎn),有M×I組約束條件,即

…

…

…

…

(11)

3.1.6 艦船航行及物資調(diào)配總成本計(jì)算

定義艦船每小時(shí)航行成本系數(shù)為c1,車(chē)輛每小時(shí)運(yùn)輸成本系數(shù)為c2,假定每個(gè)單位的物資都可以裝滿(mǎn)1車(chē),根據(jù)3.1.1～3.1.5的模型及變量定義,可以計(jì)算總成本。

1) 艦船航行成本

(12)

2) 供應(yīng)點(diǎn)之間物資調(diào)配運(yùn)輸成本

(13)

3) 供應(yīng)點(diǎn)向補(bǔ)給點(diǎn)運(yùn)輸成本

(14)

故總成本為

C=C1+C2+C3

(15)

3.2 混合0-1整數(shù)規(guī)劃模型及求解

綜合3.1.1～3.1.6的模型,可以得到式(16)的動(dòng)態(tài)態(tài)勢(shì)物資分配優(yōu)化數(shù)學(xué)模型。由于優(yōu)化變量取值范圍均為整數(shù),且部分變量只能取0或1,因此這是混合0-1整數(shù)規(guī)劃。

對(duì)于混合0-1整數(shù)規(guī)劃的求解,在優(yōu)化變量維數(shù)不太大的情況下,可以采用隱枚舉法結(jié)合分枝定界法求解,當(dāng)優(yōu)化變量維數(shù)很大的情況下,計(jì)算量將呈指數(shù)增加,耗時(shí)較長(zhǎng),這時(shí)可以采用遺傳算法、粒子群算法等優(yōu)化算法進(jìn)行求解[9～10]。對(duì)于隱枚舉法結(jié)合分枝定界法求解,可以通過(guò)Matlab編程實(shí)現(xiàn),也可以通過(guò)Excel或Lingo等軟件實(shí)現(xiàn)[11～13]。隱枚舉法求解混合0-1整數(shù)規(guī)劃的算法流程如圖6所示。

(16)

3.3 基于項(xiàng)目管理方法的實(shí)施方案優(yōu)化

根據(jù)3.1的物資分配優(yōu)化模型及3.2的混合0-1整數(shù)規(guī)劃模型求解后,可以得到最優(yōu)的艦船選擇補(bǔ)給點(diǎn)方案和物資供應(yīng)點(diǎn)之間的物資調(diào)配方案。這樣,動(dòng)態(tài)態(tài)勢(shì)物資分配方案最終可以確定。

確定動(dòng)態(tài)態(tài)勢(shì)物資分配方案后,可以根據(jù)項(xiàng)目管理的方法對(duì)物資分配實(shí)施方案進(jìn)行進(jìn)一步優(yōu)化,使實(shí)施方案總工時(shí)和配送運(yùn)輸資源、各艦船作業(yè)時(shí)間得到進(jìn)一步優(yōu)化。優(yōu)化流程如圖7所示。

圖6 隱枚舉法求解混合0-1整數(shù)規(guī)劃的算法流程

圖7 采用項(xiàng)目管理方法的實(shí)施方案優(yōu)化流程圖

4 結(jié)語(yǔ)

本文通過(guò)對(duì)一定條件下艦船保障物資優(yōu)化分配問(wèn)題進(jìn)行研究,得出的結(jié)論對(duì)于制定物資分配方案具有一定的參考價(jià)值。需要指出的是艦船保障物資優(yōu)化分配受到運(yùn)輸規(guī)劃、倉(cāng)儲(chǔ)管理、貨物配裝、需求預(yù)測(cè)等諸多因素的影響。因此,在實(shí)際應(yīng)用時(shí)應(yīng)綜合權(quán)衡各個(gè)因素,一方面要與定性分析密切結(jié)合,另一方面要在保障演習(xí)實(shí)踐中不斷地修正和完善。

[1] 駱義.物流配送車(chē)輛調(diào)度優(yōu)化研究[D].大連:大連海事大學(xué),2013:98-107.

[2] 袁慶達(dá),杜文.帶有時(shí)間窗的混合車(chē)隊(duì)車(chē)輛路徑問(wèn)題的模型與算法研究[J].西南交通大學(xué)學(xué)報(bào),2011(4):7-12.

[3] 張麗萍,柴躍廷,曹瑞.有時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng),2012(2):18-22.

[4] 姜大立,楊西龍,杜文,等.車(chē)輛路徑問(wèn)題的遺傳算法研究[J].系統(tǒng)工程理論與實(shí)踐,2009(6):13-18.

[5] Xu J, Kelly J. P. A network flow～based tabu search heuristic for the vehicle routing problem[J]. Transportation Science,2010(3):43-52.

[6] Hooker J. N, Natraj N. R. Solving a general routing and scheduling problem by chain declmposition and tabu search[J]. Transportation Science,2009(2):6-12.

[7] Gendreau M, Hertz A. tabu search heuristic for the vehicle routing problem[J]. Managememt Science,2012(4):33-42.

[8] 李軍.車(chē)輛調(diào)度問(wèn)題的分派啟發(fā)式算法[J].系統(tǒng)工程理論與實(shí)踐,2012(1):26-27.

[9] 冷德惠,張金梅,李大衛(wèi).遺傳算法在有時(shí)間窗車(chē)輛路徑問(wèn)題上的應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐,2010(8):17-19.

[10] 劉民.遺傳算法方法及其在生產(chǎn)線(xiàn)調(diào)度問(wèn)題中的應(yīng)用與研究[D].北京:清華大學(xué),2007.

[11] 李軍.非滿(mǎn)載車(chē)輛調(diào)度問(wèn)題的遺傳算法[J].系統(tǒng)工程理論方法應(yīng)用,2010(3):31-33.

[12] Balakfishnan N. Simple heuristics for the vehicle routing problems with soft time windows[J]. Journal of Operational Research Society,2013(3):11-12.

[13] Desrocher M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows[J]. Operations Research,2012(2):24-25.

Method of Optimized Distribution of Material Support of Ships and Warships

ZHU Yu1ZHANG Jian2DU Bo3WANG Lei4ZHANG Shi4

(1. Logistics Academy of PLA, Beijing 100858)(2. Plane Office of Naval Equipment Department, Beijing 100071)(3. Synthesizing Plans Ministry of Naval Equipment Department, Beijing 100841)(4. Naval Aeronautical and Astronautical University, Yantai 264001)

Based on the demand of material support of ships and warships allotment in practical application, an optimization method of dynamic material allotment is put forward. A mathematical model of optimization of dynamic material allotment is established. A mixed 0-1 integer programming model and solving strategies is provided. Based on the method of project management, an optimized flow of the project for implementation of material support allotment is put forward.

material support of ships and warships, optimized distribution, method study

2014年9月12日,

2014年10月27日

朱昱,女,研究方向:軍隊(duì)衛(wèi)生勤務(wù)。

TP393

10.3969/j.issn1672-9730.2015.03.031