艦船保障物資優化分配方法研究*

朱 昱 張 健 杜 波 王 磊 張 詩

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

?

艦船保障物資優化分配方法研究*

朱 昱1張 健2杜 波3王 磊4張 詩4

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

論文針對實際應用中艦船保障物資分配的需求,提出了動態態勢物資分配優化方法,建立了動態態勢物資分配優化數學模型,即混合0-1整數規劃模型并提供了求解策略。同時利用項目管理方法,提出了保障物資分配項目實施方案的優化流程。

艦船保障物資; 優化分配; 方法研究

Class Number TP393

1 引言

艦船保障物資優化分配方法通常采用固定態勢物資分配優化方法。事實上,在艦船保障物資優化分配中,經常出現保障物資供應點位置固定,但作戰單位位置不確定的情況。本文針對這一類動態態勢物資優化分配問題,建立相應的優化模型并進行求解,得到其最優解或準最優解,達到優化艦船物資分配的目的。

2 固定態勢物資分配優化方法

艦船保障物資優化分配需要綜合考慮作戰單位需求程度的優先級、作戰單位的可到達性等多方面問題。固定態勢物資分配優化方法(即單供應點多作戰單位物資分配優化方法和多供應點多作戰單位物資分配優化方法)作為一種物資分配形式在和平時期使用得較為廣泛。

2.1 單供應點多作戰單位分配策略

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

圖1 單供應點多作戰單位分配結構圖

圖2 基于需求迫切程度優先的分配示意圖

2.2 多供應點多作戰單位分配策略

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

圖3 多供應點多作戰單位分配結構圖

圖4 多供應點多作戰單位分配示意圖

在和平時期,固定態勢物資分配優化方法是一種較為常用的分配方法。但在實際使用上,經常出現保障物資供應點位置固定,但作戰單位位置不確定的情況。特別是戰時,如幾艘不同的艦船分別在不同海域執行任務,由于任務要求,需要靠碼頭進行物資補給,由于返航時間不盡相同,艦船選擇停靠的碼頭也不一定相同,這對物資分配優化提出了新的需求。

3 動態態勢物資分配優化方法

3.1 動態態勢物資分配優化模型

3.1.1 物資分配路徑模型建立

針對具體問題,首先建立供應點和保障點路徑模型。

圖5 供應點和保障點路徑模型

1) 供應點與供應點之間車輛運輸時間

表1 供應點與供應點之間車輛運輸時間

2) 供應點與補給點之間的車輛運輸時間

表2 供應點與補給點之間的車輛運輸時間

3) 補給點與補給點之間的航行時間

表3 補給點與補給點之間的航行時間

4) 艦船與補給點1之間最短航行時間

艦船與補給點1之間的最短航行時間為:T4,11,T4,12,…,T4,1n,…,T4,1N。

以上航行時間和車輛行駛時間均視為已知量。

3.1.2 庫存模型及需求模型建立

1) 庫存模型

表4 供應點庫存模型

2) 需求模型

表5 各艦船需求模型

3) 供應點與補給點之間對應關系模型

表6 供應點與補給點之間對應關系模型

各供應點物資庫存和各艦船需求均視為已知量。Fkm=1表示第k個補給點的物資由第m個供給點供給;Fkm=0表示第k個補給點的物資不由第m個供給點供給。

3.1.3 定義優化變量

在動態態勢物資分配優化分配問題中,優化的目標是獲得最優的艦船選擇補給點(碼頭)方案和各供應點之間的物資調配方案,因此定義如下的優化變量:

1) 艦船選擇補給點(碼頭)方案優化變量

對于艦船n,定義向量

(1)

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

(2)

其中xnk=1表示艦船n選擇第k個補給點進行靠碼頭補給;反之xnk=0表示艦船n不選擇第k個補給點進行靠碼頭補給。

對于N個艦船,可以定義N個類似的向量X1,X2,…,Xn,…,XN及N組約束條件:

(3)

特別地,當補給點數量只有2個時,上述定義可以簡化:艦船n只用一個未知數x即可表示對補給點的選擇結果,如x取0表示選擇補給點1,取1表示選擇補給點2。

2) 各供應點之間物資調配方案優化變量

對于供應點m,定義矩陣

(4)

其中,矩陣元素ym,i,1表示第m個供應點從第1個供應點調配的第i種物資的數量,ym,i,2表示第m個供應點從第2個供應點調配的第i種物資的數量,其余類似。

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

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

(5)

相應地,對于M個供應點,可以定義M個矩陣Y1,Y2,…,YM,用于表示各供應點物資調配數量,相應地有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 各補給點物資需求及各供給點需要提供的物資總量計算

