海域島礁物資補(bǔ)給任務(wù)智能規(guī)劃*

余昌仁,喬 涵,韓夢(mèng)瑤,張國(guó)杰

(陸軍勤務(wù)學(xué)院,重慶 401331)

島礁是維護(hù)我國(guó)海洋權(quán)益的前哨,是我國(guó)領(lǐng)土不可分割的組成部分,派駐人員守衛(wèi)島礁對(duì)保障我國(guó)領(lǐng)土完整具有重要的意義。遠(yuǎn)海海域諸島礁距離大陸較遠(yuǎn),位置相對(duì)分散[1],島上物資匱乏,為維持駐島人員生存生活需要,需定期由陸上保障中心派出補(bǔ)給船對(duì)島礁進(jìn)行補(bǔ)給,制定科學(xué)的物資保障方案,提高保障的效益[2]。

島礁物資補(bǔ)給有特定的保障目標(biāo)和影響因素,主要解決物資補(bǔ)給任務(wù)規(guī)劃問(wèn)題。島礁物資補(bǔ)給任務(wù)規(guī)劃問(wèn)題指在滿足自然停泊環(huán)境、保障時(shí)間、運(yùn)輸工具裝載量限制等條件下,使得保障目標(biāo)達(dá)到最優(yōu),保障目標(biāo)包括運(yùn)輸工具燃油經(jīng)濟(jì)性、物資儲(chǔ)存成本等,所以其本質(zhì)是一個(gè)車(chē)輛路徑規(guī)劃(Vehicle Routing Problem, VRP)[3]問(wèn)題,這類(lèi)問(wèn)題有精確算法與啟發(fā)式算法等[4]。精確算法主要運(yùn)用線性規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃等嚴(yán)格的數(shù)學(xué)方法求解,比較適合特定的問(wèn)題,而啟發(fā)式算法適合解決一些不規(guī)則優(yōu)化問(wèn)題。VRP問(wèn)題常有容量約束或時(shí)間窗限制[5-6],也可能兩者兼而有之,這類(lèi)問(wèn)題是NP(Non-deterministic polynominal,多項(xiàng)式復(fù)雜程度的非確定性)[7-8]難問(wèn)題。智能算法作為啟發(fā)式算法的一種,適合解決大規(guī)模的組合優(yōu)化問(wèn)題,能在解空間內(nèi)高效率地尋找出極優(yōu)解,典型的組合優(yōu)化問(wèn)題有旅行商問(wèn)題(Traveling Salesman Problem, TSP)[9]、調(diào)度問(wèn)題、0-1背包問(wèn)題、裝箱問(wèn)題等。優(yōu)化目標(biāo)是在可行解域內(nèi)找到近似解來(lái)代替最優(yōu)解,減少求解需要付出的代價(jià)。智能算法包括但不限于模擬退火、蟻群算法、遺傳算法、禁忌搜索算法等。

1 島礁物資補(bǔ)給任務(wù)規(guī)劃問(wèn)題建模

1.1 模型考慮的因素

島礁物資補(bǔ)給由后勤補(bǔ)給中心運(yùn)用各型補(bǔ)給艦船對(duì)海域島礁實(shí)施運(yùn)輸補(bǔ)給。考慮補(bǔ)給時(shí)間、補(bǔ)給需求和補(bǔ)給效益,運(yùn)輸投送方案最優(yōu)化受自然條件、經(jīng)濟(jì)成本和運(yùn)輸工具等多種因素影響。

1)自然地理?xiàng)l件。島礁附近海底地貌、岸灘底質(zhì)各不相同,靠泊條件各異,對(duì)于靠泊港口大的島礁,補(bǔ)給艦可直接補(bǔ)給,對(duì)于靠泊港口小的島礁,補(bǔ)給艦須在距島礁附近某處錨泊,通過(guò)配套小型補(bǔ)給艇進(jìn)行轉(zhuǎn)運(yùn)實(shí)現(xiàn)間接補(bǔ)給,或采用某島礁上的拖船完成物資倒運(yùn)。

2)運(yùn)輸工具?？蛇\(yùn)用不同型號(hào)的大型補(bǔ)給艦,從特定的補(bǔ)給中心出發(fā),補(bǔ)充一定數(shù)量的島礁后再返回該補(bǔ)給中心。一條運(yùn)輸路線上僅有一艘大型補(bǔ)給艦。補(bǔ)給艦配備若干小型補(bǔ)給艇,拖船也可以用于短距離的物資轉(zhuǎn)運(yùn)。

