一個基于路網表征的城市交通仿真平臺

王力超 陳燦宇 李京昊 王永瑤

（北京航空航天大學計算機學院 北京市 100191）

根據中共中央、國務院印發的《國家新型城鎮化規劃（2014 ～2020年）》，到2050年，中國城市化率需提高至70%以上。城市化過程中，一個完善的交通運輸體系成為城市良好發展的前提，國家新型城鎮化規劃指出我們要完善綜合運輸通道和區際交通骨干網絡，強化城市群之間交通聯系，加快城市群交通一體化規劃建設，改善中小城市和小城鎮對外交通，發揮綜合交通運輸網絡對城鎮化格局的支撐和引導作用。然而，我國部分地區交通發展水平低，道路建設緩慢，路網結構不合理，導致嚴重的交通擁堵問題；同時，近年來中國經濟的飛速發展帶動了城市化進程的加速，而城市化進程帶來的城市交通擁堵問題也日益嚴重。據中國交通運輸部官網的數據，中國城市交通擁堵問題已經達到了前所未有的嚴重程度。

總之，上述情況引發人們思考：

（1）針對城市的擁堵現狀，是否存在潛在的道路結構優化方式？

（2）針對鄉鎮以及城市新區的開發建設，區域的道路該如何規劃與建設？

針對這兩個問題，筆者設計了一個基于路網表征的城市交通仿真平臺：MANTIS（Multi-layer Graph Attention Network for Transportation Simulation，多層圖神經網絡交通仿真），旨在為交通管理部門合理有效地對道路進行管理和建設提供參考。

2 MANTIS平臺設計

仿真平臺的工作流程如圖1所示，分為三個階段。

圖1：MANTIS 流程圖

2.1 階段1：收集交通信息 提取OD需求

原始的汽車行駛軌跡信息是通過GPS 獲取的。GPS獲取到的汽車行駛數據通常以經度和緯度的形式呈現。這些數據可以通過GPS 設備捕捉并記錄車輛位置的變化，形成一系列坐標點，從而形成行駛軌跡。在此將一條車輛的軌跡規范表達為：

{(t1,long1,lat1),…,(tn,longn,latn)}.

其中，longi,lati表示車輛的經緯度信息，ti表示時間戳，n表示該軌跡的長度。

2.1.1 路網匹配

路網匹配（地圖匹配）[1]，是指將GPS 軌跡點匹配到路網中道路上的過程，是軌跡預處理的一部分。由于GPS 誤差，實際采集的GPS 坐標點往往是在道路附近，通常車輛只能在路網內行駛，此時就需要通過路網匹配判斷各個軌跡點實際在哪條路上，既將軌跡序列轉化為路段序列，也起到修正誤差的作用。匹配準確率會受到GPS 誤差和軌跡低采樣率影響，因此需要開發更優的匹配算法。

地圖匹配是一種將GPS 軌跡數據與地圖上的道路網絡進行匹配的技術。它是許多基于位置的服務的基礎預處理步驟，例如導航系統、交通管理和活動識別。最廣泛使用的地圖匹配算法之一是Fast Map Match（FMM）算法[2]。

FMM 算法是一種基于概率的地圖匹配方法。它假設GPS 測量數據存在噪聲和不確定性，并使用隱馬爾可夫模型（HMM）對軌跡和道路網絡進行建模。HMM由一組狀態和一組觀測值組成。狀態表示候選道路段，觀測值表示GPS 測量數據。FMM 算法使用維特比算法搜索最優狀態序列以匹配觀測值。

FMM 算法包括兩個主要步驟：初始化和迭代。在初始化步驟中，算法使用道路網絡和GPS 測量數據構建HMM。它首先確定距離GPS 測量點一定距離內的候選道路段。然后根據GPS 測量誤差和方向一致性估計每個候選段的可能性。最后，用候選段和它們的可能性初始化HMM。

在迭代步驟中，算法使用維特比算法找到最優狀態序列以匹配觀測值。它從初始狀態開始，迭代地計算每個狀態的可能性，基于前一個狀態和觀測值。然后選擇可能性最高的狀態作為當前狀態，并重復該過程直到所有觀測值匹配。最優狀態序列表示與GPS 軌跡相對應的最可能道路段序列。

通過路網匹配，得到了軌跡數據集。軌跡數據集中每一條軌跡數據為帶有時間戳的路段id 序列：

{(t1,geoid1),…,(tn,geoidn)}.

