無人機救災中的多目標物資裝配和投放點定位研究

覃炳發(fā) 王東 金焱 蔣俊林

摘 ? 要：文章以2019美國大學生數(shù)學建模B題為例，對無人機救災中的多目標物資裝配和投放定位進行了研究。首先，以無人機數(shù)量盡可能少、醫(yī)療包的數(shù)量盡可能多、無人機的飛行距離盡可能遠和集裝箱利用率盡可能高為目的，建立了多目標整數(shù)規(guī)劃模型。在至少滿足波多黎各一個月的醫(yī)療包需求以及其他約束條件下，為3個集裝箱提供了相應的打包配置。其次，使用空間多層次疊加算法來確定集裝箱的最佳投放位置。通過熵值法來給土壤類別、水文、坡度、道路網(wǎng)絡(luò)、居民分布、醫(yī)療中心和重災地區(qū)等影響集裝箱投放位置的因素進行賦權(quán)。利用ArcGIS軟件對各因素進行加權(quán)疊加后，篩選出灰度大于6.5的地區(qū)，再通過無人機的飛行距離確定集裝箱最佳的放置區(qū)域。最后，根據(jù)道路節(jié)點確定3個集裝箱的經(jīng)緯度分別是（18.267 313，﹣65.875 327），（18.279 049，﹣66.141 528），（18.315 155，﹣66.579 81）。

關(guān)鍵詞：多目標整數(shù)規(guī)劃;打包配置;空間多層次疊加算法;熵值法;投放位置

1 ? ?3個ISO貨運集裝箱的投放位置

兩年前，美國領(lǐng)土波多黎各遭受到了有史以來最嚴重的颶風襲擊，對波多黎各造成了嚴重的損壞，導致了無數(shù)人傷亡。這次颶風伴隨著狂風暴雨，幾乎摧毀了波多黎各所有的電力系統(tǒng)和通信系統(tǒng)。不僅如此，這次災害還引起了洪水的泛濫，阻塞和損壞了島上許多的公路，導致了無法為應急服務車輛規(guī)劃路線。波多黎各的醫(yī)療用品、救生設(shè)備以及醫(yī)療診所都十分緊張，非政府組織救援行動也在進一步展開。因此，設(shè)計合理的救援物資打包方案以及集裝箱投放點對救援行動有著巨大的促進作用。

目前，國內(nèi)在與救援物資裝配問題相似的裝箱問題上已經(jīng)有了大量的研究[1-2]，對于不同情形和條件下的裝箱問題，已經(jīng)有學者研究并給出了許多可行的方案[3-4]。

與單純研究裝箱問題不同的是，本文結(jié)合2019年美國大學生數(shù)學建模競賽B題中的場景，在問題中提供的現(xiàn)有無人機類型和數(shù)量、醫(yī)療包類型和數(shù)量以及無人機貨艙類型和數(shù)量的前提下，以節(jié)約成本、滿足救援需求為主要目的，建立一個多目標的線性規(guī)劃模型，為多達3個ISO貨運集裝箱設(shè)計相關(guān)的包裝配置。此外，為了使得無人機能夠進行醫(yī)療用品的交付和道路網(wǎng)絡(luò)的視頻偵察，本文充分考慮波多黎各水文、土壤類別、坡度、居民分布、醫(yī)療中心、道路網(wǎng)絡(luò)以及重災害地區(qū)等多個因素，使用空間多層疊加分析算法在ArcGIS軟件中綜合這些因素對地圖信息進行分析，最終得出3個集裝箱在波多黎各的最佳投放位置[5]。

2 ? ?貨運集裝箱包裝配置模型

2.1 ?模型假設(shè)

結(jié)合問題中的實際情況，本文提出如下假設(shè)：（1）假設(shè)無人機、貨艙和醫(yī)療包可以在集裝箱內(nèi)任意放置。（2）假設(shè)無人機貨艙的厚度可以忽略不計，即貨艙容量就是貨艙的實際大小。（3）假設(shè)每一臺無人機對應一個貨艙。

2.2 ?符號說明

