戰時物資配送模型及算法研究*

曹冠平 王躍利 丁 茜

（軍事科學院 北京 100091）

1 引言

物資配送優化問題是軍事物流學中的一個重要內容，是運籌學中運輸問題的一個分支，不僅涉及多個單位、多種資源，還需滿足資源、經費、時間、安全等多種約束條件，具有大規模、多約束、多目標等特點。采用傳統的線性規劃方法進行求解比較困難，有必要借助智能優化算法進行科學定量決策。當前，軍內外專家學者展開了大量相關研究。如，韓景倜等人以保障時間最短為目的，研究了運力充足情況下的單種物資調運問題［1］；任杰等設計了滿足應急時間約束的，基于成本最小的車輛調度數學模型，并通過設置罰函數將車輛載質量約束和時間約束轉化為運輸成本，最后借助遺傳算法進行了求解［2］；但兵兵等以總配送時間最短、動用車輛數最少和時間平衡性最佳為目標，建立了基于需求可拆分條件下的應急物資調度數學模型，并設計了一種改進蟻群優化算法進行求解［3］；朱毅等以配送時間最短為目的，研究了保障力有限情況下的器材配送問題，并用改進粒子群算法進行了求解［4］；文仁強等以調度時間最短為優化目標，對無滿載限制情形下的應急資源多目標優化調度問題進行研究，并通過蟻群算法進行求解［5］；姜大立等以應急時間最短和車輛空載率最低為目的，對單需求點物資調運問題進行了研究，并用多目標粒子群算法進行了求解［6］；宋遠清等在不考慮運輸成本的前提下，研究了需求隨機的車輛調度問題［7～8］，宋遠清運用遺傳算法對車輛調度問題進行了求解［9～10］；鄒明等運用遺傳算法對航空裝備保障的調度優化進行了研究［11～12］。

上述研究從不同視角、運用不同方法對物資配送優化等進行了分析，取得了很好的效果，但仍存在一些不足：一是物資配送過程中，對運輸車輛不足的情況考慮還不夠充分，部分研究雖然考慮了保障力量有限這個約束，但所建模型多以最短時間為目標，忽略了各需求點對物資需求緊迫程度的差異性，沒有兼顧保障時間、車輛裝載量以及物資需求緊迫度等因素；二是運用遺傳算法求解時，對計算過程中如何避免不可行解，提升算法收斂速度考慮不夠，往往只是借助罰函數來淘汰非法解，算法搜索效率不高。鑒于此，本文以配送時間和需求緊迫度的乘積最小為目標函數，建立了滿足運輸車輛最大裝載量約束的物資配送數學模型，并利用遺傳算法對最優物資配送方案進行求解。為有效確保解的優質性和算法的收斂速度，在合理編碼的基礎上，設計了特殊交叉和變異算子。最后，通過算例進行了仿真，結果表明所建模型和算法能夠快速求出滿足要求的最佳方案，對做好戰時物資保障具有很強的指導性和操作性。

2 數學模型的建立

2.1 問題描述

假設某綜合保障中心負責轄區所有單位戰時的物資保障工作。中心有m臺運輸車輛來進行物資配送，車輛序號集 K={k|k=1，2，…，m}，設A={1，2，…，n，n+1 }為地點集，1代表保障中心，其他n個物資需求點由2-n+1進行統一編號；Lij表示地點i到地點 j的距離；R表示各單位物資需求總量，rj表示第 j個單位所需物資量，P表示運輸車輛的最大載重量；ωj表示第 j個單位的物資需求緊迫度，v表示運輸車輛的平均運行速度。物資配送要求：每臺運輸車輛定向保障相應的單位，行進路線和順序固定，結合各需求點物資需求緊迫程度，在最短時間內完成配送任務。

為更好地明確研究邊界，做如下假設：1）各物資需求單位和保障中心之間以及各物資需求單位之間均滿足運輸車輛通行條件；2）問題中各已知信息能夠及時獲取，保障中心物資存儲量大于各物資需求單位的總需求量，即只考慮物資運送時間，不考慮物資裝卸載時間；4）車輛完成配送任務后不需要返回需求點上。

2.2 模型建立

模型參數和決策變量如下：

F={fk|k∈K}為配送方案集，其中第k臺車的配送方案，表示配送過程中車輛依次經過的地點序列，e為第k臺車經過的地點總數。如 f1={1，3，5，6，8}，表示配送過程中，第1臺車輛經過的地點依次為1、3、5、6、8。

TSj表示物資需求點 j配送時間和需求緊迫度的乘積，有：

xjk為決策變量，當需求點 j由第k臺車配送時，xjk等于1，否則等于0。

根據以上描述，構建數學模型如下：

目標函數：

約束條件：

3 算法求解

針對上述模型，我們采用遺傳算法進行求解，求解的基本流程如圖1。

3.1 染色體編碼

本文中，我們采用自然數編碼方式來構造表示運輸車輛可行路線的染色體。即：將數學模型的解向量編成一條長度為m+n+1的染色體{1，ip，…，iq，1，ir，…，is，1，…，1，it…，iu，1} ，在 染 色 體 中 ，ip(2≤p≤n+1)等自然數為某物資需求單位的編號，1表示保障中心，共有m+1個，它將染色體切分為m段，分別表示m臺運輸車輛的配送任務序列。染色體的編碼可解釋為：第1臺運輸車輛從保障中心出發，按照{ip，…，iq}的順序進行物資配送；第2臺運輸車輛從保障中心出發，按照{ir，…，is} 的順序進行物資配送；依次類推，第m臺運輸車輛從保障中心出發，按照{it…，iu}的順序進行物資配送。所有運輸車輛配送完畢則物資保障任務結束。

