無(wú)人機(jī)救災(zāi)中的多目標(biāo)物資裝配和投放點(diǎn)定位研究

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

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

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

1 ? ?3個(gè)ISO貨運(yùn)集裝箱的投放位置

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

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

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

2 ? ?貨運(yùn)集裝箱包裝配置模型

2.1 ?模型假設(shè)

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

2.2 ?符號(hào)說(shuō)明

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

2.4 ?模型求解

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

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

3 ? ?集裝箱投放點(diǎn)定位的數(shù)學(xué)模型

3.1 ?問題分析

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

Ti=（1-0.1）ti

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

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

3.2 ?模型構(gòu)建與投放點(diǎn)位置標(biāo)定

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

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

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

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

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

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

4 ? ?結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

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

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

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