目標函數(shù)式（1）表示實現(xiàn)成本最小化、救援供給量最大化和視頻偵察范圍最大化要求，權(quán)重系數(shù)α，β，γ為常數(shù)。約束條件式（2）保證了每個集裝箱內(nèi)至少具有一輛具有視頻功能的無人機。約束條件式（3）對醫(yī)療包總重量需要小于所有無人機的載重量進行約束。約束條件式（4）對集裝箱容量進行約束，由于考慮到醫(yī)療包和無人機的形狀問題，所以約束醫(yī)療包、無人機和無人機貨艙的總體積不能超過集裝箱最大體積的90%，確保醫(yī)療包、無人機和無人機貨艙能按照某一種擺放方式裝入集裝箱內(nèi)。約束條件式（5），（6）和（7）分別對MED1，MED2和MED3醫(yī)療包數(shù)量進行約束，確保醫(yī)療包數(shù)量能夠滿足波多黎各至少一個月的需求量。因為每一天所需3種醫(yī)療包的比例為7∶2∶4，所以3個集裝箱每一種醫(yī)療包的總數(shù)量也應該滿足7∶2∶4的比例（用約束條件式（8）和（9）表示），目的是使醫(yī)療包的利用率達到最高。

2.4 ?模型求解

針對上述模型，分別取權(quán)重系數(shù) α=0.5，β=0.3，γ=0.2，將各項參數(shù)帶入Matlab中的intlinprog函數(shù)，程序運行375 s，求解結(jié)果如表1所示。

從表1可以看出，3個集裝箱裝配飛機的方案基本都是差不多的，都主要偏向于裝載B類和C類無人機。B類飛機的飛行速度、最遠飛行距離和飛行時間都是最優(yōu)的，而C類無人機在最大有效負載、速度和飛行時間上的性能都是處于中上水平的，B，C類無人機都可以很大程度地加大援助的效率。此外，每個集裝箱還裝載了少數(shù)幾架F型無人機，雖然沒有視頻功能，但是它的飛行速度是最快的，可以以更快的速度將救援物資送到指定地點。

3 ? ?集裝箱投放點定位的數(shù)學模型

3.1 ?問題分析

在分析選址之前，需要對每一種無人機滿載時的最短飛行時間進行計算。題目中只給出了空載時的飛行時間，假設(shè)無人在滿載的時候飛行時間會下降10%，可以得出計算滿載時候各種無人機的最短飛行時間的計算公式如下：

Ti=（1-0.1）ti

其中，ti表示第i種無人機空載時的飛行時間，Ti表示第i種無人機滿載時的飛行時間。根據(jù)此飛行時間可以計算無人機在最壞情況下的飛行距離，從而對集裝箱投放點進行約束。

通過查閱美國地質(zhì)勘探局發(fā)布的國家地質(zhì)圖庫[6]，再結(jié)合題目所給地圖，得到了波多黎各的交通、水文、坡度、土壤類別、居民分布和5個醫(yī)療中心的柵格數(shù)據(jù)，并描出重災區(qū)域的大致范圍。根據(jù)以上基礎(chǔ)數(shù)據(jù)，通過ArcGIS采用空間多層疊加分析算法對地圖信息進行分析。

3.2 ?模型構(gòu)建與投放點位置標定

結(jié)合實際救援情況，選擇的集裝箱投放點應該滿足如下條件：無人機能夠在集裝箱和醫(yī)療點之間往返、遠離重災區(qū)和低洼地區(qū)以及臨近交通網(wǎng)密集地區(qū)等。

根據(jù)以上要求，在ArcGIS的ModelBuilder里創(chuàng)建了集裝箱選址分析模型，模型如圖1所示。

