1、曼哈頓無人飛機交通監控部署摘要本文討論分析了曼哈頓城市MAV交通監控部署問題，分別在四種不同的情況下求解出了最優巡航方案。 在Task1中，首先選取區域交通路口為節點，給出MAV的監控路段和節點選擇方法; 然后討論在無續航里程約束條件下，將MAV監控問題轉化為TSP問題，并運用模擬退火算法予以求解; 而在有續航里程約束條件下，運用 Kmeans聚類方法，將監控區域劃分成若干子區，進而將該問題轉化為無續航里程約束的MAV監控部署問題，最后對上城區的監控進行實證分析，給出了最優部署方案。 在Task2中，在Task 1的基礎上求解在30%的MAV無法使用的情況下如何實現巡航監控。首先將正常監控區域

2、簡化為其質心，比較無法正常巡航區域內的節點與各個質心的距離，對這些節點進行重新分配；然后在重新劃分的區域內仍舊將問題轉化為TSP問題；最后運用Task1中的模型進行求解。 在Task3中，首先根據與主干道相交道路的數量確定其權值；然后建立加權歐氏距離的K-means聚類模型進行聚類，對區域內的交通路口進行劃分；最后在每一個監控子區內，又是一個TSP問題，同樣用模擬退火算法可以求解最佳的巡航路徑。在Task4中，根據題目要求參與MAV巡航部署的和沒有參與的人都不能確切知道MAV的巡航方案，即MAV的巡航方案具有一定的動態性（隨機性）。本文首先確定巡航應當滿足的條件以及方案評價體系；然后通過隨機貪

3、心算法求解足夠多的可行靜態解，最后引入時間切片疊加的思維，在靜態解的基礎上應用深度優先搜索算法，將求解動態巡航問題轉化為在有向連通圖中尋找使目標函數達到最大的約束環路問題，最終求得動態MAV巡航方案。關鍵詞：MAV巡航 TSP問題 時間切片 加權K-means聚類1、 問題重述2、 模型假設1. 假設MAV的巡航速度100Km/h；2. 假設MAV可以急轉彎；3、 模型建立與求解Task 1 基于旅行商模型的MAV監控部署1、 問題分析MAV需要對整個曼哈頓的交通進行監控，主要是對區域的路段進行監控，尤其是十字路口。根據監控歷程是否超出飛機飛行距離，提出無人飛機在有無續航里程約束條件下的交通監

4、控部署方法。本文選取區域十字路口為節點，給出MAV的監控路段和節點的選擇方法; 在無續航里程約束條件下，將無人飛機的交通監控問題轉化為旅行商問題，并運用模擬退火算法予以求解; 在有續航里程約束條件下，運用 Kmeans聚類方法，將無人飛機的監控區域劃分成若干子監控區，從而將該問題轉化為無續航里程約束的無人飛機交通監控部署問題。2、 模型建立2.1 監控節點和監控路段的選擇根據道路的交通安全水平評價，本文將MAV的交通監控對象分為節點和路段二類。目前，國內外對道路的交通安全狀況進行了深入研究，得到了道路交通事故發生分布的一般特征。發現交通事故多發生于交通路口等地方。因此，本文選擇交通路口作為監控

5、節點。監控路段的選擇，區域內的所有交通道路均為監控路段，路段長度的計算采用定長法，即不考慮各個道路的交通量、限速、道路質量，僅考慮道路的實際長度。2.2無里程約束的無人飛機路線規劃當無人飛機的飛行距離很長時可不考慮其飛行里程的約束，在確定其監控對象后，規劃其飛行路線: 無人飛機從基地出發，遍歷這些節點、路段，然后再飛回基地，在此過程中，無人飛機將實時監控圖像傳回交通監控中心。該問題類似 于旅行商問題，即無人飛機從基地出發，遍歷每個節點、路段，且只經過一次，路徑的選擇目標是要求無人飛機的巡航路徑最短。本文將路段抽象成為具有一定里程的節點，進行數學建模，如圖1所示。監控路段 監控節點 MAV巡航路