2.1.2 收集交通信息

從軌跡數據集中，統計時空交通信息。將時空交通信息這個概念定義為：各時段、各路段的車流量、平均車速等。例如，對于編號為id的路段，其對應的時空交通信息did定義為：

其中，n表示將一天24 小時劃分成的時段個數，numi為一天中第i個時段內，在該路段通過的車輛數；vi表示一天內第i個時段內所有通過車輛在該路段的平均車速。

2.1.3 提取OD 需求

OD 需求指的是人們從某個起點（Origin）到達某個終點（Destination）的需求。這種需求在交通規劃和運營中非常重要，因為它能幫助決策者了解人們的出行模式、出行時間、出行目的地等信息，以便更好地規劃公共交通路線、調整交通流量、優化道路網絡等。

通過統計OD 需求，交通決策者才能更好地了解公眾出行需求，提高公共交通的效率和便利性。

從軌跡數據集中，提取出行OD 需求集。每一條OD 需求dem的形式如下：

dem=(t,geoido,geoidd).

其中，t表示出發時間，geoide為起點路段的編號，geoidd為終點路段的編號。

2.2 階段2：模型預測 軌跡生成

2.2.1 基于圖神經網絡的路網表征模型M-GAT

在這一階段，設計了多層圖注意力網絡模型M-GAT（Multi-layer Graph Attention Network）。

2.2.1.1 模型結構

模型結構圖如圖2所示。

圖2：M-GAT 模型圖

將路網定義為一個有向圖G：

G=(V,E,FV).

其中，V={v1,…,v|V|}，每一個節點vi表示一個路段；E?V×V為邊集數組，對任意ei,j=(vi,vj)∈E，表示表示在路網中，車輛能夠從第i個路段到達第j個路段；FV是路段的特征，包括路段長度、車道數量、最大限速、路段種類。

接下來，將建立圖神經網絡模型。這是一種針對圖結構數據的神經網絡模型，它的輸入是一個圖結構，輸出是對節點或邊的特征進行預測或分類的結果。對于沒有明確訓練任務的情況，其輸出就是一種路網的表征。

本文設計的模型是基于GAT 網絡[3]構成的。對于每一層GAT，有

其中，αij表示節點i和節點j之間的注意力系數。權重矩陣W?F×F′。F表示輸入節點特征的維數，而F′表示該層輸出節點的維數。其中的表示，節點i和節點j的節點特征，如果這層GAT 為輸入層，那么節點特征直接就是圖的原節點特征x。||符號代表表示張量的concat。例如，[[1,2],[3,4]]||[[5,6],[7,8]]=[[1,2],[3,4],[5,6],[7,8]]。

通過concat，把兩個1×F′的張量粘合成了1×2F′的大張量。然后乘以一個2F′×1 的attention kernel：。得到的數值就是未加工的attention 系數。接著通過激活函數RELU 函數，并進行softmax 歸一化。

GAT 在聚合鄰居節點的表示向量時，使用注意力權重對其進行加權。這些權重是通過計算當前節點與鄰居節點之間的相似度來確定的。

注意力機制可以使模型專注于與當前節點相關的鄰居節點，從而提高模型的效率和準確性。注意力機制還可以在學習節點表示時選擇性地強調不同節點之間的關系。

其中，Ni表示節點i的鄰接節點，αij是剛剛得到的注意力系數。

和卷積神經網絡CNN 的操作類似，CNN 中對于每一層特征圖的卷積核，其實可以有多個，而且每個卷積核相互獨立，從而使得輸出特征圖具有更多的channel。在GAT 中，可以有K 個獨立的attention 系數，在訓練過程中進行獨立訓練，并且有著獨立的注意力系數矩陣。此時上式變為：

上式代表中間層的輸出形式。最后輸出層的輸出形式為：

通過使用多頭注意力機制，能夠使模型：

（1）關注圖中更深度的子空間和位置信息；

（2）讓模型能夠抽取到更加豐富的特征信息；

（3）增強模型的穩定性和泛化能力。

2.2.1.2 模型準確性驗證

使用了真實世界的兩個大規模數據集：北京和波爾圖的路網數據以及出租車軌跡。如表1所示。

表 1：數據集來源及信息

為了進行更有效的對比，構建了與M-GAT 模型類似但不蘊含圖結構信息的多層感知機模型modified multi-layer perception，記為M-MLP。與基線模型M-MLP的訓練效果如圖3所示?？梢?，M-GAT 能夠更快、誤差更小的完成任務。

