基于遍歷算法的無(wú)人機(jī)救援模型研究

黃敬 王志堅(jiān)

摘 要：本文研究了救援響應(yīng)系統(tǒng)的開(kāi)發(fā)需面臨裝箱問(wèn)題。將無(wú)人機(jī)與自身攜帶的外部貨艙、運(yùn)輸集裝箱和醫(yī)療包組合放入標(biāo)準(zhǔn)ISO集裝箱內(nèi)，采用非線性規(guī)劃模型，根據(jù)三個(gè)港口的地理位置采用遍歷法找出三個(gè)港口到救援地點(diǎn)的最短路徑，并給出了無(wú)人機(jī)的有效載荷包裝方案、交付路線和時(shí)間表。確立飛行路徑最小化目標(biāo)，根據(jù)醫(yī)療包數(shù)量需求做出相應(yīng)約束，結(jié)合港口與無(wú)人機(jī)分配情況，使用遍歷方法求出救援最佳方案。

關(guān)鍵詞：非線性規(guī)劃；遍歷；禁忌；搜索

2017年，史上最嚴(yán)重颶風(fēng)襲擊美國(guó)波多黎各領(lǐng)土，使多黎各受到嚴(yán)重破壞，并造成多人因此死亡。非政府組織-HELP，Inc-設(shè)計(jì)了一種名為“DroneGo”的可移動(dòng)災(zāi)難響應(yīng)系統(tǒng)，本文則是為該系統(tǒng)提供救援方案來(lái)提高其響應(yīng)能力。同時(shí)根據(jù)各營(yíng)救點(diǎn)的需求以及救援路線和偵查路線為HELP，Inc制定營(yíng)救計(jì)劃。

針對(duì)以上問(wèn)題，雖然以前的學(xué)者都有研究過(guò)貨物裝配問(wèn)題及配送問(wèn)題，但本文的背景是救援，因此要綜合考慮救援效率以及救援成本的問(wèn)題，選出合適港口再制定救援路線。鑒于此，本文采用非線性規(guī)劃、遍歷方法、禁忌搜索等方法制定的救援計(jì)劃，比前人的研究更具有科學(xué)性和合理性。

1 問(wèn)題分析

ISO集裝箱?？扛劭诤螅峁o(wú)人機(jī)的有效載荷包裝方案，交付路線和時(shí)間表。首先，確立飛行路徑最小化的目標(biāo)，根據(jù)各個(gè)交貨地點(diǎn)對(duì)醫(yī)療包的數(shù)量需求。結(jié)合3個(gè)港口分配方案，賦予每個(gè)方案1-3臺(tái)無(wú)人機(jī)，計(jì)算每種分配方案的飛行總距離，運(yùn)用遍歷方法求出最佳方案。還要結(jié)合當(dāng)?shù)厝丝诜植?，?yōu)先配送傷亡人數(shù)多的地點(diǎn)。綜合考慮波多黎各的多方面因素，提出假設(shè)，得出配送路線，無(wú)人機(jī)的飛行速度，飛行路徑和飛行時(shí)間。第二步，為了提供無(wú)人機(jī)飛行計(jì)劃，使DroneGo車(chē)隊(duì)能夠使用車(chē)載攝像機(jī)評(píng)估主要高速公路和道路，從GoogleMap獲取波多黎各的主要道路的交叉點(diǎn)，定義這些交叉點(diǎn)為偵察對(duì)象，采用禁忌搜索算法得到最佳偵察路線。

2 符號(hào)意義

3 模型的建立

3.1 無(wú)人機(jī)有效載荷包裝配置、交付路線和時(shí)間表

若某個(gè)港口被選擇，就為該港口配置一臺(tái)H Tethered無(wú)人機(jī)。在考慮最短路徑時(shí)，還要結(jié)合當(dāng)?shù)厝丝诜植?，?yōu)先考慮配送傷亡人數(shù)多的地點(diǎn)。綜合考慮波多黎各的受災(zāi)情況和地理因素，得出配送路線。根據(jù)所選中的無(wú)人機(jī)的飛行速度和飛行路徑，獲得相應(yīng)的飛行時(shí)間。

3.2 評(píng)估主要高速公路和道路的搜索模型

為了提供無(wú)人機(jī)飛行計(jì)劃，使DroneGo車(chē)隊(duì)能夠使用車(chē)載攝像機(jī)評(píng)估主要的高速公路和道路。我們通過(guò)網(wǎng)絡(luò)數(shù)據(jù)獲取波多黎各的主要道路的交叉點(diǎn)，定義這些交叉點(diǎn)為無(wú)人機(jī)主要的偵察對(duì)象。采用禁忌搜索算法：

