杜小敏，胡遠(yuǎn)新

（陸軍勤務(wù)學(xué)院 軍事設(shè)施系，重慶401331）

0 引言

近年來自然災(zāi)害呈現(xiàn)頻發(fā)多發(fā)、范圍大、破壞性強(qiáng)的趨勢(shì)，在政府和軍隊(duì)的應(yīng)急處置過程中，隨著對(duì)受傷人員的救助、應(yīng)急物資的供應(yīng)、災(zāi)后恢復(fù)生產(chǎn)生活秩序等任務(wù)的開展，產(chǎn)生了總量較大的、多樣化的應(yīng)急運(yùn)輸需求。應(yīng)急運(yùn)輸是指以滿足自然災(zāi)害、公共事件等突發(fā)事件的運(yùn)輸需求為目的，綜合運(yùn)用軍隊(duì)和社會(huì)的交通運(yùn)輸設(shè)施、設(shè)備、運(yùn)載工具、信息資源，追求時(shí)間效益的最大化和災(zāi)害損失的最小化的一種特殊的運(yùn)輸活動(dòng)。軍隊(duì)平時(shí)的主要任務(wù)是練兵備戰(zhàn)，同時(shí)參與搶險(xiǎn)救災(zāi)、應(yīng)急救援等非戰(zhàn)爭(zhēng)軍事行動(dòng)，在自然災(zāi)害發(fā)生時(shí)，軍隊(duì)?wèi){借組織指揮優(yōu)勢(shì)、快速反應(yīng)能力和機(jī)動(dòng)能力，擔(dān)任了應(yīng)急運(yùn)輸?shù)耐粨絷?duì)和中堅(jiān)力量，在應(yīng)急處置過程中發(fā)揮了突出作用，同時(shí)也是對(duì)軍隊(duì)?wèi)?yīng)急運(yùn)輸能力的實(shí)戰(zhàn)化檢驗(yàn)。

車輛調(diào)度問題（Vehicle Scheduling Problem,VSP）是指在車輛數(shù)量一定的情況下，根據(jù)用戶的需求合理地調(diào)配有限的車輛資源，在最大限度滿足用戶需求的前提下使運(yùn)輸成本最低，最后得到最優(yōu)的調(diào)度方案。車輛調(diào)度方案的決策是應(yīng)急運(yùn)輸?shù)闹匾h(huán)節(jié)，對(duì)提高應(yīng)急運(yùn)輸效率、爭(zhēng)取應(yīng)急救援黃金時(shí)間、實(shí)現(xiàn)精準(zhǔn)保障具有重要意義。近年國(guó)內(nèi)外對(duì)應(yīng)急運(yùn)輸車輛調(diào)度問題的研究不斷深入，王偉[2]研究了在通信中斷和運(yùn)輸路網(wǎng)中斷導(dǎo)致物資運(yùn)輸時(shí)間延遲的車輛調(diào)度問題；喻德曠[3]針對(duì)多種運(yùn)輸貨物類型和實(shí)時(shí)路況變化構(gòu)建了車輛調(diào)度模型；楊海強(qiáng)[4]提出了基于需求優(yōu)先權(quán)重和未滿足物資需求量最小的應(yīng)急車輛調(diào)度模型；陳湉[5]研究了物資需求呈正態(tài)分布條件下物資分配不足或過量的車輛調(diào)度問題；鄧燁[6]運(yùn)用魯棒優(yōu)化理論將車輛調(diào)度問題中的物資需求等不確定參數(shù)轉(zhuǎn)化為確定性參數(shù)進(jìn)行分析；J.Sch?nberger[7]為解決短期物流設(shè)施抵達(dá)車輛過多的問題，提出了混合整數(shù)線性問題來表示多周期的運(yùn)輸決策任務(wù)，分析了不同請(qǐng)求組合對(duì)總距離最小化的影響；Safaei[8]構(gòu)建了應(yīng)急運(yùn)輸雙層優(yōu)化模型，上層是基于救濟(jì)物資分配地點(diǎn)影響的總成本最低和未滿足需求最少，下層考慮選擇風(fēng)險(xiǎn)較低的供應(yīng)商；?zdamar[9]研究了供給和需求動(dòng)態(tài)時(shí)變條件下的多種物資多階段的的應(yīng)急運(yùn)輸問題，以運(yùn)輸總時(shí)間最短為目標(biāo)函數(shù)；Korosec[10]研究了具有裝卸作業(yè)頻率高特點(diǎn)的倉(cāng)庫(kù)和港口的運(yùn)輸調(diào)度問題，分別采用分組運(yùn)輸和自由運(yùn)輸?shù)姆椒▽?duì)四項(xiàng)運(yùn)輸任務(wù)進(jìn)行優(yōu)化測(cè)試。