3)運(yùn)輸成本。某海域領(lǐng)域廣闊,島礁位置相對(duì)分散,島礁間距較遠(yuǎn),距離是影響保障成本的主要因素。各型補(bǔ)給艦各有不同的燃油經(jīng)濟(jì)成本。規(guī)劃不同的保障路徑將產(chǎn)生不同的運(yùn)輸成本。拖船與小艇產(chǎn)生的短距離運(yùn)輸成本可忽略不計(jì)。

4)運(yùn)輸與裝卸時(shí)間。各型補(bǔ)給艦航行速度已知,假設(shè)補(bǔ)給艦裝有固體、液體兩類(lèi)物資,固體、液體的裝卸也有不同的速度。各種運(yùn)輸工具(補(bǔ)給艦、小型補(bǔ)給艇、拖船)所載燃油能滿足其去各島補(bǔ)給的需要,即不考慮燃油耗盡需返回的問(wèn)題。補(bǔ)給艦(艇)卸載固體物資和液體可同時(shí)進(jìn)行,互不影響,回程時(shí),需要從島礁裝載固體回收物。

5)儲(chǔ)存成本。某海域島礁大多屬于熱帶、亞熱帶海洋性氣候,具有高溫、高濕、高鹽的突出特點(diǎn),各類(lèi)物資易腐爛變質(zhì),長(zhǎng)期存儲(chǔ)需采取低溫冷藏保鮮。物資儲(chǔ)存成本也是物資補(bǔ)給應(yīng)考慮的重要方面。固體、液體儲(chǔ)存成本以?xún)?chǔ)存天數(shù)和噸位數(shù)平均計(jì)算,單位為元/噸·天。

6)補(bǔ)給要求。各島礁存儲(chǔ)空間有限,固體、液體物資均有最大儲(chǔ)存量,各島礁補(bǔ)給之前有一定的剩余儲(chǔ)備量,固體、液體消耗速度以日均消耗量(噸)計(jì)量。需要補(bǔ)給一個(gè)時(shí)間周期內(nèi)的物資需要,且要求在島礁剩余物資消耗完畢之前進(jìn)行補(bǔ)充。

1.2 模型建立的變量

模型建立的數(shù)學(xué)變量見(jiàn)表1。

表1 變量說(shuō)明Tab.1 Variable description

1.3 目標(biāo)函數(shù)與約束條件

多艘補(bǔ)給艦從補(bǔ)給中心出發(fā),遍歷所有島礁后返回當(dāng)前補(bǔ)給中心[10],且多艘補(bǔ)給艦的路線不能重疊,總運(yùn)輸費(fèi)用最小,這是典型的多旅行商(MTSP)[11-12]問(wèn)題。旅行商問(wèn)題是車(chē)輛路徑規(guī)劃問(wèn)題的一種,如表1所述,點(diǎn)0表示出發(fā)的地點(diǎn):補(bǔ)給中心。點(diǎn)1,2,…,n表示m個(gè)旅行商(補(bǔ)給艦)要訪問(wèn)的地點(diǎn)(某海域的各個(gè)島礁)。

定義變量:

該問(wèn)題的數(shù)學(xué)模型可表示為

目標(biāo)函數(shù):

(1)

Ckdij表示第k艘運(yùn)輸工具經(jīng)過(guò)對(duì)應(yīng)弧段(i,j)所花費(fèi)用(距離與運(yùn)輸工具k單位運(yùn)輸成本的乘積)。目標(biāo)函數(shù)Z1表示使所有旅行商的費(fèi)用最小化。

(2)

目標(biāo)函數(shù)Z2表示所有島礁剩余物資(固、液體)儲(chǔ)存成本與補(bǔ)充后的物資儲(chǔ)存成本和最小。

約束條件:

(3)

(4)

(5)

約束條件(3)表示從地點(diǎn)0出發(fā),每個(gè)將被訪問(wèn)地點(diǎn)有且僅有一個(gè)旅行商經(jīng)過(guò);約束條件(4)表示任一條弧的終點(diǎn)僅有一個(gè)起點(diǎn)地方與之相連;約束條件(5)表示任一條弧的起點(diǎn)地方僅有一個(gè)終點(diǎn)地方與之相連[13]。

