盧　昱， 陳興凱， 韓　震

(軍械工程學(xué)院裝備指揮與管理系, 河北 石家莊 050003)

戰(zhàn)時(shí)網(wǎng)絡(luò)化物資調(diào)度建模

盧昱， 陳興凱， 韓震

(軍械工程學(xué)院裝備指揮與管理系, 河北 石家莊 050003)

摘要：從物資調(diào)度網(wǎng)絡(luò)化與物資儲(chǔ)備平衡角度研究了戰(zhàn)時(shí)物資調(diào)度問題，以供應(yīng)時(shí)間、供應(yīng)成本以及運(yùn)輸路徑安全度為優(yōu)化目標(biāo)，建立了網(wǎng)絡(luò)化多目標(biāo)優(yōu)化調(diào)度模型，設(shè)計(jì)了GASA(Genetic Algorithms Simulated Annealing)分時(shí)段混合優(yōu)化調(diào)度算法，并通過實(shí)例對(duì)網(wǎng)絡(luò)化調(diào)度模型及算法的有效性進(jìn)行了驗(yàn)證，為解決戰(zhàn)時(shí)網(wǎng)絡(luò)化物資調(diào)度優(yōu)化問題提供參考。

關(guān)鍵詞：儲(chǔ)備平衡； 調(diào)度模型； GASA算法

信息化戰(zhàn)爭中物資消耗巨大，常常使前沿物資補(bǔ)給站的物資儲(chǔ)備量難以滿足作戰(zhàn)部隊(duì)的需求，因此迫切需要科學(xué)、合理地調(diào)度運(yùn)輸力量，維持各單元的物資儲(chǔ)備平衡，使前沿物資補(bǔ)給站能按時(shí)獲得物資保障。目前，已有許多學(xué)者對(duì)調(diào)度問題進(jìn)行了建模研究，如：文獻(xiàn)[1-2]作者建立了最小化任務(wù)完成時(shí)間調(diào)度模型；文獻(xiàn)[3-4]作者從維修專業(yè)角度出發(fā)，構(gòu)建了混合維修專業(yè)任務(wù)調(diào)度模型；汪濤等[5]從應(yīng)急開始時(shí)間與運(yùn)輸總費(fèi)用角度出發(fā)，建立了多目標(biāo)調(diào)度模型；任帆等[6]構(gòu)建了物資運(yùn)輸時(shí)間與物資運(yùn)輸成本整體最優(yōu)的物資調(diào)度模型。但上述研究在模型構(gòu)建上主要以運(yùn)輸時(shí)間或運(yùn)輸費(fèi)用為目標(biāo)函數(shù)，未考慮運(yùn)輸安全，且均以平時(shí)任務(wù)調(diào)度為主，也未考慮戰(zhàn)時(shí)調(diào)度的特殊性，更未考慮調(diào)度網(wǎng)絡(luò)中物資儲(chǔ)備平衡。

戰(zhàn)時(shí)物資調(diào)度是一個(gè)多目標(biāo)優(yōu)化問題，筆者從供應(yīng)時(shí)間、供應(yīng)成本以及運(yùn)輸路徑安全度3個(gè)方面，構(gòu)建了戰(zhàn)時(shí)前沿物資庫存中心向前沿物資補(bǔ)給站供應(yīng)物資的網(wǎng)絡(luò)化調(diào)度模型，旨在提出一種新的研究思路和方法，為解決物資調(diào)度優(yōu)化問題提供參考。

1調(diào)度問題描述

戰(zhàn)時(shí)，當(dāng)前沿物資庫存中心在裝備保障信息網(wǎng)絡(luò)的支持下感知到前沿物資補(bǔ)給站的物資需求信息時(shí)，即迅速組織并調(diào)度相關(guān)保障力量實(shí)施物資供應(yīng)保障，快速機(jī)動(dòng)將所需物資運(yùn)輸至指定地點(diǎn)。因此，各個(gè)保障單元及物資運(yùn)輸路徑就構(gòu)成了一個(gè)物資調(diào)度網(wǎng)絡(luò)。其中：庫存中心、補(bǔ)給站為網(wǎng)絡(luò)的節(jié)點(diǎn)，物資運(yùn)輸路徑為網(wǎng)絡(luò)的邊，設(shè)該物資調(diào)度網(wǎng)絡(luò)為G=(V,E,T,C,S)。式中：V為節(jié)點(diǎn)的集合；E為邊的集合；T為在邊上行駛的時(shí)間；C為在邊上行駛的成本；S為在邊上運(yùn)輸?shù)陌踩取?/p>

