福建省高速公路多義性路徑識(shí)別技術(shù)的研究

■林宇寧

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

1 研究背景

高速公路聯(lián)網(wǎng)收費(fèi)系統(tǒng)中的多路徑問題已經(jīng)逐步成為全國(guó)各省市高速公路收費(fèi)中的一個(gè)突出問題，截至2017年末，福建省高速公路通車?yán)锍?228km，高速公路主體骨架網(wǎng)絡(luò)已經(jīng)形成，路網(wǎng)結(jié)構(gòu)復(fù)雜，多義性路徑數(shù)量已超過10萬(wàn)條。如果簡(jiǎn)單的采用最短路徑法收費(fèi)對(duì)高速公路的投資者顯然是不公平的，那么如何確認(rèn)車輛的實(shí)際行駛路徑呢？如何根據(jù)高速公路路網(wǎng)特點(diǎn)以及車輛行駛習(xí)慣建立一套適合本省聯(lián)網(wǎng)收費(fèi)系統(tǒng)的多路徑處理方案，各省都在不斷研究探索新的技術(shù)和新的方法，來(lái)解決聯(lián)網(wǎng)收費(fèi)管理和高速公路發(fā)展的需要。

目前國(guó)內(nèi)存在兩種方法來(lái)解決多義性路徑問題，一種方法是概率識(shí)別法，一種是精確識(shí)別法。概率識(shí)別法相對(duì)精確識(shí)別法來(lái)說(shuō)，具有投資相對(duì)較小，系統(tǒng)改造風(fēng)險(xiǎn)較低等特點(diǎn)，故全國(guó)高速公路多數(shù)采用了概率識(shí)別法來(lái)解決多路徑問題。

車輛路徑的概率識(shí)別是通過交通均衡或非均衡理論為基礎(chǔ)，建立各種理論模型和算法，分析計(jì)算特定高速公路網(wǎng)絡(luò)的通行車輛交通分布與分配，從而確定路網(wǎng)中整體出行交通的行駛路徑或單車的可能行駛路徑。通過概率計(jì)算，可以確定路網(wǎng)中車輛整體行駛路徑的分布，因此，當(dāng)聯(lián)網(wǎng)收費(fèi)的拆分模式是由結(jié)算中心統(tǒng)一拆分時(shí)，就可以根據(jù)路網(wǎng)中車輛整體行駛路徑的分布，按某一時(shí)間間隔拆分多路徑的通行費(fèi)。福建省采用了高清車牌照識(shí)別的方法來(lái)判斷車輛的行駛路徑，并基于識(shí)別出的車輛收費(fèi)金額的比例對(duì)多路徑的通行費(fèi)進(jìn)行拆分。下面詳細(xì)討論多義性路徑識(shí)別系統(tǒng)在福建高速的具體實(shí)現(xiàn)方法及應(yīng)用場(chǎng)景。

2 多義性路徑生成

福建省高速公路路網(wǎng)基礎(chǔ)數(shù)據(jù)是由表示路網(wǎng)頂點(diǎn)的收費(fèi)站（包括互通樞紐）及表示路網(wǎng)邊的區(qū)間構(gòu)成。多義性路徑生成就是要計(jì)算出每個(gè)收費(fèi)站出發(fā)到達(dá)其他各收費(fèi)站的車輛可能通行的路徑。

2.1 多義性路徑定義

福建省高速公路對(duì)多義性路徑的判斷依據(jù)：

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

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

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

(4)多義性路徑環(huán)上“環(huán)內(nèi)進(jìn)、環(huán)內(nèi)出”的車輛，若相對(duì)里程差20%以下，且絕對(duì)路徑里程差距小于50km的，即為競(jìng)爭(zhēng)性路徑；否則為非競(jìng)爭(zhēng)路徑?！碍h(huán)內(nèi)進(jìn)、環(huán)內(nèi)出”。采用相對(duì)較低的相對(duì)里程差，是因?yàn)榕c其他情況比，這種情況的司機(jī)具有較好的方向感。

