基于量子遺傳算法的作戰(zhàn)油料調(diào)運(yùn)優(yōu)化?

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

（1.中國(guó)人民解放軍陸軍勤務(wù)學(xué)院 重慶 401331）（2.中國(guó)人民解放軍32322部隊(duì) 烏魯木齊 830000）

1 引言

油料調(diào)度的突發(fā)性、安全性、可靠性等要求都增加了調(diào)度油料的困難程度［1～3］。油料的調(diào)度問(wèn)題除了要考慮需求量約束和儲(chǔ)備量約束外［4］，還要考慮需求點(diǎn)時(shí)間窗口和運(yùn)力約束等要求［5］。因此傳統(tǒng)的數(shù)學(xué)規(guī)劃模型難以對(duì)問(wèn)題進(jìn)行描述［6～7］。

本文對(duì)油料調(diào)度問(wèn)題的研究，通過(guò)引入需求點(diǎn)時(shí)間窗、調(diào)度過(guò)程中安全性因子，考慮相關(guān)單位的運(yùn)力約束，基于此建立了油料調(diào)度模型，采用量子遺傳算法對(duì)模型進(jìn)行求解，并通過(guò)算例驗(yàn)證了模型和算法的有效性。

2 戰(zhàn)時(shí)油料調(diào)運(yùn)優(yōu)化模型

2.1 模型假設(shè)

本文中的模型假設(shè)如下。

假設(shè)1油料儲(chǔ)備點(diǎn)均配置有一定數(shù)量的運(yùn)力。運(yùn)力可以將儲(chǔ)備點(diǎn)的油料調(diào)往所有的需求點(diǎn)，在本儲(chǔ)蓄點(diǎn)儲(chǔ)備量為0前，只可返回本儲(chǔ)備點(diǎn)且只有返回儲(chǔ)備點(diǎn)后才能執(zhí)行下次調(diào)度任務(wù)。

假設(shè)2油料裝（卸）載時(shí)間忽略不計(jì)，運(yùn)力運(yùn)輸速度在任何情況下保持不變。

假設(shè)3油料儲(chǔ)備點(diǎn)與需求點(diǎn)之間、需求點(diǎn)與需求點(diǎn)之間的最佳路徑均已知，路程均已知，運(yùn)力沿最佳路徑往返。最佳路徑有安全威脅時(shí)，路程可適當(dāng)增加。

假設(shè)4油料儲(chǔ)備點(diǎn)與需求點(diǎn)地理位置均已知。

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

2.2 問(wèn)題形式化描述

本文以某地區(qū)的油料調(diào)度為例，多個(gè)需求點(diǎn)對(duì)某種油料提出需求。選擇臨近地區(qū)若干油料倉(cāng)庫(kù)、野戰(zhàn)油料倉(cāng)庫(kù)等作為油料供給點(diǎn)。通過(guò)對(duì)供給點(diǎn)的油料儲(chǔ)存量和各需求點(diǎn)的油料需求量，并充分考慮需求點(diǎn)的時(shí)間窗約束，規(guī)劃出油料調(diào)度方案，使得各需求點(diǎn)獲取油料的時(shí)間最短。

2.3 模型的建立

根據(jù)上述對(duì)問(wèn)題的描述，在滿足油料保障時(shí)間窗口約束下，最大限度地滿足需求點(diǎn)的需求，同時(shí)保證各需求點(diǎn)開(kāi)始保障的時(shí)間盡可能早，從而構(gòu)建數(shù)學(xué)模型如下：

其中η和 ρ分別為目標(biāo)Z1和Z2的權(quán)重，分別取0.4、0.6，即優(yōu)先滿足需求量目標(biāo)。根據(jù)上述公式，可將目標(biāo)函數(shù)轉(zhuǎn)化為

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

式（5）表示每個(gè)需求點(diǎn)的需求量不低于該需求點(diǎn)的供給量，式（6）表示調(diào)運(yùn)的油料總和應(yīng)不高于油料的儲(chǔ)備總量，式（7）表示每個(gè)運(yùn)力梯隊(duì)離開(kāi)供給點(diǎn)的時(shí)間不早于需求點(diǎn)最早開(kāi)始保障的時(shí)間，不早于運(yùn)力梯隊(duì)完成保障任務(wù)回到需求點(diǎn)的時(shí)間，式（8）表示第a個(gè)供給點(diǎn)在出任務(wù)的運(yùn)力數(shù)量不大于第a個(gè)供給點(diǎn)的運(yùn)力數(shù)量，式（9）表示當(dāng)?shù)赼個(gè)供給點(diǎn)的所有運(yùn)力被派出后，下一個(gè)梯隊(duì)從供給點(diǎn)出發(fā)的時(shí)間應(yīng)不小于上一運(yùn)力梯隊(duì)回到供給點(diǎn)的時(shí)間。

