基于匈牙利算法的戰(zhàn)時運油車前送油料調度優(yōu)化模型研究

【后勤保障與裝備管理】

基于匈牙利算法的戰(zhàn)時運油車前送油料調度優(yōu)化模型研究

李開紅1,肖輝2，李橫1，胡汝翼1，郭鵬1

(1.后勤工程學院 軍事油料應用與管理工程系，重慶401311;

2.西藏軍區(qū)后勤部 軍需物資油料處，拉薩851600)

摘要：戰(zhàn)時運油車前送油料調度優(yōu)化，是一個綜合考慮部隊用油需求、戰(zhàn)場環(huán)境、地形、路徑等多因素，追求保障的安全性和時效性等多目標的保障決策問題；在復雜戰(zhàn)場條件下，戰(zhàn)區(qū)應急保障旅油料營通常編成若干個功能齊全、機動性好的小型機動支援油料保障分隊，充分利用公路交通網(wǎng)分散配置，形成“網(wǎng)狀部署”，針對在不同作戰(zhàn)地域擔負不同作戰(zhàn)任務的部隊，快速、靈活、安全地實施油料支援保障；通過構建基于匈牙利算法的戰(zhàn)時運油車調度模型，當獲取多個作戰(zhàn)部隊的油料補給實時需求后，可自動在滿足條件的所有保障分隊中進行快速匹配，為決策者提供最佳保障策略建議；經(jīng)Matlab仿真和實例分析驗證，該模型在解決戰(zhàn)場油料前送實時調度問題上是一個非常有效的方法。

關鍵詞：匈牙利算法；運油車；前送油料；調度優(yōu)化；模型

作者簡介：李開紅(1985—)，男，碩士研究生，主要從事油料勤務研究。

doi:10.11809/scbgxb2015.06.016

中圖分類號：E917

文章編號：1006-0707(2015)06-0061-05

本文引用格式：李開紅,肖輝，李橫，等.基于匈牙利算法的戰(zhàn)時運油車前送油料調度優(yōu)化模型研究[J].四川兵工學報，2015(6):61-65.

Citation format:LI Kai-hong, XIAO Hui, LI Heng,et al.Scheduling Optimization Model of Forward POL Transportation by Oil Tank Car on Wartime Based on Hungarian-Algorithm[J].Journal of Sichuan Ordnance,2015(6):61-65.

Scheduling Optimization Model of Forward POL Transportation

by Oil Tank Car on Wartime Based on Hungarian-Algorithm

LI Kai-hong1, XIAO Hui2, LI Heng1, HU Ru-yi1, GUO Peng1

(1.Department of Petroleum Application and Management Engineering,

Logistic Engineering University, Chongqing 401311, China; 2.Military Supplies and Oil Office,

Tibet Military Logistic Department, Lhasa 851600, China)

Abstract:The scheduling optimization of forward POL transportation by oil tank car on wartime is a comprehensive consideration of many factors such as oil demand from army, battlefield environment, terrain, route, etc, and it pursuits a multi-targets of time and security support decision problem. In the complex battlefield conditions, the theater emergency support brigade POL support battalion usually consists of several complete function, good maneuver flexibility and little scale POL support units to make full use of highway traffic network distributed configuration and to form a “net deployment” to implement fast, smart and safe POL support according to the different combat mission armies in different region. By constructing a scheduling model of oil tank car on wartime based on the Hungarian algorithm, when the system obtain the real-time fuel supply requirement from combat troops, it will automatic quick matching in POL support units which satisfying the conditions to provide the best guarantee strategy for decision maker. By Matlab simulation, it was proved that it is a very effective method in solving the decision problem of real-time scheduling of forward transport POL by oil tank car.

Key words: Hungarian algorithm; oil tank car; forward POL transportation; scheduling optimization;

model