在緊急情況下，應(yīng)急運(yùn)輸具有時(shí)效性、弱經(jīng)濟(jì)性的特點(diǎn)，因此車輛調(diào)度對(duì)時(shí)間的要求比較高，對(duì)成本的要求比較低，以最短的時(shí)間完成應(yīng)急運(yùn)輸任務(wù)具有現(xiàn)實(shí)意義；軍隊(duì)參與非戰(zhàn)爭(zhēng)軍事任務(wù)同樣是以完成任務(wù)為第一目標(biāo)，經(jīng)濟(jì)成本方面的考慮次之，與應(yīng)急運(yùn)輸?shù)哪繕?biāo)是統(tǒng)一的，因此軍隊(duì)在遂行應(yīng)急運(yùn)輸任務(wù)上天然具有優(yōu)勢(shì)。本文構(gòu)建了基于單邊時(shí)間窗的軍隊(duì)?wèi)?yīng)急運(yùn)輸車輛調(diào)度模型，只考慮最晚到達(dá)時(shí)間的單邊時(shí)間窗符合應(yīng)急運(yùn)輸目標(biāo)特點(diǎn)，計(jì)劃通過車輛編組實(shí)施應(yīng)急運(yùn)輸保障，然后設(shè)計(jì)了一種改進(jìn)遺傳算法進(jìn)行求解，對(duì)交叉算子、變異算子和可行化過程進(jìn)行了改進(jìn)。

1 問題描述與模型構(gòu)建

根據(jù)近年自然災(zāi)害應(yīng)急運(yùn)輸實(shí)踐，對(duì)災(zāi)時(shí)軍隊(duì)車輛調(diào)度問題描述如下：在自然災(zāi)害發(fā)生后，有多個(gè)受災(zāi)點(diǎn)需要緊急調(diào)撥各類物資，受災(zāi)點(diǎn)用i（i=1,2,…,n）表示，受災(zāi)點(diǎn)的物資需求量表示為Gi（g1,g2,…,gn），駐地部隊(duì)某運(yùn)輸旅發(fā)現(xiàn)災(zāi)情后，立即啟動(dòng)應(yīng)急響應(yīng)，擬派出k（k=1,2,…,K）個(gè)車隊(duì)組織進(jìn)行救災(zāi)物資的應(yīng)急運(yùn)輸，每個(gè)車隊(duì)有L輛車，一個(gè)車隊(duì)要求統(tǒng)一行動(dòng)，先前往物資儲(chǔ)備庫(kù)裝載物資，然后按照計(jì)劃路徑前往受災(zāi)點(diǎn)卸載物資，最后全部返回運(yùn)輸旅。

為便于構(gòu)建模型，作以下假設(shè)和參數(shù)定義：

（1）每個(gè)受災(zāi)點(diǎn)由單個(gè)車隊(duì)進(jìn)行保障；

（2）每個(gè)車隊(duì)單次裝載物資或卸載物資的時(shí)間均為Tx；

（3）根據(jù)受災(zāi)程度的不同，受災(zāi)點(diǎn)要求應(yīng)急運(yùn)輸物資的最晚到達(dá)時(shí)間，即考慮單邊時(shí)間窗，表示為[0,LTi]；車隊(duì)預(yù)計(jì)抵達(dá)受災(zāi)點(diǎn)i的時(shí)間為Ti；