由于戰(zhàn)時(shí)作戰(zhàn)部隊(duì)所需的物資類型、數(shù)量繁多，運(yùn)輸時(shí)間緊迫，而且在運(yùn)輸過程中交通狀況復(fù)雜多變，常常會(huì)受到潛在的威脅，但物資運(yùn)輸費(fèi)用卻十分有限。根據(jù)戰(zhàn)時(shí)物資保障的任務(wù)需求，保障物資應(yīng)按一定比例分配在各個(gè)保障單元中，且在戰(zhàn)時(shí)的動(dòng)態(tài)消耗中應(yīng)保持比例不變，以實(shí)現(xiàn)物資儲(chǔ)備平衡。構(gòu)建網(wǎng)絡(luò)化調(diào)度模型旨在確定最佳物資調(diào)度方案，即在滿足相關(guān)約束條件下，維持調(diào)度網(wǎng)絡(luò)的儲(chǔ)備平衡，實(shí)現(xiàn)調(diào)度路徑行駛時(shí)間T最短、運(yùn)輸費(fèi)用C最少以及運(yùn)輸路徑安全度S最大。

2網(wǎng)絡(luò)化多目標(biāo)調(diào)度模型

為了方便研究，以1次物資調(diào)度過程為背景構(gòu)建網(wǎng)絡(luò)化多目標(biāo)調(diào)度模型，假設(shè)：1)前沿物資補(bǔ)給站所需的物資類型與數(shù)量在前沿物資庫存中心中都有相應(yīng)儲(chǔ)備；2)前沿物資補(bǔ)給站和前沿物資庫存中心的相關(guān)信息在裝備保障信息網(wǎng)絡(luò)中都能感知到；3)不考慮運(yùn)輸過程中物資追加的情況。

設(shè)Ai(i=1, 2,…,n)為前沿物資補(bǔ)給站，Bj(j=1, 2,…,m)為前沿物資庫存中心，Q為戰(zhàn)前A1,A2,…,An,B1,B2,…,Bm儲(chǔ)備物資的總量，k1∶k2∶… ∶kn+m為戰(zhàn)前A1,A2,…,An與B1,B2,…,Bm儲(chǔ)備物資的數(shù)量比例，Ri為戰(zhàn)時(shí)Ai消耗的物資數(shù)量，TLi為到達(dá)Ai的時(shí)間限額，CLi為到達(dá)Ai的費(fèi)用限額，SLji為Bj與Ai之間路徑安全度的限額。tji為從Bj到Ai的路徑行駛時(shí)間，sji為從Bj到Ai的行駛路徑安全度，cji為從Bj到Ai的單位時(shí)間運(yùn)輸成本，yji為Bj向Ai供應(yīng)的物資量，vji為從Bj到Ai的行駛路徑判別值，

若ω={(B1,y1i,t1i,v1i), (B2,y2i,t2i,v2i),…, (Bm,ymi,tmi,vmi)}為前沿物資補(bǔ)給站Ai的一個(gè)調(diào)度方案，T(ω)物資運(yùn)輸總時(shí)間，S(ω)為路徑安全度，C(ω)為物資運(yùn)輸總費(fèi)用，ψ為所有調(diào)度方案的集合，則區(qū)域內(nèi)物資網(wǎng)絡(luò)化調(diào)度模型的目標(biāo)函數(shù)為

(1)

(2)

將式(1)中的3個(gè)目標(biāo)函數(shù)通過線性變換轉(zhuǎn)換為新的目標(biāo)函數(shù)Z，則

Z=min(ρ1T+ρ2S+ρ3C),

(3)

式中:ρ1、ρ2、ρ3為權(quán)重系數(shù)，且0≤ρ1,ρ2,ρ3≤1，ρ1+ρ2+ρ3=1。

權(quán)重系數(shù)的取值將直接影響目標(biāo)函數(shù)Z的最優(yōu)求解，應(yīng)根據(jù)戰(zhàn)時(shí)物資調(diào)度的具體情況，同時(shí)參考以往戰(zhàn)場上出現(xiàn)的類似情況來確定其取值的大小。

3GASA分時(shí)段算法