戰(zhàn)時運油車的調度問題是一類高難度的運輸決策問題，軍內外對這類問題的研究比較多，研究的主要方法有：單純性法，排隊論，圖論，遺傳算法[1]等。2005年，后勤工程學院的李萌等提出的聯(lián)合戰(zhàn)役油料輸送系統(tǒng)模擬模型及優(yōu)化研究[2]，就是采用排隊論的方法，將聯(lián)合戰(zhàn)役油料輸送視為一個由多個子系統(tǒng)組成的排隊系統(tǒng)，綜合考慮了各種運輸工具[3]的選取，提出了最經(jīng)濟的運輸方案；2006年，李橫等發(fā)表的聯(lián)合戰(zhàn)役野戰(zhàn)油庫部署多目標優(yōu)化模擬模型[4]，也是基于排隊論提出了戰(zhàn)役野戰(zhàn)油庫向部隊油料輸送力量的分配模型，屬于一對多式保障，研究重點是如何分配使運油車數(shù)最少；2012年，王強等發(fā)表的《基于GPSSW的油料運輸力量模擬模型》[5]中，提出了后方油庫與戰(zhàn)役野戰(zhàn)油庫之間進行油料輸轉的一種運輸模型，且只限于研究單個路徑中一對一式油料運輸問題。上述文章中，雖然從不同側重點分別研究了戰(zhàn)時油料保障的各個環(huán)節(jié)，但均未考慮前送油料這類戰(zhàn)場末端保障問題，也未深入研究戰(zhàn)時油料保障的安全性和時效性等戰(zhàn)場特殊性要求。而且采用的計算機模擬方法效率比較低，比如GPSSW仿真方法[6]需進行反復模擬，得出最優(yōu)解的速度較慢，而如果初始解選取不合適的話，甚至很難求出最優(yōu)解，因此需要一種更高效的匹配方法，來解決這類多路徑多目標的油料運輸決策難題。匈牙利算法就是一種高效的匹配算法，以二分圖為理論基礎，總能在有限步內收斂于最優(yōu)解，而且不依賴初始解的選擇，在解決最佳匹配問題上具有快速、高效的特點，通常得出的最終解就是完美匹配。

目前，采用匈牙利算法對運輸車輛調度問題進行研究的還不多，主要有：2009年，武警工程學院的徐小林[7]提出的基于匈牙利算法的多車型車輛調度問題；2010年，北京交通大學的于煥英[8]提出的基于匈牙利算法的多車型配送問題。以上研究都是基于匈牙利算法建立以最小總油耗量為目標函數(shù)的車輛調度決策模型，目的是以最低的費用完成運輸工作，主要考慮的是經(jīng)濟效益；在戰(zhàn)時條件下油料前送的車輛調度需考慮的因素重多，如果僅僅考慮經(jīng)濟效益明顯是不科學、不適用的，而且需要考慮的因素越多，其復雜程度可能就呈幾何級數(shù)增加。因此，從戰(zhàn)時油料保障的實際情況來分析，建立運油車的調度模型時必須考慮的主要因素是運油車調度的時效性和安全性。

1戰(zhàn)時前送油料支援保障分析

1.1保障實體

本文的研究對象是戰(zhàn)區(qū)應急保障旅油料營，它是由戰(zhàn)區(qū)聯(lián)勤分部抽組的綜合性戰(zhàn)役后勤油料應急機動保障部(分)隊，具有較強的快速反應能力、機動保障能力和綜合保障能力，是一支應急支援保障的“拳頭”力量[9]。著眼未來戰(zhàn)爭爆發(fā)突然、應急機動部隊行動緊急、攜行油料較少、在集結地域停留時間短等特點，要求應急保障油料營必須在任何情況下都能作出快速反應，與機動部隊同步反應，實施穿插補給任務，必須以最快的速度在最短的時間內為作戰(zhàn)部隊提供有力補給，贏得寶貴時間、創(chuàng)造獲勝條件。

1.2保障模式

