王冬冬，何勝學(xué)，路 揚

（上海理工大學(xué) 管理學(xué)院，上海 200093）

實時、可靠、準(zhǔn)確的交通信息是進行有效交通管理和控制的基礎(chǔ)。目前的交通信息采集主要依賴配備在固定位置的各類固定型交通檢測器，主要包括線圈檢測器、紅外線檢測器和視頻檢測器（AVI）等。但由于受到建設(shè)和維修預(yù)算的限制，固定型交通檢測器布設(shè)數(shù)量有限，不能在時間和空間上為道路網(wǎng)絡(luò)提供完整的交通信息。針對上述問題，本文建立考慮單路段巡視次數(shù)和限制同一路段多次巡視的時間間隔的無人機路網(wǎng)巡視的路徑優(yōu)化模型，以此解決路網(wǎng)巡視的路徑優(yōu)化問題。

無人駕駛飛機簡稱無人機（unmanned aerial vehicle，UAV），最早被應(yīng)用于軍事領(lǐng)域，執(zhí)行戰(zhàn)場偵察、跟蹤定位、精確制導(dǎo)等任務(wù)[1]。近年來無人機在民用方面的應(yīng)用也逐漸擴展，包括交通檢測、天氣監(jiān)測、災(zāi)害響應(yīng)及地質(zhì)調(diào)查等[2]。南京和蘇州相繼出現(xiàn)了使用無人機進行輸電線路巡視和交通路網(wǎng)巡視的案例，效果顯著。使用無人機進行交通巡視不受路面交通擁堵的影響，而且成本低、機動性強?？纱钶d感應(yīng)裝置如傳感器、攝像機、照相機等，在一定的高度以俯視的角度獲得連續(xù)完整的交通信息，并實時地將拍攝畫面?zhèn)魉偷街笓]中心，方便對城市交通的實時監(jiān)控?？梢灶A(yù)見，在不久的將來會有越來越多的地方選擇使用無人機進行交通巡視，而使用無人機進行交通巡視需要一套高效合理的飛行計劃，因此，在滿足一系列任務(wù)約束的前提下確定無人機的最佳飛行路徑就變得非常重要和有意義。

無人機的路徑規(guī)劃是交通檢測的重要部分，是指無人機在給定約束條件下從指定的出發(fā)點飛向指定的目的地，完成預(yù)設(shè)的觀測任務(wù)且飛行距離最短[3]。無人機的路徑規(guī)劃研究主要包括：以總飛行時間最短和在最短時間內(nèi)完成所有任務(wù)的多目標(biāo)研究；帶有時間窗約束的多無人機協(xié)同路徑規(guī)劃研究；確定最佳的無人機數(shù)量的多無人機路徑規(guī)劃研究等。文獻[4-6]對無人機用于交通事件監(jiān)測、交通信息采集方面進行了相應(yīng)的研究。在無人機數(shù)量有限，不足以對所有目標(biāo)進行偵察的前提下，建立了以巡航總距離最短且巡視目標(biāo)盡可能多為目標(biāo)的優(yōu)化模型，并使用遺傳算法進行求解[5]。Kim 等[7]對用于交通道路巡視的無人機自動控制算法進行研究，通過UAV 人工視覺系統(tǒng)（AVS）分析應(yīng)急和異常交通情況，提供車輛跟蹤和速度檢測問題的解決方案。Huang 等[8]提出了一種多UAV 協(xié)同路徑規(guī)劃方法，通過蟻群優(yōu)化算法獲得UAV 的初始路徑，并通過K-means 平滑方法獲得更多的可飛行路徑。Habib 等[9]對多起訖點的無人機路徑優(yōu)化問題進行了研究，對每架無人機巡視目標(biāo)的數(shù)量進行約束，并考慮了無人機因故障導(dǎo)致數(shù)量減少，路徑重規(guī)劃的情況。Avellar 等[10]介紹了給定有限數(shù)量的無人機，確定最佳的無人機數(shù)量，以及使所有無人機的覆蓋時間最短的解決方法。Karakaya[11]研究了使用有限數(shù)量的無人機進行路徑優(yōu)化，在考慮它們飛行范圍的基礎(chǔ)上盡可能多地覆蓋目標(biāo)，并通過修改后的最大最小螞蟻算法（MMAS）進行求解。

