張 杰，王山東，徐志遠(yuǎn)，劉恒瑞

（1.河海大學(xué)地球科學(xué)與工程學(xué)院，江蘇 南京211100）

項目來源：國家自然科學(xué)基金資助項目（41271538）。

目前,對交通可達(dá)性的研究日益成熟，但現(xiàn)有的交通可達(dá)性研究中車牌識別卡口之間的可達(dá)性研究較少。本文從交通可達(dá)性概念出發(fā)，研究車牌識別卡口之間的可達(dá)性關(guān)系，構(gòu)建車牌識別卡口可達(dá)性網(wǎng)絡(luò)［1］。

A*算法作為一種啟發(fā)式算法［2］，在最短路徑搜索中有著重要的應(yīng)用［3］。本文以雙向搜索的A*算法為基礎(chǔ)［4］，針對在卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建中遇到的問題對A*算法進(jìn)行改進(jìn)，用于計算卡口間的可達(dá)關(guān)系，構(gòu)建可達(dá)性網(wǎng)絡(luò)。

1 卡口可達(dá)性網(wǎng)絡(luò)與改進(jìn)的A*算法

1.1 車牌識別系統(tǒng)

車牌識別系統(tǒng)在城市安全管理中有著重要的作用［5］，為了城市的安全管理，需要在城市重要的卡口裝有車牌識別系統(tǒng)。同時，為了節(jié)約車牌識別系統(tǒng)的布設(shè)成本、避免數(shù)據(jù)冗余，不可能對所有的流向?qū)嵤┎荚O(shè)監(jiān)控，實際布設(shè)方案的目標(biāo)是用最少的車牌識別系統(tǒng)獲取路網(wǎng)中盡可能完備的交通信息。

對于每一條路段，車牌識別系統(tǒng)可以布設(shè)為監(jiān)控所有駛?cè)牖蝰偝鲈撀范蔚能囕v信息，同時，車牌識別系統(tǒng)可以對道路卡口進(jìn)行多流向監(jiān)控，每一個交通治安卡口的多個流向，如十字路口的八個流向均可布設(shè)車牌識別系統(tǒng)，如圖1所示。因此，車牌識別系統(tǒng)的監(jiān)控是一種基于流向的監(jiān)控, 可達(dá)性網(wǎng)絡(luò)為有向圖。因此，在進(jìn)行可達(dá)性網(wǎng)絡(luò)構(gòu)建之前，需要先確認(rèn)城市車牌識別系統(tǒng)的布設(shè)方案。

1.2 卡口可達(dá)性網(wǎng)絡(luò)

本文將卡口之間的可達(dá)關(guān)系分為直接可達(dá)關(guān)系、唯一直接可達(dá)關(guān)系和非直接可達(dá)關(guān)系，將可達(dá)性網(wǎng)絡(luò)分為直接可達(dá)網(wǎng)絡(luò)和唯一直接可達(dá)網(wǎng)絡(luò)。

圖1 基于流向布設(shè)的車牌識別系統(tǒng)

設(shè)兩個車牌識別卡口為C1、C2，若其間存在一條路徑P，使得C1從任意方向能夠不通過其他任何卡口到C2，則P稱為直接可達(dá)路徑，稱C1、C2存在直接可達(dá)關(guān)系；若其間有且僅有一條路徑P，使得C1從任意方向能夠不通過其他任何卡口到C2，則P稱為唯一直接可達(dá)路徑，稱C1、C2存在唯一直接可達(dá)關(guān)系；若其間不存在任何一條路徑，使得C1能夠不通過其他任何卡口到達(dá)C2，則稱C1、C2之間為非直接可達(dá)關(guān)系。

一個有序的二元組

1.3 問題提出

卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建的核心在于判斷兩個車牌識別卡口之間的直接可達(dá)關(guān)系和唯一直接可達(dá)關(guān)系，即直接可達(dá)路徑的存在性及唯一性。從本質(zhì)上看，直接可達(dá)路徑的求解相當(dāng)于最短路徑問題，在道路網(wǎng)絡(luò)中確定起點、終點、道路及約束條件，尋找起訖點間符合約束條件的路徑，因此兩個車牌識別卡口間的直接可達(dá)路徑可以借助最短路徑算法求解。