從一個(gè)初始可行解出發(fā)，選擇一系列的特定搜索方向作為試探，選擇實(shí)現(xiàn)讓特定的目標(biāo)函數(shù)值變化最多的移動(dòng)。建立Tabu表，對(duì)已經(jīng)優(yōu)化的過(guò)程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向，避免陷入局部最優(yōu)解。

第一步：令禁忌表H=空集，并選定一個(gè)初始解xnow；

第二步：滿足停止規(guī)則時(shí)，停止計(jì)算，輸出結(jié)果；否則，在xnow的鄰域N（xnow）中選擇不受禁忌的候選集Can_N（xnow）；在Can_N（xnow）中選一個(gè)評(píng)價(jià)值最佳的解xnext，xnow=xnext；更新歷史記錄H，保存f（xnow），重復(fù)step2；

第三步：在保存的眾多f中，挑選最?。ù螅┲底鳛榻?。

4 主要結(jié)果

當(dāng)?？緼recibo，F(xiàn)ajardo，San Juan這三個(gè)港口時(shí)，每個(gè)港口各配置1架無(wú)人機(jī)。結(jié)合交貨地點(diǎn)與港口的距離以及醫(yī)療包的需求，得出以下結(jié)果：

（1）港口Arecibo配置一臺(tái)E型無(wú)人機(jī)，負(fù)責(zé)的救援點(diǎn)：Hospital Pavia Arecibo，飛行路線是由Arecibo飛到Hospital Pavia Arecibo，飛行時(shí)間是5.43分鐘（設(shè)開(kāi)始飛行時(shí)間為0）。

（2）港口Fajardo配置一臺(tái)無(wú)人機(jī)E，負(fù)責(zé)救援點(diǎn)：Caribbean Medical Center，飛行路線為由Fajardo飛到Caribbean Medical Center，飛行時(shí)間2.41分鐘。

（3）港口San Juan配置一臺(tái)無(wú)人機(jī)B，負(fù)責(zé)救援點(diǎn)：Hospital HIMA、Hospital Pavia Santurce、Puerto Rico Children's Hospital。考慮到無(wú)人機(jī)B的配送能力以及為了縮短飛行時(shí)間，該無(wú)人機(jī)的配送方案為：無(wú)人機(jī)先攜帶救援點(diǎn)Hospital Pavia Santurce、Puerto Rico Children's Hospital所需的總救援物資，然后先飛往Hospital Pavia Santurce，飛行時(shí)間為10.45分鐘；再飛往Puerto Rico Children's Hospital，飛行時(shí)間為10.91分鐘，總飛行時(shí)間21.36分鐘。在無(wú)人機(jī)B離開(kāi)港口的同時(shí)，派出一輛營(yíng)救車(chē)帶著1個(gè)H Tethered平臺(tái)直接沿著救援點(diǎn)Hospital HIMA的方向駛?cè)?。?dāng)?shù)竭_(dá)無(wú)人機(jī)B可以把醫(yī)療包帶往的救援點(diǎn)Hospital HIMA時(shí)，并在能夠返回的范圍內(nèi)，等待無(wú)人機(jī)的到來(lái)，再進(jìn)行充電以及對(duì)醫(yī)療包進(jìn)行裝配，最后飛往Hospital HIMA，飛行時(shí)間為20分鐘（重新飛行時(shí)，開(kāi)始飛行時(shí)間為0）。通過(guò)禁忌搜索算法使用python求得的飛行最短路徑結(jié)果如下圖所示：

5 結(jié)語(yǔ)

在保證合理的情況下，運(yùn)用了遍歷算法，在假設(shè)條件下考慮了所有可能的情況，減少了誤差的產(chǎn)生。在確定最佳飛行路線時(shí)，綜合考慮了當(dāng)?shù)厝丝诿芗兀０魏褪┕さ攸c(diǎn)等因素，增加了模型的可靠性。

參考文獻(xiàn)：

[1]王帥.智能輪式機(jī)器人在養(yǎng)殖場(chǎng)中路徑規(guī)劃的研究[D].長(zhǎng)春大學(xué)，2017.

[2]張雪婷，陳英武，王琦，周浩，葛冰峰.整車(chē)物流的任務(wù)規(guī)劃模型和算法[J].中國(guó)管理科學(xué)，2015，23（S1）：624-629.

[3]蘇迎迎.果蔬農(nóng)產(chǎn)品物流運(yùn)輸路徑優(yōu)化研究[D].中國(guó)石油大學(xué)（華東），2016.

[4]江偉，秦翠蘭，康順光.整車(chē)物流運(yùn)輸計(jì)劃優(yōu)化模型研究[J].物流工程與管理，2014，36（11）：69-71.

作者簡(jiǎn)介：黃敬（1996-），男，廣東清城人，2016級(jí)本科生，研究方向：應(yīng)用統(tǒng)計(jì)學(xué)；王志堅(jiān)（1982-），江西余干人，博士，講師，研究方向：管理統(tǒng)計(jì)方法。