基于聚類分析的無(wú)人機(jī)最優(yōu)投遞位置研究

楊洪 郭瑞 張千胤

摘 ?要：2017年，美國(guó)波多黎各遭受了史上最嚴(yán)重的颶風(fēng)，已造成2900多人死亡。其中有一個(gè)非政府組織試圖設(shè)計(jì)一種稱為無(wú)人機(jī)的可運(yùn)輸災(zāi)難響應(yīng)系統(tǒng)。本文被要求利用波多黎各2017年的情況設(shè)計(jì)該系統(tǒng)，從中求出貨物集裝箱的位置。針對(duì)這一問(wèn)題，首先，本文對(duì)區(qū)域的數(shù)量進(jìn)行聚類分析，然后使用空間分析和決策評(píng)估系統(tǒng)來(lái)確定系統(tǒng)貨物集裝箱的位置。

關(guān)鍵詞：颶風(fēng);無(wú)人機(jī);最優(yōu)位置

前言

颶風(fēng)是一種突如其來(lái)的自然災(zāi)害，強(qiáng)風(fēng)暴和海浪往往會(huì)對(duì)城市造成嚴(yán)重破壞。災(zāi)難發(fā)生后，該市的電力和運(yùn)輸系統(tǒng)將癱瘓，救援隊(duì)無(wú)法通過(guò)地面交通了解道路損壞或運(yùn)輸藥品。在這種情況下，無(wú)人機(jī)可能很有用。2017年，美國(guó)波多黎各遭受最嚴(yán)重的災(zāi)難，這次的災(zāi)難破壞或摧毀了島上大部分的蜂窩通信網(wǎng)絡(luò)，還阻塞并破壞島上的許多高速公路和道路，使得緊急服務(wù)地面車輛幾乎不可能規(guī)劃和導(dǎo)航他們的路線，數(shù)十個(gè)區(qū)域被隔離并且沒(méi)有通信，導(dǎo)致增加美國(guó)政府救援的難度。因此，設(shè)計(jì)無(wú)人機(jī)災(zāi)難響應(yīng)系統(tǒng)是當(dāng)務(wù)之急的事。

1模型處理

1.1找出五個(gè)地點(diǎn)

當(dāng)災(zāi)難發(fā)生時(shí)，無(wú)人機(jī)災(zāi)難響應(yīng)系統(tǒng)的任務(wù)是發(fā)送無(wú)人機(jī)將藥物運(yùn)送到指定地點(diǎn)并拍攝最大可能的道路區(qū)域。因此，有兩個(gè)主要因素需要考慮容器選址：第一，到達(dá)交貨地點(diǎn);第二，可以拍攝的道路范圍。根據(jù)緯度和經(jīng)度信息，根據(jù)這些條件，本文從波多黎各的地理信息中找到了五個(gè)醫(yī)療包裹遞送地點(diǎn)，這些地點(diǎn)分布在北海岸和東南沿海，五個(gè)醫(yī)療包裹遞送地點(diǎn)為加勒比醫(yī)療中心、HIMA醫(yī)院、帕維亞桑圖爾塞醫(yī)院、波多黎各兒童醫(yī)院和帕維亞阿雷西博醫(yī)院。

1.2聚類分析

為了提高同一個(gè)無(wú)人機(jī)的使用率，本文首先考慮每架飛機(jī)在送藥的同時(shí)拍攝道路的照片。為了減少無(wú)人機(jī)運(yùn)輸藥物的飛行時(shí)間而不影響射擊覆蓋范圍，本文將無(wú)人機(jī)劃分為兩個(gè)車隊(duì)，用于醫(yī)療包裹運(yùn)輸和道路網(wǎng)絡(luò)的視頻偵察。