式(1)是一個(gè)多目標(biāo)非線性混合規(guī)劃模型，該模型的約束條件繁雜，很難通過動(dòng)態(tài)規(guī)劃法、分支定界法、枚舉法以及梯度法等傳統(tǒng)算法來求解其目標(biāo)函數(shù)值。20世紀(jì)80年代興起的粒子群算法[7]、禁忌搜索算法[8]、模擬退火算法[9]以及遺傳算法[10]等現(xiàn)代智能優(yōu)化算法為混合規(guī)劃模型求解提供了新的思路和方法。根據(jù)物資調(diào)度模型的特點(diǎn)，結(jié)合各種現(xiàn)代智能優(yōu)化算法的優(yōu)缺點(diǎn)以及適用范圍，筆者設(shè)計(jì)了GASA(Genetic Algorithms Simulated Annealing)分時(shí)段混合優(yōu)化算法，來求解該調(diào)度問題。具體求解步驟如圖1所示。

圖1　GASA分時(shí)段混合優(yōu)化算法求解步驟

4實(shí)例應(yīng)用

假設(shè)某區(qū)域部署了6個(gè)前沿物資補(bǔ)給站與2個(gè)前沿物資庫存中心，并且儲(chǔ)備了I型和II型2種物資。戰(zhàn)前，2種物資在A1、A2、A3、A4、A5、A6、B1、B2中的數(shù)量比均為10∶10∶3∶4∶6∶6∶4∶3。8個(gè)物資儲(chǔ)備點(diǎn)的物資儲(chǔ)備總量Q=200 t，6個(gè)前沿物資補(bǔ)給站的物資消耗情況如表1所示。

表1　前沿物資補(bǔ)給站物資消耗情況

B1有1架直升機(jī)、2輛運(yùn)輸車輛，B2有2架直升機(jī)、2輛運(yùn)輸車輛;直升機(jī)與運(yùn)輸車輛的載質(zhì)量分別為3 t與7 t；單位時(shí)間運(yùn)輸成本分別為6與2。B1、B2到各前沿物質(zhì)補(bǔ)給站的路徑機(jī)動(dòng)時(shí)間分別如表2、3所示。

表2　B1到各前沿物質(zhì)補(bǔ)給站機(jī)動(dòng)時(shí)間　　min

表3　B2到各前沿物質(zhì)補(bǔ)給站的機(jī)動(dòng)時(shí)間　min

考慮供應(yīng)優(yōu)先級(jí):A3與A4優(yōu)先級(jí)最高，A2與A5次之，A1與A6最低。前沿物資庫存中心到各前沿物資補(bǔ)給站的運(yùn)輸路徑安全度如表4所示。各前沿物資補(bǔ)給站對(duì)I型與II型物資供應(yīng)保障的時(shí)間限額如表5所示。到達(dá)各前沿物資補(bǔ)給站的費(fèi)用限額均為50，前沿物資庫存中心與前沿物資補(bǔ)給站之間的運(yùn)輸路徑安全度的限額均為0.5。

表4　前沿物資庫存中心到前沿物資補(bǔ)給站運(yùn)輸路徑安全度

