基于?？諈f(xié)同的群島救援方案優(yōu)化模型及算法

林婉妮， 王 諾， 沈銘棋， 宋云婷

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026)

0 引言

我國海域遼闊，海上島嶼眾多，有的相互距離較遠(yuǎn)，在發(fā)生緊急情況亟需救援時(shí)，僅利用船舶救援效率過低，通常采取?？諈f(xié)同方式完成。但由于船舶與直升機(jī)在運(yùn)載能力、馳援速度等方面的性能差異較大，相互協(xié)同救援關(guān)系復(fù)雜，因而如何有效地配置救援船舶與直升機(jī)的數(shù)量，科學(xué)地制定調(diào)度方案，是有待深入研究的重要課題。

對(duì)于遠(yuǎn)離大陸的群島，通常將群島中較大的島嶼作為中心島，與周邊小島形成輻射型中心-衛(wèi)星島支撐關(guān)系。這樣，以中心島為起點(diǎn)，以衛(wèi)星島為終點(diǎn)的?？站仍袆?dòng)，實(shí)際上是一個(gè)帶容量約束的單車場(chǎng)多車型最快完成車輛路徑優(yōu)化問題(vehicle routing problem，VRP)，可以看作由中心島(配送中心)向周邊衛(wèi)星島(顧客)提供救援物資(貨物)，由船舶和直升機(jī)負(fù)責(zé)運(yùn)送(多種車型)，各船舶及直升機(jī)負(fù)責(zé)若干不同島嶼的物資配送，以實(shí)現(xiàn)整體配送時(shí)間最短的目標(biāo)。有關(guān)車輛路徑優(yōu)化問題已有許多研究，例如Nikolakopoulou等人針對(duì)時(shí)間要求提出了完成時(shí)間最短的車輛路徑問題，以最后一臺(tái)車輛完成任務(wù)的時(shí)間最小為優(yōu)化目標(biāo)[1]；Zhang等人研究了以平衡車輛使用時(shí)間最短為目標(biāo)的車輛路徑優(yōu)化問題[2]；丁秋雷等人研究了考慮顧客時(shí)間要求的車輛路徑優(yōu)化，并用混合蟻群算法對(duì)其進(jìn)行求解[3]；鄭斌等研究了震后應(yīng)急物流動(dòng)態(tài)選址聯(lián)運(yùn)問題，并用混合遺傳算法進(jìn)行求解[4]；王海軍等針對(duì)應(yīng)急物資配送選址-路徑問題，建立了雙目標(biāo)隨機(jī)規(guī)劃模型，通過啟發(fā)式算法來求解[5]等等。上述成果雖然考慮了帶時(shí)間窗口的車輛路徑優(yōu)化問題，但使用的運(yùn)輸工具僅限于車輛，且尚未考慮節(jié)點(diǎn)容量和運(yùn)輸批次，因而并不適應(yīng)本文問題，需要進(jìn)行改進(jìn)。

關(guān)于群島救援也有學(xué)者做過一些研究，例如Sheller分析了2010年海地地震的重建過程，通過建立物流網(wǎng)絡(luò)體系，探討了海上島嶼災(zāi)后救援及物流運(yùn)輸過程中因孤島運(yùn)輸條件限制產(chǎn)生的阻礙效應(yīng)問題[6]；Makkonen等人研究了群島人口變化對(duì)其運(yùn)輸系統(tǒng)的影響，并以芬蘭群島為例分析了如何通過改變?nèi)丝谀Ｊ揭约翱臻g布局來提高群島的運(yùn)輸服務(wù)水平[7]；Gil等人研究了群島之間的可持續(xù)交通規(guī)劃模型，并以葡萄牙亞述爾群島為例探討了使用該模型解決人口可持續(xù)遷移問題的可能性[8]；Shi等人以我國南沙群島為例，分析了周邊國家海上搜索和救援能力，建立了海上搜救模型，并驗(yàn)證其可行性[9]；Hu等人針對(duì)緊急情況下的海運(yùn)大批量貨物的配送問題建立了開放式VRP模型和算法[10]；杜永浩等人建立了多平臺(tái)海上協(xié)同搜索路徑優(yōu)化模型，設(shè)計(jì)了多平臺(tái)海上協(xié)同搜索與路徑優(yōu)化策略，并開展了不同規(guī)模的搜索路徑優(yōu)化仿真[11]；佟士祺等人以軸輻式三級(jí)物流網(wǎng)絡(luò)為基礎(chǔ)，建立了群島海運(yùn)物流體系框架[12]；吳迪等人針對(duì)邊遠(yuǎn)群島海運(yùn)物流體系在構(gòu)建與優(yōu)化中所面對(duì)的選址-庫存-路徑問題，構(gòu)建出物流成本最低的優(yōu)化模型[13]；王諾等人針對(duì)陸海聯(lián)運(yùn)海上戰(zhàn)略投送過程中需解決的選址-路徑優(yōu)化問題，分析了陸海協(xié)同運(yùn)輸體系的運(yùn)作機(jī)理和特點(diǎn)，構(gòu)建了以下水港選址、運(yùn)輸船舶航次、航線配置以及天氣條件等不確定性因素為變量、以投送時(shí)間最短為目標(biāo)的選址-路徑優(yōu)化模型[14]等等。上述成果雖涉及了群島運(yùn)輸系統(tǒng)以及災(zāi)后救援，但未涉及海運(yùn)和空運(yùn)兩種方式的協(xié)同運(yùn)輸問題，因而還需要進(jìn)行深化研究。

