周小琳, 焦子恒, 胡錦林, 李彥怡, 王長鵬

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

0 引 言

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

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

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

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

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

針對以上問題, 筆者做了以下工作：

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

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

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

1 符號說明

2 基于K-means的聚類模型

2.1 泰森多邊形模型

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

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

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

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

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

2.2 K-means聚類模型

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

(1)

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

(2)

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

(3)

2.3 算法設(shè)計

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

算法1

Input: 人口分布dataloc，聚類閾值thre

Initialize:

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

Do:

對每個點(diǎn)計算與center0的距離d;

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

計算k個集合的中心centerk；

While: |centerk-center0|≥thre

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

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

Output。

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

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

3.1 模型分析

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

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

3.2 模型建立

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

(4)

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

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

(5)

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

(6)

3.3 算法設(shè)計

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

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

算法2

Input: 無人機(jī)數(shù)量ndrone，聚類閾值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);

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

生成初始群體gini;

Do:

For every 8 groups:

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

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

生成出新的8個個體, 代替原來的8個個體

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

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

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

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

4 模型求解

4.1 集裝箱的最佳位置確定

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

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

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

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

4.2 無人機(jī)的交付路線和偵察路線

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

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

5 靈敏度分析

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

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

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

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

6 結(jié) 語

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