6、徑圖1 監控路段抽象為節點示意圖 假設監控網絡中有個交通監控對象，是第個和第個監控對象之間的距離，無人飛機的巡航路線規劃模型為:其中： 目標函數是使MAV的總巡航距離最短，公式(1)保證無人飛機僅到達監控對象一次; 公式（2）保證無人飛機僅離開監控對象一次。無里程約束的無人飛機路線規劃問題類似于旅行商問題，該問題屬于NP完全問題。2.3 有里程約束的監控小區劃分當無人飛機的飛行距離有限且監控范圍較大時，所需的無人飛機巡航里程可能超過其最大飛行里程，且監控時間較長，此時需要考慮無人飛機監控小區的劃分，配置多架無人飛機進行交通監控。通過監控小區的劃分，一方面可滿足無人飛機的最大飛行里程要求，另一方

7、面可縮小單架次無人飛機的監控范圍，提高交通監控的響應速度，從而將有里程約束的問題轉換成為無里程約束問題。無人飛機監控小區劃分的方法為: 根據無人飛機監控點、路段的空間分布，對監控對象進行聚類，實現監控小區劃分。在監控小區劃分的過程中，不斷增加監控小區數量，保證每一監控小區有一架無人飛機進行交通監控.設有監控對象其中每個監控對象有2個空間坐標，即:；引入K means方法將監控對象劃入若干小區內。考慮到曼哈頓地區道路交通監控對象在空間上的分布特征，以及無人飛機的最大飛行里程的限制，監控小區數量的劃分上限設，其中表示向上取整。2.4部署方案的評價將無人飛機監控區域劃分成為不同的偵察子區域，并在每個

8、子區域部署一架無人飛機，則不同的子區域劃分對應著不同的無人飛機偵察代價，因此，本文提出2個指標評價無人飛機的部署效果。（1） 總巡航距離：（2） 監控時間標準差：其中；為劃分的子區域數量; 為無人飛機在第個子區域的巡航距離;為無人飛機在第個子區域的巡航時間。指標1表示所有的無人飛機巡航距離之和; 指標2表示所有無人飛機巡航時間的標準差; 這2個指標用于衡量部署無人飛機的成本和使用協同性。從直觀上講，無人飛機的數量越多，則平均監控時間變短，交通監控的響應速度就越快，同時無人飛機的購置成本也在增加。另一方面，部署多架無人飛機后，總巡航距離和監控時間的協調性會發生動態的變化，此時需要根據交通監控的需

9、求做出權衡。3、 模型求解 經查閱，整個曼哈頓地區屬于有續航差約束的情景，由于總巡航距離較長，監控時間將會較長，且超出許多無人飛機的最大飛行距離，因此可進行監控小區的劃分，在此，本文以曼哈頓上城區進行實證分析。 上城區的交通道路如圖2，其中代表城市的交通道路，代表交通路口。圖2 曼哈頓上城區城市交通圖結合該區域交通道路特征，建立平面直角坐標系。讀取各個節點的坐標。運用Kmeans聚類方法將該路網劃分為27 個監控小區。表1給出了劃分結果。表1 運用Kmeans聚類方法將該路網劃分為27 個監控小區數目12345678910111213141516171819202122232425262728

10、293031234567 運用Kmeans聚類方法將該路網劃分為27 個監控小區每個小區配置一架無人飛機(假設巡航速度為100 km/h，則最大續航里程為500 km) ，每個小區內的無人飛機監控問題轉化為無續航里程約束的TSP 問題，并用模擬退火算法求解，不同UAV 監控小區的無人飛機總巡航距離、監控時間對比情況如圖3所示。圖3不同MAV監控小區監控時間（單位：h）與總的巡航距離對比圖（單位Km）由圖3可知，隨著無人飛機監控小區數量的增多，總巡航距離呈動態變化，劃分為1個監控小區時總巡航距離最小，為760 km; 劃分為6個監控小區時總巡航距離最大，為881 km。由圖3可知，平均監控時間隨

11、著小區數量的增加而下降，劃分為2個監控小區時平均監控時間為1.8 h，劃分為7 個監控小區時平均監控時間為0.3 h，監控的響應速度大為提高。同時通過計算得到，監控時間的標準差隨著小區數量的增加而動態變化，劃分為3個監控小區時標準差最大，為0. 74 h，各小區的無人飛機監控協調最差，劃分為6 個監控小區時標準差最小，為0. 13 h，此時各小區的無人飛機監控協調最好。 綜合以上分析，在曼哈頓上城區劃分6個監控子區域最為合適，滿足題中所要求城市每個角落保持在15分鐘內被監控，同時監控時間的標準差最小，所有MAV的協調性最高。至此，在各個子區域則轉化成為一個TSP（旅行商）問題。在MATLAB

