基于完善交通信息收集的UAV路徑規劃

王冬冬，何勝學，路 揚

（上海理工大學管理學院，上海 200093）

0 引言

實時、準確的交通信息是實施交通管理和控制的基礎。目前交通信息采集主要依賴于配備在固定位置的各類固定型交通信息檢測器，如固定線圈、紅外和視頻檢測器等。受經濟預算的限制，部分城市路段沒有布置固定型交通信息檢測器，無法獲取有效的交通信息。作為新時代的產物，無人機（Unmanned Aerial Vehicle，簡稱UAV）已經廣泛應用于交通信息收集、緊急救援、電力巡檢等各領域[1-4]。針對現有交通巡檢設備巡檢效率低、靈活性差等問題，提出使用無人機收集完善交通信息的方法[5]。然而，因受電池容量的限制，無人機的飛行時間有限，研究無人機的最佳飛行路徑就變得非常重要和有意義。

目前國內外對無人機路徑規劃方面的研究主要涉及算法研究，確定最佳的無人機數量以及使用有限數量的無人機巡視盡可能多的目標等。Kim等對用于交通道路巡查的無人機自動控制算法進行研究，通過UAV人工視覺系統（Artificial Vision Sys?tem，簡稱AVS）分析應急和異常交通情況，提供車輛跟蹤和速度檢測問題的解決方案[6]。Karakaya研究使用有限數量的無人機進行路徑優化，在考慮飛行范圍的基礎上盡可能多地覆蓋目標，并通過改進后的最大最小螞蟻算法（MAX-MIN Ant System，簡稱MMAS）進行求解[7]。Huang等提出一種多UAV協同路徑規劃方法,通過蟻群優化算法獲得UAV的初始路徑，并通過K-means方法獲得更多的可飛行路徑[8]。Avellar等在無人機數量有限的條件下，確定最佳的無人機數量，并給出使所有無人機覆蓋時間最短的方法[9]。Niu等提出使用無人機作為一種移動型交通檢測器對高速公路進行巡視，在總飛行時間最短的情況下盡可能多地巡視未布設固定型交通檢測器路段[10]。劉曉鋒等對無人機用于交通事件監測、交通信息采集進行了研究[11-13]。劉曉鋒等在無人機數量有限，不足以對所有目標進行偵察的前提下，建立了以巡航總距離最短且巡視目標盡可能多為目的的優化模型，并使用遺傳算法進行求解[11]。上述研究雖然對未布設固定型交通檢測器的路段進行信息收集，但沒有考慮到收集信息的準確性以及利用無人機資源的合理性。

本文擬通過時空網絡，建立以總飛行時間最短和最大單機飛行時間最短為目標的多目標模型，優化巡視路徑，并通過添加巡視次數和巡視時間間隔使收集到的信息更加符合實際需要。

1 時空網絡介紹

為細致刻畫無人機在路網巡視過程中的動態飛行特征，將動態的路網巡視過程轉化為靜態的無人機飛行軌跡，在此引入時空網絡作為研究框架[14-15]。將普通的原始路網拓展為時空路網后一般網絡規模都比較大，問題的求解有一定難度。考慮到本文主要研究UAV的路徑規劃問題，為降低求解難度，假設無人機的飛行速度固定，且不考慮無人機轉彎的時耗。圖1所示為原始路網到時空路網的具體轉化過程。首先，根據所有路段的行程時間確定時空路網的單位時長，確保所有路段的行程時間都是單位時長的整數倍。然后，根據完成任務所需的路段行程時間，將原始路網中所有節點復制n份。最后，進行時空路段的連接，依據原始路段添加相應的時空路段，即無人機從一個節點前往另一個節點的過程，在時空路網中用運行弧表示。

圖1中，線型1表示運行弧，代表無人機所有可能飛行的路徑；線型2連接位于相鄰時刻的同一節點，表示無人機在一個節點等待一個分段時長，即隨著時間的變化，無人機的空間位置未發生變化。有向實線（線型3）給出了一個無人機在時空路網中的運行軌跡：無人機p在t=0時刻從節點a出發開始巡邏任務，在下一時刻到達節點b，然后經過節點b在t=3時刻到達節點c，最后從節點c按照原路返回，在t=6時刻經節點b回到節點a。因本研究不考慮無人機的等待行為，故對于等待弧不予考慮。

圖1 一個簡單原始路網的時空網絡圖

2 模型構建

2.1 目標函數的建立