有關(guān)?？諈f(xié)同運(yùn)輸也有一些可供借鑒的成果，如Yang通過分析高雄市的交通需求，利用灰色預(yù)測(cè)模型預(yù)測(cè)了未來?？章?lián)運(yùn)的預(yù)期運(yùn)輸市場(chǎng)[15]；Menou等人探討了摩洛哥建立?？章?lián)運(yùn)中心的可能性[16]；Kim和Chang分析了韓國海空聯(lián)運(yùn)現(xiàn)有模式，利用線性規(guī)劃模型從環(huán)境角度討論了海空聯(lián)運(yùn)的環(huán)境污染問題[17]等等。以上成果雖然考慮了海空聯(lián)運(yùn)的協(xié)同運(yùn)輸方式，但僅限于常規(guī)下的運(yùn)行，并未將其作為應(yīng)急救援手段，與本文問題在本質(zhì)上仍有所不同。

分析發(fā)現(xiàn)，以上成果可為本文研究提供部分思路和借鑒，但在規(guī)劃模型構(gòu)建上需做進(jìn)一步的深化。梳理問題可以發(fā)現(xiàn)，本文規(guī)劃的群島救援方案是以?？章?lián)運(yùn)為背景，帶容量約束的多車型多批次車輛路徑問題，此類系統(tǒng)與傳統(tǒng)多車型VRP問題的主要區(qū)別在于：①優(yōu)化目標(biāo)分為輕重緩急兩類。由于救援的緊迫性，首先考慮在最短的時(shí)間內(nèi)搶送關(guān)系到生存的部分藥品、淡水等最急需的物資，以此作為第一個(gè)優(yōu)化目標(biāo)，然后再考慮如何在最短的時(shí)間內(nèi)完成后續(xù)救援物資(包括搶修設(shè)備、發(fā)電機(jī)等)的運(yùn)輸，以此作為第二個(gè)目標(biāo)；②由于救援時(shí)采用空運(yùn)作業(yè)可以在短時(shí)間內(nèi)完成多批次搶運(yùn)，因而使得救援船舶對(duì)各島嶼的物資補(bǔ)給一直處于動(dòng)態(tài)變化中。具體而言，由于空運(yùn)具有速度快的特點(diǎn)，因此首輪救援主要選擇直升機(jī)搶運(yùn)，目標(biāo)函數(shù)為搶送最急需物資的時(shí)間最短。但航空運(yùn)輸運(yùn)量較小，送達(dá)的救援物資有限，為克服這一局限，后續(xù)救援物資的運(yùn)輸由直升機(jī)和救援船舶共同完成，即當(dāng)直升機(jī)完成首輪物資搶送后，將繼續(xù)為各受災(zāi)島嶼運(yùn)送救援物資。直升機(jī)和救援船舶的運(yùn)輸速度相差較大，因此在救援船舶到達(dá)相應(yīng)島嶼之前，直升機(jī)可能已完成對(duì)該島嶼的多次運(yùn)輸。在這一過程中，救援船舶因此對(duì)各島嶼的物資補(bǔ)給需要參考在第一輪和第二輪救援過程中各島嶼已經(jīng)通過直升機(jī)運(yùn)輸獲得的補(bǔ)給物資量進(jìn)行綜合考慮，進(jìn)而對(duì)直升機(jī)和救援船舶各航次和航線的路徑、運(yùn)輸量、運(yùn)輸組織形式(往返運(yùn)輸或循環(huán)運(yùn)輸)進(jìn)行統(tǒng)籌優(yōu)化，這與傳統(tǒng)的VRP問題存在較大不同；③變量多，模型復(fù)雜。船舶與直升機(jī)在運(yùn)載能力、馳援速度等方面差異較大，運(yùn)行航線交錯(cuò)復(fù)雜，交叉聯(lián)動(dòng)，且各自存在往返運(yùn)輸與循環(huán)運(yùn)輸兩種并行方式，需綜合考慮海運(yùn)和空運(yùn)兩種不同運(yùn)輸方式的特點(diǎn)協(xié)同組合，較傳統(tǒng)VRP問題模型中變量更多且關(guān)系更為復(fù)雜。