與此同時(shí),還要考慮時(shí)間窗與各運(yùn)輸工具容量限制。各島礁所需物資最早在其剩余物資剛消耗時(shí)進(jìn)行補(bǔ)充,最晚于剩余物資耗盡時(shí)進(jìn)行補(bǔ)充,再補(bǔ)充時(shí)可以按最大儲(chǔ)存量進(jìn)行補(bǔ)充。所以有以下約束條件:

(6)

(7)

(8)

約束條件(8)表示第k艘運(yùn)輸工具到達(dá)島礁i的時(shí)刻加上物資裝卸時(shí)間須小于島礁i剩余物資消耗完畢所耗費(fèi)的時(shí)間。因運(yùn)輸工具有容量限制,還有關(guān)系式:

(9)

(10)

約束條件(9)、(10)分別表示第k艘運(yùn)輸工具所補(bǔ)充島礁液體需求量小于其最大液體載重量、最大固體載重量。

1.4 智能算法求解

如前所述,VRP問(wèn)題可運(yùn)用的算法有多種,但此問(wèn)題有諸多的約束條件,可采用智能算法如模擬退火、禁忌算法、遺傳算法(Genetic Algorithm, GA)[14]甚至是多種算法的結(jié)合進(jìn)行求解。這些算法不存在對(duì)函數(shù)求導(dǎo)或連續(xù)性等限制,對(duì)多目標(biāo)規(guī)劃具有較好的全局搜索最優(yōu)解能力。島礁物資補(bǔ)給任務(wù)規(guī)劃問(wèn)題中若島礁數(shù)量不太多時(shí),可采用一種具有代表性的算法如GA進(jìn)行求解,GA是一種智能進(jìn)化算法[15],通過(guò)把問(wèn)題參數(shù)編碼為“染色體”,利用迭代運(yùn)算方式,設(shè)定適應(yīng)度函數(shù),使經(jīng)選擇、交叉和變異等操作后的“染色體”最終符合優(yōu)化目標(biāo)。

1)染色體編碼。島礁物資補(bǔ)給路徑規(guī)劃問(wèn)題可采取實(shí)數(shù)編碼方式,即補(bǔ)給中心為0,各島礁為1,2,…,n,編碼長(zhǎng)度為n+m。如島礁數(shù)量為8、運(yùn)輸工具數(shù)量為2時(shí),若編碼為{0,1,2,5,0,3,4,6,8,7}表示路徑為0-1-2-5-0和0-3-4-6-8-7-0。按此編碼方式生成一定規(guī)模的初始種群。

2)適應(yīng)度函數(shù)。遺傳算法是一個(gè)不斷從種群中選擇適應(yīng)度高的個(gè)體的迭代優(yōu)化過(guò)程,該任務(wù)規(guī)劃問(wèn)題中,目標(biāo)函數(shù)取極小值,故以目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)F。

4)交叉算子。采取部分映射雜交,對(duì)初始解中兩個(gè)基因串中的隨機(jī)片斷進(jìn)行交叉操作,還是以n=8,m=2為例,對(duì)下列兩基因中的第4、7位中間數(shù)據(jù)進(jìn)行交叉,交叉后有部分?jǐn)?shù)據(jù)沖突,用*表示,再采用部分映射的方法消除重復(fù),得到以下結(jié)果。

5)變異算子。在父代基因中隨機(jī)選擇兩個(gè)斷點(diǎn),將斷點(diǎn)之間的基因逆序排列或交換斷點(diǎn)位置,從而產(chǎn)生一個(gè)新的個(gè)體。

6)重新插入初始種群得到更新后的新種群。進(jìn)行迭代運(yùn)算,以適應(yīng)度函數(shù)為選擇準(zhǔn)則,不斷把問(wèn)題的可行解進(jìn)行收斂,從而得到最優(yōu)解。

2 實(shí)例運(yùn)用