根據艦船選擇補給點(碼頭)方案優化變量X1,X2,…,Xn,…XN和表5所示的各艦船需求數據,可以計算得到每個補給點的物資需求。

第k個補給點對第i種物資的總需求為

(7)

從而第k個補給點對各種物資的總需求Rk1,Rk2,…,RkI也可以計算得到。

由于補給點和供給點之間的對應關系已經確定,故與第k個補給點對應的供給點的物資總需求也可以確定。

(8)

故第m個供應點需要提供各種物資的總量RFm1,RFm2,…,RFmI也可以計算得到。

3.1.5 供應點之間物資調配約束條件

當第m個供應點的第i種物資庫存滿足對應的補給點需求時,不需要從其它供應點進行物資調配,只有第m個供應點的第i種物資庫存不滿足對應的補給點需求時,才需要從其它供給點進行物資調配,因此有如下約束條件:

(9)

對于I種物資,有I組約束條件,即

…

(10)

對于M個供應點,有M×I組約束條件,即

…

…

…

…

(11)

3.1.6 艦船航行及物資調配總成本計算

定義艦船每小時航行成本系數為c1,車輛每小時運輸成本系數為c2,假定每個單位的物資都可以裝滿1車,根據3.1.1～3.1.5的模型及變量定義,可以計算總成本。

1) 艦船航行成本

(12)

2) 供應點之間物資調配運輸成本

(13)

3) 供應點向補給點運輸成本

(14)

故總成本為

C=C1+C2+C3

(15)

3.2 混合0-1整數規劃模型及求解

綜合3.1.1～3.1.6的模型,可以得到式(16)的動態態勢物資分配優化數學模型。由于優化變量取值范圍均為整數,且部分變量只能取0或1,因此這是混合0-1整數規劃。

對于混合0-1整數規劃的求解,在優化變量維數不太大的情況下,可以采用隱枚舉法結合分枝定界法求解,當優化變量維數很大的情況下,計算量將呈指數增加,耗時較長,這時可以采用遺傳算法、粒子群算法等優化算法進行求解[9～10]。對于隱枚舉法結合分枝定界法求解,可以通過Matlab編程實現,也可以通過Excel或Lingo等軟件實現[11～13]。隱枚舉法求解混合0-1整數規劃的算法流程如圖6所示。

(16)

3.3 基于項目管理方法的實施方案優化

根據3.1的物資分配優化模型及3.2的混合0-1整數規劃模型求解后,可以得到最優的艦船選擇補給點方案和物資供應點之間的物資調配方案。這樣,動態態勢物資分配方案最終可以確定。

確定動態態勢物資分配方案后,可以根據項目管理的方法對物資分配實施方案進行進一步優化,使實施方案總工時和配送運輸資源、各艦船作業時間得到進一步優化。優化流程如圖7所示。

圖6 隱枚舉法求解混合0-1整數規劃的算法流程

圖7 采用項目管理方法的實施方案優化流程圖

4 結語

本文通過對一定條件下艦船保障物資優化分配問題進行研究,得出的結論對于制定物資分配方案具有一定的參考價值。需要指出的是艦船保障物資優化分配受到運輸規劃、倉儲管理、貨物配裝、需求預測等諸多因素的影響。因此,在實際應用時應綜合權衡各個因素,一方面要與定性分析密切結合,另一方面要在保障演習實踐中不斷地修正和完善。

[1] 駱義.物流配送車輛調度優化研究[D].大連:大連海事大學,2013:98-107.

[2] 袁慶達,杜文.帶有時間窗的混合車隊車輛路徑問題的模型與算法研究[J].西南交通大學學報,2011(4):7-12.

[3] 張麗萍,柴躍廷,曹瑞.有時間窗車輛路徑問題的改進遺傳算法[J].計算機集成制造系統,2012(2):18-22.

[4] 姜大立,楊西龍,杜文,等.車輛路徑問題的遺傳算法研究[J].系統工程理論與實踐,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] 李軍.車輛調度問題的分派啟發式算法[J].系統工程理論與實踐,2012(1):26-27.

[9] 冷德惠,張金梅,李大衛.遺傳算法在有時間窗車輛路徑問題上的應用[J].系統工程理論與實踐,2010(8):17-19.

[10] 劉民.遺傳算法方法及其在生產線調度問題中的應用與研究[D].北京:清華大學,2007.

[11] 李軍.非滿載車輛調度問題的遺傳算法[J].系統工程理論方法應用,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日

朱昱,女,研究方向:軍隊衛生勤務。

TP393

10.3969/j.issn1672-9730.2015.03.031