綜上，以上各項(xiàng)因素決定了群島應(yīng)急救援與傳統(tǒng)的單批次多車型車輛路徑優(yōu)化問題有所不同，需要建立特定的?？諈f(xié)同救援模型開展研究。本文以突發(fā)事件為背景，基于需救援的島嶼數(shù)量、島嶼間距離、物資補(bǔ)給最小基數(shù)等要素，為制定?？諈f(xié)同的運(yùn)輸航次，編排循環(huán)或往返航線，分配機(jī)、船各航程運(yùn)載量等調(diào)度策略建立相應(yīng)的優(yōu)化模型和求解算法，并以南海群島的救援為實(shí)例，驗(yàn)證了所建模型和算法的可行性和合理性。

1 模型構(gòu)建

1.1 問題分析與假設(shè)

通常情況下，針對(duì)群島救援可供使用的應(yīng)急交通工具有直升機(jī)和救援船舶兩種。由于群島距大陸較遠(yuǎn)，當(dāng)突發(fā)事件發(fā)生時(shí)，可考慮以設(shè)施、設(shè)備、物資完善的中心島嶼作為基地對(duì)周邊衛(wèi)星島展開救援。在直升機(jī)與救援船舶數(shù)量均有限的情況下，為了贏得時(shí)間，在制定調(diào)度方案時(shí)將采取以下做法：將救援過程分為兩個(gè)并行步驟(按登島的時(shí)間順序?qū)⑵浞Q為首輪救援和后續(xù)救援)，其中，首輪救援是指利用直升機(jī)以最快的速度為各個(gè)衛(wèi)星島搶送少量最急需的物資(如藥品、淡水等)。在這一階段中，直升機(jī)運(yùn)輸?shù)慕M織形式包括往返運(yùn)輸和循環(huán)運(yùn)輸兩種，需要根據(jù)島嶼的需求，以首輪救援時(shí)間最短為目標(biāo)進(jìn)行優(yōu)化；后續(xù)救援包括救援船舶運(yùn)輸和完成首輪救援后的直升機(jī)運(yùn)輸兩個(gè)方面，需要綜合考慮救援船舶和直升機(jī)在運(yùn)輸能力、裝卸速度和運(yùn)輸速度等方面的差異，以共同運(yùn)輸時(shí)間最短為目標(biāo)，對(duì)不同運(yùn)輸工具的運(yùn)輸路線、航次數(shù)量、運(yùn)輸量和運(yùn)輸組織形式進(jìn)行統(tǒng)籌優(yōu)化。

