曾 斌，姚 路，秦 瀟

（海軍工程大學(xué)管理工程系，武漢 430033）

0 引言

對未來沖突特點(diǎn)的研究顯示，城市和海岸地區(qū)作戰(zhàn)行動將日益頻繁，它們對后勤保障的需求也大大增加。原因在于：一方面彈藥、裝備等物質(zhì)消耗量更大，補(bǔ)給量隨之增大，批次增多；人員傷亡率高，傷情復(fù)雜，救治任務(wù)艱巨；武器裝備損壞率提高，技術(shù)保障更加頻繁［1］。另一方面作戰(zhàn)部隊規(guī)模較小，分散交戰(zhàn)的可能性增大，增加了運(yùn)輸保障難度。

戰(zhàn)況復(fù)雜時的運(yùn)輸路徑規(guī)劃模型必須考慮以下特點(diǎn)。

1）動態(tài)性。如運(yùn)輸保障任務(wù)的隨機(jī)到來，運(yùn)輸能力的變化（如運(yùn)輸工具變化、車輛故障戰(zhàn)損等），運(yùn)輸?shù)缆返淖兓取?/p>

2）需求復(fù)雜。在運(yùn)輸時效要求上，有的運(yùn)輸任務(wù)要求越快到達(dá)越好，而也有部分任務(wù)指定的時間窗或時限較為寬松［2］，例如一些非緊急物資的計劃配送，在能夠提高整體效率的情況下可以適當(dāng)?shù)乩@路。在運(yùn)力消耗上，隨著運(yùn)輸裝備的大型化和高速化，而且在城市和海岸作戰(zhàn)時，各節(jié)點(diǎn)（表示供應(yīng)點(diǎn)、停靠點(diǎn)或作戰(zhàn)部隊位置等）相互距離不遠(yuǎn)，不少任務(wù)能夠在較短時間內(nèi)完成，不能完全利用運(yùn)載能力（非滿載），造成運(yùn)力的空閑。

3）供需節(jié)點(diǎn)部署的網(wǎng)絡(luò)化?，F(xiàn)代后裝保障要求盡量前伸，甚至與作戰(zhàn)單元混編，供應(yīng)模式從以前線性供應(yīng)逐漸轉(zhuǎn)為網(wǎng)絡(luò)化保障［3］，理論上每支部隊都可能成為保障節(jié)點(diǎn)，即路徑規(guī)劃應(yīng)同時具有集貨和送貨功能。

為此本文針對特點(diǎn)1）在第3 節(jié)提出了基于在線資源分配的任務(wù)調(diào)度算法，在調(diào)度任務(wù)時，針對特點(diǎn)3）中運(yùn)輸路徑網(wǎng)絡(luò)化且要求同時具有集貨和送貨功能，利用特點(diǎn)2）中可以復(fù)用的運(yùn)力（完成任務(wù)返回或非滿載）且允許繞路的特點(diǎn)，借鑒了c-w節(jié)約法的思路［4］，把具有關(guān)聯(lián)路徑的任務(wù)進(jìn)行合并規(guī)劃，從而達(dá)到節(jié)省運(yùn)輸總開銷的目的。

隨著人工智能和組合優(yōu)化技術(shù)的發(fā)展，模擬退火算法、遺傳算法［5-6］、粒子群算法［7］、蟻群算法［8］以及禁忌算法［9］等方法在車輛運(yùn)輸路徑規(guī)劃領(lǐng)域得到了大量研究，它們?yōu)榻鉀Q大規(guī)模、多目標(biāo)的運(yùn)輸問題提供了新的優(yōu)化手段，但它們計算量較大而且不能保證算法的實時性［10］。目前涉及在線規(guī)劃的研究不多，主要可分為“動態(tài)路徑規(guī)劃”和“叫車服務(wù)問題（dial-a-ride）”［11-12］。動態(tài)路徑規(guī)劃方法主要有兩種：一是利用某種啟發(fā)規(guī)則，盡量將新的任務(wù)插入到已經(jīng)制定的調(diào)度方案中或改變現(xiàn)有路線［13］，但優(yōu)化性能受到較大影響；二是利用預(yù)測信息運(yùn)行或重新運(yùn)行規(guī)劃算法［14］，但計算量較大而且不能保證算法的實時性。動態(tài)算法主要考慮偶發(fā)性變化，當(dāng)運(yùn)輸任務(wù)反復(fù)多批次到達(dá)時，算法適用性明顯下降［15］，而且沒有考慮運(yùn)力到達(dá)目的地后繼續(xù)使用的情況。本文研究問題與dial-a-ride 問題類似，但也有以下不同。