（5）青州大橋所在區(qū)間僅允許通行一次，通過繞環(huán)網(wǎng)調(diào)頭而兩次經(jīng)過青州大橋的路徑視為不存在的非法路徑。

2．2 使用路網(wǎng)基礎(chǔ)數(shù)據(jù)進(jìn)行多義性路徑計(jì)算的問題

在實(shí)際開發(fā)的過程中，發(fā)現(xiàn)僅使用代表路網(wǎng)頂點(diǎn)的收費(fèi)站與虛擬收費(fèi)站（互通樞紐）及代表路網(wǎng)邊的雙向區(qū)間進(jìn)行多義性路徑生成存在如下問題：

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

圖1 路網(wǎng)特殊情況

（2）對(duì)于互通需要特殊判斷每個(gè)互通只能連續(xù)通過兩個(gè)節(jié)點(diǎn)，不允許通過多于兩個(gè)節(jié)點(diǎn)如互通A→互通B→互通C這樣的路徑，見圖1B。

（3）因路網(wǎng)特殊點(diǎn)軋道連接實(shí)際情況導(dǎo)致不允許通行的情況 （如漳州→福井可以通行，福井→紫泥可以通行，漳州→福井→紫泥不允許通行，需要在福井收費(fèi)所下高速重新上高速才可以通行），見圖1C。需要將每一個(gè)不允許通行的情況都記錄下來(lái)特殊處理，容易遺漏且會(huì)大幅增加路徑計(jì)算時(shí)間。

2.3 增加虛擬收費(fèi)站點(diǎn)及用單向邊表示高速區(qū)間

針對(duì)上述的問題，本系統(tǒng)中通過將一個(gè)收費(fèi)站化作多個(gè)節(jié)點(diǎn)（A道、B道、高速入口、高速出口等）以及用單向邊表示高速區(qū)間的辦法對(duì)路網(wǎng)結(jié)構(gòu)進(jìn)行處理后，可以用圖結(jié)構(gòu)表示出高速路網(wǎng)的真實(shí)情況，避免上述的問題。

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

對(duì)實(shí)體收費(fèi)站，入口點(diǎn)連接AB道表示雙向均有軋道可以上高速；AB道連接出口點(diǎn)表示雙向均有軋道可以下高速。而特殊的某一測(cè)無(wú)上下高速軋道的收費(fèi)站可以通過只有單向連接出入口來(lái)表示，如圖2B。

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

圖3 對(duì)圖1 B的處理

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

圖2 對(duì)圖1 A的處理

圖4 對(duì)圖1 C的處理

2.4 計(jì)算出入口點(diǎn)對(duì)間可能路徑的算法選擇

將路網(wǎng)轉(zhuǎn)化為由虛擬節(jié)點(diǎn)和單向車道組成的圖結(jié)構(gòu)之后，就可以直接使用圖的通用算法進(jìn)行多義性路徑的查找工作。

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

所以Dijkstra算法找出最短路徑的方法無(wú)法適應(yīng)這一特殊規(guī)則。并且其他非遍歷的查找最短路徑的算法也無(wú)法適應(yīng)這一規(guī)則。因此最終的軟件實(shí)現(xiàn)采用深度優(yōu)先遍歷，并在過程中更新從該入口出發(fā)到每一個(gè)頂點(diǎn)的最短距離，以此來(lái)限制遍歷深度的做法。

3 車輛多義性路徑識(shí)別

3.1 高清車牌設(shè)備部署要求

福建省高速公路對(duì)所有存在多義性路徑出入口點(diǎn)對(duì)間的每條競(jìng)爭(zhēng)路段上至少安裝一套高清車牌照識(shí)別設(shè)備，確保能識(shí)別到路徑比例計(jì)算的“公平、公正、科學(xué)、合理”。

競(jìng)爭(zhēng)路段指兩個(gè)存在多異性路徑的收費(fèi)站之間的幾條路徑中不重疊的路段部分。

3.2 多義性路徑標(biāo)示串生成