由于無(wú)人機(jī)的最大飛行距離的限制，每個(gè)集裝箱所在位置的無(wú)人機(jī)可以飛行的范圍是有限的。因此，本文需要對(duì)這些位置進(jìn)行分類并劃分無(wú)人機(jī)可以到達(dá)的位置。相同的容器位置進(jìn)入同一區(qū)域。本文對(duì)五個(gè)地點(diǎn)的經(jīng)度和緯度轉(zhuǎn)換為大地坐標(biāo)，然后使用MATLAB將聚類好的結(jié)果繪制出來(lái)，得到圖1：

2模型的建立與求解

根據(jù)上述數(shù)據(jù)，確定好聚類區(qū)域的數(shù)量之后，還需要確定每個(gè)容器的具體位置。每個(gè)區(qū)域內(nèi)的集裝箱結(jié)算地點(diǎn)應(yīng)符合下列條件：

1）假設(shè)攜帶醫(yī)療包的無(wú)人機(jī)將在X，Y平面上以直線飛行。為了最小化飛行時(shí)間，來(lái)自同一容器的飛行距離之和應(yīng)該最短。

2）在每個(gè)區(qū)域，應(yīng)該沒(méi)有與容器的距離超過(guò)最大范圍的交貨地點(diǎn)

3）根據(jù)地理第一定律的原理，地理事物或?qū)傩栽诳臻g分布上相互關(guān)聯(lián)，彼此接近的事物關(guān)系更密切。因此，由一個(gè)點(diǎn)形成的區(qū)域中的容器位置應(yīng)盡可能接近其他位置。

綜上所述，本文構(gòu)建了以下聚類中心調(diào)整模型：

（1）當(dāng)集群中只有一個(gè)點(diǎn)時(shí)

當(dāng)單個(gè)點(diǎn)自己形成一個(gè)集群時(shí)，運(yùn)輸醫(yī)療包的解決方案變得非常簡(jiǎn)單。通過(guò)將容器直接放置在該位置可以實(shí)現(xiàn)最短的交付時(shí)間。然而，根據(jù)地理的第一定律，本文傾向于改善該區(qū)域與其他聚類區(qū)域之間的相關(guān)性，以及道路的連續(xù)性，因此它應(yīng)盡可能接近其他容器放置站點(diǎn)。

本文將該簇的樣本點(diǎn)與其它簇的樣本點(diǎn)連接起來(lái)，這些簇在一條直線上最接近它。距離直線上的采樣點(diǎn)的距離是最大飛行距離的點(diǎn)是樣本所在區(qū)域中的容器沉降點(diǎn)的最佳解。此時(shí)，不同集群之間的相關(guān)性最強(qiáng)。

根據(jù)假設(shè)，每個(gè)交界處都有：

此時(shí)，由一個(gè)點(diǎn)形成的聚類區(qū)域的范圍擴(kuò)展為圓形。以集裝箱放置點(diǎn)為中心，最大航程為半徑。

（2）當(dāng)群集中有兩個(gè)或多個(gè)點(diǎn)時(shí)

當(dāng)該地區(qū)有多個(gè)樣本點(diǎn)時(shí)，運(yùn)輸藥物的任務(wù)變得更加復(fù)雜。在這種情況下，本文希望無(wú)人機(jī)的交付時(shí)間盡可能短。所以需要找到一個(gè)與所有采樣點(diǎn)之間距離最小的點(diǎn)。受數(shù)字圖像處理中像素采樣方法的啟發(fā)，本文采用類似于雙線性模型的方法來(lái)計(jì)算，得到以下公式：

將聚類出來(lái)的結(jié)果替換為上述公式進(jìn)行迭代計(jì)算，得到的結(jié)果放在地圖上，得到圖2：

[1] ?孔祥元.大地測(cè)量學(xué)基礎(chǔ)[M].武漢大學(xué)出版社，2005.

[2] ?陳東艷，李冬梅，王樹(shù)忠.數(shù)學(xué)建模[M].科學(xué)出版社，2007.

[3] ?洪軍，余麗來(lái)，黃肇星，羅霞.模糊ISODATA聚類方法的設(shè)計(jì)[M].計(jì)算機(jī)與數(shù)字工程，2019.