12、中運用模擬退火算法求解無人飛機最短巡航距離。模擬退火算法的參數設置為: 初始溫度為10000 ，冷卻速度為0. 99，最大迭代次數為10000 次。此時的監控小區劃分及無人飛機的飛行路徑如圖4所示。當需要進一步提高無人飛機的監控響應速度時，則需要繼續增加無人飛機的監控小區并配置更多的無人飛機。圖4 6 監控小區及無人飛機飛行路徑 基于此，本文求解出了曼哈頓上城區飛機監控部署方案，用同樣的方法可以確定其他區域的MAV部署。其他區域的監控部署見附錄1。Task 2 基于最短距離的節點劃分模型1、 問題分析在Task 1中將城市交通的有歷程約束的巡航轉化為無里程約束巡航，本文繼續以上城區進行實證分析

13、，求解在30%的MAV無法使用過的情況下如何實現巡航監控。將正常監控區域簡化一點，即其質心，比較無法正常巡航區域內的交點與各個質心的距離，對于某一節點而言，將其劃入與質心的距離最短的質心所代表的區域，對于距離相等的節點，先將該節點歸入對應的多個區域，通過計算多個區域的巡航時間，若存在某一加入該節點后的某一區域巡航時間比其他區域巡航時間段，則該節點應該歸入巡航時間短的區域。本文以區域3、區域4無法正常巡航進行實證分析。2、模型建立與求解設可以正常巡航的的區域為,將該區域簡化為質點記，記無法正常巡航區域內的各個節點的坐標，。計算得到質心、節點坐標如圖5。圖5 正常巡航區域的質心坐標與無法正常巡航區

14、域內的節點坐標根據已知條件，可以計算出這些無法正常巡航區域內的各個節點與正常巡航區域中心坐標的距離 根據中計算的各個節點到質心的距離，各個節點的劃分區域如表2所示。表2 無法正常巡航區域內的各節點重新劃分后的所屬區域情況區域編號所包含節點11,12,13,148，9,1018,17,22，15,16,24,23根據表2中各正常巡航區域重新劃入的節點，將問題再次轉化為旅行商問題，在各個重新劃分的子區域內運用模擬退火算法求解出MAV的最佳巡航路徑。如圖6所示。圖6 重新規劃后的監控小區及無人飛機飛行路徑 最后可以得出當區域3、區域4無法正常巡航時剩余的MAV巡航范圍及路徑。當遇到某一個節點到多個質

15、心的距離相等時，先將該節點劃分到各個質心所代表的區域，然后用同樣的方法求出解，最后比較巡航時間，將節點歸入巡航時間最短的質心所代表的區域。 同理，可以用同樣的方法確定曼哈頓其他區域的交通在緊急狀況下MAV的部署方案。根據不用的緊急情況確定不同的部署方案，進而可以確定在此情況下MAV的巡航監控范圍。Task 3 基于交通道路加權的MAV巡航改進模型1、 問題分析盡管所有地區都是平等的，但是有些地區更為重要。城市的交通主干道總是和一些較小的道路縱橫交錯，一條主干道與其他道路相交的越多則一定程度上表明該條主干道上的交通量越大，即具有較高密度的亂穿馬路的人，因此這些地區應該加強巡邏，同時對于一些交通量

16、少的交通主干道，則可以適當減少巡航監控的頻率。由此可以根據與主干道相交道路的數量確定其權值，在確定權值以后，建立加權歐幾里得距離K-means聚類模型進行聚類對區域內的交通路口進行劃分，在每一個監控子區內，則又是一個旅行商的問題，同樣用模擬退火算法可以求解最佳的巡航路徑。2、 模型建立于求解2.1 基于加權的歐氏距離K-means聚類模型交通道路的加權根據上文分析，本文將主干道與其相交的道路數目作為該條道路的權，如圖7，與主干道相交的道路有，由此確定主干道的權為7。 表示交通路口，表示主干道圖7 道路的加權示意圖 以此方法可以得到其他道路的權值。本文選取上城區的交通道路進行實證分析，以此闡明如