根據(jù)文獻(xiàn)[16]給出的實(shí)例,由補(bǔ)給中心點(diǎn)C為島礁(D1～D9)運(yùn)送所需物資,由A、B兩種型號(hào)補(bǔ)給艦執(zhí)行物資補(bǔ)給任務(wù),每條補(bǔ)給艦各配備2艘小艇。補(bǔ)給艦回程運(yùn)回固體垃圾。補(bǔ)給方案應(yīng)包括補(bǔ)給艦種類(lèi)、補(bǔ)給路線、補(bǔ)給數(shù)量、轉(zhuǎn)運(yùn)方式、物資裝卸與回收材料的數(shù)量等。各島礁(含補(bǔ)給中心)位置、儲(chǔ)物情況、補(bǔ)給艦(艇)信息見(jiàn)該文獻(xiàn)相關(guān)數(shù)據(jù)。

VRP問(wèn)題中,目標(biāo)函數(shù)與約束條件的處理較為復(fù)雜,總目標(biāo)函數(shù)通?？扇《鄠€(gè)目標(biāo)函數(shù)的加權(quán)平均,考慮約束條件時(shí),遺傳算法編碼生成的初始種群及交叉(變異)后種群還要驗(yàn)證其是否滿足約束條件,若是不可行解,需要一系列復(fù)雜的處理,總體計(jì)算量大,迭代較慢。在島礁物資補(bǔ)給問(wèn)題中,可以具體問(wèn)題具體分析,靈活處理目標(biāo)函數(shù)與約束條件。補(bǔ)給艦的燃油成本及各島礁物資儲(chǔ)存成本是一個(gè)多目標(biāo)取優(yōu)問(wèn)題,通過(guò)計(jì)算,可發(fā)現(xiàn)物資儲(chǔ)存成本遠(yuǎn)小于運(yùn)輸成本,故在目標(biāo)函數(shù)上可以運(yùn)輸成本為主,為使儲(chǔ)存成本最低,補(bǔ)給原則是在滿足島礁物資保障不間斷的前提下盡量延長(zhǎng)補(bǔ)給時(shí)間,待各島礁剩余物資耗盡后再進(jìn)行補(bǔ)充。與此同時(shí),還要考慮運(yùn)輸工具的容量限制,基于上述分析,可運(yùn)用分步優(yōu)化的思路,運(yùn)用智能算法先找出符合成本最低的運(yùn)輸路徑,然后基于該路徑做出微調(diào)以符合時(shí)間窗要求和為各島礁分配物資數(shù)量。

2.1 遺傳算法仿真運(yùn)行結(jié)果

為任務(wù)規(guī)劃的均衡性,可設(shè)定每條路線所經(jīng)歷的島礁數(shù)量至少為2個(gè)以上[17]。通過(guò)編程,使用Matlab2013b程序進(jìn)行仿真,得出優(yōu)化結(jié)果見(jiàn)圖1,遺傳代數(shù)為25。虛粗線表示A艦航行路徑C-D2-D9-D4-D3-C,實(shí)細(xì)線表示B艦航行路徑C-D1-D5-D8-D6-D7-C。

圖1 雙艦補(bǔ)給路徑規(guī)劃圖Fig.1 Supply paths planning of dual ships

2.2 優(yōu)化方案的確定

1)最優(yōu)路徑順序的選擇

使用A、B艦給島礁實(shí)施物資保障時(shí),要求使得各島礁至少維持一個(gè)特定的供給周期。補(bǔ)給總的原則是:①優(yōu)先補(bǔ)給資源即將耗盡的島嶼,如D1、D2、D3、D4等;②盡量使得補(bǔ)給在現(xiàn)有物資耗盡之后再補(bǔ)充,并且補(bǔ)充周期內(nèi)所需最大庫(kù)存,因?yàn)檫@樣可以使儲(chǔ)存成本減少;③現(xiàn)有庫(kù)存物資與后續(xù)補(bǔ)充的物資可用天數(shù)之和至少能滿足一個(gè)補(bǔ)給周期所需。

