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

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

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

總之，上述情況引發(fā)人們思考：

（1）針對城市的擁堵現(xiàn)狀，是否存在潛在的道路結構優(yōu)化方式？

（2）針對鄉(xiāng)鎮(zhèn)以及城市新區(qū)的開發(fā)建設，區(qū)域的道路該如何規(guī)劃與建設？

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

2 MANTIS平臺設計

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

圖1：MANTIS 流程圖

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

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

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

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

2.1.1 路網(wǎng)匹配

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

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

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

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

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

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

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

2.1.2 收集交通信息

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

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

2.1.3 提取OD 需求

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

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

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

dem=(t,geoido,geoidd).

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

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

2.2.1 基于圖神經(jīng)網(wǎng)絡的路網(wǎng)表征模型M-GAT

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

2.2.1.1 模型結構

模型結構圖如圖2所示。

圖2：M-GAT 模型圖

將路網(wǎng)定義為一個有向圖G：

G=(V,E,FV).

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

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

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

其中，αij表示節(jié)點i和節(jié)點j之間的注意力系數(shù)。權重矩陣W?F×F′。F表示輸入節(jié)點特征的維數(shù)，而F′表示該層輸出節(jié)點的維數(shù)。其中的表示，節(jié)點i和節(jié)點j的節(jié)點特征，如果這層GAT 為輸入層，那么節(jié)點特征直接就是圖的原節(jié)點特征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：。得到的數(shù)值就是未加工的attention 系數(shù)。接著通過激活函數(shù)RELU 函數(shù)，并進行softmax 歸一化。

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

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

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

和卷積神經(jīng)網(wǎng)絡CNN 的操作類似，CNN 中對于每一層特征圖的卷積核，其實可以有多個，而且每個卷積核相互獨立，從而使得輸出特征圖具有更多的channel。在GAT 中，可以有K 個獨立的attention 系數(shù)，在訓練過程中進行獨立訓練，并且有著獨立的注意力系數(shù)矩陣。此時上式變?yōu)椋?/p>

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

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

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

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

（3）增強模型的穩(wěn)定性和泛化能力。

2.2.1.2 模型準確性驗證

使用了真實世界的兩個大規(guī)模數(shù)據(jù)集：北京和波爾圖的路網(wǎng)數(shù)據(jù)以及出租車軌跡。如表1所示。

表 1：數(shù)據(jù)集來源及信息

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

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

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

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

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

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

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

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

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

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

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

A*算法在運算過程中，每次從優(yōu)先隊列中選取f(x)值最小（優(yōu)先級最高）的節(jié)點作為下一個待遍歷的節(jié)點。

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

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

2.3 階段3：統(tǒng)計仿真 可視化

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

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

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

2.3.1 單路網(wǎng)（原始路網(wǎng)）時空交通分析

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

（1）道路數(shù)據(jù)統(tǒng)計顯示；

（2）擁堵排名統(tǒng)計；

（3）擁堵影響關聯(lián)分析；

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

2.3.2 路網(wǎng)編輯

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

2.3.3 編輯前后雙路網(wǎng)宏微觀對比

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

圖6：編輯前后雙路網(wǎng)宏觀對比分析

圖7：編輯前后雙路網(wǎng)微觀對比分析

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

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

3 總結展望

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