（4）車隊(duì)勻速行駛速度為V；

（5）每輛車可裝載物資為Q；

（7）dij表示點(diǎn)i與j之間距離，使用決策變量xijk表示車隊(duì)k從i點(diǎn)出發(fā)到達(dá)j點(diǎn)，此處的點(diǎn)i、j包括物資儲(chǔ)備庫(kù)點(diǎn)0和運(yùn)輸旅駐地點(diǎn)n+1；

目標(biāo)函數(shù)表示為帶時(shí)間窗懲罰函數(shù)的總路程最短，如式（1），L代表每個(gè)車隊(duì)具有相同的車輛數(shù)目，S是一個(gè)車輛調(diào)度方案的總路程，P是懲罰函數(shù)：

其中：

α和β是懲罰系數(shù)，α是車隊(duì)超時(shí)的時(shí)間之和的懲罰系數(shù)，β是超時(shí)的車隊(duì)數(shù)目的懲罰系數(shù)，Viol代表在n個(gè)受災(zāi)點(diǎn)中超過最晚到達(dá)時(shí)間的個(gè)數(shù)。假使將目標(biāo)函數(shù)中的L替代為L(zhǎng)k，Lk代表車輛調(diào)度方案中的第k個(gè)車隊(duì)的車輛數(shù)目不大于L，那么最終車輛調(diào)度方案會(huì)使車輛運(yùn)行的總路徑更小，即代表成本更低，但是配送時(shí)間相對(duì)地會(huì)少許延長(zhǎng)。由于應(yīng)急運(yùn)輸更強(qiáng)調(diào)時(shí)效性，而不強(qiáng)調(diào)經(jīng)濟(jì)性，受災(zāi)民眾仍然希望在滿足時(shí)間窗的前提下盡可能早地收到應(yīng)急物資，因此目標(biāo)函數(shù)仍采用式（1），在計(jì)算出最優(yōu)車輛調(diào)度方案后，再判斷各個(gè)車隊(duì)是否存在空載的車輛，并剔除多余車輛，以保證以最短時(shí)間完成應(yīng)急運(yùn)輸任務(wù)。

模型約束條件如下：

其中式（4）表示從需求點(diǎn)i出發(fā)的只有一個(gè)車隊(duì)；式（5）表示抵達(dá)需求點(diǎn)j的只有一個(gè)車隊(duì)；式（6）表示車隊(duì)k經(jīng)過受災(zāi)點(diǎn)的需求總和不大于載重Q；式（7）表示每個(gè)點(diǎn)都有車隊(duì)運(yùn)輸滿足其需求。

2 基于改進(jìn)遺傳算法的模型求解

車輛調(diào)度優(yōu)化問題被證明為NP-Hard問題，隨著需求點(diǎn)的增加，問題解的組合數(shù)呈爆炸式增長(zhǎng)，求解難度大。車輛調(diào)度優(yōu)化問題的求解方法可分為兩大類，即精確算法和啟發(fā)式算法，精確算法包括分支定界法、列生成法等，對(duì)于規(guī)模較大的車輛調(diào)度問題使用精確算法求解難度較大，目前學(xué)界更多傾向于啟發(fā)式算法研究，有混合蛙跳算法[11]、免疫算法[12]、混合遺傳算法[13]、層次蝙蝠算法[14]、鯨魚群優(yōu)化算法[15]等。

為對(duì)上述模型求解，設(shè)計(jì)一種改進(jìn)遺傳算法，目的是提高尋優(yōu)效率、避免局部最優(yōu)，具體步驟如下：

（1）基因編碼、解碼和種群初始化。遺傳算法中基因指的是問題的解，在應(yīng)急運(yùn)輸車輛調(diào)度問題中，所有車隊(duì)的調(diào)度方案作為一個(gè)染色體，若干的染色體的集合作為一個(gè)種群，編碼指的是從表現(xiàn)型到基因型的映射，基因解碼反之。