多義性路徑按照路徑上所有的識(shí)別器，按照從入口到出口的順序?qū)⒆R(shí)別器編號(hào)連接起來(lái)為該路徑的車牌識(shí)別器標(biāo)識(shí)串。而所有多義性路徑均有經(jīng)過的車牌識(shí)別器，并不會(huì)影響到對(duì)車輛多義性路徑的判斷，所以可以不列入車牌識(shí)別器標(biāo)識(shí)串中。

如圖5所示的環(huán)網(wǎng)中，邊上的編號(hào)為安裝的高清車牌識(shí)別器的編號(hào)。從A收費(fèi)站出發(fā)到G收費(fèi)站，共計(jì)有四條多義性路徑，見下表1。其中在所有多義性路徑公共部分的車牌識(shí)別器因?yàn)椴挥绊懢唧w路徑的識(shí)別過程，所以可以不考慮（1001及1009）。

圖5

表1

3．3 車輛行駛軌跡標(biāo)識(shí)串生成

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

如對(duì)車牌藍(lán)閩A00001，在通行時(shí)間范圍內(nèi)有抓拍數(shù)據(jù)的識(shí)別點(diǎn)如下表2：

表2

則車輛行駛軌跡標(biāo)識(shí)串為1002@1004（1001在環(huán)外不計(jì)）。

3.4 車輛行駛軌跡標(biāo)示串與多義性路徑標(biāo)示串的匹配規(guī)則

車輛行駛軌跡標(biāo)示串與多義性路徑標(biāo)示串的匹配規(guī)則為：車輛行駛軌跡標(biāo)示串的每一個(gè)識(shí)別器均在多義性路徑標(biāo)示串中存在且前后順序一致。

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

表3

3.5 不能精確匹配的車輛二次分配規(guī)則

在多義性路徑匹配中能唯一匹配到一條路徑上的流水?dāng)?shù)據(jù)，根據(jù)費(fèi)率路徑在環(huán)內(nèi)部分費(fèi)額占總費(fèi)額的比例直接將環(huán)上部分的金額及車次累加到對(duì)應(yīng)路徑上。

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

表4

二次分配時(shí)對(duì)不能精確匹配的金額及車次進(jìn)行重新分配，分配規(guī)則為按照一次分配的金額及車次的比例，將二次分配的金額及車次分配給對(duì)應(yīng)的路徑。表4經(jīng)過二次分配后最終環(huán)網(wǎng)金額及車次比例見下表5：

表5

4 多義性路徑識(shí)別系統(tǒng)在福建高速的應(yīng)用

目前本系統(tǒng)在福建省高速已有如下應(yīng)用場(chǎng)景：

（1）收費(fèi)收入在各路段公司的拆分

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

（2）估算區(qū)間車流量

根據(jù)多義性路徑車流量比例，將每個(gè)出入口點(diǎn)對(duì)間的車流量分配到不同多義性路徑上，可得不同路徑上的車流量。最終累加所有點(diǎn)對(duì)上的車次獲得高速每一個(gè)區(qū)間的估算車流量。

（3）測(cè)算精確路徑收費(fèi)的影響

目前福建省高速公路收費(fèi)采用按照最低價(jià)路徑收費(fèi)的標(biāo)準(zhǔn)。通過多義性路徑識(shí)別系統(tǒng)可以計(jì)算能夠精確識(shí)別通行路徑的車輛占高速總過車數(shù)的比例，并且通過車輛實(shí)際通行路徑的費(fèi)額可以估算車輛按照實(shí)際通行路徑收費(fèi)對(duì)全省收費(fèi)額的影響。

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

高清車牌識(shí)別器在本系統(tǒng)中起到的僅僅是定位車輛位置及唯一標(biāo)識(shí)車輛信息的作用。如今后車輛均安裝電子車牌后，可替換成使用電子車牌信息讀取設(shè)備，同樣適用于本系統(tǒng)。只需要識(shí)別點(diǎn)的輸入信息換成電子車牌信息讀取器讀取到的車牌信息即可，系統(tǒng)整體結(jié)構(gòu)無(wú)需變化。