戰(zhàn)時油料前送支援保障通常需保障戰(zhàn)役軍團多方向、多地域、多地點作戰(zhàn)，因此，根據(jù)區(qū)域空間和可能擔負的機動支援油料保障任務，將應急機動支援油料保障力量小型化、模塊化，按照“合成、混編、超常”的要求，以定點保障點為依托，優(yōu)化組合，編成若干個功能齊全、機動性好的小型機動支援油料保障分隊，充分利用交通網(wǎng)分散配置，形成“網(wǎng)狀部署”，針對在不同作戰(zhàn)地域擔負不同作戰(zhàn)任務的部隊[10]，快速、靈活、安全地實施前送油料支援保障，為作戰(zhàn)部隊快速反應贏得寶貴的時間。

未來信息化戰(zhàn)爭中，隨著野戰(zhàn)單裝定位與油料動態(tài)監(jiān)控系統(tǒng)[11]的成功應用，配合先進的定位設備和數(shù)據(jù)采集設備，可以實時收集作戰(zhàn)部隊的地理位置、油料需求量和油料保障分隊的地理位置、最大保障能力，實現(xiàn)戰(zhàn)場油料保障需求和保障資源的“可視化”。一旦多個作戰(zhàn)部隊同一時間內提出油料補給需求后，系統(tǒng)可自動在滿足條件的所有保障分隊中進行快速匹配，得出最佳保障策略，從而為決策者提供科學、合理的決策建議。

2基于匈牙利算法的調度優(yōu)化模型

2.1匈牙利算法

匈牙利算法是匈牙利數(shù)學家Edmonds提出的，該算法的核心是基于Hall定理中充分性證明的思想來尋找增廣路徑求最大匹配。匈牙利算法的理論基礎是在效益矩陣的任何行或列中，加上或減去一個常數(shù)后不會改變最優(yōu)分配。它的基本思想是修改效益矩陣的行或列，使得每一行或列中至少有一個為零的元素，經(jīng)過修正后，直至在不同行、不同列中至少有一個零元素，從而得到與這些零元素相對應的一個完全分配方案。當用于效益矩陣時，這個完全分配方案就是一個最優(yōu)分配。

求最大匹配的一種常見的算法是枚舉法：先找出全部匹配，然后保留匹配數(shù)最多的。但是該算法的復雜度為邊數(shù)的指數(shù)級函數(shù)，求解具有n個變量的問題時需枚舉2n種可能。相比其他算法，匈牙利算法的最大優(yōu)點是總能在有限步內收斂出一個最優(yōu)解。它在解決復雜網(wǎng)絡結構和實時性要求比較高的問題時，速度很快，效果明顯。經(jīng)計算機模擬仿真結果證明，當數(shù)據(jù)量n急劇加大時，時間復雜度變化不大，耗時相對較少，它在解決該多目標匹配問題時具有非常明顯的優(yōu)勢。

2.2模型構建

2.2.1問題描述

戰(zhàn)時運油車前送油料的調度優(yōu)化，是一個綜合考慮部隊用油需求、戰(zhàn)場環(huán)境、地形、路徑等多因素，追求保障的安全性和時效性等多目標的保障決策問題[12]，任何一個參數(shù)的改變都可能影響最終的決策結果。該類問題可簡化描述為：

設有N個處于不同地域的作戰(zhàn)部隊X= (X1,X2,…,Xn) 同一時間內提出油料補給需求，現(xiàn)安排M個油料運輸分隊Y= (Y1,Y2,…,Ym) 向上述N個單位前送油料，規(guī)定必須在t時限內完成補給任務，已知相對路徑矩陣C和路徑安全矩陣P，如何調度分配運油車使得當前油料保障軍事效益最大化。

2.2.2調度模型

該問題涉及因素很多，采用傳統(tǒng)的數(shù)學解析方法難以得出準確的答案，戰(zhàn)場最重要的因素是油料保障的安全性和時效性，即保證任務安全的基礎上使運輸時間的最小化是實現(xiàn)保障效能最大化的根本途徑。因此，該問題的關鍵因素是考慮在戰(zhàn)時確保安全前提下前送油料的時效性，因此可轉化為已知路徑矩陣C，通過構建安全矩陣P，求得等效時間矩陣T的最小值問題。模型目標方程：