合理的飛行路徑應要求所有無人機在滿足飛行特性約束和巡視任務約束的前提下，總飛行代價最小。這里考慮的飛行代價包括無人機的總飛行時間和完成任務的時間跨度，其飛行代價分別用式（1）和式（2）表示為：

式（1）中：f1表示無人機的總飛行時間（min）；m,n表示節點號；Nm表示所有與節點m直接相連的節點的集合；P表示無人機的集合，p表示其中一架無人機；tm,n表示節點m到節點n所在道路的路段行程時間（min），有tm,n=tn,m，其中某一時刻用t表示；xpm,t,n是一個0-1變量，表示無人機p是否在t時刻進行從節點m到節點n的巡視。當xpm,t,n=1時，代表無人機p在t時刻進行從m點到n點的巡視；xpm,t,n=0則表明不進行。

式（2）中：f2表示最大單機飛行時間（min）；Z為新引入的參數，表示任意單架無人機的飛行時間上限（min），有

傳統求解多目標問題的方法主要通過對多個目標賦予不同的權重系數，然后通過線性組合將多目標問題轉化為單目標問題。這種方法便于通過調整權重系數得到想要的結果，也有利于問題的分析。在使用這種平均加權因子的方法計算模型之前，需要先用公式（3）和公式（4）對兩個目標進行歸一化處理：

最終的目標函數值計算如下：

式（3）～式（5）中：Tpperfect表示遍歷整個路網所需要的單機飛行時間（min）；表示遍歷整個路網所需要的總飛行時間（min）；g1,g2分別表示目標f1和目標f2歸一化后的值；w1,w2是無人機飛行代價的權重系數，分別表示無人機的總飛行時間最少和最大單機飛行時間最少的重要程度，且滿足w1+w2=1，w1,w2∈[0,1]；g表示多目標歸一化后考慮權重系數的和，g值越小越好。

2.2 約束條件的建立

為保證所收集交通信息的準確性和巡視路徑的合理性，模型需要考慮單路段的巡視次數、巡視時間間隔、節點流量守恒以及單架無人機的最大飛行時間約束。

首先，考慮單路段的巡視次數，要求每條路段(m,n)至少巡視Rm,n次，即：

式（6）中：M,N表示路網中所有路段起點和終點的集合；(M,N)表示所有路段的集合，且(m,n)∈(M,N)；Rm,n表示路段(m,n)的最少巡視次數（次）。

接著，考慮單路段的巡視時間間隔約束，要求單路段在最小巡視時間間隔內至多被巡視一次，即：

式（7）中：Δt表示單路段的最小巡視時間間隔（min）；T表示時空路網中所有時間的集合（min），有t∈T；(M,T,N)表示時空路網中所有時空路段的集合，即任意時刻所有路段的集合，有

隨后，考慮節點的流量守恒。在任意時刻，無人機進入某一結點的次數加（減）無人機從該結點加載進入（離開）時空路網的次數等于無人機離開該結點的次數。對應的流量守恒約束如下：

式（8）中：引入整數變量rp n,t，表示無人機p是否

在t時刻從節點n加載進入或離開時空路網。當時，表示無人機p在t時刻從節點n加載進入時空路網；當時，表示無人機p在t時刻從節點n離開時空路網；表示其他情況；(N,T)表示所有節點在時空路網中的集合，即任意時刻所有節點的集合，有

最后，每架無人機的巡視時間都應小于等于其最大續航時間，即：

式（9）中：Tp表示無人機p的最大飛行時間（min）。

若要求無人機在最短時間內完成全部的交通信息收集任務，還需添加如下約束：

以式（5）為目標、式（6）～式（10）為約束的多UAV交通信息收集路徑規劃模型是一個大規模線性整數規劃模型。求解這類問題的經典方法主要有分支定界法[16]和割平面法，也可以使用經典的啟發式方法，如遺傳算法[17]、模擬退火算法[18]和粒子群算法等求解模型。其中部分較成熟的算法已經在一些商業軟件當中得到應用，并且有著較好的求解效率。本文將使用商用軟件Lingo對模型進行求解。

3 算例分析和驗證

3.1 算例分析

圖2所示交通網絡由10個節點和36條路段組成。節點間的路段行程時間標注在路段上方，選擇1min作為一個單位時長。使用2架無人機對該網絡進行信息收集。無人機在起飛前分別位于節點3和節點8的基站位置，完成巡視任務后分別回到起飛的基站位置。圖中（1,3），（2,5），（4,7），（6,7）所在路段不能收集到有效的交通信息，需要使用無人機對以上各路段至少巡視兩次，且巡視時間間隔應大于上述路段最大行程時間的2倍。

圖2 路網示意圖

