曹冠平 王躍利 丁 茜

（軍事科學(xué)院 北京 100091）

1 引言

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

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

2 數(shù)學(xué)模型的建立

2.1 問題描述

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

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

2.2 模型建立

模型參數(shù)和決策變量如下：

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

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

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

根據(jù)以上描述，構(gòu)建數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：

約束條件：

3 算法求解

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

3.1 染色體編碼

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

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

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

3.2 初始化種群

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

3.3 計算適應(yīng)度

適應(yīng)度函數(shù)定義的好壞直接影響整個算法的執(zhí)行效率，針對本文設(shè)計的模型算法，將適應(yīng)度函數(shù)f(x)設(shè)為目標(biāo)函數(shù)的倒數(shù)，即：

適應(yīng)度函數(shù)值越大的染色體越優(yōu)越，也越有可能接近最優(yōu)解。

3.4 交叉和變異操作

為有效保持群體的多樣性，需要對染色體進(jìn)行交叉和變異操作。交叉時，由于染色體中包含多個“1”，直接交叉容易產(chǎn)生誤碼，出現(xiàn)大量不可行解，進(jìn)而降低算法的收斂速度。同時，考慮到如果某種排列能夠得到較優(yōu)的解，應(yīng)當(dāng)適當(dāng)保留染色體的順序，因此，我們對交叉方式進(jìn)行了改進(jìn)，具體如下：第一步，將父代染色體中的“1”刪除，并記錄其位置；第二步，隨機(jī)選擇父代染色體一個基因位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}

隨機(jī)選取基因位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}

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

3.5 選擇操作

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

3.6 算法終止條件

設(shè)定算法的最大迭代次數(shù)為M，當(dāng)?shù)螖?shù)超過M時，算法結(jié)束。

4 仿真實驗及分析

假設(shè)在一次保障任務(wù)中，某保障中心擔(dān)負(fù)轄區(qū)所有11個單位的物資配送，保障中心僅有4臺運(yùn)輸車輛，車輛載重量均為16t，平均行駛速度為50km/h，計算時間時，只考慮車輛到達(dá)最后一個需求單位的時間，不考慮物資裝卸載和返回時間。已知各單位 物 資 需 求 集 合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為各物資需求單位的編號），現(xiàn)要求在符合上述條件下，設(shè)計最佳配送方案。

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

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

表2 物資配送最佳方案表

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

5 結(jié)語

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