為簡化問題，假設(shè)：①中心島儲(chǔ)備有足夠的救援物資可供調(diào)用；②所有衛(wèi)星島都處于救援船舶和直升機(jī)的航程內(nèi)；③各衛(wèi)星島物資所需的最小補(bǔ)給基數(shù)比例相同，救援優(yōu)先級(jí)相同；④直升機(jī)在中心島的裝載時(shí)間、衛(wèi)星島的卸載時(shí)間固定，救援船舶的裝卸時(shí)間與裝卸量有關(guān)；⑤首輪救援任務(wù)由直升機(jī)負(fù)責(zé)完成，且運(yùn)載量需滿足最低的需求量；⑥當(dāng)直升機(jī)或船舶同一航次途經(jīng)多個(gè)島嶼時(shí)，卸載量按各島嶼物資需求量等比例分配；⑦各機(jī)組以最快速度在前s個(gè)執(zhí)飛航次中完成遍訪各島的首輪救援任務(wù)；⑧后續(xù)救援中，對(duì)于救援船舶已投送過的島嶼，直升機(jī)不再投送。

1.2 符號(hào)定義

設(shè)中心島共有I架直升機(jī)，直升機(jī)的平均飛行速度為va，額定載重量為na，直升機(jī)的首輪救援時(shí)間為Z，直升機(jī)總救援時(shí)間為X；在中心島的裝載時(shí)間為te，第i架直升機(jī)的航次數(shù)量為Ji，i∈{1,2,…,I}。設(shè)中心島共有M艘救援船舶，救援船舶完成的總救援時(shí)間為Y，救援船舶的航行速度為vb，額定載重量為nb，在中心島的裝載速度為vl，在衛(wèi)星島的卸載速度為vm，第m艘救援船的航次數(shù)量為Nm，m∈{1,2,…,M}。設(shè)共有D個(gè)衛(wèi)星島，第d個(gè)衛(wèi)星島的救援物資需求為Qd，d∈1,2,…,D，第d個(gè)衛(wèi)星島的卸載時(shí)間為td，首輪救援物資對(duì)衛(wèi)星島最小補(bǔ)給基數(shù)的比例為P。

對(duì)于第i架直升機(jī)的第j個(gè)航次，設(shè)路經(jīng)衛(wèi)星島嶼的集合為dij，路經(jīng)的衛(wèi)星島上卸載的貨量為Nd，d∈dij，路經(jīng)中心島到衛(wèi)星島的距離為Ld，d∈dij，路經(jīng)衛(wèi)星島d與衛(wèi)星島d′之間的距離為Ldd′，d、d′∈dij，設(shè)aij、bij為0-1變量，若其航線為往返航線，則aij=1，bij=0；若為循環(huán)航線，則aij=0，bij=1；設(shè)直升機(jī)路經(jīng)島嶼g救援時(shí)為Xijg，g∈{1,2,…,D}，為0-1變量，若路經(jīng)編號(hào)為g的島嶼，則Xijg=1，否則Xijg=0。

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

設(shè)直升機(jī)的首輪救援時(shí)間為Z，直升機(jī)總的救援時(shí)間為X，救援船舶的總救援時(shí)間為Y，有:

(1)

(2)

m∈{1,2,…,M},n∈{1,2,…,Nm}

(3)

按照救援時(shí)間最短原則，設(shè)置目標(biāo)函數(shù)如下:

Tone=min(Z)

(4)

Ttwo=min(X,Y)

(5)

1.4 約束條件

(6)

(7)

(8)

vl·tmn≤nb,m∈{1,2,…,M},n∈{1,2,…,Nm}

(9)

2 計(jì)算方法

由以上建模過程可知，?？諈f(xié)同救援路線、批量的優(yōu)化實(shí)際上是一個(gè)NP-Hard問題[18]，可采用啟發(fā)式算法或進(jìn)化算法進(jìn)行求解，禁忌搜索算法、遺傳算法、模擬退火算法和蟻群算法都可用于解決該類問題[19]。潘振東等采用遺傳算法，提出先安排路線后分組的染色體設(shè)定方法，并設(shè)計(jì)一種基于運(yùn)輸點(diǎn)劃分的遺傳算法(partition based on autonomous genetic algorithm，PB-GA)，該算法按照染色體上基因的順序，依次在滿足運(yùn)輸載體載重量的約束條件下計(jì)算每個(gè)節(jié)點(diǎn)費(fèi)用最小的劃分，并根據(jù)當(dāng)前節(jié)點(diǎn)的最小劃分對(duì)其所有后繼節(jié)點(diǎn)的最小劃分進(jìn)行改進(jìn)，直到得出染色體每段基因的最小劃分，即整個(gè)染色體對(duì)應(yīng)的可行解[20]。PB-GA算法雖然在運(yùn)輸節(jié)點(diǎn)的劃分方面有所創(chuàng)新，但其目標(biāo)函數(shù)是以成本最小為目標(biāo)，且沒有考慮各個(gè)運(yùn)輸節(jié)點(diǎn)的需求量，因而對(duì)本文情況并不適用。相對(duì)于傳統(tǒng)的多車型車輛路徑優(yōu)化，本文所設(shè)問題與其主要差異是在考慮多批次運(yùn)輸?shù)耐瑫r(shí)，還要求完成時(shí)間的最短，且只有當(dāng)所有島嶼都得到所需的救援物資時(shí)整個(gè)任務(wù)才算完成。基于以上分析，本文對(duì)PB-GA算法進(jìn)行進(jìn)一步的改進(jìn)，提出一種能夠同時(shí)考慮兩種運(yùn)輸方式、多批次運(yùn)輸?shù)碾p層搜索遺傳算法(double-deck search genetic algorithm，DS-GA)。

