戰(zhàn)場(chǎng)運(yùn)輸在線路徑規(guī)劃算法研究*

曾 斌，姚 路，秦 瀟

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

0 引言

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

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

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

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

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

為此本文針對(duì)特點(diǎn)1）在第3 節(jié)提出了基于在線資源分配的任務(wù)調(diào)度算法，在調(diào)度任務(wù)時(shí)，針對(duì)特點(diǎn)3）中運(yùn)輸路徑網(wǎng)絡(luò)化且要求同時(shí)具有集貨和送貨功能，利用特點(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)輸總開(kāi)銷的目的。

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

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

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

1 基于圖理論的問(wèn)題建模

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

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

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

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

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

圖1 雙向連接的2 條路徑

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

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

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ù)以下步驟把它們合并為一個(gè)任務(wù)j3。

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

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

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

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

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

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

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

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

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

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

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

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

它們分別產(chǎn)生如下2 個(gè)總開(kāi)銷：

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

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

即依次執(zhí)行j1、j2直至jn，這時(shí)新到達(dá)一個(gè)具有相同終點(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ù)

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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