福建省高速公路多義性路徑識別技術的研究

■林宇寧

（福建省高速公路信息科技有限公司，福州 350013）

1 研究背景

高速公路聯網收費系統中的多路徑問題已經逐步成為全國各省市高速公路收費中的一個突出問題，截至2017年末，福建省高速公路通車里程5228km，高速公路主體骨架網絡已經形成，路網結構復雜，多義性路徑數量已超過10萬條。如果簡單的采用最短路徑法收費對高速公路的投資者顯然是不公平的，那么如何確認車輛的實際行駛路徑呢？如何根據高速公路路網特點以及車輛行駛習慣建立一套適合本省聯網收費系統的多路徑處理方案，各省都在不斷研究探索新的技術和新的方法，來解決聯網收費管理和高速公路發展的需要。

目前國內存在兩種方法來解決多義性路徑問題，一種方法是概率識別法，一種是精確識別法。概率識別法相對精確識別法來說，具有投資相對較小，系統改造風險較低等特點，故全國高速公路多數采用了概率識別法來解決多路徑問題。

車輛路徑的概率識別是通過交通均衡或非均衡理論為基礎，建立各種理論模型和算法，分析計算特定高速公路網絡的通行車輛交通分布與分配，從而確定路網中整體出行交通的行駛路徑或單車的可能行駛路徑。通過概率計算，可以確定路網中車輛整體行駛路徑的分布，因此，當聯網收費的拆分模式是由結算中心統一拆分時，就可以根據路網中車輛整體行駛路徑的分布，按某一時間間隔拆分多路徑的通行費。福建省采用了高清車牌照識別的方法來判斷車輛的行駛路徑，并基于識別出的車輛收費金額的比例對多路徑的通行費進行拆分。下面詳細討論多義性路徑識別系統在福建高速的具體實現方法及應用場景。

2 多義性路徑生成

福建省高速公路路網基礎數據是由表示路網頂點的收費站（包括互通樞紐）及表示路網邊的區間構成。多義性路徑生成就是要計算出每個收費站出發到達其他各收費站的車輛可能通行的路徑。

2.1 多義性路徑定義

福建省高速公路對多義性路徑的判斷依據：

(1)多義性路徑環上“環外進、環內出”的車輛，若相對里程差30%以下，且絕對路徑里程差距小于50km的，即為競爭性路徑；否則為非競爭路徑。

(2)多義性路徑環上“環外進、環外出”的車輛，若相對里程差30%以下，且絕對路徑里程差距小于50km的，即為競爭性路徑；否則為非競爭路徑。

(3)多義性路徑環上“環內進、環外出”的車輛，若相對里程差30%以下，且絕對路徑里程差距小于50km的，即為競爭性路徑；否則為非競爭路徑。

(4)多義性路徑環上“環內進、環內出”的車輛，若相對里程差20%以下，且絕對路徑里程差距小于50km的，即為競爭性路徑；否則為非競爭路徑。“環內進、環內出”。采用相對較低的相對里程差，是因為與其他情況比，這種情況的司機具有較好的方向感。

（5）青州大橋所在區間僅允許通行一次，通過繞環網調頭而兩次經過青州大橋的路徑視為不存在的非法路徑。

2．2 使用路網基礎數據進行多義性路徑計算的問題

在實際開發的過程中，發現僅使用代表路網頂點的收費站與虛擬收費站（互通樞紐）及代表路網邊的雙向區間進行多義性路徑生成存在如下問題：

（1）存在部分收費站因單側高速未修建軋道導致從該測通行的車輛無法下高速或者上高速后只能往一側通行（如漳港、水古等），見圖1A。

圖1 路網特殊情況

（2）對于互通需要特殊判斷每個互通只能連續通過兩個節點，不允許通過多于兩個節點如互通A→互通B→互通C這樣的路徑，見圖1B。

（3）因路網特殊點軋道連接實際情況導致不允許通行的情況 （如漳州→福井可以通行，福井→紫泥可以通行，漳州→福井→紫泥不允許通行，需要在福井收費所下高速重新上高速才可以通行），見圖1C。需要將每一個不允許通行的情況都記錄下來特殊處理，容易遺漏且會大幅增加路徑計算時間。

2.3 增加虛擬收費站點及用單向邊表示高速區間

針對上述的問題，本系統中通過將一個收費站化作多個節點（A道、B道、高速入口、高速出口等）以及用單向邊表示高速區間的辦法對路網結構進行處理后，可以用圖結構表示出高速路網的真實情況，避免上述的問題。

相連站點的A道與A道連接、B道與B道連接，AB道之間不存在相互連接，如圖2A。

對實體收費站，入口點連接AB道表示雙向均有軋道可以上高速；AB道連接出口點表示雙向均有軋道可以下高速。而特殊的某一測無上下高速軋道的收費站可以通過只有單向連接出入口來表示，如圖2B。

對于互通樞紐的虛擬站點，將其化作兩個節點（互通入口、互通出口），外部站點進入互通連接到互通的入口點，互通的出口點連接到外部站點出高速。而互通樞紐虛擬站點之間，每個互通樞紐的入口連接其他互通樞紐的出口，如圖3所示。這樣可以從路網結構圖上直接屏蔽互通站點內部通行的可能性，簡化多義性路徑查找的算法。

圖3 對圖1 B的處理

最后生成的用于多義性路徑生成的路網圖其中部分如下圖4所示（正常站點的出入口節點不再畫出）。圖中可以看出存在很多特殊地點因軋道修建情況導致無法通行，如果只使用收費站點及雙向的區間是無法表示，需要特殊處理。