約束條件如下：

1)N為需求油料的作戰(zhàn)部隊數(shù)，M為油料保障分隊數(shù)，i為第i個保障分隊，j為第j個需求部隊，k為第k種油品；

2)A為每個作戰(zhàn)部隊的油料需求矩陣，Ajk代表j部隊的k油品(汽油，輕柴油，軍柴油等)的需求數(shù)量；

3)B為每個分隊的油料保障能力矩陣，它滿足：運輸分隊i的k油品剩余量應不少于i部隊的需求，Ajk≤Bik；B的最后一列是保障分隊的行軍速度：vi=Bin；

4)C為相對路徑矩陣，Cij代表Yi分隊向Xj部隊前送油料時的路徑權值，道路遭敵破壞，或油料保障分隊的保障能力無法滿足需求時，其權重可設為一個極大值，即Cij=Max；

5)P為路徑的安全系數(shù)矩陣，根據(jù)戰(zhàn)場情報，由專家打分得出，評分越高越安全；

6)T為時間矩陣，它由路徑矩陣和安全矩陣計算得出：tij= (cij/vi) /pij，滿足0 ≤tij≤tmax；

7)Z為派遣矩陣，它是標準的單元矩陣，即只存在一一對應關系。

2.3模型求解

2.3.1模型求解方法

1) 構造平衡的相對路徑矩陣C。因匈牙利算法擅長解決平衡問題，當保障分隊數(shù)和需求部隊數(shù)不對等時，可通過構造虛擬的保障分隊或需求分隊，重新建立平衡路徑矩陣C＇。具體解法如下：

① 若N>M，則一個分隊可能需保障多個部隊的油料前送，可虛擬N-M個運油分隊，構造新的路徑平衡矩陣C＇={Cm×n|C(n-m)×n}即可。

② 若N

③ 若N=M，則屬于平衡問題，可直接由匈牙利算法求解。

④ 模型轉化，若對應的模型是求最大值，可將其變換為求最小值。

2) 修改相對路徑矩陣C。如果道路不通或者油料保障分隊當前剩余油料少于作戰(zhàn)分隊需求，則可修改路徑矩陣C，將其對應的權重設置為最大值。即滿足：

3) 對安全性量化評估，建立路徑安全矩陣P

在信息化戰(zhàn)爭條件下，公路交通網(wǎng)是敵方打擊的首要目標，而由于戰(zhàn)場路況和敵情的錯綜復雜，運油分隊被敵發(fā)現(xiàn)進而遭打擊的概率會顯著增大，其安全面臨著前所未有的挑戰(zhàn)，因此，必須對路徑的安全性進行科學評價。采用德爾斐法，通過實時收集戰(zhàn)場情報、作戰(zhàn)分隊報告情況、咨詢經(jīng)驗豐富的部隊油勤人員和指揮參謀人員等多種途徑，歷經(jīng)咨詢、反饋、決策的循環(huán)過程，依據(jù)表1所示的安全評估指標體系，運用層次分析法[13]，可建立初步的路徑安全評分矩陣S。得出各條道路的安全系數(shù)矩陣后，再進行歸一化處理，即令Pij=Sij/Smax，即可建立歸一化的安全矩陣P。

表1　安全評估指標

注：滿分10分。

4) 時間矩陣T可由路徑矩陣C和安全矩陣P直接計算得出。

其中vi=Bin。

根據(jù)目標函數(shù)最優(yōu)解，得出派遣矩陣Z。

2.3.2Matlab編程實現(xiàn)

本文采用Matlab來模擬該問題[14]，要將基于實際油料業(yè)務工作的數(shù)學模型轉化為Matlab程序，需要構建滿足匈牙利算法的關鍵計算模塊，通過反復模擬，并對輸出結果進行統(tǒng)計分析，從而得出合理、可行、實用的結論。

Matlab關鍵代碼如下：