3 求解算法

本文針對(duì)上述問(wèn)題采用量子遺傳算法進(jìn)行計(jì)算。量子遺傳算法是一種求解全局最優(yōu)解的方法，具有魯棒性強(qiáng)、易操作等特點(diǎn)，是解決優(yōu)化問(wèn)題的重要算法。

3.1 問(wèn)題的轉(zhuǎn)化

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

上式中，s為總虛擬需求點(diǎn)個(gè)數(shù)，βb為需求點(diǎn)b的需求量，x1為一次派送的運(yùn)載量。

3.2 算法的實(shí)現(xiàn)

3.2.1 量子編碼轉(zhuǎn)化

染色體編碼方式描述為將所有虛擬需求點(diǎn)和供應(yīng)點(diǎn)以及運(yùn)輸工具的序號(hào)編碼在染色體上，形成由3個(gè)子串編碼而成的染色體，如下例：

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

子串1表示由自然數(shù)1～4隨機(jī)生成的s個(gè)供應(yīng)點(diǎn)編碼，表示方案中4個(gè)供應(yīng)點(diǎn)的總供應(yīng)次數(shù)為s次，子串2表示由自然數(shù)1～3隨機(jī)生成的s個(gè)運(yùn)輸工具編碼，表示3種運(yùn)輸工具的所有運(yùn)輸次數(shù)為s次，子串3表示由自然數(shù)5～16隨機(jī)生成的s個(gè)需求點(diǎn)編碼，表示12個(gè)實(shí)際需求點(diǎn)的虛擬需求點(diǎn)為s個(gè)。

對(duì)于運(yùn)輸工具1，找到子串2中序號(hào)1的所有位置，并對(duì)應(yīng)查找到子串1和子串3中對(duì)應(yīng)位置的供應(yīng)點(diǎn)序號(hào)和需求點(diǎn)序號(hào)，則表示運(yùn)輸工具1的調(diào)運(yùn)方案為

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

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

3.2.2 量子旋轉(zhuǎn)門操作

由于量子比特的疊加態(tài)形式復(fù)雜，不能采取傳統(tǒng)遺傳算法的染色體選擇、交叉、變異等操作實(shí)現(xiàn)染色體的更新。量子比特由于采用概率幅的表示方式，可以采取旋轉(zhuǎn)復(fù)數(shù)幅的方式進(jìn)行量子態(tài)的干涉和雜交，這種基于量子比特基態(tài)的染色體進(jìn)化方式的重點(diǎn)在于量子旋轉(zhuǎn)門的設(shè)計(jì)，其形式為

量子更新為

[αi，βi]'表示第i量子態(tài)，θi為旋轉(zhuǎn)角。

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

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

3.2.3 量子交叉、變異、災(zāi)變操作

對(duì)轉(zhuǎn)化為量子編碼后的染色體進(jìn)行旋轉(zhuǎn)門操作后得到雜交后的新染色體，下一步進(jìn)行量子交叉操作：選取配對(duì)的染色體的子串中隨機(jī)選取兩個(gè)交叉點(diǎn)，互換交叉點(diǎn)基因，得到新個(gè)體。若交叉后的個(gè)體在進(jìn)行適應(yīng)函數(shù)迭代優(yōu)化后沒(méi)有達(dá)到最優(yōu)，此時(shí)應(yīng)采取量子變異操作，基于高斯變異或者均勻變異方式對(duì)量子位進(jìn)行改變，避免了算法的過(guò)早收斂。量子遺傳算法如果陷入了局部最優(yōu)，則應(yīng)對(duì)染色體進(jìn)行災(zāi)變操作。

3.3 算法的終止條件

設(shè)定量子遺傳算法的最大迭代次數(shù)MAX?GEN，當(dāng)?shù)螖?shù)gen＞MAXGEN時(shí)自動(dòng)終止。

4 模型的應(yīng)用及分析

4.1 模型的應(yīng)用

為驗(yàn)證模型的可行性，通過(guò)算例進(jìn)行仿真試驗(yàn)。假設(shè)有兩個(gè)油料儲(chǔ)備油庫(kù)、兩個(gè)野戰(zhàn)油庫(kù)、12個(gè)需求點(diǎn)，其位置信息在400km*400km的平面坐標(biāo)上展示，需求點(diǎn)為隨機(jī)生成，各個(gè)點(diǎn)的編號(hào)及位置分布。擔(dān)任油料調(diào)度任務(wù)的運(yùn)力均由供給點(diǎn)提供，運(yùn)力由運(yùn)輸工具1、運(yùn)輸工具2、運(yùn)輸工具3組成，具體數(shù)據(jù)見(jiàn)表2。