本文提出的DS-GA算法的核心思想是：對(duì)于任意一條染色體，首先按救援批次的先后順序，將其劃分為上層和下層兩個(gè)部分，設(shè)上層為首輪救援，下層為后續(xù)救援，基于上層和下層使用的運(yùn)輸工具，按其數(shù)量劃分為不同長度的信息段，每個(gè)信息段表示1個(gè)航次。根據(jù)需救援島嶼的數(shù)量、與中心島的距離以及投入救援的物資量，對(duì)上層染色體進(jìn)行初始化配置，使其先滿足首輪救援任務(wù)，得到上層的初始可行解。然后，再對(duì)下層染色體進(jìn)行搜索，根據(jù)其在運(yùn)量、運(yùn)輸距離以及運(yùn)輸路線之間的復(fù)雜關(guān)系，對(duì)直升機(jī)和救援船舶同時(shí)進(jìn)行配置，找到下層的可行解?；谠摽尚薪?，再對(duì)上層染色體的約束域進(jìn)行劃分，并開展搜索，找到上層新一輪的最優(yōu)解，如此反復(fù)交互，直到上層和下層的約束域都唯一時(shí)，跳出循環(huán)結(jié)束，得出優(yōu)化結(jié)果。由于染色體信息龐大，且有小數(shù)(由裝卸量引起)存在，所以不做編碼、解碼處理，得到的初始可行解直接按式(4)、(5)進(jìn)行適值計(jì)算，并完成后續(xù)的選擇、變異和交叉操作。

2.1 染色體設(shè)計(jì)

為表達(dá)不同運(yùn)輸方式各航次、航線配置以及運(yùn)載量，滿足染色體序列能夠完整表達(dá)全部解空間(極限情況下所有航次都為往返航線)的要求完成劃分階段操作。先將染色體分為兩層，上層為首輪(由直升機(jī)執(zhí)行)救援目標(biāo)函數(shù)，下層為后續(xù)救援(由救援船舶和完成首輪救援的直升機(jī)共同執(zhí)行)目標(biāo)函數(shù)。對(duì)上、下層的染色體按各層涉及的交通工具數(shù)量、航次數(shù)量設(shè)置分隔符，兩個(gè)分隔符之間的連續(xù)基因即表示某艘船或某架飛機(jī)1個(gè)航次依次經(jīng)過的島嶼。此外，考慮到直升機(jī)與救援船舶不同的運(yùn)載能力，每架直升機(jī)每航次單位染色體的長度固定為3位，第1、2位是其航線所經(jīng)過的島嶼編號(hào)，若第2位編號(hào)為0，表示其航線為往返航線，第3位為固定的分隔符0；每艘救援船舶每航次單位染色體的長度固定為5位，第1位是其在中心島的裝載時(shí)間，第2、3、4位是其航線訪問島嶼的順序編號(hào)，若第4位編號(hào)為0，表示只經(jīng)過兩個(gè)島，若第3、4位都為0，表示為往返航線，第5位是固定的分隔符0。為方便計(jì)算，不對(duì)每個(gè)航次航線上各個(gè)島嶼的卸載量以染色體表達(dá)，而是將其作為隱形條件，由其航線上的島嶼編號(hào)決定，按島嶼所需要的救援物資比例分配。例如，當(dāng)有7個(gè)衛(wèi)星島需要救援時(shí)，出動(dòng)救援直升機(jī)為2架，每架執(zhí)飛4個(gè)航次；救援船舶為2艘，每艘救援船舶出海1個(gè)航次，按照上述規(guī)則進(jìn)行初始配置，生成的染色體表達(dá)式如圖1所示。

