災時軍隊應急運輸車輛調度優化

杜小敏，胡遠新

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

0 引言

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

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

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

1 問題描述與模型構建

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

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

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

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

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

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

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

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

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

其中：

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

模型約束條件如下：

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

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

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

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

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

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

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

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

第一種交叉：

第二種交叉：

變異操作的步驟是，首先對種群內所有個體進行判斷，當隨機數Pt小于Pm時，對該個體進行變異操作，產生新的個體。變異操作設計為，對染色體受災點序列中的一個片段進行倒序逆轉，同時讓斷點序列基因中的隨機項突變為另一個數，并重新排序，獲得子代個體的DNA序列。例如：

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

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

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

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

（5）結束判斷。當迭代次數達到最大設定值，結束迭代循環。

3 算例分析

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

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

受災點分布如圖1所示。

圖1 受災點坐標分布

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

表2 測試結果

圖2 最優路徑圖示

計算結果表明，10次測試中每次的最優解均沒有超過時間窗，可以滿足應急運輸的時間要求和受災點的物資需求，能夠獲得該車輛調度問題最優路程的近似解，保證以最短時間完成應急運輸，提高了應急運輸的效率；使用的改進遺傳算法對該模型求解有較好的收斂效果，證明了該改進遺傳算法在解決軍隊應急運輸車輛調度優化問題的有效性。其中第9次的測試結果為最優，其目標函數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%。

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

4 結語

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