17、何基于交通道路加權的MAV巡航改進模型。圖8給出了曼哈頓上城區的各條道路的加權值。圖8 曼哈頓上城區的各條道路加權值交通路口的加權歐幾里得距離在圖論中通常二點之間的距離進行比較，一般情況下歐氏距離計算式為：其中的坐標。而本題涉及到加權，即對每個變量賦予權重，那么加權的歐幾里得距離為其中是節點所連接道路的權。在進行聚類時合理地運用加權歐氏距離，對改進聚類結果能起到較好的效果。 一下是基于加權歐幾里得距離的K-means聚類算法的一般過程： 算法輸入：聚類個數，以及個節點集合； 算法輸出：滿足方差最小的標準的個聚類； 算法步驟：（1） 從個節點對象中任意選擇個對象作為初始聚類中心；（2） 根據每個

18、聚類中所有對象的均值（中心對象），計算樣本集中每個對象與這些中心對象的加權歐幾里得距離，病根據最小的加權歐氏距離重新對相應對象進行劃分；（3） 重新計算每個（有變化）聚類的均值（中心對象）；（4） 循環執行（2），（3），直到每個聚類不再發生變化為止。 根據以上對算法的設計和對曼哈頓城市交通圖的分析，借助MATLAB進行計算，最終求的在加權情況下，上城區監控區域的劃分。表9給出了輸出的監控區域劃分結果。表3 基于加權歐氏距離的K-means節點聚類劃分數目12345678910111213141516171819202122232425262728293031234562.2 基于TSP的MA

19、V巡航部署模型運用Kmeans聚類方法將該路網劃分為26 個監控小區每個小區配置一架無人飛機(假設巡航速度為100 km/h，則最大續航里程為500 km) ，每個小區內的無人飛機監控問題轉化為無續航里程約束的TSP 問題，并用模擬退火算法求解，得到在各個子區的巡航軌跡。在得到各個子區巡航軌跡只有，根據中提出的對不同巡航路徑的評價指標，即無人飛機總巡航距離、監控時間，對各個不同情況進行評價分析，以找出最為合理地子區劃分。表給出了相關結果。表10不同監控子區的的評價分析監控子區數目23456最大巡航時間1.8h1.6h0.66h0.66h0.31h最小巡航時間1.6h0.66h0.42h0.08

20、h0.07h總巡航距離760Km820Km 820Km800Km860Km監控時間標準差0.58h0.74h0.44h0.29h0.15h根據題目要求，城市的部分地區有較高密度的亂穿馬路者，這些地區應該在每5分鐘巡航一次，而另一些地區則只需要每隔20分鐘巡航一次，因此各個監控子區的最大巡航時間應該小于20分鐘，最小巡航時間應該小于5分鐘，由表3可以看出，符合這一條件至少需要將上城區劃分為6個子監控區，而且在劃分為6個子區時所有MAV的總巡航距離最大，這意味著MAV監視的范圍就越大，同時6個子區的監控時間標準差最小，也就是說在此情況下，所有MAV的協調性最好，綜合分析，將監控區域劃分為6個子區已

21、經符合題目要求，如果再多劃分一個子區勢必增加一架MAV，繼而增加監控成本。圖9給出了，上城區6個子監控區的劃分以及各個子區域的MAV巡航軌跡。圖9 6個子監控區的劃分以及各個子區域的MAV巡航軌跡最后，運用同樣的方法可以將整個曼哈頓進行監控子區的劃分，在各個子區均看做是TSP問題。TASK 4 基于時間切片疊加的MAV動態部署模型1 問題分析題目要求從MAV的角度考慮，做到對每個人都公平，即參與MAV巡航部署的和沒有參與的人都不能確切知道MAV的巡航方案，這就要求MAV的巡航方案具有一定的隨機性。使所有人都無法掌握MAV的巡航規律。該問題可以理解為求解MAV的動態巡航方案問題。本文通過一些必要