國內(nèi)外對無人機路徑規(guī)劃方面的研究多集中于處理特定任務(wù)點對之間無人機路徑最優(yōu)選擇問題。在最短的時間內(nèi)滿足一定任務(wù)約束條件下巡視完所有目標(biāo)點，或針對無人機的任務(wù)分配，確定最佳的無人機數(shù)量。上述研究均以節(jié)點為研究對象，沒有考慮節(jié)點之間是否存在道路連接。而使用無人機進行路網(wǎng)巡視時，需要巡視具體路段。Niu 等[12]提出在總巡航時間最短的情況下應(yīng)盡可能多地巡測未設(shè)置固定型交通檢測器的路段。Niu 等[12]以路段作為研究對象，卻沒有考慮路段的巡視次數(shù)問題。根據(jù)現(xiàn)實需要，無人機路網(wǎng)巡視需要沿道路巡視，巡視區(qū)域內(nèi)的所有路段應(yīng)至少被巡視一次，重要路段可能需要多次巡視。同時還要考慮適當(dāng)?shù)难惨晻r間間隔，避免無人機之間的相互碰撞和短時間內(nèi)對同一路段的重復(fù)巡視。為了減少冗余飛行，使無人機的巡視路線更加合理，可以適當(dāng)增加無人機的基站數(shù)量，因此，本文研究考慮多基站的多無人機路網(wǎng)巡視問題。

1 基于時空網(wǎng)絡(luò)的問題描述

本文研究的無人機路徑規(guī)劃問題要求遍歷所有路段，重要路段多次巡視，類似于連續(xù)域范圍內(nèi)的遍歷式路徑規(guī)劃問題。解決此類問題需要先進行環(huán)境建模，最常用的方法有柵格法、模板模型法等，本文考慮使用時空網(wǎng)絡(luò)[13-15]的方法進行建模。時空網(wǎng)絡(luò)不僅能夠較好地表達本文考慮的時間約束問題，而且能夠?qū)討B(tài)的路徑規(guī)劃轉(zhuǎn)化為靜態(tài)路徑規(guī)劃，實現(xiàn)對無人機動態(tài)時空軌跡的細(xì)致刻畫。

圖1 給出了簡單原始路網(wǎng)的時空網(wǎng)絡(luò)圖。原始的實際路網(wǎng)在圖的上方，由3 個節(jié)點組成，對應(yīng)的行程時間標(biāo)示在路段上方。由于無人機飛行速度固定，因此，同一路段的雙向行程時間相同。在轉(zhuǎn)化為時空路網(wǎng)前，首先需要根據(jù)所有路段的行程時間來確定時空路網(wǎng)中的單位時長，確保所有路段的行程時間都是單位時長的整數(shù)倍。其次根據(jù)完成任務(wù)所需的路段行程時間確定劃分的時段總數(shù)n。然后根據(jù)劃分的時段對原始路網(wǎng)中所有的節(jié)點復(fù)制 n份，并依據(jù)原始路段添加對應(yīng)時空 路段，完成原始路網(wǎng)到時空路網(wǎng)的轉(zhuǎn)換。

圖 1 簡單原始路網(wǎng)的時空網(wǎng)絡(luò)圖Fig.1 A space-time network diagram for simple road network

將無人機的巡邏行為，即無人機從一個節(jié)點前往另一個節(jié)點的過程，在時空路網(wǎng)中用運行弧表示。圖1 中運行弧表示為線型1，代表無人機所有可能飛行的路線。位于相鄰時刻的同一節(jié)點之間用線型2 連接，表示無人機在一個節(jié)點位置等待一個分段時長，即在一個單位時間內(nèi)，無人機的空間位置未發(fā)生變化。因本文研究不考慮無人機的等待行為，因此，此處的等待弧后文不予考慮。在圖1 中用有向?qū)嵕€（線型3）給出了一個無人機在時空路網(wǎng)中的運行軌跡。無人機 p在時刻t=0從節(jié)點a出 發(fā)開始巡邏任務(wù)，經(jīng)一個時間單位到達節(jié)點b，然后經(jīng)過節(jié)點 b在t=3時到達了節(jié)點c，最后從節(jié)點c 按照原路返回，在 t =6 時 經(jīng)節(jié)點 b回到節(jié)點a。

