災時軍隊應急運輸車輛調(diào)度優(yōu)化

杜小敏，胡遠新

（陸軍勤務學院 軍事設施系，重慶401331）

0 引言

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

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

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

1 問題描述與模型構建

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

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

（1）每個受災點由單個車隊進行保障；

（2）每個車隊單次裝載物資或卸載物資的時間均為Tx；

（3）根據(jù)受災程度的不同，受災點要求應急運輸物資的最晚到達時間，即考慮單邊時間窗，表示為[0,LTi]；車隊預計抵達受災點i的時間為Ti；

（4）車隊勻速行駛速度為V；

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

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

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

其中：

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

模型約束條件如下：

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

2 基于改進遺傳算法的模型求解

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

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

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

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

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

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

第一種交叉：

第二種交叉：

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

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

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

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

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

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

3 算例分析

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

表1 受災點物資需求和最晚到達時間信息

受災點分布如圖1所示。

圖1 受災點坐標分布

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

表2 測試結(jié)果

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

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

圖3 迭代過程

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

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

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

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

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

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

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

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

實際上按照該車輛調(diào)度方案8個車隊50輛運輸車可以完成應急運輸任務。

4 結(jié)語

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