1) 時間矩陣構造。時間矩陣構造如下：

function[D,T]=Panbie(A,B,C,P)

[m1,n1]=size(A)

[m2,n2]=size(B)

tmax=100

cmax=1000

forj=1:m1

fork=1:n1

fori= 1:m1

ifA(j,k)>B(i,k)

C(i,j)=Cmax

end

D(i,j)=C(i,j)

Ifp(I,j)=0

T(i,j)=tmax

else

T(i,j)= (D(i,j)/B(i,n2))/P(i,j)

end

end

end

2) 匈牙利算法的關鍵實現(xiàn)。

function [Matching,Cost] = Edmonds(T)

function [P_cond,stepnum] = step1(P_cond)

function [r_cov,c_cov,M,stepnum] = step2(P_cond)

function [c_cov,stepnum] = step3(M,P_size)

function [M,r_cov,c_cov,Z_c,stepnum] = step4(P_cond,r_cov,c_cov,M)

function [M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov)

function [P_cond,stepnum] = step6(P_cond,r_cov,c_cov)

function cnum = min_line_cover(Edge)

function[D,T]=Panbie(A,B,C)

3實例分析

3.1實例描述

假想XX邊境地區(qū)發(fā)生武裝沖突，某戰(zhàn)區(qū)XX集團軍奉命進入邊境地區(qū)執(zhí)行反擊作戰(zhàn)任務。某次戰(zhàn)役中該集團軍受領任務需多線同時作戰(zhàn)，所屬部隊分別部署于4個不同方向地域，因戰(zhàn)斗比較激烈，油料消耗巨大，現(xiàn)有4個作戰(zhàn)單位油料即將消耗殆盡，分別是摩步旅，高炮旅，高炮旅，工兵團(代號分別是A,B,C,D)，同時向后方指揮部提出油料補充需求(表2)。后方指揮部油料助理員根據(jù)指揮部命令，現(xiàn)緊急派遣4個油料保障分隊(代號分別是甲，乙，丙，丁)，為作戰(zhàn)部隊前送油料，要求必須在4 h內完成補給任務。現(xiàn)已給出各油料保障分隊距離作戰(zhàn)部隊的相對路徑(表3)及其最大保障能力(表4)，由情報系統(tǒng)給出的路徑安全系數(shù)評分(表5)，試問，如何進行調度，確保在完成任務的基礎上使運輸時間最短。

表2　作戰(zhàn)部隊油料需求　t

表3　保障分隊距作戰(zhàn)部隊距離　km

注：“-”代表因道路被敵方破壞，車隊無法到達。

表4　保障分隊當前保障能力

注：因分隊車輛種類不同，所以平均行軍速度略有不同。

表5　路徑安全系數(shù)評分

注：得分越高，代表越安全，滿分10分，0分代表該路徑不通。

3.2求解過程

第1步：因道路受損的約束條件篩選出路徑(丙-B，丁-C)無法完成保障任務，根據(jù)分隊的保障能力約束條件，可篩選出路徑(甲-D，乙-A)無法完成保障任務。將無法達到的路徑值直接設置為極大值，這里設為1 000即可。由此可建立路徑矩陣C：

第2步：對評分矩陣進行歸一化處理，得出安全矩陣P：

第3步：代入行軍速度和安全矩陣P，可計算出時間矩陣T:

第4步：利用匈牙利算法對時間矩陣T進行求解：

ABCD甲1.892.924.4825.63乙22.732.681.431.16丙3.961002.905.30丁3.220.931001.38=01.042.5923.7521.571.520.2801.0697.1002.402.30099.070.45

第5步：由此得到最佳的派遣矩陣Z為：

ABCD甲1000乙0001丙0010丁0100

3.3最佳解決方案

由此得出最佳的匹配方案是：甲—A，乙—D，丙—C，丁—B。最短用時分別是：1.89 h，1.16 h，2.9 h，0.93 h，均滿足時限要求，總的耗時為6.88 h。

4結論