考慮到沿道路飛行的無人機需要針對地面雙向交通的某一特定方向進行跟蹤拍攝，所以，一條雙向路段的無人機巡視的路線應(yīng)設(shè)定為雙向，這與以往的單向路徑規(guī)劃不同，建模和求解的復(fù)雜度都大大提高。無人機的運動規(guī)劃包括路徑規(guī)劃和航跡規(guī)劃。本文主要研究無人機的路徑規(guī)劃問題，因此，假設(shè)無人機飛行速度固定，同時無人機改變方向時的時間消耗以及無人機起飛和降落時的加、減速時間也已經(jīng)包含在相應(yīng)路段的飛行時間中。無人機路徑規(guī)劃模型是為了使所有的無人機從指定的基站出發(fā)完成規(guī)定巡邏任務(wù)后返回到基站，且所用時間總和最短。

2 無人機路徑規(guī)劃模型

2.1 參變量說明

由于時空路網(wǎng)在二維平面空間的基礎(chǔ)上增加了一個時間維度，因此，對于實際的節(jié)點以及路段也需要在原本的表達方法上相應(yīng)地增加一個時間坐標(biāo)。原始路網(wǎng)中一維的節(jié)點用 n表示，而在時空路網(wǎng)中用二維的 ( n,t)表示。在原始路網(wǎng)中二維的實際路段(m,n)在時空路網(wǎng)中用三維的(m,t,n)表示，其中， m，n為路段起、訖節(jié)點， t為從節(jié)點 m出發(fā)的時間。同時引入了2 個整數(shù)變量 Xmp,t,n和rnp,t。Xmp,t,n表示無人機 p是否在 t時刻進行從節(jié)點 m到節(jié)點 n的巡視。當(dāng)Xmp,t,n=1時，代表無人機 p在t時刻進行從m點到 n點的巡視；否則，Xmp,t,n=0。對一架無人機p而言，將路網(wǎng)中所有的Xmp,t,n=1的時空路段按照時間順序取出連接，即可得到無人機 p在時空路網(wǎng)中的運行軌跡。 rnp,t表 示無人機 p是否在t時刻從節(jié)點 n加載進入或離開時空路網(wǎng)。當(dāng) rnp,t=1 時，表示無人機 p在t時刻從節(jié)點 n加載進入時空路網(wǎng)；當(dāng)rnp,t=-1時，表示無人機 p在t時刻從節(jié)點 n離開時空路網(wǎng)；在其他情況時，rnp,t=0。

其他主要參變量簡介如下：

N代表路網(wǎng)中所有節(jié)點的集合，有 n∈N ；

P代表所有無人機的集合，有p ∈P ；

T 代表時空路網(wǎng)中的時間集合，其中， t∈T ；

(N,T)代表時空路網(wǎng)中的節(jié)點集合，是一個節(jié)點以及時間組成的二維集合，集合中元素的表達方式為 ( n,t)；

tm,n代 表節(jié)點 m到節(jié)點 n之間的路段行程時間，由于無人機飛行速度固定，因此， tm,n=tn,m；

(M,T,N)代表時空路網(wǎng)中的路段集合，其中的時空路段(m,t,n)由2 個時空節(jié)點(m,t)和(n,t+tm,n)連接而成，表示在t 時刻從節(jié)點 m出發(fā)前往節(jié)點n；

Δt代表某一路段被多次巡視的最小時間間隔；

Nm代表與節(jié)點 m相鄰的所有節(jié)點的集合，其中Nm?N；

Rm,n代表路段 ( m,n)的最少巡視次數(shù)；

Mo代表路網(wǎng)中無人機發(fā)射基站的集合，其中，mo ∈Mo；

Nd代表路網(wǎng)中無人機降落基站的集合，其中，nd∈Nd；

t0代表多架無人機在同一基站起降的最少時間間隔；

Tp代表無人機 p的最大巡航時間。

2.2 目標(biāo)函數(shù)的建立

使用多無人機協(xié)同對目標(biāo)路網(wǎng)進行路網(wǎng)巡視，應(yīng)使所有無人機在滿足飛行特性約束和巡視任務(wù)約束的前提下總飛行代價最小。這里考慮的飛行代價包括無人機的總飛行時間f1以及完成任務(wù)的時間跨度。其中，無人機從開始起飛到任務(wù)完成所需要的總時間代價為所有無人機的飛行時間之和，可表示為

所有的無人機進行協(xié)同路徑規(guī)劃，需要考慮無人機在最短的時間內(nèi)完成所有的巡視任務(wù)。這里通過限制單機的最大巡航時間來實現(xiàn)該目標(biāo)，f2為完成任務(wù)需要的最大單機時間。引入一個參數(shù)Z ，其中，， 只要令Z的值最小即可。對應(yīng)的代價函數(shù)可表示為