圖2 對圖1 A的處理

圖4 對圖1 C的處理

2.4 計算出入口點對間可能路徑的算法選擇

將路網轉化為由虛擬節點和單向車道組成的圖結構之后，就可以直接使用圖的通用算法進行多義性路徑的查找工作。

在查找多義性路徑時，理論上可以先使用Dijkstra算法找出最短路徑，然后以該最短路徑的長度作為限制，優化深度優先算法的搜索范圍，砍掉不需要搜索的路徑。但是由于福建高速青州大橋所在區間有特殊規則，其AB向車道總計只能夠通行一次，而水古收費所以北的站點到水古收費所因只修了單側匝道，需要經過馬尾樞紐繞小環后折返，經過青州大橋兩次返回水古另一側車道下高速。這一實際上的最短路徑不滿足福建高速青州大橋只能通過一次的規則，需要當作非法路徑處理。

所以Dijkstra算法找出最短路徑的方法無法適應這一特殊規則。并且其他非遍歷的查找最短路徑的算法也無法適應這一規則。因此最終的軟件實現采用深度優先遍歷，并在過程中更新從該入口出發到每一個頂點的最短距離，以此來限制遍歷深度的做法。

3 車輛多義性路徑識別

3.1 高清車牌設備部署要求

福建省高速公路對所有存在多義性路徑出入口點對間的每條競爭路段上至少安裝一套高清車牌照識別設備，確保能識別到路徑比例計算的“公平、公正、科學、合理”。

競爭路段指兩個存在多異性路徑的收費站之間的幾條路徑中不重疊的路段部分。

3.2 多義性路徑標示串生成

多義性路徑按照路徑上所有的識別器，按照從入口到出口的順序將識別器編號連接起來為該路徑的車牌識別器標識串。而所有多義性路徑均有經過的車牌識別器，并不會影響到對車輛多義性路徑的判斷，所以可以不列入車牌識別器標識串中。

如圖5所示的環網中，邊上的編號為安裝的高清車牌識別器的編號。從A收費站出發到G收費站，共計有四條多義性路徑，見下表1。其中在所有多義性路徑公共部分的車牌識別器因為不影響具體路徑的識別過程，所以可以不考慮（1001及1009）。

圖5

表1

3．3 車輛行駛軌跡標識串生成

針對每一條存在多義性路徑的點對之間的過車流水（無多義性路徑點對間的流水不參與比例計算），根據流水的入口時間、出口時間及車牌，查找路徑識別器數據中滿足 （識別器抓拍車牌 =流水出口車牌且流水入口時間<識別器抓拍時間<流水出口時間）的所有識別器數據。將查詢出的識別器數據按照抓拍時間排序并生成識別器串。其中車牌匹配要求為完全匹配，包括車牌的顏色在內需要和流水中的車牌完全一致。

如對車牌藍閩A00001，在通行時間范圍內有抓拍數據的識別點如下表2：

表2

則車輛行駛軌跡標識串為1002@1004（1001在環外不計）。

3.4 車輛行駛軌跡標示串與多義性路徑標示串的匹配規則

車輛行駛軌跡標示串與多義性路徑標示串的匹配規則為：車輛行駛軌跡標示串的每一個識別器均在多義性路徑標示串中存在且前后順序一致。

以表1中的四條路徑為例：

表3

3.5 不能精確匹配的車輛二次分配規則

在多義性路徑匹配中能唯一匹配到一條路徑上的流水數據，根據費率路徑在環內部分費額占總費額的比例直接將環上部分的金額及車次累加到對應路徑上。

如果不能唯一匹配到一條路徑上則將所有可能的路徑記錄并分配金額。表3中的過車流水經過一次分配結束后結果如下表4所示：

表4

二次分配時對不能精確匹配的金額及車次進行重新分配，分配規則為按照一次分配的金額及車次的比例，將二次分配的金額及車次分配給對應的路徑。表4經過二次分配后最終環網金額及車次比例見下表5：

表5

4 多義性路徑識別系統在福建高速的應用

目前本系統在福建省高速已有如下應用場景：

（1）收費收入在各路段公司的拆分

根據多義性路徑過車金額比例，將每個出入口點對間的過車收入按照比例分配到不同的路線上，再根據每一條路線上的區間歸屬的路段公司將收入分配到路段公司上，最終累加所有點對上分配的收入獲得路段公司拆帳總分配收入。

（2）估算區間車流量

根據多義性路徑車流量比例，將每個出入口點對間的車流量分配到不同多義性路徑上，可得不同路徑上的車流量。最終累加所有點對上的車次獲得高速每一個區間的估算車流量。

（3）測算精確路徑收費的影響

目前福建省高速公路收費采用按照最低價路徑收費的標準。通過多義性路徑識別系統可以計算能夠精確識別通行路徑的車輛占高速總過車數的比例，并且通過車輛實際通行路徑的費額可以估算車輛按照實際通行路徑收費對全省收費額的影響。

（4）高清車牌識別器可以用電子車牌信息讀取器等設備替代

高清車牌識別器在本系統中起到的僅僅是定位車輛位置及唯一標識車輛信息的作用。如今后車輛均安裝電子車牌后，可替換成使用電子車牌信息讀取設備，同樣適用于本系統。只需要識別點的輸入信息換成電子車牌信息讀取器讀取到的車牌信息即可，系統整體結構無需變化。