本文從戰(zhàn)時油料前送支援保障流程入手，重點針對戰(zhàn)場環(huán)境下油料前送支援保障的安全性和時效性建立目標函數(shù)，采用匈牙利算法構建了運油車調度模型，首先基于戰(zhàn)場環(huán)境因素和保障能力制約對路徑矩陣C進行篩選，再根據(jù)戰(zhàn)場情報和專家打分建立路徑安全矩陣P，并由此建立時效性等效矩陣T，然后利用匈牙利算法對等效矩陣T進行求解得出了派遣矩陣Z，最終得到合理的決策方案建議。經(jīng)MATLAB模擬仿真和實例分析驗證，該模型能夠快速形成科學、合理的派遣方案和決策建議，在解決戰(zhàn)場油料前送實時調度問題上是一種更加高效的方法。但仍有需要進一步深入研究的內容：

1) 路徑安全矩陣P的構建依賴專家打分，不同的人會有不同的意見，一個細小的判斷錯誤將會導致重大決策失誤，在戰(zhàn)爭中甚至可能造成災難性后果。因此，專家選取必須是有豐富經(jīng)驗并對戰(zhàn)場情況有清晰判斷的保障指揮員。同時，建立可靠的戰(zhàn)場情報搜集和預警分析體系也非常必要。

2) 本模型只考慮了安全性和時效性兩個因素，而戰(zhàn)場因素是錯綜復雜的，需考慮的問題很多，作為戰(zhàn)場后勤保障指揮員必須全局考慮，抓住關鍵因素，才能實現(xiàn)高效無縫鏈接式油料保障。

參考文獻：

[1]張亮,周繼寶.基于遺傳算法的后勤運輸車路徑規(guī)劃[J].四川兵工學報,2012,33(2):81-83.

[2]李萌,李少鳴,李橫.聯(lián)合戰(zhàn)役油料輸送系統(tǒng)模擬模型及優(yōu)化研究[J].后勤工程學院學報,2005,21(3):89-92.

[3]王富平,李橫,李少鳴,等.戰(zhàn)時鐵路運輸油料搶收模擬優(yōu)化[J].后勤工程學院學報,2010,26(6):40-43,77.

[4]李橫,蘇永東.聯(lián)合戰(zhàn)役野戰(zhàn)油庫部署多目標優(yōu)化模擬模型[J].后勤工程學院學報，2005,21(3):89-93.

[5]王強,李橫,龍智強,等.基于GPSSW的油料運輸力量模擬模型[J].物流科技,2012(7):119-123.

[6]郝亮,王靜,周慶忠.基于GPSSW的油料裝備戰(zhàn)場維修力量優(yōu)化分配[J].四川兵工學報,2010,31(3):18-21.

[7]徐小林.基于匈牙利算法的多車型車輛調度問題[J].火力與指揮控制,2009,34(2):137-139.

[8]于煥英,孫晚華,何峣.基于匈牙利算法的多車型配送問題[J].物流技術,2010(11):74-75.

[9]黃海波,李少鳴.聯(lián)勤分部應急機動支援油料保障研究[D].重慶:后勤工程學院.2006.

[10]李巖,李少鳴.旅營制集團軍部隊油料勤務分隊建設與運用研究[D].重慶:后勤工程學院.2011.

[11]李橫.基于信息系統(tǒng)的部隊遠程摩托化機動油料保障研究[J].物流工程與管理,2011(9):11-13.

[12]張寧,劉巖,錢利民,等.基于改進型多目標模糊優(yōu)選的作戰(zhàn)油料保障決策研究[J].四川兵工學報,2009,30(6):6-9.

[13]舒先勝,丁澤中,夏亦寒,等.基于主成分分析法的油料保障能力評估[J].四川兵工學報，2014,35(3):76-79.

[14]王海英,黃強,李傳濤,等.圖論算法及其MATLAB實現(xiàn)[M].北京：北京航空航天大學出版社,2010:97-101.

(責任編輯楊繼森)