2.3 約束條件的建立

首先考慮巡視次數(shù)約束。使用無人機進行路網(wǎng)巡視時，根據(jù)實際狀況，一般需要對路網(wǎng)中的每條路段至少巡視一次，一些事故頻發(fā)的重點路段需進行多次巡視，相關(guān)約束為

其次考慮同路段相鄰巡視的時間間隔約束。當(dāng)要求對重點路段多次巡視時，無人機可能會在短時間內(nèi)對一條路段往返重復(fù)巡視，而在后面的巡視中“忽略”此路段。這種巡視無疑是不合理的，因此，添加巡視時間間隔約束，要求每條路段在一段時間內(nèi)只能被巡視一次，具體形式為

接著考慮節(jié)點流量守恒。時空網(wǎng)絡(luò)細(xì)致刻畫了無人機在原始路網(wǎng)中的飛行軌跡，將動態(tài)的原始路網(wǎng)路徑規(guī)劃轉(zhuǎn)化為靜態(tài)的時空路網(wǎng)路徑規(guī)劃。為了在原始路網(wǎng)中得到連續(xù)的飛行路徑，需要考慮時空路網(wǎng)中節(jié)點的流量守恒，即在任意一個時段，無人機進入某一節(jié)點的次數(shù)加（減）無人機從該節(jié)點加載進入（離開）時空路網(wǎng)的次數(shù)等于無人機離開該節(jié)點的次數(shù)，對應(yīng)的流量守恒約束為

為了避免無人機之間的相互碰撞和保證基站的有效運作，還需要考慮在一段時間內(nèi)只允許一架無人機在同一基站起飛或降落的約束為

單架無人機的飛行時間受到其最大續(xù)航能力的影響，因此，每架無人機的巡視時間應(yīng)小于其最大續(xù)航時間，相關(guān)約束為

如果優(yōu)化的目標(biāo)是在最短時間內(nèi)完成所有巡視任務(wù)，則還需考慮的約束為

以式（1）和式（2）為優(yōu)化目標(biāo)，式（3）～（9）為約束的多UAV 交通網(wǎng)絡(luò)巡視模型是一個線性整數(shù)規(guī)劃模型，該類問題可以使用一些經(jīng)典的算法求解，如分支定界法和割平面法，也可以使用一些經(jīng)典啟發(fā)式算法，如遺傳算法、模擬退火算法和粒子群算法等。其中，部分較成熟的算法已經(jīng)在一些商業(yè)軟件中得到應(yīng)用，本文將使用商業(yè)軟件Lingo 對模型進行求解。

3 案例分析

圖2 是1 個由14 個節(jié)點和42 條路段組成的道路網(wǎng)絡(luò)。道路均為雙向車道，無人機的2 個基站分別位于節(jié)點4 和節(jié)點13（假設(shè)無人機從節(jié)點4 和節(jié)點13 起降）。根據(jù)路網(wǎng)的路段行程時間，以1 min 作為一個單位時長，路段行程時間均以單位時長的整數(shù)倍標(biāo)示在相應(yīng)的路段上。該路網(wǎng)中共有4 架無人機參與巡視，單機最大續(xù)航時間為40 min。在初始階段，標(biāo)號為1，3 和2，4 的無人機分別在節(jié)點4 和13 的基站，且同一基站的任意時刻至多一架無人機起飛或降落。巡視任務(wù)從第一架無人機起飛開始，直到所有無人機全部完成各自任務(wù)降落，巡視結(jié)束。

該案例中起飛基站的集合 Mo以及降落基站的集合 Nd均由節(jié)點4 和節(jié)點13 組成。4 架無人機分別從2 個基站起飛，有，。

圖 2 上海虹橋臨空經(jīng)濟區(qū)北區(qū)的道路網(wǎng)絡(luò)Fig. 2 Road network for the north district of airport economic zone of Shanghai Hongqiao

首先不區(qū)分重點路段與非重點路段，即不考慮多次巡視任務(wù)的路徑規(guī)劃。此時不考慮單路段的巡視時間間隔約束問題，對任意路段(m,n)而言，Rm,n=1。得到無人機的飛行路徑如表1 所示，1，2，3，4 號無人機分別在0，0，1，1 時刻起飛，在26，27，28，27 時刻降落，總飛行時間為106 min，在28 min 內(nèi)完成所有巡視任務(wù)。