1）多種運(yùn)輸任務(wù)類型。例如，戰(zhàn)場運(yùn)輸既包括周期性任務(wù)也包括突發(fā)性任務(wù)，既有大負(fù)載任務(wù)也存在輕負(fù)載任務(wù)。

2）對繞路問題沒有嚴(yán)格要求。如果路徑能夠提升總體性能，允許繞路。

1 基于圖理論的問題建模

定義4：當(dāng)下列條件之一滿足時，路徑R1和路徑R2相互連接，用符號?標(biāo)識。

1）一條路徑是另一條路徑的子路徑。

2）一條路徑的終點(diǎn)是另一條路徑的起點(diǎn)。

3）一條路徑的起始子路徑為另一條路徑的終端子路徑。這里又存在兩種情況：如果兩條路徑之間只存在一條重合的起始和終端子路徑，稱為單向連接。如果R1的某段起始子路徑與R2的終端子路徑重合，同時存在R2的某段起始子路徑與R1的終端子路徑重合，則稱R1和R2為雙向連接。

如果兩條路徑中間的某段子路徑重合，并不表明它們是連接的。

圖1 雙向連接的2 條路徑

任務(wù)j 的最小開銷路徑MRj可定義為：

式中，posi表示空閑運(yùn)輸分隊i 在執(zhí)行任務(wù)j 前所處的位置，startj是任務(wù)j 的起始位置。運(yùn)輸分隊一次可以執(zhí)行多個任務(wù)，因此，在線規(guī)劃算法的主要目標(biāo)就是最小化所有任務(wù)的運(yùn)輸開銷函數(shù)cij。為了減小第1 項開銷，應(yīng)該把任務(wù)指派給離其起始位置最近的運(yùn)輸分隊，本文主要討論如何降低第2項開銷。

2 任務(wù)的合并規(guī)劃算法

合并任務(wù)必然導(dǎo)致運(yùn)輸量的增加，需在路線規(guī)劃前考慮運(yùn)輸量約束條件是否滿足，本文把重點(diǎn)放在路徑優(yōu)化方面。任務(wù)的關(guān)聯(lián)關(guān)系主要考慮以下3種：路線連接、共起點(diǎn)和共終點(diǎn)。如果任務(wù)j1和j2存在以上關(guān)聯(lián)，那么可以根據(jù)以下步驟把它們合并為一個任務(wù)j3。

其中，first 和last 函數(shù)返回路徑中第1 個和最后一個頂點(diǎn)，pri 為任務(wù)的優(yōu)先級。在實際運(yùn)行過程中，每當(dāng)某個運(yùn)輸任務(wù)j1到達(dá)指揮系統(tǒng)調(diào)度時，第2 節(jié)的調(diào)度算法都要檢測在隊列中是否存在還未開始的運(yùn)輸任務(wù)j2，如果j2與j1滿足關(guān)聯(lián)關(guān)系，則把它們合并成一個任務(wù)j3。函數(shù)f 與關(guān)聯(lián)類型相關(guān)，下面具體討論。

2.1 連接路徑的任務(wù)合并

圖2 能合并的2 條單向連接任務(wù)（j1 實線表示，j2 虛線表示）

第1 個關(guān)聯(lián)關(guān)系如圖2 所示，2 個任務(wù)j1和j2都到達(dá)，分別指派給分隊i1和i2，邊的開銷分別為c1、c2和c3，假設(shè)2 個任務(wù)的優(yōu)先級都為1，總開銷可按下式計算：

因為j2的部分開銷被j1執(zhí)行，所以合并后j3的開銷小于j1和j2的開銷和。從中看出利用連接路徑的任務(wù)合并，可以減小目標(biāo)函數(shù)。

圖3 不能合并的任務(wù)（j1 實線表示，j2 虛線表示）

但并不是所有存在路段重合的任務(wù)合并后都可以減小總開銷，如圖3 所示。本算法中只有滿足連接關(guān)系?（定義4）的任務(wù)才進(jìn)行合并，計算公式如下：

2.2 相同終點(diǎn)或起點(diǎn)的任務(wù)合并

常見的物資配送問題通常是要從多個地點(diǎn)調(diào)運(yùn)軍事物資，給多個作戰(zhàn)部門執(zhí)行配送任務(wù)。這時的多個運(yùn)輸任務(wù)具有相同的起點(diǎn)或終點(diǎn)，路徑規(guī)劃則更為復(fù)雜。

