基于智能算法的災(zāi)區(qū)救援路徑規(guī)劃

周小琳, 焦子恒, 胡錦林, 李彥怡, 王長(zhǎng)鵬

(1. 長(zhǎng)安大學(xué) a. 信息工程學(xué)院; b. 理學(xué)院, 西安 710000； 2. 寶雞文理學(xué)院 經(jīng)濟(jì)管理學(xué)院, 陜西 寶雞 721013)

0 引 言

21世紀(jì)以來(lái), 世界各地災(zāi)害頻發(fā), 使各國(guó)人民遭受了巨大的生命威脅和經(jīng)濟(jì)損失, 越來(lái)越多的學(xué)者進(jìn)行應(yīng)急救災(zāi)的模型構(gòu)建及研究, 隨著科技的發(fā)展, 智能算法在各行各業(yè)中得到了廣泛應(yīng)用。2017年, 美國(guó)波多黎各[1]遭受了最嚴(yán)重的颶風(fēng)災(zāi)害, 致使該島的人員傷亡和經(jīng)濟(jì)損失極為慘重, 交通網(wǎng)絡(luò)的大部分功能喪失。由于持續(xù)嚴(yán)重受災(zāi), 波多黎各的城鎮(zhèn)情況在相當(dāng)長(zhǎng)的一段時(shí)間內(nèi)十分不明朗, 救援無(wú)法進(jìn)行； 數(shù)十個(gè)地區(qū)孤立且無(wú)法通信。各地區(qū)對(duì)醫(yī)療用品、 救生設(shè)備的需求量急劇增大, 對(duì)緊急救護(hù)診所、 醫(yī)院急診室和非政府組織救濟(jì)行動(dòng)的需求也急劇增大。在災(zāi)情期間, 一個(gè)非政府組織HELP, Inc.試圖通過(guò)設(shè)計(jì)一種名為“DroneGo”的災(zāi)難響應(yīng)系統(tǒng)[2]減少災(zāi)害造成的損失。DroneGo將使用旋翼無(wú)人機(jī)提供預(yù)先封裝的醫(yī)療用品和高分辨率航拍視頻偵察, 以進(jìn)行醫(yī)療救援和提供交通道路網(wǎng)絡(luò)的破壞情況等相關(guān)信息。

針對(duì)急缺電力、 水源、 救災(zāi)物資的重大災(zāi)難突發(fā)地, 筆者建立了利用現(xiàn)代無(wú)人機(jī)和救援集裝箱進(jìn)行首要物資的分配以及受損交通干線(xiàn)偵測(cè)的災(zāi)難相應(yīng)模型, 其中急需解決的任務(wù)有(以美國(guó)波多黎各受災(zāi)為例)： 結(jié)合人口分布和地理位置, 確定集裝箱放置的最佳位置[3], 以便能進(jìn)行醫(yī)療供應(yīng)交付和道路網(wǎng)絡(luò)的視頻偵察; 形成最佳的無(wú)人機(jī)調(diào)度時(shí)間表[4], 以滿(mǎn)足偵查和物資配送需求。

當(dāng)災(zāi)情發(fā)生后, 如何及時(shí)、 有效、 合理地把各個(gè)儲(chǔ)備點(diǎn)有限的救災(zāi)物資分配到災(zāi)區(qū)的各個(gè)物資發(fā)放點(diǎn), 成為應(yīng)急管理部門(mén)非常關(guān)心的一個(gè)重要問(wèn)題, 也是國(guó)內(nèi)外學(xué)者研究的一個(gè)熱點(diǎn)。目前, 現(xiàn)有針對(duì)救災(zāi)物資分配問(wèn)題的研究大致可以粗略地分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化兩大類(lèi)。

在單目標(biāo)優(yōu)化方面, 王冬冬等[5]以救災(zāi)物資配送路徑最短為目標(biāo)建立期望最短模型和α最短路徑模型。模型將災(zāi)區(qū)救援物資配送上的不確定因素, 使不確定權(quán)重下的災(zāi)區(qū)救援物資配送問(wèn)題得到解決。李永義等[6]以最優(yōu)分配策略為目標(biāo)建立物資分配優(yōu)化模型。引入?yún)^(qū)間數(shù)可能度概念, 對(duì)災(zāi)區(qū)區(qū)域大小、 受災(zāi)程度、 人口密度和災(zāi)區(qū)群眾需求等不確定因素進(jìn)行區(qū)間化, 簡(jiǎn)化了計(jì)算過(guò)程, 同時(shí)使應(yīng)急物資的分配量分布更為均衡。