該模型的一個(gè)解所對(duì)應(yīng)的染色體分為兩段，DNA_1=[dna1,dna2,…,dnan]是受災(zāi)點(diǎn)的序列號(hào)，DNA_2=[dna1,dna2,…,dna(K-1)]是斷點(diǎn)序列號(hào)作為區(qū)分各個(gè)車隊(duì)負(fù)責(zé)運(yùn)輸路徑，其中物資儲(chǔ)備庫(kù)的序號(hào)為0，運(yùn)輸旅駐地的序號(hào)為n+1。例如根據(jù)上文對(duì)問題和模型的描述，車隊(duì)先從運(yùn)輸旅駐地出發(fā)，前往物資儲(chǔ)備庫(kù)裝載物資，到達(dá)受災(zāi)點(diǎn)卸載物資再返回，因此該DNA表示第一車隊(duì)的運(yùn)輸路徑是10-0-3-2-10，第二車隊(duì)的運(yùn)輸路徑是10-0-1-6-5-10，第三車隊(duì)為10-0-4-9-0，第四車隊(duì)為10-0-8-7-0。

種群是遺傳交叉、變異和自然選擇的基本單位，初始種群采用隨機(jī)產(chǎn)生序列的方式生成，初始種群是稂莠不齊的，種群規(guī)模越大，種群的多樣性越豐富，初始種群中包含優(yōu)質(zhì)個(gè)體的幾率越高，交叉和變異產(chǎn)生的子代個(gè)體也越多，但是相應(yīng)的計(jì)算量呈線性增長(zhǎng)，因此適當(dāng)設(shè)定種群規(guī)模有助于提高計(jì)算效率，種群中染色體的數(shù)量一般設(shè)置為染色體長(zhǎng)度的線性級(jí)別倍數(shù)。

（2）交叉算子和變異算子。將種群隨機(jī)分為兩兩一組，根據(jù)交叉算子Pc，產(chǎn)生本輪的隨機(jī)數(shù)Pt，當(dāng)Pt小于交叉算子Pc時(shí)，隨機(jī)對(duì)其中某段進(jìn)行交叉操作，產(chǎn)生新的個(gè)體。交叉操作設(shè)計(jì)為兩種，第一種交叉操作采用部分匹配法（Partially Matching Crossover,PMX），第二種是對(duì)交叉段基因交換，移到首部位置后，消除重復(fù)項(xiàng)，產(chǎn)生兩個(gè)子代個(gè)體，可稱為類PMX算子。例如：

第一種交叉：

第二種交叉：

變異操作的步驟是，首先對(duì)種群內(nèi)所有個(gè)體進(jìn)行判斷，當(dāng)隨機(jī)數(shù)Pt小于Pm時(shí)，對(duì)該個(gè)體進(jìn)行變異操作，產(chǎn)生新的個(gè)體。變異操作設(shè)計(jì)為，對(duì)染色體受災(zāi)點(diǎn)序列中的一個(gè)片段進(jìn)行倒序逆轉(zhuǎn)，同時(shí)讓斷點(diǎn)序列基因中的隨機(jī)項(xiàng)突變?yōu)榱硪粋€(gè)數(shù)，并重新排序，獲得子代個(gè)體的DNA序列。例如：

在交叉和變異操作之后，由原種群加上交叉變異產(chǎn)生的子代種群，共同構(gòu)成新的種群，此時(shí)新種群數(shù)量約為原種群的（1+Pm+Pc）倍。交叉操作是為了讓DNA中的優(yōu)秀基因片段充分交換，產(chǎn)生新的優(yōu)質(zhì)個(gè)體，變異操作是為了增強(qiáng)種群的多樣性，避免過快收斂進(jìn)入局部最優(yōu)。

