考慮觀測(cè)次數(shù)的無(wú)人機(jī)交通巡視時(shí)空網(wǎng)絡(luò)模型

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 參變量說(shuō)明

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

其他主要參變量簡(jiǎn)介如下：

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

P代表所有無(wú)人機(jī)的集合，有p ∈P ；

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

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

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

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

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

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

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

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

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

t0代表多架無(wú)人機(jī)在同一基站起降的最少時(shí)間間隔；

Tp代表無(wú)人機(jī) p的最大巡航時(shí)間。

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

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

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

2.3 約束條件的建立

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

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

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

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

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

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

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

3 案例分析

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

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

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

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

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

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

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

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

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

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

圖 3 無(wú)人機(jī)飛行路徑Fig.3 Flight path of unmanned aerial vehicle

4 結(jié) 論

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

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