注： “*/*”為車輛路徑的安全度/直升機(jī)航線的安全度

表5　各前沿物資補(bǔ)給站對(duì)物資供應(yīng)保障時(shí)間限額　　min

為了驗(yàn)證GASA分時(shí)段混合優(yōu)化算法的有效性，筆者將該算法與傳統(tǒng)的GA算法、SA算法、GASA算法、文獻(xiàn)[11]的GASA算法、文獻(xiàn)[12]的GASA算法進(jìn)行了對(duì)比分析。各算法求解加權(quán)目標(biāo)函數(shù)最優(yōu)值的對(duì)比如圖2所示。

圖2　6種優(yōu)化算法求解加權(quán)目標(biāo)函數(shù)最優(yōu)值對(duì)比

由圖2可見：1) 由于傳統(tǒng)的GA算法具有早熟收斂特性，使得加權(quán)目標(biāo)函數(shù)值較早地收斂于一個(gè)局部極值；2)由于傳統(tǒng)的SA算法對(duì)參數(shù)具有較強(qiáng)的依賴性，使得加權(quán)目標(biāo)函數(shù)值經(jīng)過較長的迭代次數(shù)才逼近于一個(gè)局部最優(yōu)值；3) 所有GASA算法均借鑒了SA算法和GA算法在尋優(yōu)時(shí)的優(yōu)點(diǎn)，但筆者提出的GASA算法可根據(jù)進(jìn)化階段適時(shí)調(diào)整參數(shù)，雖然收斂時(shí)間(即迭代次數(shù))較長，但其尋優(yōu)結(jié)果優(yōu)于其他5種算法。

根據(jù)圖2加權(quán)目標(biāo)函數(shù)的最優(yōu)結(jié)果，獲得對(duì)應(yīng)的方案即滿意的物資調(diào)度方案，如圖3所示。

圖3　滿意的物資調(diào)度方案

5結(jié)論

與現(xiàn)有研究相比，筆者在構(gòu)建戰(zhàn)時(shí)網(wǎng)絡(luò)化物資調(diào)度模型時(shí)考慮了諸多戰(zhàn)時(shí)因素，更加貼近作戰(zhàn)實(shí)際，且通過實(shí)例應(yīng)用驗(yàn)證了網(wǎng)絡(luò)化模型及優(yōu)化算法的有效性，不足之處主要是針對(duì)建模方法進(jìn)行研究，相關(guān)條件參數(shù)選取較為簡單，且僅考慮了1次調(diào)度過程。下一步將結(jié)合作戰(zhàn)實(shí)際情況，進(jìn)一步驗(yàn)證模型的有效性。

參考文獻(xiàn)：

[1]劉亞東，伊洪冰，陳祥斌, 等. 基于多優(yōu)先級(jí)動(dòng)態(tài)規(guī)劃算法的裝備保障任務(wù)調(diào)度[J]. 軍事交通學(xué)院學(xué)報(bào), 2014, 16(4): 24-29.

[2]呂學(xué)志，陳樂，尹健, 等. 考慮休息的維修任務(wù)調(diào)度模型及其求解算法[J]. 兵工學(xué)報(bào), 2014, 35(12): 2116-2123.

[3]朱昱，梁娟，曹繼平, 等. 一種基于混合維修流程的裝備維修任務(wù)調(diào)度方法[J]. 第二炮兵工程大學(xué)學(xué)報(bào)(自然科學(xué)版), 2014, 28(1): 69-73.

[4]朱昱，宋建社，王正元. 一種基于最大保障時(shí)間的戰(zhàn)時(shí)裝備維修任務(wù)調(diào)度[J]. 系統(tǒng)工程與電子技術(shù), 2007, 29(11): 1900-1903.

[5]汪濤，吳琳麗. 基于粒子群算法的應(yīng)急物資調(diào)度研究[J]. 軍事交通學(xué)院學(xué)報(bào), 2011, 13(5): 70-74.

[6]任帆，呂學(xué)志，王憲文. 巡回修理中的維修任務(wù)調(diào)度策略[J]. 火力與指揮控制, 2013, 38(12): 171-175.

[7]Ali M M, Kaelo P. Improved Particle Swarm Algorithms for Global Optimization [J]. Applied Mathematics and Computation, 2008, 196(2): 578-593.

[8]Saidi-Mehrabad M, Fattahi P. Flexible Job Shop Scheduling with Tabu Search Algorithms [J]. The International Journal of Advanced Manufacturing Technology, 2007, 32(5): 563-570.

[9]Tekinalp O, Karsli G. A New Multiobjective Simulated Annealing Algorithm [J]. Journal of Global Optimization, 2007, 39(1): 49-77.

[10]Botta M, Negro G. Multiple Sequence Alignment with Genetic Algorithms [J]. Lecture Notes in Computer Science, 2010, 6160(1): 206-214.

[11]蔣建林，徐進(jìn)澎，文杰.基于單親遺傳模擬退火算法的定點(diǎn)p-中心問題[J]. 系統(tǒng)工程學(xué)報(bào), 2011, 26(3): 414-420.

[12]謝琦，李連升，劉繼紅. 基于GASA優(yōu)化算法的自適應(yīng)協(xié)同優(yōu)化方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2010, 16(11): 2410-2415.

(責(zé)任編輯: 王生鳳)

Modeling on Network Material Scheduling in Wartime

LU Yu, CHEN Xing-kai, HAN Zhen

(Department of Equipment Command and Administration, Ordnance Engineering College, Shijiazhuang 050003, China)

Abstract：From the perspective of material scheduling network and material reserve balance, the wartime material scheduling problem is studied and a multi-object scheduling model is established to optimize the supply time, supply costs and the safety degree of transportation route. The GASA (Genetic Algorithms Simulated Annealing) hybrid optimization scheduling algorithm at different time is designed, and the validity of network scheduling model and algorithm is verified with examples, which provides reference method for solving the network material scheduling optimization problem in wartime.

Key words:reserve balance; scheduling model; GASA algorithm

文章編號(hào)：1672-1497(2016)01-0021-04

收稿日期：2015-12-09

基金項(xiàng)目：軍隊(duì)科研計(jì)劃項(xiàng)目

作者簡介：盧昱(1960-)，男，教授，博士。

中圖分類號(hào)：E234; E911

文獻(xiàn)標(biāo)志碼：A

DOI：10.3969/j.issn.1672-1497.2016.01.005