在多目標(biāo)優(yōu)化方面, 夏紅云等[7]利用前景理論建立了一個(gè)以最短應(yīng)急總響應(yīng)時(shí)間、 最小災(zāi)民心理恐慌度、 最小救災(zāi)物資為滿(mǎn)足度、 最小災(zāi)民心理嫉妒值、 最小災(zāi)民損失及最小應(yīng)急響應(yīng)總成本為目標(biāo)的救災(zāi)物資高緯度多目標(biāo)分配模型。運(yùn)用SPEA2+SDE算法進(jìn)行求解, 并對(duì)SPEA2+SDE算法進(jìn)行了改進(jìn), 引入個(gè)體編碼方案和個(gè)體修正策略, 后稱(chēng)SPEA2+SDE+AIR算法, 增強(qiáng)了算法的收斂性能。王挺等[8]根據(jù)配送車(chē)輛通行時(shí)間最小和風(fēng)險(xiǎn)最小為目標(biāo)建立震后多目標(biāo)路徑優(yōu)化模型。

針對(duì)以上問(wèn)題, 筆者做了以下工作：

1) 引入泰森多邊形進(jìn)行不同等級(jí)的救援響應(yīng)。引入泰森多變形排除了地勢(shì)較高、 人煙稀少的地區(qū), 優(yōu)先搜救人口以及公路網(wǎng)密集區(qū)域, 增加模型的實(shí)用性。

2) 基于K-means的救援中心預(yù)選。利用K-means聚類(lèi)模型在泰森多邊形完成后的結(jié)果上進(jìn)行聚類(lèi), 選出更加合理的救援中心投放物資, 增加救援效率。

3) 基于遺傳算法的多點(diǎn)式最小搜救路徑規(guī)劃。通過(guò)智能遺傳算法完成多源有約束的最短搜索路徑規(guī)劃。

1 符號(hào)說(shuō)明

2 基于K-means的聚類(lèi)模型

2.1 泰森多邊形模型

在實(shí)際救災(zāi)中, 應(yīng)該首先針對(duì)5所醫(yī)院、 公路網(wǎng)密集、 人口密度大以及平原地區(qū)進(jìn)行救助, 從而確定集裝箱位置的選取以及救助與偵察路線(xiàn)的規(guī)劃。具體如圖1所示。

圖1 人口熱力圖Fig.1 Population heat map

圖1中粗點(diǎn)表示人口密集區(qū)域。從圖1中可以直觀(guān)地看到波多黎各的人口分布情況： 沿海地區(qū)和東部地區(qū)的人口分布較為密集, 中部較為稀疏。

筆者將這些信息在地圖上以離散點(diǎn)的形式呈現(xiàn)出來(lái), 以這些信息為依據(jù)利用泰森多邊形模型[9]對(duì)點(diǎn)進(jìn)行劃分, 從而篩除高海拔山地區(qū)域。

畫(huà)出所有點(diǎn)的垂直平分線(xiàn), 交叉后會(huì)形成很多泰森多邊形。每個(gè)多邊形中僅含有一個(gè)離散點(diǎn), 且該區(qū)域所有點(diǎn)到相應(yīng)離散點(diǎn)的距離最近, 故可用離散點(diǎn)的性質(zhì)代替整個(gè)區(qū)域的性質(zhì)。由此可以對(duì)平原地區(qū)和高海拔山地區(qū)域進(jìn)行劃分。

2.2 K-means聚類(lèi)模型

運(yùn)用K-means聚類(lèi)算法[10], 以無(wú)人機(jī)最大飛行半徑Rm作為聚類(lèi)的標(biāo)準(zhǔn), 將篩除山脈的地圖聚成3類(lèi), 且所有醫(yī)院必須包括在聚類(lèi)以?xún)?nèi)。最后的聚類(lèi)中心作為集裝箱的位置?；谏鲜龇治? 可建立聚類(lèi)模型。

(1)

第j個(gè)點(diǎn)到聚類(lèi)中心距離小于最大飛行半徑Rm, 可表示為

(2)

聚類(lèi)的目標(biāo)是覆蓋率達(dá)到最大, 可表示為

(3)

2.3 算法設(shè)計(jì)

為了實(shí)現(xiàn)符合實(shí)際要求的快速搜索規(guī)劃, 結(jié)合K-means中心聚類(lèi)以及泰森多邊形實(shí)現(xiàn)算法, 算法如下。

算法1

Input: 人口分布dataloc，聚類(lèi)閾值thre

Initialize:

隨機(jī)選擇聚類(lèi)中心center0;

Do:

對(duì)每個(gè)點(diǎn)計(jì)算與center0的距離d;

根據(jù)d劃分dataloc為k個(gè)集合；

計(jì)算k個(gè)集合的中心centerk；

While: |centerk-center0|≥thre

利用泰森多邊形對(duì)聚類(lèi)結(jié)果進(jìn)行篩選；

再進(jìn)行聚類(lèi)獲得輸出結(jié)果area1、area2、area2

Output。

運(yùn)用K-means算法對(duì)地圖中的點(diǎn)進(jìn)行聚類(lèi), 然后用聚類(lèi)中心代替地圖中的點(diǎn)以達(dá)到對(duì)地圖中的點(diǎn)離散化的效果; 運(yùn)用泰森多邊形對(duì)離散化后的點(diǎn)進(jìn)行劃分, 從而篩選出地圖中的高海拔山地區(qū)域, 并排除; 運(yùn)用改進(jìn)的K-means算法對(duì)地圖中剩下的點(diǎn)進(jìn)行聚類(lèi)。以點(diǎn)的最大覆蓋率為目標(biāo)進(jìn)行聚類(lèi)中心的搜索。

3 基于遺傳算法的多人最短路徑模型

3.1 模型分析

在第2節(jié)中求出了集裝箱的最佳投放位置, 并通過(guò)泰森多邊形算法將區(qū)域離散化, 將問(wèn)題轉(zhuǎn)化為從離散數(shù)據(jù)中找出滿(mǎn)足約束條件的路徑。

已知離散化數(shù)據(jù)分布, 求解出通過(guò)這些點(diǎn)最少1次情況下的最短路徑, 這便是經(jīng)典的旅行商問(wèn)題。而無(wú)人機(jī)有航程約束, 因此路徑肯定不止1條，所以采用解決基于遺傳算法[11]的多旅行商問(wèn)題[12]的解法求出無(wú)人機(jī)搜索路徑。

3.2 模型建立

無(wú)人機(jī)全部的搜索范圍可看作加權(quán)圖G, 求出每臺(tái)無(wú)人機(jī)的搜索區(qū)域, 即求解其頂點(diǎn)集的分組V1,V2,…,Vn在G中生成的n個(gè)子圖G(V1),G(V2),…,G(Vn), 顯然

(4)

無(wú)人機(jī)完成偵察任務(wù)后要返回集裝箱充電。設(shè)原點(diǎn)為O, 且

O∈Vi,i=1,2,…,n

(5)

設(shè)Ai(i=1,2,…,n)為G(Vi)中無(wú)人機(jī)飛行的最佳路線(xiàn),ω(Ai)為Ai中所有邊的權(quán)之和。要使所有無(wú)人機(jī)的飛行路徑之和最短, 則有

(6)

3.3 算法設(shè)計(jì)

下面以無(wú)人機(jī)路程之和最小為優(yōu)化目標(biāo), 運(yùn)用遺傳算法對(duì)其進(jìn)行優(yōu)化求解。

已知起點(diǎn)和需要經(jīng)過(guò)的點(diǎn), 同時(shí)每條路徑都有長(zhǎng)度限制, 因此需要對(duì)多人旅行商問(wèn)題的解決方法進(jìn)行調(diào)整改進(jìn), 增加每條路徑長(zhǎng)度小于無(wú)人機(jī)最大航程的約束條件。

算法2

Input: 無(wú)人機(jī)數(shù)量ndrone，聚類(lèi)閾值thre

Initialize:

Do:

在區(qū)域內(nèi)隨機(jī)生成N組點(diǎn);

根據(jù)ndrone數(shù)生成斷點(diǎn)數(shù)ncut;

根據(jù)斷點(diǎn)數(shù)ncut生成N組不同的斷點(diǎn);

對(duì)每一組根據(jù)對(duì)應(yīng)的斷點(diǎn)進(jìn)行分?jǐn)?，并?jì)算全部路徑的距離總和;

生成初始群體gini;

Do:

For every 8 groups:

找出最佳的一組, 對(duì)其進(jìn)行復(fù)制操作;

并在復(fù)制出來(lái)的個(gè)體當(dāng)中進(jìn)行不同的交叉操作和小概率的變異操作;

生成出新的8個(gè)個(gè)體, 代替原來(lái)的8個(gè)個(gè)體

如果更優(yōu)則替換

While: 滿(mǎn)足遺傳代數(shù)

While: 存在某路徑長(zhǎng)度大于無(wú)人機(jī)的最大航程；

Output: 最少無(wú)人機(jī)數(shù)下的路徑最佳劃分。

4 模型求解