如圖4 所示，假設(shè)有3 個任務(wù)：j1（實線）、j2（虛線）和j4（點(diǎn)線），都在指揮中心等待調(diào)度，不失一般性，假設(shè)它們的優(yōu)先級都為1，初始把任務(wù)j1和j2分配給運(yùn)輸分隊i1和i2，忽略i1當(dāng)前位置移動到j(luò)1起點(diǎn)的開銷以及i2當(dāng)前位置移動到j(luò)2起點(diǎn)的開銷，可得

圖4 具有相同終點(diǎn)的任務(wù)（j1實線表示，j2虛線表示，j4點(diǎn)線表示）

按照節(jié)約法思想，另一種規(guī)劃方法是先到兩個任務(wù)的集貨點(diǎn)裝載物質(zhì)，再把它們配送到目的地，即把j1和j2合并成一個任務(wù)j3。這時存在兩個選擇，先到哪一個任務(wù)的起點(diǎn)，這時最小路徑規(guī)劃函數(shù)f（）可分別定義如下：

它們分別產(chǎn)生如下2 個總開銷：

很明顯如果c3小于c1或c2，則可減小總開銷。因此，合并后能夠減小運(yùn)輸總開銷的條件可定義如下：

下面把問題進(jìn)一步擴(kuò)展到2 個以上具有相同終點(diǎn)的任務(wù)。假設(shè)規(guī)劃算法的等待調(diào)度隊列（調(diào)度池）中已存在n 個具有相同終點(diǎn)的任務(wù)集合（J1），且已按照起點(diǎn)的集貨順序排序，其路徑可表達(dá)為：

即依次執(zhí)行j1、j2直至jn，這時新到達(dá)一個具有相同終點(diǎn)的運(yùn)輸任務(wù)jnew，算法按照以下規(guī)則插入jnew。從J1中選擇某任務(wù)ji，其起點(diǎn)到j(luò)new的起點(diǎn)之間距離最小，則插入規(guī)則如下：

如果ji=j1，jnew按下式插入：

圖5 具有相同終點(diǎn)但不能合并的任務(wù)

對于具有相同起點(diǎn)的任務(wù)，其合并公式與條件與相同終點(diǎn)的任務(wù)類似。

2.3 不同關(guān)聯(lián)關(guān)系的任務(wù)合并

新任務(wù)到達(dá)規(guī)劃算法待調(diào)度隊列時，與之關(guān)聯(lián)的待調(diào)度任務(wù)可能有多個且關(guān)聯(lián)關(guān)系都不同，這時需要判定哪一種關(guān)聯(lián)關(guān)系具有較高優(yōu)先級，能夠先與新任務(wù)合并。出于兩個原因算法指定連接關(guān)系優(yōu)先于同起點(diǎn)或終點(diǎn)關(guān)系：一是戰(zhàn)場運(yùn)輸環(huán)境下頂點(diǎn)度數(shù)一般較低，出現(xiàn)重復(fù)路段的可能性較高；二是合并連接關(guān)系的路徑所節(jié)省的開銷要大于同起點(diǎn)或同終點(diǎn)。

3 在線調(diào)度算法的描述

算法的核心思想是：當(dāng)某運(yùn)輸分隊i1有空閑運(yùn)力時，選取執(zhí)行調(diào)度池中權(quán)重最大的任務(wù)jk，從而最小化總開銷。其中：

prij為任務(wù)j 的優(yōu)先級。當(dāng)某運(yùn)輸分隊有空閑運(yùn)力時，該運(yùn)輸分隊放入空閑隊列AvailQueue。當(dāng)有新任務(wù)到達(dá)時，再從空閑隊列中分派運(yùn)輸分隊。如果空閑隊列中有多個運(yùn)輸分隊，可以按照2 種策略分派。一種是負(fù)載平衡策略，即務(wù)求各個運(yùn)輸分隊執(zhí)行的任務(wù)數(shù)量相等。另一種為最小開銷策略。如果任務(wù)到達(dá)時沒有可用的運(yùn)輸分隊（空閑隊列為空），不是直接拒絕和延遲該任務(wù)，而是按照第1 節(jié)的3種關(guān)聯(lián)關(guān)系合并任務(wù)。為了減輕運(yùn)算負(fù)荷，算法分為2 個部分，一個為AddTask，當(dāng)有新的運(yùn)輸任務(wù)到達(dá)指揮中心時按上述思想運(yùn)行；一個為Request-Task，當(dāng)運(yùn)輸分隊有空閑運(yùn)力時調(diào)用，首先檢測調(diào)度池是否為空，為空表明沒有等待的運(yùn)輸任務(wù)，該分隊放入空閑隊列，否則選擇最高權(quán)重的任務(wù)執(zhí)行。它們的偽代碼如下。