圖1 遺傳算法求解基本流程圖

例如：若 m=3，n=10，染色體為 {1，2，5，3，1，4，11，6，1，7，9，8，10，1}，按照編碼規則可以確定配送方案：第1、2、3臺運輸車輛配送順序分別為1→2→5→3，1→4→11→6和 1→7→9→8→10。

3.2 初始化種群

初始種群是進化計算開始時的群體，設種群規模為N，本文初始種群產生方法如下：第一步，將物資需求單位的編號進行隨機排序；第二步，按染色體編碼順序從左至右進行計算，如果第一臺車輛裝載量大于前α個單位物資需求量之和且小于前α+1個單位物資需求量之和，則得到第1臺車輛的配送序列；第三步，刪除染色體中前α個物資需求單位的編號，染色體剩余部分繼續按步驟2的方式計算，求得第2臺車輛的配送序列，如此反復，直至所有車輛和物資需求單位的編號均被安排完；第四步，在每兩個配送序列之間插入“1”后，將所有配送序列連接起來，最后在首尾添加“1”，即得到一條初始染色體；第五步，重新對物資需求單位的編號隨機排序，按相同辦法產生剩余染色體直至種群規模達到N。

3.3 計算適應度

適應度函數定義的好壞直接影響整個算法的執行效率，針對本文設計的模型算法，將適應度函數f(x)設為目標函數的倒數，即：

適應度函數值越大的染色體越優越，也越有可能接近最優解。

3.4 交叉和變異操作

為有效保持群體的多樣性，需要對染色體進行交叉和變異操作。交叉時，由于染色體中包含多個“1”，直接交叉容易產生誤碼，出現大量不可行解，進而降低算法的收斂速度。同時，考慮到如果某種排列能夠得到較優的解，應當適當保留染色體的順序，因此，我們對交叉方式進行了改進，具體如下：第一步，將父代染色體中的“1”刪除，并記錄其位置；第二步，隨機選擇父代染色體一個基因位i；第三步：保留兩個父代染色體中位于基因位i之前的基因值，將之后的基因值按對方基因值重新排列；第四步：將“1”插入之前記錄的位置，得到子代染色體。

以3輛車10個需求點為例，若：

父染色體 1 為 {1，6，3，11，1，7，8，5，2，1，4，9，10，1} ；父 染 色 體 2 為 {1，11，5，6，1，3，10，8，1，4，7，2，9，1}

隨機選取基因位5，交叉后：

子 染 色 體 1 為 {1，6，3，11，1，7，8，5，10，1，4，2，9，1} ；子染色體 2 為 {1，11，5，6，1，3，10，7，1，8，2，4，9，1}

變異時，為防止改變染色體的結構和物理性狀，減少無效染色體的產生，采取交換變異的方式，具體如下：第一步，將染色體中的“1”刪除，并記錄其位置；第二步，隨機選擇染色體上2個基因位，交換二者的位置；第三步，將“1”插入之前記錄的位置，得到新的染色體。

3.5 選擇操作

選擇策略采用輪盤賭和精英保留相結合的方式進行，即：在生產下一代種群時，先采用輪盤賭法從父代中選擇一部分染色體進行交叉和變異操作進入下一代種群（選擇概率為GGAP）；其他個體則由父代中最優個體直接復制而得。

3.6 算法終止條件

設定算法的最大迭代次數為M，當迭代次數超過M時，算法結束。

4 仿真實驗及分析

假設在一次保障任務中，某保障中心擔負轄區所有11個單位的物資配送，保障中心僅有4臺運輸車輛，車輛載重量均為16t，平均行駛速度為50km/h，計算時間時，只考慮車輛到達最后一個需求單位的時間，不考慮物資裝卸載和返回時間。已知各單位 物 資 需 求 集 合R={4.6，3.6，6.2，5.2，6.4，7.0，5.4，3.8，8.6，7.4，5.0}，緊迫度集合ω={0.13，0.08，0.06，0.07，0.06，0.09，0.05，0.11，0.12，0.14，0.09} ，保障中心和各物資需求單位之間的距離如表1（1代表保障中心，2～12為各物資需求單位的編號），現要求在符合上述條件下，設計最佳配送方案。

表1 保障中心和各物資需求單位之間的距離（單位：km）

在運用遺傳算法進行求解時，設置種群規模N=50，M=500，GGAP=0.9。通過Matlab編程對算例進行求解，得到最佳配送方案，見表2。

表2 物資配送最佳方案表

結果分析：從得到的配送方案看，能夠完全滿足各運輸車輛的最大載重量約束，并且各運輸車輛任務完成時間比較一致，在滿足物資需求緊迫度方面，需求緊迫的11、2、10、9號單位得到了優先保障，其他單位的配送順序，也都綜合考慮了配送時間和緊迫程度，實現了保障方案的最優化。

5 結語

戰時，物資消耗巨大、需求時間緊迫、保障力量有限，科學的物資配送方案是部隊保持戰斗力的關鍵。本文針對現有戰時物資配送問題中存在的不足，通過建立物資配送問題的數學模型，并運用遺傳算法進行了求解，為提升算法的有效性和收斂速度，對初始種群產生方法進行了合理設計，多染色體交叉和變異算子進行了有效改進，使得算法能夠快速求出滿足要求的最優解，為戰時物資配送問題提供了一個行之有效的方法。本文設計的模型和算法也適用于軍兵種物資配送、路徑尋優以及任務指派等問題。下一步，將進一步對車輛載重量不同、物資需求種類不同等情況的物資配送問題進行研究。