4.1 集裝箱的最佳位置確定

根據(jù)波多黎各人口熱力圖和交通網(wǎng)絡(luò)圖等實(shí)際情況, 將其地圖離散化, 如圖2a所示, 以便后續(xù)求解。其中實(shí)心圓代表具有原始人口熱力值等信息的點(diǎn), 空心圓代表離散化后的點(diǎn)。利用泰森多邊形得到區(qū)域劃分, 如圖2b所示。

a 離散化數(shù)據(jù) b 泰森多邊形區(qū)域劃分 圖3 K-means聚類(lèi)圖 圖2 初始化數(shù)據(jù)圖 Fig.3 K-means clustering diagram Fig.2 Initialize data

可以直觀(guān)地看到, 面積較小的泰森多邊形為人口較密集和交通線(xiàn)路較密集的地區(qū), 面積較大的泰森多邊形可視為海拔較高的山地區(qū)域, 可以從地圖中剔除, 同時(shí)泰森多邊形將區(qū)域均勻地劃分為了較小的區(qū)域, 可以用區(qū)域中心的點(diǎn)代替整個(gè)泰森多邊形, 便于后續(xù)的集裝箱區(qū)域劃分和路徑規(guī)劃。根據(jù)所建模型, 可得到如圖3所示的聚類(lèi)結(jié)果。

不同顏色的點(diǎn)代表不同的聚類(lèi), 實(shí)心點(diǎn)代表聚類(lèi)中心?？梢缘玫郊b箱的位置在[18.383,-67.005],[18.302,-66.406],[18.301,-65.9], 可以覆蓋81%的島嶼面積?？梢?jiàn), 運(yùn)用K-means聚類(lèi)模型可以較好地選取集裝箱的最佳位置, 使其覆蓋范圍最大。

4.2 無(wú)人機(jī)的交付路線(xiàn)和偵察路線(xiàn)

根據(jù)所建模型, 得到了無(wú)人機(jī)最優(yōu)的偵察路線(xiàn), 如圖4所示。發(fā)現(xiàn)無(wú)人機(jī)都是繞一個(gè)極窄的類(lèi)似橢圓的路線(xiàn)最后返回集裝箱位置, 總體上看無(wú)人機(jī)的偵察路線(xiàn)圖呈輻射狀。

圖4 無(wú)人機(jī)最優(yōu)偵察路線(xiàn)圖Fig.4 Optimal uav reconnaissance roadmap

5 靈敏度分析

下面對(duì)模型中的一些參數(shù)進(jìn)行調(diào)整[12], 以驗(yàn)證所建模型的合理性和穩(wěn)定性。

首先研究遺傳算法的迭代次數(shù)對(duì)結(jié)果的影響, 如圖5所示。由圖5可知, 迭代次數(shù)較低時(shí), 算法得到的結(jié)果很差； 迭代次數(shù)越高, 遺傳算法獲得的路徑越短, 無(wú)人機(jī)進(jìn)行偵察的時(shí)間越短, 但相應(yīng)的算法收斂時(shí)間越長(zhǎng)。而迭代次數(shù)增加到一定數(shù)值時(shí), 路徑總和的變化幅度很小。所以需要合理地調(diào)整迭代次數(shù)。且無(wú)人機(jī)數(shù)量較少時(shí), 偵察用時(shí)很長(zhǎng)； 此時(shí)增加無(wú)人機(jī)數(shù)量, 偵察用時(shí)急劇下降, 模型的靈敏度較高， 故無(wú)人機(jī)的數(shù)量對(duì)模型的影響較大, 因而需要選取合理的集裝箱裝載方案。

圖5 遺傳算法的靈敏度分析Fig.5 Sensitivity analysis of genetic algorithm

基于上述分析, 可以得知筆者建立的模型能很好地應(yīng)用于實(shí)際問(wèn)題, 模型的穩(wěn)定性較好。

6 結(jié) 語(yǔ)

通過(guò)結(jié)合智能算法和泰森多邊形建立災(zāi)區(qū)響應(yīng)救援模型, 利用泰森多邊形, 以公路網(wǎng)密集程度、 人口密度等為標(biāo)準(zhǔn)以點(diǎn)代面, 篩除高海拔地區(qū), 建立了基于遺傳算法的多旅行商模型, 采用多目標(biāo)全局最優(yōu)啟發(fā)式搜索策略, 很好地求得了無(wú)人機(jī)的飛行最短路徑, 同時(shí)以美國(guó)波多黎各受災(zāi)區(qū)域?yàn)槔? 成功檢驗(yàn)了模型在實(shí)際中的有效性。