由于3 種關(guān)聯(lián)關(guān)系只與運(yùn)輸任務(wù)屬性有關(guān)，與當(dāng)前運(yùn)力位置無關(guān)，所以任務(wù)合并可以只在新任務(wù)到達(dá)時執(zhí)行。為了防止在線調(diào)動時的“任務(wù)饑餓”問題，當(dāng)某任務(wù)沒有得到調(diào)度的次數(shù)大于某閾值時，AdjustPriority 增大其優(yōu)先級。

4 模擬計算與結(jié)果分析

下面以一次登陸演習(xí)的作戰(zhàn)環(huán)境作為測試背景，模擬設(shè)置作戰(zhàn)時間為2 d，包含6 支小規(guī)模運(yùn)輸分隊。初始保障作戰(zhàn)節(jié)點(diǎn)為10 個，其中作戰(zhàn)節(jié)點(diǎn)為6 個，保障節(jié)點(diǎn)4 個，兼具保障功能的作戰(zhàn)節(jié)點(diǎn)為4個，并根據(jù)演習(xí)數(shù)據(jù)，隨仿真展開不斷調(diào)整節(jié)點(diǎn)數(shù)量，測試結(jié)束時節(jié)點(diǎn)數(shù)量為25 個。每個節(jié)點(diǎn)按指數(shù)分布隨機(jī)生成保障任務(wù)（=1 h），每個任務(wù)的起點(diǎn)在其他節(jié)點(diǎn)中隨機(jī)選取，數(shù)量服從1 到3 的均勻分布。簡化起見，所有任務(wù)的優(yōu)先級都為1，開銷為路程距離（km），其中第1 天和第2 天的節(jié)點(diǎn)位置不同，表1 和表2 分別為兩天運(yùn)輸性能的統(tǒng)計數(shù)據(jù)。

表1 第1 天算法性能比較 單位：km

表2 第2 天算法性能比較 單位：km

表格中帶* 號的為本文算法按負(fù)載平衡策略進(jìn)行調(diào)度的計算結(jié)果，不帶*的為比對方法的調(diào)度結(jié)果。比對方法按事先指定的分管關(guān)系來分配運(yùn)輸任務(wù)。從表中看出本文算法負(fù)載較為均衡。表中表示按分管關(guān)系指派的總體開銷，表示按優(yōu)化算法指派的總體開銷式（1），盡管按優(yōu)化算法，某些分隊（例如4 號分隊）的開銷會比對比方法增加，但所有分隊的總計開銷是減小的，兩天約節(jié)省了17%的總運(yùn)輸時間。和表示如果按分管關(guān)系指派和優(yōu)化算法指派，從運(yùn)輸分隊當(dāng)前位置到任務(wù)的起點(diǎn)之間的開銷（式（1）中的第1 項），從中可以看出就近指派而節(jié)約的運(yùn)輸開銷，從統(tǒng)計數(shù)據(jù)可以看出，采用就近指派可以大幅度降低運(yùn)輸開銷，即對運(yùn)輸力量進(jìn)行聯(lián)合指揮有較大優(yōu)勢。

5 結(jié)論

為了適應(yīng)戰(zhàn)場的動態(tài)不確定性，本文提出了一種快速實時的運(yùn)輸分隊指派及路徑規(guī)劃算法。算法的優(yōu)化目標(biāo)是最小化戰(zhàn)場運(yùn)輸力量的平均加權(quán)開銷（花費(fèi)路程及時間等），本文提出的調(diào)度和規(guī)劃算法能夠取得較高的任務(wù)吞吐率（單位時間執(zhí)行更多的運(yùn)輸任務(wù)），且方便不同粒度的運(yùn)力組織。另外由于本文提出的優(yōu)化規(guī)劃算法具有輕型靈活等特點(diǎn)，適應(yīng)性強(qiáng)。對于運(yùn)輸?shù)囊恍┘s束條件，例如運(yùn)載量的限制、時間窗的指定等，稍加修改就可以擴(kuò)充到本算法中。