余昌仁,喬 涵,韓夢瑤,張國杰

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

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

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

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

1.1 模型考慮的因素

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

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

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

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

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

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

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

1.2 模型建立的變量

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

表1 變量說明Tab.1 Variable description

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

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

定義變量:

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

目標函數(shù):

(1)

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

(2)

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

約束條件:

(3)

(4)

(5)

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

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

(6)

(7)

(8)

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

(9)

(10)

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

1.4 智能算法求解

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

1)染色體編碼。島礁物資補給路徑規(guī)劃問題可采取實數(shù)編碼方式,即補給中心為0,各島礁為1,2,…,n,編碼長度為n+m。如島礁數(shù)量為8、運輸工具數(shù)量為2時,若編碼為{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ù)。遺傳算法是一個不斷從種群中選擇適應(yīng)度高的個體的迭代優(yōu)化過程,該任務(wù)規(guī)劃問題中,目標函數(shù)取極小值,故以目標函數(shù)的倒數(shù)為適應(yīng)度函數(shù)F。

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

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

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

2 實例運用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3)最終方案成本分析

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

3 結(jié)束語

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