確定最優(yōu)路徑后,需要進(jìn)一步安排A、B艦補(bǔ)給各島的順序,考慮A、B艦保障的各島當(dāng)前儲(chǔ)存物資可消耗天數(shù)情況,在圖1所示的路徑基礎(chǔ)上,應(yīng)對(duì)此做出微調(diào),A艦先保障D2,再D3,爾后D4,再D9;由于D9是小島,應(yīng)于小島外拋錨,再由小艇倒送物資。由于D8的可維持天數(shù)較長(zhǎng),而D6、D7保障時(shí)效要求更強(qiáng),還應(yīng)對(duì)B艦路徑再做出微小調(diào)整,B艦先保障D1,再D5,爾后D6,再D7;由于D8需求量不大,時(shí)間又較為寬松,可利用2艘小艇同時(shí)由D7向D8運(yùn)輸物資。調(diào)整后的路線為A艦的C-D2-D3-D4-D9-C,路徑長(zhǎng)1574.07海里;B艦為C-D1-D5-D6-D7-C,路徑長(zhǎng)1 288.04海里,見(jiàn)圖2。

圖2 調(diào)整后的優(yōu)化路徑Fig.2 Adjusted optimization paths

2)各島礁物資補(bǔ)給的數(shù)量與時(shí)間

在規(guī)劃好A、B艦路徑后,物資分配應(yīng)按各島礁能支持消耗一個(gè)補(bǔ)給周期的量分配,即按每天的消耗水平乘以補(bǔ)給周期再減去當(dāng)前儲(chǔ)存量,這樣可以使得補(bǔ)給物資滿足容量限制。進(jìn)一步計(jì)算A、B艦到各島的航行時(shí)間與裝卸物資時(shí)間。需要注意的是D8、D9比較特殊,對(duì)于A艦來(lái)說(shuō),需要?？緿9外某處,同時(shí)用2小艇倒運(yùn)艦上物資保障D9島所需,計(jì)算出小艇運(yùn)輸與裝卸總耗時(shí)為17.27小時(shí)。對(duì)于B艦來(lái)說(shuō),?？坑贒7后再保障D8所需,由于D8固體、液體的保障量較小,可以考慮運(yùn)用2小艇來(lái)進(jìn)行倒運(yùn)物資,計(jì)算出總耗時(shí)為46.21小時(shí)。A、B艦到達(dá)各島的補(bǔ)給量與固體回收量、航行時(shí)間與物資裝卸時(shí)間計(jì)算結(jié)果見(jiàn)表2。

表2 A艦、B到達(dá)各島的補(bǔ)給量、航行時(shí)間與物資裝卸時(shí)間Tab.2 Supply volume, sailing time and material loading time of ship A and ship B arriving at each island

通過(guò)計(jì)算,A、B兩艦需裝載補(bǔ)充的固體總量為85.1 t。A艦固體量為40.9 t,B艦固體量為44.2 t。A多出的0.9 t固體可以放小艇中。A、B兩艦需裝載補(bǔ)充的液體總量為435 t。A液體量為176.25 t,B液體量為258.75 t。

3)最終方案成本分析

各島補(bǔ)充后的物資儲(chǔ)存總成本為66 690.9元。加上補(bǔ)充前的當(dāng)前已有物資儲(chǔ)存成本8 650.15,共75 341.05元。根據(jù)前面的優(yōu)化路徑,A的運(yùn)輸里程為1 574.07海里,B的運(yùn)輸里程為1 288.04海里,總費(fèi)用為2 232 482元。最終的運(yùn)輸成本加上儲(chǔ)存成本合計(jì)為2 307 823.05元。

3 結(jié)束語(yǔ)

文章建立了島礁物資補(bǔ)給任務(wù)規(guī)劃模型,分析了智能算法的求解過(guò)程,結(jié)合一個(gè)實(shí)例,采用算法進(jìn)行仿真運(yùn)算,綜合利用數(shù)據(jù)分析,得出了優(yōu)化方案[18-19]。方案從現(xiàn)實(shí)復(fù)雜問(wèn)題出發(fā),考慮保障任務(wù)較高的構(gòu)成成本——島礁物資運(yùn)輸成本,其次考慮儲(chǔ)存成本、容量限制、補(bǔ)給周期等,分步進(jìn)行優(yōu)化調(diào)整,符合物資補(bǔ)給實(shí)際需要[20]。當(dāng)然,考慮模型的拓展性,還需要進(jìn)一步結(jié)合實(shí)際情況中的多種條件如天氣情況對(duì)物資保障的影響,考慮把某些島礁作為中轉(zhuǎn)站進(jìn)行二次補(bǔ)給的情況進(jìn)行規(guī)劃,這些還需在未來(lái)的研究中進(jìn)一步深化。