圖3：與基線模型的訓練結果對比

此外，仿真了北京三元橋道路施工案例中交通管制對車輛出行的影響?？梢钥吹?，仿真結果與實際情況相近。如圖4所示。

圖4：道路施工案例中交通管制對車輛出行的影響

2.2.2 將OD 需求轉化為預測軌跡

這一步的任務是將OD 需求(t,geoido,geoidd)轉化為預測軌跡 {(t1,id1),…,(tn,idn)}。這涉及到路徑規劃問題。

選用A*算法。A*算法是一種常用于路徑搜索的啟發式搜索算法。它采用了最優先搜索策略，結合了BFS和貪心算法的思想，在減少搜索空間的同時能夠保證找到最優解。這種算法的核心在于利用一個估價函數來預估到目標節點的代價，并根據此來決定搜索的方向。因此，A*算法在許多領域都得到了廣泛應用，如游戲AI、路線規劃、機器人路徑規劃等。A*算法的優點在于它具有高效性和準確性。通過合理地選擇估價函數，A*算法可以在相對較短的時間內找到最優解，并且在大多數情況下能夠減少搜索的節點數。如圖5所示。

圖5：M-GAT based A*結構圖

A*路徑搜索啟發式算法的核心是構建估價函數f(x)來計算每個節點的優先級：

f(x)=g(x)+h(x).

其中，x表示當前所在的位置；g(x)表示歷史代價，使用前述模型預測路段通行時間ti，ti作為有向圖的weights 送入A*算法；h(x)表示未來代價，通過計算當前位置與目標位置的距離來得到。為保證g(x)和h(x)的影響相當，β在實際操作中取300。

A*算法在運算過程中，每次從優先隊列中選取f(x)值最?。▋炏燃壸罡撸┑墓濣c作為下一個待遍歷的節點。

在軌跡搜索中，采用多種其它路徑搜索算法進行了實驗。如表 2所示，相比BFS、Dijkstra，選用的A*算法在算法執行耗時，生成軌跡的通行用時兩個指標的綜合考量中表現最好。

表 2：A*與其他路徑搜索算法的對比

2.3 階段3：統計仿真 可視化

基于前兩個階段的成果，開發了可交互的仿真平臺名為MANTIS（Multi-layer Graph Attention Network for Transportation Simulation）。

MANTIS 的核心工作原理為：在已有路網以及歷史出行數據的訓練基礎上，在編輯后的新路網下，按照歷史的OD 需求，預測每條OD 需求的軌跡，并利用這些軌跡進行統計，從而得到在新路網下的時空交通信息。

MANTIS 包括了路網導入編輯等功能，并搭載了UCAPS 智慧交通模塊以及SUMO 仿真系統。這部分的具體效果可參見視頻附件。

2.3.1 單路網（原始路網）時空交通分析

這一部分搭載了新興好用、功能完善的UCAPS 智慧交通模塊，實現了對于單個路網的時空交通分析。在這一部分，MANTIS 具體涵蓋了以下功能：

（1）道路數據統計顯示；

（2）擁堵排名統計；

（3）擁堵影響關聯分析；

（4）擁堵時空熱力圖展示。

2.3.2 路網編輯

用戶可以進行新增路段以及刪除道路的操作，通過這種方式模擬交通管制、道路改道。

2.3.3 編輯前后雙路網宏微觀對比

在路網編輯模塊的基礎上，平臺能夠對編輯前后的路網下的交通狀況進行宏觀以及微觀的對比分析。如圖6 和圖7所示。

圖6：編輯前后雙路網宏觀對比分析

圖7：編輯前后雙路網微觀對比分析

宏觀分析：分析的粒度在整個路網。展示的是各個時段下的交通信息的數據對比。如圖6所示。

微觀分析：在路段路段下進行可視化展示。如圖7所示。這部分通過對接SUMO 仿真軟件的功能模塊來實現展示。

3 總結展望

交通仿真技術的應用可以幫助交通管理部門進行交通流量的優化和交通規劃的設計，從而提高城市道路交通的效率和安全性。MANTIS 平臺作為一種基于圖神經網絡的路網表征模型，能夠模擬城市道路交通系統的各種情況，并通過可視化平臺對模擬結果進行直觀的展示，能有效為城市交通管理部門的管理和建設工作提供參考。