戰時網絡化物資調度建模

盧　昱， 陳興凱， 韓　震

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

戰時網絡化物資調度建模

盧昱， 陳興凱， 韓震

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

摘要：從物資調度網絡化與物資儲備平衡角度研究了戰時物資調度問題，以供應時間、供應成本以及運輸路徑安全度為優化目標，建立了網絡化多目標優化調度模型，設計了GASA(Genetic Algorithms Simulated Annealing)分時段混合優化調度算法，并通過實例對網絡化調度模型及算法的有效性進行了驗證，為解決戰時網絡化物資調度優化問題提供參考。

關鍵詞：儲備平衡； 調度模型； GASA算法

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

戰時物資調度是一個多目標優化問題，筆者從供應時間、供應成本以及運輸路徑安全度3個方面，構建了戰時前沿物資庫存中心向前沿物資補給站供應物資的網絡化調度模型，旨在提出一種新的研究思路和方法，為解決物資調度優化問題提供參考。

1調度問題描述

戰時，當前沿物資庫存中心在裝備保障信息網絡的支持下感知到前沿物資補給站的物資需求信息時，即迅速組織并調度相關保障力量實施物資供應保障，快速機動將所需物資運輸至指定地點。因此，各個保障單元及物資運輸路徑就構成了一個物資調度網絡。其中：庫存中心、補給站為網絡的節點，物資運輸路徑為網絡的邊，設該物資調度網絡為G=(V,E,T,C,S)。式中：V為節點的集合；E為邊的集合；T為在邊上行駛的時間；C為在邊上行駛的成本；S為在邊上運輸的安全度。

由于戰時作戰部隊所需的物資類型、數量繁多，運輸時間緊迫，而且在運輸過程中交通狀況復雜多變，常常會受到潛在的威脅，但物資運輸費用卻十分有限。根據戰時物資保障的任務需求，保障物資應按一定比例分配在各個保障單元中，且在戰時的動態消耗中應保持比例不變，以實現物資儲備平衡。構建網絡化調度模型旨在確定最佳物資調度方案，即在滿足相關約束條件下，維持調度網絡的儲備平衡，實現調度路徑行駛時間T最短、運輸費用C最少以及運輸路徑安全度S最大。

2網絡化多目標調度模型

為了方便研究，以1次物資調度過程為背景構建網絡化多目標調度模型，假設：1)前沿物資補給站所需的物資類型與數量在前沿物資庫存中心中都有相應儲備；2)前沿物資補給站和前沿物資庫存中心的相關信息在裝備保障信息網絡中都能感知到；3)不考慮運輸過程中物資追加的情況。

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

若ω={(B1,y1i,t1i,v1i), (B2,y2i,t2i,v2i),…, (Bm,ymi,tmi,vmi)}為前沿物資補給站Ai的一個調度方案，T(ω)物資運輸總時間，S(ω)為路徑安全度，C(ω)為物資運輸總費用，ψ為所有調度方案的集合，則區域內物資網絡化調度模型的目標函數為

(1)

(2)

將式(1)中的3個目標函數通過線性變換轉換為新的目標函數Z，則

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

(3)

式中:ρ1、ρ2、ρ3為權重系數，且0≤ρ1,ρ2,ρ3≤1，ρ1+ρ2+ρ3=1。

權重系數的取值將直接影響目標函數Z的最優求解，應根據戰時物資調度的具體情況，同時參考以往戰場上出現的類似情況來確定其取值的大小。

3GASA分時段算法

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

圖1　GASA分時段混合優化算法求解步驟

4實例應用

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

表1　前沿物資補給站物資消耗情況

B1有1架直升機、2輛運輸車輛，B2有2架直升機、2輛運輸車輛;直升機與運輸車輛的載質量分別為3 t與7 t；單位時間運輸成本分別為6與2。B1、B2到各前沿物質補給站的路徑機動時間分別如表2、3所示。

表2　B1到各前沿物質補給站機動時間　　min

表3　B2到各前沿物質補給站的機動時間　min

考慮供應優先級:A3與A4優先級最高，A2與A5次之，A1與A6最低。前沿物資庫存中心到各前沿物資補給站的運輸路徑安全度如表4所示。各前沿物資補給站對I型與II型物資供應保障的時間限額如表5所示。到達各前沿物資補給站的費用限額均為50，前沿物資庫存中心與前沿物資補給站之間的運輸路徑安全度的限額均為0.5。

表4　前沿物資庫存中心到前沿物資補給站運輸路徑安全度

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

表5　各前沿物資補給站對物資供應保障時間限額　　min

為了驗證GASA分時段混合優化算法的有效性，筆者將該算法與傳統的GA算法、SA算法、GASA算法、文獻[11]的GASA算法、文獻[12]的GASA算法進行了對比分析。各算法求解加權目標函數最優值的對比如圖2所示。

圖2　6種優化算法求解加權目標函數最優值對比

由圖2可見：1) 由于傳統的GA算法具有早熟收斂特性，使得加權目標函數值較早地收斂于一個局部極值；2)由于傳統的SA算法對參數具有較強的依賴性，使得加權目標函數值經過較長的迭代次數才逼近于一個局部最優值；3) 所有GASA算法均借鑒了SA算法和GA算法在尋優時的優點，但筆者提出的GASA算法可根據進化階段適時調整參數，雖然收斂時間(即迭代次數)較長，但其尋優結果優于其他5種算法。

根據圖2加權目標函數的最優結果，獲得對應的方案即滿意的物資調度方案，如圖3所示。

圖3　滿意的物資調度方案

5結論

與現有研究相比，筆者在構建戰時網絡化物資調度模型時考慮了諸多戰時因素，更加貼近作戰實際，且通過實例應用驗證了網絡化模型及優化算法的有效性，不足之處主要是針對建模方法進行研究，相關條件參數選取較為簡單，且僅考慮了1次調度過程。下一步將結合作戰實際情況，進一步驗證模型的有效性。

參考文獻：

[1]劉亞東，伊洪冰，陳祥斌, 等. 基于多優先級動態規劃算法的裝備保障任務調度[J]. 軍事交通學院學報, 2014, 16(4): 24-29.

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

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

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

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

[6]任帆，呂學志，王憲文. 巡回修理中的維修任務調度策略[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]蔣建林，徐進澎，文杰.基于單親遺傳模擬退火算法的定點p-中心問題[J]. 系統工程學報, 2011, 26(3): 414-420.

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

(責任編輯: 王生鳳)

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

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

收稿日期：2015-12-09

基金項目：軍隊科研計劃項目

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

中圖分類號：E234; E911

文獻標志碼：A

DOI：10.3969/j.issn.1672-1497.2016.01.005