首先，通過高程圖生成坡度數(shù)據(jù)。為了得到集裝箱安放的位置與因素之間的遠近關(guān)系，需要提取水文、居民分布、5個醫(yī)療中心、道路交通和重災地區(qū)的直線距離數(shù)據(jù)集。在用歐氏距離提取完距離數(shù)據(jù)集后，需要根據(jù)偏好值、敏感度值、優(yōu)先級值或者某些類似的條件指定給各因素分等級，方便評價。為坡的坡度平均劃分為5個級別，為水文、道路、居民分布、醫(yī)療中心、重災地區(qū)的距離平均劃分為10個級別。分級等級越高，越適宜安放集裝箱。波多黎各在颶風過后，各地出現(xiàn)洪水的情況下，不宜靠近水文，且應遠離。因此，到水文的距離越遠，分數(shù)越高。重災地區(qū)也是一樣的，需要遠離，避免二次災害，也是越遠越好。坡度的等級劃分，也與洪水相關(guān)，太平容易漫，太陡不易放，選擇偏緩的坡度為最高級。對于醫(yī)療中心的距離，考慮到勘探路面的需求，勘探方位應盡可能地大，選擇適中的距離為最佳，保證能送達藥品的同時，勘察面積可以最大化。道路和居民分布應該選擇越近越好，方便物資的運輸和救援。對土壤類別進行重分類，刪去沼澤、脆弱的土質(zhì)等地，對其余的土質(zhì)重新賦值。

為了得到最佳選址區(qū)域，需要對每個區(qū)域進行疊加。地理信息以矢量或柵格的數(shù)據(jù)層面存在，可以通過疊加數(shù)層，得到新的一個數(shù)層，它將擁有原來兩層或多層要素所具有的屬性。為更直觀體現(xiàn)不同要素對選址的影響，選用權(quán)重對要素的重要性進行區(qū)分，重要的因素賦予較大的權(quán)重值。在對數(shù)據(jù)層面做疊加分析時，在波多黎各選取5個采樣點，根據(jù)采樣的各項指標數(shù)據(jù)使用熵值法對各因素進行賦權(quán)。通過熵值法最終計算各指標權(quán)重如表2所示。

在輸入權(quán)重后，得到了最終的選址圖，圖層的分值為8。為更好篩選集裝箱放置地點，提取灰度大于6.5的柵格數(shù)據(jù)，并將柵格數(shù)據(jù)矢量化。導入題目所給的地圖作為底圖，可以看出地圖明顯地被劃分為3塊區(qū)域，如圖2所示。

通過下載波多黎各的道路網(wǎng)絡(luò)圖，找尋重要的交通結(jié)點，選取交通結(jié)點附近的地址，作為集裝箱放置的主要地點。結(jié)合每個集裝箱中無人機的飛行距離，最終確定3個集裝箱的投放位置，如表3所示。

4 ? ?結(jié)語

本文波多黎各受到颶風襲擊的事件為背景，根據(jù)問題中提供的各項數(shù)據(jù)，建立了多目標整數(shù)規(guī)劃模型，為無人機救災設(shè)計了3個集裝箱的打包配置。結(jié)合每個集裝箱中無人機的配置以及對投放地點的約束，在ArcGIS軟件中利用空間多層次疊加分析算法對地圖數(shù)據(jù)進行分析，最終精確地確定了3個集裝箱的投放地點。最終確定的集裝箱投放地點不僅能夠使得正常交付醫(yī)療包到醫(yī)療點，還能夠在交付過程中用視頻偵測到更多的道路數(shù)據(jù)。

[參考文獻]

[1]王悅宸，蘇醒，賈熹濱，等.應急救援中基于線性規(guī)劃的多目標多資源分配模型[J].中國科學技術(shù)大學學報，2018（6）：458-466.

[2]崔會芬，許佳瑜，朱鴻國，等.基于改進遺傳算法的三維單箱裝箱問題研究[J].工業(yè)工程與管理，2018（1）：86-89.

[3]那日薩，崔雪蓮，韓琪瑋.基于實際約束的三維裝箱問題優(yōu)化算法[J].工業(yè)工程與管理，2017（4）：10-16.

[4]張雅艦，劉勇，謝松江.一種求解裝箱問題的改進遺傳算法[J].控制工程，2016（3）：327-331.

[5]鐘石泉，王雪蓮.多箱型三維裝箱問題及其優(yōu)化研究[J].計算機工程與應用，2009（22）：197-199.

[6]美國地質(zhì)勘探局.國家地質(zhì)圖庫[EB/OL].（2018-12-12）[2019-08-20].https：//ngmdb.usgs.gov/Prodesc/proddesc_15561.htm.