表2 供給點(diǎn)相關(guān)數(shù)據(jù)（部分?jǐn)?shù)據(jù)）

表3 需求點(diǎn)相關(guān)數(shù)據(jù)

表4 運(yùn)力相關(guān)數(shù)據(jù)（部分?jǐn)?shù)據(jù)）

針對(duì)上述算例，采用量子遺傳算法進(jìn)行油料的調(diào)度方案優(yōu)化，同時(shí)采用實(shí)數(shù)編碼方式運(yùn)用常規(guī)遺傳算法對(duì)本算例進(jìn)行優(yōu)化求解。常規(guī)遺傳算法中的交叉概率、變異概率以及代溝設(shè)置為Pc=0.9、Pm=0.05、GGAP=0.9，量子遺傳算法的變異因子設(shè)定為pmutaition=0.01。根據(jù)相關(guān)參數(shù)設(shè)置，得到如下的油料調(diào)度方案。

根據(jù)表5，做出任務(wù)甘特圖，較為直觀地看出需求點(diǎn)對(duì)應(yīng)的每個(gè)時(shí)間窗內(nèi)的調(diào)度任務(wù)。

表5 油料調(diào)運(yùn)方案（部分?jǐn)?shù)據(jù)）

圖1 調(diào)度任務(wù)甘特圖

4.2 結(jié)果分析

圖2為分別采用常規(guī)遺傳算法以及量子遺傳算法優(yōu)化過(guò)程中最優(yōu)個(gè)體的適應(yīng)度收斂情況對(duì)比，可以看出由于量子遺傳算法采用了量子比特編碼方式，最優(yōu)個(gè)體的適應(yīng)度的遺傳代數(shù)較小，收斂速度快。而標(biāo)準(zhǔn)遺傳算法在接近最大遺傳代數(shù)時(shí)最優(yōu)適應(yīng)度仍未穩(wěn)定下來(lái)，可見(jiàn)在求解復(fù)雜的油料的調(diào)度模型時(shí)，量子遺傳算法較之常規(guī)遺傳算法更適合用于求解最優(yōu)解。

圖2 量子遺傳算法與常規(guī)遺傳算法對(duì)比圖

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

圖3 運(yùn)輸工具1的油料調(diào)度熱力圖

圖4則為某運(yùn)輸工具的油料調(diào)度安排圖，以帶運(yùn)輸工具數(shù)量的地理坐標(biāo)有向箭頭表示油料的調(diào)度情況，結(jié)合arcgis技術(shù)可以進(jìn)一步在地圖上精準(zhǔn)顯示，實(shí)現(xiàn)油料調(diào)度的地理信息可視化。

圖4 運(yùn)輸工具調(diào)度安排圖

圖5為某需求點(diǎn)的運(yùn)力情況色塊圖，其中，深色色塊［i，j］對(duì)應(yīng)的判斷矩陣數(shù)值為-1，表示供應(yīng)點(diǎn)i對(duì)應(yīng)的運(yùn)輸工具j存在運(yùn)力不足的情況。此時(shí)為滿足該需求點(diǎn)的油料需求應(yīng)當(dāng)進(jìn)行橫向協(xié)調(diào)或縱向協(xié)調(diào)。橫向協(xié)調(diào)即由其他供應(yīng)點(diǎn)提供運(yùn)力支援，縱向協(xié)調(diào)則表示運(yùn)力不足部分由其他運(yùn)輸工具替代。通過(guò)需求點(diǎn)的運(yùn)力情況判斷，可以精準(zhǔn)反映該點(diǎn)需求量的實(shí)際滿足情況，從而為油料調(diào)度決策提供第一手資料。

圖5 需求點(diǎn)運(yùn)力情況色塊圖

5 結(jié)語(yǔ)

本文研究了基于量子遺傳算法的戰(zhàn)時(shí)油料調(diào)運(yùn)優(yōu)化模型。首先油料供給點(diǎn)、需求點(diǎn)、時(shí)間窗口等問(wèn)題的形式化描述，在此基礎(chǔ)上，通過(guò)考慮保障時(shí)間窗口和運(yùn)力約束，建立了油料調(diào)度模型，并運(yùn)用量子遺傳算法進(jìn)行求解。通過(guò)引入某地區(qū)的算例，證明了該模型具有可行性和使用價(jià)值。