基于貪婪算法的無人機(jī)運(yùn)輸方案研究

侯志浩 吉林大學(xué)數(shù)學(xué)學(xué)院

引言

2017 年，美國波多黎各領(lǐng)土遭遇了最嚴(yán)重的颶風(fēng)，對(duì)數(shù)百萬居民造成了巨大的不利影響。由于許多高速公路已經(jīng)中斷，所以各地居民迫切需要救生醫(yī)療用品。在這種情況下，非政府組織提出了“Dronego”項(xiàng)目，將無人機(jī)的3 個(gè)醫(yī)療包轉(zhuǎn)移到5 家選定的醫(yī)院。我們需要設(shè)計(jì)一個(gè)從已確定的各種候選旋翼無人機(jī)中選出的“DroneGo”機(jī)隊(duì)，以完成轉(zhuǎn)移醫(yī)療包和檢測道路狀況的任務(wù)。

1 初步分析

我們利用經(jīng)度作為橫坐標(biāo)，緯度作為Y 軸坐標(biāo)來獲得圖1，因此我們可以直觀地指出5 個(gè)位置的分布。當(dāng)然，實(shí)際位置位于拱形，而我們的坐標(biāo)圖是平坦的。事實(shí)上，我們的地圖是地球的一個(gè)橫截面，因此可能與直覺中的真實(shí)地圖有所不同，但距離，經(jīng)度和經(jīng)度都是準(zhǔn)確的值。

圖1 波多黎各的坐標(biāo)圖顯示了5 個(gè)目的地

首先，我們給出以下定義：

獨(dú)立需求（di）：相應(yīng)中心每天對(duì)醫(yī)療包的需求?？傂枨螅⊿）：每天醫(yī)療包5 個(gè)中心需求的總和。

隨后，我們將醫(yī)療中心的比例系數(shù)定義為：

在我們看來，這個(gè)定義是合理的，因?yàn)槊總€(gè)中心需要的包裹數(shù)量與其接納人口，各種醫(yī)療水平的指數(shù)正相關(guān)。該系數(shù)表明了相應(yīng)醫(yī)療中心在緊急情況下的重要性。然后我們定義了另一個(gè)公式來比較任何兩個(gè)災(zāi)害應(yīng)對(duì)方案。首先，我們給出以下定義：

然后得到：

2 分類討論

到目前為止，我們已經(jīng)確定了車隊(duì)，考慮到每個(gè)位置的最佳距離不是唯一的，我們將ISO 容器作為圓心，找到交叉區(qū)域后，覆蓋道路，人口和地形做出選擇。最佳位置是（見圖2 和圖3）

圖2 最佳位置

圖3 平面圖中的最佳位置

如圖3 所示，我們可以要求無人機(jī)可以從A 點(diǎn)出發(fā)，并在到達(dá)由A點(diǎn)和醫(yī)院確定的橢圓的任何點(diǎn)后到達(dá)醫(yī)院，如果可能的話，保持飛行剩余距離的一半到任何要求的地方，最后回到醫(yī)院。（如（b）所示）

球場并不總是直的，無人機(jī)可以在曲線路線上飛行，只要它們可以返回（醫(yī)院或集裝箱）至于VRD（視頻偵察無人機(jī)），可檢測區(qū)域是如上所述的偵察圈（SC）。

草圖僅顯示兩個(gè)不同的路線以給出簡單的符號(hào)。坐標(biāo)由經(jīng)度和緯度組成，這使得性能不像現(xiàn)實(shí)那么直觀。

3 結(jié)論

對(duì)于前往D1 的無人機(jī)，每架無人機(jī)B 最多可以滿足D1 的2 天要求，所以我們只需要在兩天內(nèi)發(fā)送一架無人機(jī)B.對(duì)于支持D2 的無人機(jī)，每架無人機(jī)F最多可以滿足一天的請(qǐng)求，并有足夠的空間來攜帶MED包，比例為202/112/211，因此我們可以在前兩天指定一架無人機(jī)F，然后發(fā)送其余要求的4 天（此外，無人機(jī)可以在一次飛行中提供D3 和D2，我們可以通過這種方式實(shí)現(xiàn)D1 和D2 的包裝管理）。在考慮D3 時(shí)，每架無人機(jī)B 最多可以滿足一天的要求。根據(jù)比例系數(shù)，我們只需在四天內(nèi)分配一架無人機(jī)。