首先根據圖2在Lingo中建立原始路網，并根據圖1所示的方法在原始路網的基礎上增加一個時間維度，完成原始路網到時空路網的轉化。然后根據上文提到的目標和任務約束建立目標函數和約束條件，要求兩架無人機分別從節點3和節點8起飛，巡視結束后回到起飛位置。運算程序，得到所有xpm,t,n=1的量。對同一架無人機p而言，將所有的xpm,t,n=1按照時間順序排列，即可得到無人機p在時空網絡中的運行軌跡。最后，將無人機在時空網絡中所經過的時空節點按順序對應到原始節點，得到的原始節點順序就是無人機的實際飛行路徑。

下面對算例進行運算。首先給予雙目標相等的權重，令w1=w2=0.5，得到無人機在時空路網中的具體運行軌跡，如表1所示。

表1 時空路網運行軌跡

由表1可知，2架無人機分別在t=0時刻從節點3和節點8起飛，并分別在14min和23min回到基站。無人機的總飛行時間為37min，最大單機飛行時間為23min。兩架無人機的單機飛行時間差距懸殊，沒有做到合理分配續航時間。因此需要進一步增大w2，要求整個交通信息收集任務在最短的時間內完成。依次改變w1和w2的值，得到2架無人機的飛行時間以及目標函數值的大小，如表2所示。其中UAV-1和UAV-2分別表示兩架無人機的飛行時間，g表示雙目標歸一化后考慮權重系數的和。

表2 情景分析

分析表2中的結果，當w1≤0.4時，2架無人機的總飛行時間變為41min，最大單機飛行時間為21min，即整個飛行任務最短在21min內完成。對比表1，無人機的總飛行時間增加了9.76%，最大單機飛行時間減少了8.70%。隨著權重w1的增加，第一目標所占的比重增大，無人機的總飛行時間逐漸縮短，最大單機飛行時間逐漸延長。當w1所占比重足夠大時，系統僅使用1架無人機進行巡視，對應的總飛行時間最短，單架無人機的飛行時間為34min。如果僅考慮總目標函數最小，使用1架無人機的巡視效果最優，對應的飛行路徑為3-1-2-5-4-6-7-4-6-7-4-5-2-1-3。通過Lingo軟件，該算例的運算時間小于10s。

3.2 算例驗證

為進一步驗證本模型和方法的有效性，這里選擇Sioux-Fall城市路網進行驗證，如圖3所示。Sioux-Fall城市路網被廣泛應用于交通領域，該路網由24個節點和76條路段組成，基站位于節點4和節點19。有2架無人機分別從基站起飛，巡視結束后回到起飛位置，其中（4,5），（7,8），（9,14），（10,11），（11,16），（19,20）需要巡視2次，且巡視時間間隔不低于6 min。

給予雙目標相等的權重，重復上述方法，在Lingo中建立時空路網，得到無人機的飛行路徑（UAV-1：4-5-7-8-9-14-13-15-18-17-20-19-16-11-10-3-4；UAV-2：19-16-11-10-3-4-5-7-8-9-14-13-12-17-20-19）。2架無人機在t=0時刻分別從節點4和節點19起飛，在t=28時刻同時回到起飛位置，整個任務在28min內完成。通過Lin?go軟件，該算例的運算時間不超過30min。

圖3 Sioux-Fall城市路網

Lingo軟件的運算時間直接與時空網絡的規模相關，它求解線性規劃問題采用的是一種精確搜索方法，因此計算時間會隨著時空網絡規模的增大而呈指數增加。對于由24個節點、76條路段組成的Sioux-Fall城市路網，依然能夠在30min內得到最優解，因此本文提出的模型和方法可以解決無人機在大規模路網的路徑規劃問題。

4 結語

針對部分路段由于固定型交通信息檢測器布設不足或因后期損毀導致無法獲取有效交通信息的問題，提出使用無人機對該路段進行巡視以完善交通信息的方法。為保證收集信息的準確性，要求無人機多次巡視該路段，并且一段時間內至多巡視一次。由于時空網絡的時間拓撲特性能夠較好地表達巡視次數和時間間隔約束問題，本文以時空網絡作為研究框架，建立了以總飛行時間最短和最大單機飛行時間最短為目標的多目標模型。算例分析表明，本文所建模型能夠求出最佳的無人機數量和相應的巡視路徑，證實了模型的有效性。不過，本文假設無人機飛行速度固定，沒有考慮無人機轉彎時的加速度變化和時間消耗，接下來將進一步研究考慮航跡的UAV路徑規劃問題。