（3）可行化。滿足約束條件的個(gè)體稱之為良種，反之為劣種，可行化指的是將劣種轉(zhuǎn)化為良種的過程。上述模型的約束條件在此處主要表現(xiàn)為車隊(duì)的載重約束，對(duì)新的種群進(jìn)行約束條件判斷，對(duì)不可行解逐一進(jìn)行可行化。對(duì)劣種的可行化過程具有一定必要性，如果不進(jìn)行可行化而是直接刪除劣種，在運(yùn)輸旅的運(yùn)輸力量不太充足的情況下，隨機(jī)產(chǎn)生的初始種群會(huì)包含大量的劣種，將劣種直接從種群中刪除將導(dǎo)致種群數(shù)目急劇下降，導(dǎo)致難以維持預(yù)期的種群規(guī)模，無法進(jìn)入下一次遺傳迭代?？尚谢惴ǖ乃悸窞?，首先根據(jù)不可行解的路徑集合，找出超載最多的車隊(duì)kmax和載重最小的車隊(duì)kmin，將車隊(duì)kmax路徑中的一個(gè)需求點(diǎn)轉(zhuǎn)移至車隊(duì)kmax的路徑中，當(dāng)循環(huán)7次仍不能滿足載重約束，刪除該個(gè)體。測(cè)試表明當(dāng)不進(jìn)行可行化時(shí)，對(duì)初始種群的劣種通常刪除超過50%，使用該可行化算法后在5 000次迭代中平均每次迭代刪除劣種0.63個(gè)。

（4）自然選擇。對(duì)可行化之后的新種群，逐一計(jì)算適應(yīng)度，擇優(yōu)進(jìn)入下一代，將種群淘汰至初始種群規(guī)模。為確保優(yōu)質(zhì)個(gè)體與劣質(zhì)個(gè)體在自然選擇中的差別，適應(yīng)度函數(shù)表示如下。

自然選擇的方法一般有輪盤賭選擇法，隨機(jī)遍歷抽樣法，錦標(biāo)賽選擇法，考慮到算法收斂效率采取精英保留策略和輪盤賭選擇法相結(jié)合的策略，首先按1/4的比例將適應(yīng)度最優(yōu)的個(gè)體直接保留至下一代種群，剩余部分采用輪盤賭選擇法進(jìn)行選擇，可以在充分保證種群中的優(yōu)秀個(gè)體能夠遺傳到下一代的同時(shí)，其余個(gè)體憑借自身適應(yīng)度接受輪盤賭的隨機(jī)選擇，適應(yīng)度高的個(gè)體自然能夠大概率遺傳下去，減緩種群收斂過程，充分迭代優(yōu)化更容易尋到全局最優(yōu)。

（5）結(jié)束判斷。當(dāng)?shù)螖?shù)達(dá)到最大設(shè)定值，結(jié)束迭代循環(huán)。

3 算例分析

選取Solomon VRSPTW問題測(cè)試集的RC208前15個(gè)和后15個(gè)位置數(shù)據(jù)進(jìn)行算例分析，即保證需求點(diǎn)的位置分布包含聚類結(jié)構(gòu)和隨機(jī)結(jié)構(gòu)，物資儲(chǔ)備庫(kù)坐標(biāo)[40,50]，運(yùn)輸旅駐地坐標(biāo)[35,45]。單車載重Q=6，一個(gè)車隊(duì)的車輛數(shù)L=7，車隊(duì)數(shù)K=8，每次裝載和卸載時(shí)間Tx=0.5，車隊(duì)速度V=40，物資需求Gi和最晚到達(dá)時(shí)間LTi見表1。

表1 受災(zāi)點(diǎn)物資需求和最晚到達(dá)時(shí)間信息

受災(zāi)點(diǎn)分布如圖1所示。

圖1 受災(zāi)點(diǎn)坐標(biāo)分布

對(duì)該算例使用上述改進(jìn)遺傳算法進(jìn)行測(cè)試分析，機(jī)器配置為i7-2620m，主頻2.70GHz，內(nèi)存8G，軟件Matlab2010a，交叉概率pc=0.8，變異概率pm=0.1，懲罰系數(shù)α=40，β=100，種群規(guī)模為80，最大迭代次數(shù)5 000次，分別進(jìn)行了10次優(yōu)化求解，測(cè)試結(jié)果見表2，最優(yōu)路徑圖示和迭代過程如圖2、圖3所示。

表2 測(cè)試結(jié)果

圖2 最優(yōu)路徑圖示

