基于量子遺傳算法的作戰油料調運優化?

王 帥 郭月凱 屈少輝 朱愈歡 王 燦 陳宇昕

（1.中國人民解放軍陸軍勤務學院 重慶 401331）（2.中國人民解放軍32322部隊 烏魯木齊 830000）

1 引言

油料調度的突發性、安全性、可靠性等要求都增加了調度油料的困難程度［1～3］。油料的調度問題除了要考慮需求量約束和儲備量約束外［4］，還要考慮需求點時間窗口和運力約束等要求［5］。因此傳統的數學規劃模型難以對問題進行描述［6～7］。

本文對油料調度問題的研究，通過引入需求點時間窗、調度過程中安全性因子，考慮相關單位的運力約束，基于此建立了油料調度模型，采用量子遺傳算法對模型進行求解，并通過算例驗證了模型和算法的有效性。

2 戰時油料調運優化模型

2.1 模型假設

本文中的模型假設如下。

假設1油料儲備點均配置有一定數量的運力。運力可以將儲備點的油料調往所有的需求點，在本儲蓄點儲備量為0前，只可返回本儲備點且只有返回儲備點后才能執行下次調度任務。

假設2油料裝（卸）載時間忽略不計，運力運輸速度在任何情況下保持不變。

假設3油料儲備點與需求點之間、需求點與需求點之間的最佳路徑均已知，路程均已知，運力沿最佳路徑往返。最佳路徑有安全威脅時，路程可適當增加。

假設4油料儲備點與需求點地理位置均已知。

一般情況下，各油料儲備點均配置有一定數量的運力，在完成本儲備點調度任務后可以參與其他儲備點任務，因此，假設1符合油料調度的實際；假設2～4主要是為了方便計算，最佳路徑的安全威脅可以簡化為路程增加10%。

2.2 問題形式化描述

本文以某地區的油料調度為例，多個需求點對某種油料提出需求。選擇臨近地區若干油料倉庫、野戰油料倉庫等作為油料供給點。通過對供給點的油料儲存量和各需求點的油料需求量，并充分考慮需求點的時間窗約束，規劃出油料調度方案，使得各需求點獲取油料的時間最短。

2.3 模型的建立

根據上述對問題的描述，在滿足油料保障時間窗口約束下，最大限度地滿足需求點的需求，同時保證各需求點開始保障的時間盡可能早，從而構建數學模型如下：

其中η和 ρ分別為目標Z1和Z2的權重，分別取0.4、0.6，即優先滿足需求量目標。根據上述公式，可將目標函數轉化為

綜合上述的分析，本模型的約束條件可以表示如下：

式（5）表示每個需求點的需求量不低于該需求點的供給量，式（6）表示調運的油料總和應不高于油料的儲備總量，式（7）表示每個運力梯隊離開供給點的時間不早于需求點最早開始保障的時間，不早于運力梯隊完成保障任務回到需求點的時間，式（8）表示第a個供給點在出任務的運力數量不大于第a個供給點的運力數量，式（9）表示當第a個供給點的所有運力被派出后，下一個梯隊從供給點出發的時間應不小于上一運力梯隊回到供給點的時間。

3 求解算法

本文針對上述問題采用量子遺傳算法進行計算。量子遺傳算法是一種求解全局最優解的方法，具有魯棒性強、易操作等特點，是解決優化問題的重要算法。

3.1 問題的轉化

結合相關文獻，本文采用按照運輸工具任務序列的編碼方式。編碼方式描述為在某個油料調度方案中，將所有任務序列排列在一條染色體中，以每個運輸工具的任務作為染色體的子基因，每個子基因的基因位表示為供應點或者需求點。根據所建模型可知，運輸工具需要在保障時間窗內多次派送才能滿足某個需求點的需求，故根據任務量和運載力的比值設定虛擬需求點，描述為將一次派送所滿足的需求設置為一個需求點，則滿足所有需求的總虛擬需求點的個數為

上式中，s為總虛擬需求點個數，βb為需求點b的需求量，x1為一次派送的運載量。

3.2 算法的實現

3.2.1 量子編碼轉化

染色體編碼方式描述為將所有虛擬需求點和供應點以及運輸工具的序號編碼在染色體上，形成由3個子串編碼而成的染色體，如下例：

1-2-1-4-1-1（子串1）-1-3-2-3-1-2（子 串2）-1-5-12-7-9-8（子串3）

子串1表示由自然數1～4隨機生成的s個供應點編碼，表示方案中4個供應點的總供應次數為s次，子串2表示由自然數1～3隨機生成的s個運輸工具編碼，表示3種運輸工具的所有運輸次數為s次，子串3表示由自然數5～16隨機生成的s個需求點編碼，表示12個實際需求點的虛擬需求點為s個。

對于運輸工具1，找到子串2中序號1的所有位置，并對應查找到子串1和子串3中對應位置的供應點序號和需求點序號，則表示運輸工具1的調運方案為