表 1 不考慮巡視次數(shù)的時空路線Tab.1 Space-time routes without considering the number of visits

如果選擇路段（5,9）和（7,8）為重點路段，要求重點路段至少巡視3 次。為避免無人機在連續(xù)時間內(nèi)對該類路段進行往返重復(fù)巡視，規(guī)定巡視時間間隔至少應(yīng)為6 min。此時模型中的系數(shù)R5,9，R9,5，R7,8，R8,7均等于3，其他任意路段(m,n)，Rm,n=1；巡視時間間隔為6 s。得到無人機的飛行路徑如表2 所示。1，2，3，4 號無人機分別在0，0，1，1 時 刻起 飛，在33，32，30，33 時 刻降落，無人機的總飛行時間為126 min，并且所有的無人機在33 min 內(nèi)完成任務(wù)。

表 2 考慮巡視次數(shù)和時間間隔的時空路線Tab.2 Space-time routes considering the number of visits and time intervals

由表1 和表2 數(shù)據(jù)可知，由于受到同一時間內(nèi)至多有一架無人機在基站起降的限制，3 號和4 號無人機選擇在 t=1 時刻起飛。其中，兩種情景下完成巡視任務(wù)所需的時間分別為28 min 和33 min。對該案例的兩種情景進行比較，與不考慮巡視次數(shù)的路徑規(guī)劃相比，無人機的總飛行時間和單機飛行時間分別增加15.87%和15.15%。案例第二種情景下每架無人機只需多飛5 min，即可完成對重要路段巡視3 次的任務(wù)。就所有無人機的總飛行時間而言，無人機完成任務(wù)的效率達到了100%。案例分析表明，該模型是有效可行的。使用Lingo 軟件對該問題進行求解，計算時間少于2 min。

Lingo 軟件的運算時間與時空網(wǎng)絡(luò)的規(guī)模相關(guān)。Lingo 求解問題采用的是一種精確搜索方法，運算時間會隨著求解問題規(guī)模的擴大呈指數(shù)增長，因此，Lingo 只能夠解決一般路網(wǎng)規(guī)模的路徑規(guī)劃問題。受到電池容量的限制，無人機的單機飛行時間有限，能夠巡視的路網(wǎng)規(guī)模也有限，因此，使用Lingo 能夠解決無人機的路網(wǎng)巡視問題。

第二種情景下無人機的巡航距離受到約束時，為了完成特定的飛行任務(wù)，同時滿足總巡航距離最短的目標(biāo)，單架無人機的飛行路徑趨于區(qū)域化，即無人機在各自固定的幾條路段來回飛行。從圖3 無人機的飛行路徑中可以看到，1 號和2 號無人機分別從節(jié)點4 和節(jié)點13 起飛，在飛行路徑上有著近似性的互補關(guān)系，3 號和4 號無人機也有類似的關(guān)系，說明多無人機路網(wǎng)巡視能夠使各架無人機的巡視路徑更加區(qū)域化，同時也使總體的飛行路徑更加合理，避免冗余飛行。

圖 3 無人機飛行路徑Fig.3 Flight path of unmanned aerial vehicle

4 結(jié) 論

針對傳統(tǒng)交通信息收集方式不能有效獲取路網(wǎng)全面實時性交通信息的問題，提出使用無人機進行路網(wǎng)巡視的方法。無人機沿路網(wǎng)巡視不受道路交通狀況的影響，而且能夠在一定的高度上獲得完整的道路交通信息，有利于實現(xiàn)地空協(xié)調(diào)，更加高效地解決交通問題。根據(jù)路網(wǎng)中道路的擁堵程度、事故發(fā)生頻率等因素將路段分為重點路段和普通路段，要求無人機在路網(wǎng)巡視時普通路段至少巡視一次，重點路段多次巡視，合理分配無人機資源。為了使飛行路徑更加合理，添加了巡視時間間隔約束，避免無人機在一個連續(xù)的時段內(nèi)對同一重點路段重復(fù)巡視。本文還限制了無人機在基站同時起降的數(shù)量，減少基站的人員配備。本文研究可促進無人機在交通路網(wǎng)巡視方面的應(yīng)用，為使用無人機解決相關(guān)交通問題提供理論基礎(chǔ)。

本研究的后續(xù)拓展方向包括：a. 無人機基站的選址優(yōu)化；b. 無人機機型對路徑規(guī)劃的影響分析；c. 考慮在道路交叉口利用無人機進行交通控制。