計(jì)算結(jié)果表明，10次測(cè)試中每次的最優(yōu)解均沒有超過時(shí)間窗，可以滿足應(yīng)急運(yùn)輸?shù)臅r(shí)間要求和受災(zāi)點(diǎn)的物資需求，能夠獲得該車輛調(diào)度問題最優(yōu)路程的近似解，保證以最短時(shí)間完成應(yīng)急運(yùn)輸，提高了應(yīng)急運(yùn)輸?shù)男剩皇褂玫母倪M(jìn)遺傳算法對(duì)該模型求解有較好的收斂效果，證明了該改進(jìn)遺傳算法在解決軍隊(duì)?wèi)?yīng)急運(yùn)輸車輛調(diào)度優(yōu)化問題的有效性。其中第9次的測(cè)試結(jié)果為最優(yōu)，其目標(biāo)函數(shù)Z為4 902.78，總路程為700.40km，車隊(duì)路徑為：

圖3 迭代過程

k=1：20-16-27-17，行駛路程98.50km，加物資裝卸時(shí)間共耗時(shí)4.96h，物資裝載率為98%；

k=2：21-22-25-19，行駛路程115.01km，耗時(shí)5.38h，物資裝載率為69%，因此可以在車隊(duì)中減少2輛運(yùn)輸車；

k=3：2-18-28-29，行駛 路程91.77km，耗 時(shí)4.79h，物資裝載率為87%；

k=4：26-23-24，行駛路程56.78km，耗時(shí)3.42h，物資裝載率為62%，車隊(duì)可減少2輛運(yùn)輸車；

k=5：12-14-15-13-9，行駛路程86.05km，耗時(shí)5.15h，物資裝載率為95%；

k=6：4-8-7，行駛路程89.18km，耗時(shí)4.23h，物資裝載率為83%，車隊(duì)可減少1輛運(yùn)輸車；

k=7：10-11，行駛路程68.15km，耗時(shí)3.20h，物資裝載率為83%，車隊(duì)可減少1輛運(yùn)輸車；

k=8：30-1-3-5-6，行駛路程94.96km，耗時(shí)5.37h，物資裝載率為87%。

實(shí)際上按照該車輛調(diào)度方案8個(gè)車隊(duì)50輛運(yùn)輸車可以完成應(yīng)急運(yùn)輸任務(wù)。

4 結(jié)語(yǔ)

應(yīng)急運(yùn)輸在應(yīng)急管理體系中具有基礎(chǔ)性支撐作用，各項(xiàng)應(yīng)急處置行動(dòng)對(duì)運(yùn)輸?shù)男枨笫瞧毡榈模瑹o論是救援行動(dòng)、衛(wèi)生醫(yī)療保障、重要生活物資保障、恢復(fù)生產(chǎn)生活秩序都離不開高效的應(yīng)急運(yùn)輸保障。為提高軍隊(duì)完成應(yīng)急運(yùn)輸保障任務(wù)的能力，構(gòu)建了基于單邊時(shí)間窗的軍隊(duì)?wèi)?yīng)急運(yùn)輸車輛調(diào)度模型，目標(biāo)函數(shù)為帶時(shí)間懲罰函數(shù)的總路程最短，使用改進(jìn)遺傳算法進(jìn)行優(yōu)化求解，主要方法是交叉算子使用PMX算子和類PMX算子，變異算子使用受災(zāi)點(diǎn)序列倒序變異結(jié)合斷點(diǎn)序列單點(diǎn)變異的方式，在自然選擇之前通過可行化算子將種群中的劣種轉(zhuǎn)化為良種。結(jié)果表明，該算法能夠保持優(yōu)良基因，較好地克服早熟收斂的問題，得出了更精確、高效的車輛調(diào)度方案，有效保障了受災(zāi)點(diǎn)需求，能夠發(fā)揮軍隊(duì)組織指揮優(yōu)勢(shì)、快速反應(yīng)能力和運(yùn)輸投送能力，為我軍參與非戰(zhàn)爭(zhēng)軍事行動(dòng)的應(yīng)急運(yùn)輸決策提供了參考。