22、簡化首先確定巡航發難應當滿足的條件以及方案的評價體系，通過隨機貪心算法求解足夠多的可行靜態解，并引入時間片疊加的思維在靜態解的基礎上應用深度優先搜索算法，將求解動態巡航問題轉化為在有向連通圖中尋找使目標函數達到最大的約束環路問題，最終求得動態MAV巡航方案。2 模型建立于求解2 模型建立于求解2.1 MAV巡航方案評價體系的建立為了巡航方案的優化選擇，本文定義4個評價巡航方案的指標，分別為抵達第個交通路口的平均時間，最大巡航死角時間，巡航合理性，整個巡航方案的巡航總里程。MAV抵達交通路口的平均時間：假設在所有交通路口為，現在要求向派遣一架MAV，距離該點最近的MAV設為，之間的距離為，MAV

23、趕往該節點的速度為，則平均時間可以表示為；最大巡航死角時間：本文定義某個節點的巡航死角時間為在巡航過程中沒有處在監控范圍內的時間之和，則最大巡航死角時間從整體上體現了MAV對城市內各條街道的覆蓋情況，為了避免出現巡航死角時間，應該是巡航的盡可能地尋遍城市的各個交通路口，以體現巡航的全面性和整體性。巡航合理性：在不同權重的地區，MAV的配置應該與權重相適應，第個交通路口的權為，記整個巡航方案中單位時間內第個交通路口出現MAV數量的平均值為故有：則的定義為其中，。 總巡航距離：某一部署方案所有MAV巡航距離的總和。記單個MAV巡航距離為則總巡航里程為：將上述四個指標分別用如下方法進行標準化：最后將

24、四個指標綜合，得到綜合評價指標為2.2MAV巡航靜態方案求解 MAV巡航可以分為靜態巡航和動態巡航二種情況，靜態方案可以理解為MAV在各自的監控區域進行監控，即可以認為負責監控該區域的MAV繞著該區域的質心進行監控，而動態監控是指所有MAV按照一定的計劃在城市內動態的巡航。動態巡航方案可以看做是由一個時間序列上多個靜態巡航方案組成的。本文引入時間片段疊加模型來從靜態方案構造動態方案。模型的主要思想為：求解出一系列的滿足基本條件的靜態解，將這些靜態解看做是一個一個的切片，通過構建合理地組合模型將這些切片堆砌起來形成最終的動態解。 首先定義：若在城市交通圖中節點上空有MAV，則記，否則為0，若MA

25、V可以再要求時間內從節點到節點則記，否則為0，若點在某一MAV監控范圍內，則，否則為0.之間的關系可以表示為：即若巡航方案要求達到的覆蓋率為，交通路口數為，則靜態模型可以表示為：這是一個0-1規劃問題，可以使用隨機貪心算法求解。2.3 時間切片疊加算法的MAV動態巡航求解 事實上，MAV的動態巡航過程可以看做是連續時間點上靜態方案的疊加，即動態巡航的MAV部署在每一刻都可以看作是一個滿足基本條件的靜態配置，而動態巡航過程正是由這些時間切片堆疊起來的，因此，我們引入時間片度疊加的思想，利用大量滿足基本條件的靜態解為基礎，以評價指標函數為目標函數求動態部署方案。圖10是該思想的示意圖，每一層代表一

26、個時間點MAV的配置情況。圖10 時間切片疊加算法示意圖在用之前所述的靜態求解模型生成大量可行解的基礎上，時間切片疊加模型的核心問題是要在備選的靜態中選擇正確的時間切片并給出正確的時間疊加順序。 首先，對于給定的兩個靜態解，本文給出一個標準來確定他們之間是否能夠作為相鄰的時間切片，為了描述靜態解之間的差異程度，本文定義了兩個靜態解之間的距離，如果兩個靜態解具有相同的節點數和MAV數，同一個MAV在兩個方案之間會有一定的距離，即定義為所有MAV的距離中的最大值，可以確定出一個閾值，當時，認為對應的兩個方案是可以作為連續時間片的。在此基礎上，我們可以建立一個加權的無向連通圖模型來描述動態巡航方案求

27、解問題如圖11所示。其中每個節點表示一個由之前模型生成的備選靜態方案，另一條邊的權重表示對應兩個方案之間的距離，如果能從圖中找到一個有向回路，且回路中每兩個相鄰節點都滿足時，即找到了一個可行的動態方案，也就是說，所有可行的方案均可以為該連通圖中的一個“連續”的回路所表示.例如, 假如為100m，下圖中有4個備選靜態方案構成的連通圖, 則下圖中紅色回路即表示一個動態解方案, 在該方案中, 所有車輛依次在靜態方案中的對應位置上。圖11 由靜態方案求解動態方案示意圖對于可行的動態方案, 顯然綜合評價指標的值越大, 該巡邏方案越優秀. 因此我們以綜合評價指標為目標函數, 根據以上思想, 時間片疊加算法