圖1 染色體表達(dá)式

在圖1(a)中，表示直升機(jī)執(zhí)飛的前2個(gè)航次，以該染色體的前6位為例，第1～3位染色體表示機(jī)組執(zhí)飛的第1個(gè)航次為循環(huán)航線，其救援路線為中心島→4#島嶼→5#島嶼，第4～6位染色體表示機(jī)組執(zhí)飛的第1個(gè)航次也為循環(huán)航線，其救援路線為中心島→1#島嶼→6#島嶼。圖1(b)表示救援船舶的運(yùn)輸航次以及直升機(jī)執(zhí)飛的后2個(gè)航次，以前5位為例，該段染色體表示救援船舶Ⅰ在中心島的裝載時(shí)間為2.3h，只出海1個(gè)航次，其方式為循環(huán)航線，救援路線為中心島→4#島嶼→7#島嶼→2#島嶼。

得到上述救援路線方案后，便可對(duì)各路線的配載量進(jìn)行計(jì)算，相應(yīng)的規(guī)則如下：①當(dāng)直升機(jī)或者船舶同一航次途經(jīng)多個(gè)島嶼時(shí)，在各個(gè)島嶼上的卸載量按各島嶼最小補(bǔ)給基數(shù)等比例分配；②當(dāng)按上述比例分配無法滿足個(gè)別島嶼的最低需求量或最小補(bǔ)給基數(shù)時(shí)，需進(jìn)行鄰域搜索，在航線上選擇超出最低需求量或最小補(bǔ)給基數(shù)比例最大的島嶼，將該島嶼的卸載量降至滿足條件的最小值，依次調(diào)整不滿足要求的島嶼卸載量，直至所有被救援的島嶼都滿足需求為止。

2.2 交叉與變異算子設(shè)計(jì)

根據(jù)染色體編碼的特點(diǎn)，DS-GA以救援船舶裝卸時(shí)間和航次島嶼號(hào)分別交叉的方式進(jìn)行交叉運(yùn)算，對(duì)于救援船舶單航次情況，其子代繼承了父代1的裝卸時(shí)間和父代2的路經(jīng)島嶼順序；對(duì)于直升機(jī)單航次情況，其子代按順序依次繼承父代1和父代2路經(jīng)島嶼的順序。具體交叉操作如圖2所示。

圖2 交叉算子

當(dāng)島嶼數(shù)量較多時(shí)，各衛(wèi)星島需要救援的物資量總和增大，需要的救援航次也增多，因此染色體將較長，包含信息也較多。為求解較為復(fù)雜的染色體，可將變異算子分為兩種情況：第1種是相同運(yùn)輸工具不同航次間島嶼編號(hào)的交換，第2種是單獨(dú)染色體某1位(除分隔符)的變異，具體操作過程如圖3所示，具體流程見圖4。

圖3 變異算子

圖4 計(jì)算流程示意圖

3 算例

3.1 基本數(shù)據(jù)

現(xiàn)以我國南海部分島嶼為例，假定需救援的島嶼共有9個(gè)，各島嶼位置及坐標(biāo)分別如圖5和表1所示。設(shè)可調(diào)用直升機(jī)5架，最大載重量5t，在衛(wèi)星島的裝載和卸載時(shí)間均為0.5h，最大續(xù)航時(shí)間為2.5h，平均飛行速度為260km/h(約合140n mile/h)；調(diào)用救援船舶3艘，載重量200t，航速12節(jié)，在中心島的裝載速度為60t/h，在衛(wèi)星島的卸載速度為50t/h。各衛(wèi)星島物資所需最小補(bǔ)給基數(shù)Qd如表2所示，首輪救援物資量設(shè)定為各衛(wèi)星島物資最小補(bǔ)給基數(shù)的5%。

圖5 某群島各島嶼分布位置示意圖