1-14-4-11-1-5-1-9-2-15

上述描述為實數編碼方式，在量子遺傳算法中需要將實數編碼方式轉化為量子編碼方式，并通過二進制轉換成0-1矩陣進行量子旋轉門操作得到進化之后的染色體編碼。

3.2.2 量子旋轉門操作

由于量子比特的疊加態形式復雜，不能采取傳統遺傳算法的染色體選擇、交叉、變異等操作實現染色體的更新。量子比特由于采用概率幅的表示方式，可以采取旋轉復數幅的方式進行量子態的干涉和雜交，這種基于量子比特基態的染色體進化方式的重點在于量子旋轉門的設計，其形式為

量子更新為

[αi，βi]'表示第i量子態，θi為旋轉角。

θi的取值由α，β決定。具體如表1。

表1 α，β取值表（部分）

3.2.3 量子交叉、變異、災變操作

對轉化為量子編碼后的染色體進行旋轉門操作后得到雜交后的新染色體，下一步進行量子交叉操作：選取配對的染色體的子串中隨機選取兩個交叉點，互換交叉點基因，得到新個體。若交叉后的個體在進行適應函數迭代優化后沒有達到最優，此時應采取量子變異操作，基于高斯變異或者均勻變異方式對量子位進行改變，避免了算法的過早收斂。量子遺傳算法如果陷入了局部最優，則應對染色體進行災變操作。

3.3 算法的終止條件

設定量子遺傳算法的最大迭代次數MAX?GEN，當迭代次數gen＞MAXGEN時自動終止。

4 模型的應用及分析

4.1 模型的應用

為驗證模型的可行性，通過算例進行仿真試驗。假設有兩個油料儲備油庫、兩個野戰油庫、12個需求點，其位置信息在400km*400km的平面坐標上展示，需求點為隨機生成，各個點的編號及位置分布。擔任油料調度任務的運力均由供給點提供，運力由運輸工具1、運輸工具2、運輸工具3組成，具體數據見表2。

表2 供給點相關數據（部分數據）

表3 需求點相關數據

表4 運力相關數據（部分數據）

針對上述算例，采用量子遺傳算法進行油料的調度方案優化，同時采用實數編碼方式運用常規遺傳算法對本算例進行優化求解。常規遺傳算法中的交叉概率、變異概率以及代溝設置為Pc=0.9、Pm=0.05、GGAP=0.9，量子遺傳算法的變異因子設定為pmutaition=0.01。根據相關參數設置，得到如下的油料調度方案。

根據表5，做出任務甘特圖，較為直觀地看出需求點對應的每個時間窗內的調度任務。

表5 油料調運方案（部分數據）

圖1 調度任務甘特圖

4.2 結果分析

圖2為分別采用常規遺傳算法以及量子遺傳算法優化過程中最優個體的適應度收斂情況對比，可以看出由于量子遺傳算法采用了量子比特編碼方式，最優個體的適應度的遺傳代數較小，收斂速度快。而標準遺傳算法在接近最大遺傳代數時最優適應度仍未穩定下來，可見在求解復雜的油料的調度模型時，量子遺傳算法較之常規遺傳算法更適合用于求解最優解。

圖2 量子遺傳算法與常規遺傳算法對比圖

圖3為采用量子遺傳算法得到的油料調度熱力圖，圓越大代表由該供應點至需求點派送的運輸工具數量越多，如圖中［supply_3，Demand_2］=4，表示在保障時間窗口內從供應點3至需求點2總共調度了4輛運輸工具1。油料調度熱力圖清晰地展示了各種運輸工具的油料調度情況。

圖3 運輸工具1的油料調度熱力圖

圖4則為某運輸工具的油料調度安排圖，以帶運輸工具數量的地理坐標有向箭頭表示油料的調度情況，結合arcgis技術可以進一步在地圖上精準顯示，實現油料調度的地理信息可視化。

圖4 運輸工具調度安排圖

圖5為某需求點的運力情況色塊圖，其中，深色色塊［i，j］對應的判斷矩陣數值為-1，表示供應點i對應的運輸工具j存在運力不足的情況。此時為滿足該需求點的油料需求應當進行橫向協調或縱向協調。橫向協調即由其他供應點提供運力支援，縱向協調則表示運力不足部分由其他運輸工具替代。通過需求點的運力情況判斷，可以精準反映該點需求量的實際滿足情況，從而為油料調度決策提供第一手資料。

圖5 需求點運力情況色塊圖

5 結語

本文研究了基于量子遺傳算法的戰時油料調運優化模型。首先油料供給點、需求點、時間窗口等問題的形式化描述，在此基礎上，通過考慮保障時間窗口和運力約束，建立了油料調度模型，并運用量子遺傳算法進行求解。通過引入某地區的算例，證明了該模型具有可行性和使用價值。