28、可以轉化為在一個有向圖中尋找一個帶約束回路使綜合評價指標函數達到最大的組合模型, 描述如下：給定閾值和無向圖，為頂點集,為邊集, 每個頂點用"表示, 含義為一個靜態解，表示兩個靜態解之間的距離, 則有，表示從到轉移的評價值(此處為兩靜態解內所有MAV移動距離之和).經過定性分析可以發現, 若使得評價函數達到最大, 則在求解過程中需要滿足方案中所有MAV移動距離之和盡可能大. 則間題可以轉化為: 求解中較大回路，其中，且最大化。綜合上述分析，求求解動態解過程已經轉化為無向圖求最大(較大) 環的問題.廣泛使用的圖的深度優先遍歷即可在很短的時間內求得間題的解,這里我們采用之前部分提出的綜合

29、評價指標作為目標函數.該算法思想描述如下: 假設給定圖的初態是所有頂點均未曾訪問過. 在中任選一頂點為初始出發點(源點), 則深度優先遍歷可定義如下:首先訪問出發點,并將其標記為已訪問過;然后依次從出發搜索的每個鄰接點。若未曾訪問過, 則以為新的出發點繼續進行深度優先遍歷, 直至圖中所有和源點有路徑相通的頂點(亦稱為從源點可達的頂點) 均已被訪問為止;若曾被訪問過, 則找到一個環, 這個環由和在遍歷樹中的公共祖先出發分別到和路徑上所有的邊以及邊組成.若此時圖中仍有未訪問的頂點, 則另選一個尚未訪問的頂點作為新的源點重復上述過程, 直至圖中所有頂點均已被訪問為止。 2.4 模型檢驗與評價本文繼續

30、選取曼哈頓上城區的交通圖進行實證分析。設方案滿足的設方案需滿足的條件為在任一時刻, 地圖上90%的區域必須分別在最近的MAV控制區內,控制區的范圍為附近MAV15分鐘內能夠到達. 我們使用時間片疊加算法求出了巡邏方案,結果顯示, 該地區巡邏需要5架MAV。 同理，運用時間切片疊加法可以求解出曼哈頓其他地區的MAV動態部署方案。4、 模型優缺點分析在Task1中，本文選取區域十字路口為節點，給出MAV的監控路段和節點的選擇方法; 在無續航里程約束條件下，將無人飛機的交通監控問題轉化為旅行商問題，并運用模擬退火算法予以求解; 在有續航里程約束條件下，運用 Kmeans聚類方法，將無人飛機的監控區域

31、劃分成若干子監控區，從而將該問題轉化為無續航里程約束的無人飛機交通監控部署問題。但是本文僅實現了對各個交通路口進行監控，而對交通道路的監控有待進一步完善。在Task2中，本文基于Task 1中將城市交通的有歷程約束的巡航轉化為無里程約束巡航的方法，繼續以上城區進行實證分析，求解在30%的MAV無法使用過的情況下如何實現巡航監控。將正常監控區域簡化一點，即其質心，比較無法正常巡航區域內的交點與各個質心的距離，對于某一節點而言，將其劃入與質心的距離最短的質心所代表的區域，對于距離相等的節點，先將該節點歸入對應的多個區域，通過計算多個區域的巡航時間，若存在某一加入該節點后的某一區域巡航時間比其他區域巡航時間段，則該節點應該歸入巡航時間短的區域。模型缺點在于本文將所有正常巡航的區域簡化為質心，從而導致模型結果誤差較大；在轉化為TSP問題求解時認為每個節點都是等權的，存在一定的不合理性。在Task3中，根據與主干道相交道路的數量確定其權值，在確定權值以后，建立加權歐幾里得距離K-means聚類模型進行聚類，對區域內的交通路口進行劃分，在每一個監控子區內，則又是一個旅行商的問題，同樣用模擬退火算法可以求解最佳的巡航路徑。但是同樣僅實現了對各個交通路