由于直接可達(dá)路徑搜索是在兩個車牌識別卡口之間進(jìn)行的，基本元素為卡口邊，并非單一的道路結(jié)點，所以考慮將最短路徑算法中輸入和搜索過程中的結(jié)點均轉(zhuǎn)換為邊的形式。同時，起訖卡口均為具有方向的邊，起始卡口監(jiān)控多個駛出方向，任何一個方向均可能與目標(biāo)卡口存在直接可達(dá)路徑，因此計算之前需要根據(jù)車道明確起始卡口的駛出方向，而目標(biāo)卡口的監(jiān)控方向即為車輛的駛?cè)敕较?。圖2為車牌識別卡口C1分別作為起始卡口和目標(biāo)卡口時車輛的駛出方向與駛?cè)敕较颉?/p>

圖2 起始卡口和目標(biāo)卡口方向示意圖

這樣，直接可達(dá)路徑的求解問題就轉(zhuǎn)變成了以起始卡口及駛出方向為起點、目標(biāo)卡口為終點，城市道路網(wǎng)絡(luò)為載體，除起訖卡口外其余所有卡口作為障礙物約束條件下，起始卡口與目標(biāo)卡口之間的路徑規(guī)劃問題。

1.4 改進(jìn)的A*算法

由于卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建的核心是車牌識別卡口之間直接可達(dá)路徑的存在性，并非嚴(yán)格的最短路徑，即計算精度要求不高；但針對所有車牌識別卡口各個可能的駛出方向，均要對其余所有卡口進(jìn)行直接可達(dá)路徑的計算，對于復(fù)雜的道路網(wǎng)絡(luò)以及密集布設(shè)的車牌識別卡口，計算量仍舊龐大，需要對問題求解的效率進(jìn)行考慮。

本文采用改進(jìn)的A*算法為基礎(chǔ)，應(yīng)用到直接可達(dá)路徑的求解問題中。針對卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建中遇到的問題對基礎(chǔ)算法進(jìn)行改進(jìn)，用于計算卡口間的可達(dá)關(guān)系。算法的改進(jìn)思想如下：①以圖數(shù)據(jù)結(jié)構(gòu)中的有向邊而非結(jié)點作為輸入元素，采用兩條有向邊末端端點計算啟發(fā)式距離；若結(jié)點搜索過程中遇到車牌識別卡口邊形成的障礙邊，則跳過繼續(xù)運行，即直接可達(dá)路徑不能經(jīng)過其他卡口；②由于判斷直接可達(dá)路徑存在性的同時，需要判斷路徑的數(shù)量，即直接可達(dá)關(guān)系是否為唯一直接可達(dá)關(guān)系，所以在尋找到目標(biāo)卡口后將路徑存儲至路徑庫，算法繼續(xù)運行，以開放列表是否為空作為算法的終止條件；③算法結(jié)束時若路徑庫為空，則尋徑失敗，起訖卡口間為非直接可達(dá)關(guān)系；若路徑庫中存在唯一路徑，則起訖卡口間為唯一直接可達(dá)關(guān)系；若路徑庫中存在多條路徑，則起訖卡口間為直接可達(dá)但非唯一直接可達(dá)關(guān)系。

改進(jìn)的A*算法執(zhí)行步驟如下：

1）初始化，確定起始卡口S=(i, j)和駛出方向，終點卡口T=(u,v)，將起始卡口加入開放列表并計算代價估值F(S)=G(j)+H(j)，設(shè)置父邊p(S)為空。

2）邊選擇，尋找開放列表中代價估計值F最小的有向邊C，彈出作為當(dāng)前邊。

3）判斷C=T是否成立，若成立，則將尋找到的路徑、距離、到達(dá)時間等存入路徑庫，轉(zhuǎn)到步驟7），否則轉(zhuǎn)到步驟4）。

4）將C加入關(guān)閉列表，檢查C的每條相鄰邊N，若N在關(guān)閉列表中為障礙物邊，則跳過；若N不在開放列表中，則轉(zhuǎn)向步驟5）；若N已在開放列表中，則轉(zhuǎn)向步驟6）。

5）將N加入開放列表，并設(shè)置父邊p(N)=C，計算代價估值F(N)。

6）邊松弛，對有向邊N進(jìn)行松弛，即判斷G(C)+w(N)

