張 杰，王山東，徐志遠，劉恒瑞

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

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

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

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

1 卡口可達性網(wǎng)絡與改進的A*算法

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

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

對于每一條路段，車牌識別系統(tǒng)可以布設為監(jiān)控所有駛入或駛出該路段的車輛信息，同時，車牌識別系統(tǒng)可以對道路卡口進行多流向監(jiān)控，每一個交通治安卡口的多個流向，如十字路口的八個流向均可布設車牌識別系統(tǒng)，如圖1所示。因此，車牌識別系統(tǒng)的監(jiān)控是一種基于流向的監(jiān)控, 可達性網(wǎng)絡為有向圖。因此，在進行可達性網(wǎng)絡構建之前，需要先確認城市車牌識別系統(tǒng)的布設方案。

1.2 卡口可達性網(wǎng)絡

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

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

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

一個有序的二元組

1.3 問題提出

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

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

圖2 起始卡口和目標卡口方向示意圖

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

1.4 改進的A*算法

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

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

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

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

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

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

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

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

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

7）若開放列表為空，輸出路徑庫并判斷起訖卡口間的可達關系，算法結束，否則轉向步驟2）。

2 可達性網(wǎng)絡構建實例分析

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

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

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

圖4 直接可達關系

圖5 唯一直接可達關系

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

圖6 直接可達網(wǎng)絡

圖7 唯一直接可達網(wǎng)絡

3 結 語

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

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

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

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

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

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