表1 各島嶼坐標(biāo)(單位：n mile)

表2 各衛(wèi)星島物資補(bǔ)給最小基數(shù)(t)

3.2 計(jì)算結(jié)果

采用MATLAB 6.5運(yùn)行DS-GA算法，設(shè)置種群個(gè)數(shù)N=30，交叉概率Nc=0.5，變異概率Nm=0.005，在windows XP，AMD Anthon(tm) Ⅱ X2 240 Processor 2.81Ghz，2GB內(nèi)存的環(huán)境下完成計(jì)算。迭代3275次后得到最優(yōu)解，收斂過程如圖6所示。運(yùn)行計(jì)算程序10次，得到首輪救援和全部完成救援的平均時(shí)間分別為3.65h、15.63h，對(duì)應(yīng)的路徑方案和所需時(shí)間見表3、表4和圖7和圖8。

圖6 計(jì)算收斂過程示意圖

表3 直升機(jī)救援運(yùn)行方案

表4 救援船舶運(yùn)行方案

圖7 首輪救援直升機(jī)飛行路線

圖8 船舶救援航線

3.3 算法對(duì)比

為說明本文算法的有效性，分別采用基于運(yùn)輸點(diǎn)劃分的遺傳算法(PB-GA)和CPLEX軟件計(jì)算的精確解進(jìn)行對(duì)比，對(duì)比實(shí)驗(yàn)仍在相同的計(jì)算機(jī)上運(yùn)行，各計(jì)算10次。結(jié)果顯示，在優(yōu)化結(jié)果上，本文算法得到的平均救援時(shí)間為15.63h，相對(duì)于PB-GA算法的16.88h縮短了7.30%，與CPLEX求解出的結(jié)果一致，表明本文算法能夠較好地找到滿意解。在計(jì)算時(shí)間上，本文算法僅用時(shí)19.21s，比PB-GA算法用時(shí)21.56s縮短了11.32%，比CPLEX計(jì)算用時(shí)583s縮短了96.7%，說明本文算法具有更好的計(jì)算效率。在物理內(nèi)存占用上，本文算法占用2587MB，比PB-GA算法和CPLEX計(jì)算分別減少了2.63%和5.34%。以上對(duì)比說明，本文算法能夠快速收斂并得到較好結(jié)果，具體見表5。

表5 算法對(duì)比結(jié)果

4 結(jié)論

海空協(xié)同對(duì)邊遠(yuǎn)群島開展救援是最有效的一種方式，但已有研究涉及此類問題的還較少。由于救援的緊迫性，通常先要考慮在最短的時(shí)間內(nèi)搶送關(guān)系到生存的部分藥品、淡水等最急需的物資，然后再考慮如何在最短的時(shí)間內(nèi)完成后續(xù)救援，因此整個(gè)救援實(shí)際上具有分階段的特點(diǎn)?？者\(yùn)救援速度快，但運(yùn)量小，船舶救援運(yùn)量大，但速度慢，在救援船舶到達(dá)相應(yīng)島嶼之前，直升機(jī)可能已完成對(duì)島嶼的多次運(yùn)輸。船舶與直升機(jī)在運(yùn)載能力、馳援速度等方面存在巨大差異，協(xié)同時(shí)運(yùn)行航線交錯(cuò)復(fù)雜，交叉聯(lián)動(dòng)，因而較傳統(tǒng)的VRP問題更為復(fù)雜，需要建立新的規(guī)劃模型和求解方法。

為解決以上問題，本文給出了?？諈f(xié)同救援的調(diào)度方案優(yōu)化模型，提出雙層搜索遺傳算法(DS-GA)，并結(jié)合算例進(jìn)行了求解，得到了較為理想的優(yōu)化效果，表明本文所建模型及算法是合理有效的，可為我國有關(guān)部門制定救援方案提供借鑒。

需要指出，本文僅以同一群島的中心島對(duì)各衛(wèi)星島展開救援為研究背景，而當(dāng)面對(duì)多組群島，或有的救援物資需從大陸緊急調(diào)撥時(shí)，其調(diào)度計(jì)劃將會(huì)變得更為復(fù)雜，對(duì)于此類問題如何構(gòu)建優(yōu)化模型，是下一步需要深入研究的內(nèi)容。