7）若開放列表為空，輸出路徑庫并判斷起訖卡口間的可達(dá)關(guān)系，算法結(jié)束，否則轉(zhuǎn)向步驟2）。

2 可達(dá)性網(wǎng)絡(luò)構(gòu)建實例分析

以馬鞍山市道路網(wǎng)絡(luò)為例，針對每一個車牌識別卡口及可能的行駛方向，分別以其作為起始卡口，將其余卡口分別作為目標(biāo)卡口，采用改進(jìn)的A*算法計算兩個卡口之間的可達(dá)關(guān)系；將所有存在直接可達(dá)關(guān)系和唯一直接可達(dá)關(guān)系的車牌識別卡口組合，以道路網(wǎng)絡(luò)中所有車牌識別卡口為結(jié)點，以卡口間的可達(dá)關(guān)系為邊，構(gòu)建卡口的直接可達(dá)網(wǎng)絡(luò)和唯一直接可達(dá)網(wǎng)絡(luò)。圖3為馬鞍山市道路網(wǎng)絡(luò)模型及車牌識別系統(tǒng)布設(shè)方案，結(jié)點代表道路交叉口結(jié)點，結(jié)點間的連線代表有向路段，箭頭代表該流向路段為布設(shè)有車牌識別系統(tǒng)的卡口，示例路網(wǎng)中共布設(shè)有17個流向的車牌識別系統(tǒng)。

圖3 道路網(wǎng)絡(luò)模型及車牌識別系統(tǒng)布設(shè)方案

從圖4中可以看出，39號卡口與35號卡口為直接可達(dá)關(guān)系，且存在多條路徑使兩個卡口直接可達(dá)；39號卡口與25號卡口為唯一直接可達(dá)關(guān)系，只存在一條路徑{23,24,11,6｝使得兩個卡口直接可達(dá)，如圖5所示。

圖4 直接可達(dá)關(guān)系

圖5 唯一直接可達(dá)關(guān)系

車牌識別卡口直接可達(dá)網(wǎng)絡(luò)如圖6所示，唯一直接可達(dá)網(wǎng)絡(luò)如圖7所示，從中可以看出任意卡口之間的可達(dá)關(guān)系，如39號卡口是路網(wǎng)的入口點，只能作為可達(dá)關(guān)系中的起始卡口而無法作為目標(biāo)卡口。唯一直接可達(dá)網(wǎng)絡(luò)是直接可達(dá)網(wǎng)絡(luò)的子圖，存在唯一直接可達(dá)關(guān)系的卡口之間能夠用于重建確定性的車輛軌跡。從圖中可以看出，唯一直接可達(dá)關(guān)系的數(shù)量要遠(yuǎn)小于直接可達(dá)關(guān)系。

圖6 直接可達(dá)網(wǎng)絡(luò)

圖7 唯一直接可達(dá)網(wǎng)絡(luò)

3 結(jié) 語

本文從交通可達(dá)性概念出發(fā)研究卡口可達(dá)性，將卡口可達(dá)性網(wǎng)絡(luò)分為直接可達(dá)性網(wǎng)絡(luò)和唯一直接可達(dá)性網(wǎng)絡(luò)。對計算最短路徑的A*算法進(jìn)行改進(jìn)，在城市道路網(wǎng)絡(luò)和車牌識別系統(tǒng)布設(shè)方案的基礎(chǔ)上，用于計算卡口間的可達(dá)關(guān)系，構(gòu)建城市車牌識別卡口可達(dá)性網(wǎng)絡(luò)，對卡口車輛數(shù)據(jù)的深度挖掘有一定的意義。

[1] 約翰斯頓 R J． 人文地理學(xué)詞典[M]．北京: 商務(wù)印書館, 2004

[2] 張海濤, 程蔭杭． 基于A*算法的全局路徑搜索[J]．微計算機信息,2007,23(17):238-239

[3] 劉浩,鮑遠(yuǎn)律． A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J]．計算機仿真,2008(4):253-257

[4] 孟慶浩,劉大維． 基于雙向A*算法的自主車全局路徑規(guī)劃[J]．天津大學(xué)學(xué)報:自然科學(xué)與工程技術(shù)版, 1998(6):747-751

[5] 黃健敏．淺談我國目前車牌識別系統(tǒng)的應(yīng)用研究[J]．山東工業(yè)技術(shù), 2016(1):214-214