王 握，張 晗，任仲山，劉 俊，彭 攀，林 雄

（東南大學(xué) 智能運(yùn)輸系統(tǒng)研究中心，江蘇 南京 210096）

基于關(guān)聯(lián)矩陣的高速公路標(biāo)識(shí)站優(yōu)化選址模型與算法研究

王 握，張 晗，任仲山，劉 俊，彭 攀，林 雄

（東南大學(xué) 智能運(yùn)輸系統(tǒng)研究中心，江蘇 南京 210096）

為了進(jìn)一步研究高速公路路徑識(shí)別中標(biāo)識(shí)站選址問(wèn)題，以路網(wǎng)拓?fù)浣Y(jié)構(gòu)為基礎(chǔ)，采用生成樹(shù)理論對(duì)標(biāo)識(shí)站的優(yōu)化選址進(jìn)行了分析。首先，給出了標(biāo)識(shí)站選址原則，并根據(jù)圖論的相關(guān)理論基礎(chǔ)，提出了標(biāo)識(shí)站的選址定理，確定了標(biāo)識(shí)站的最優(yōu)數(shù)量。然后，建立了標(biāo)識(shí)站選址的優(yōu)化模型，根據(jù)數(shù)量最少和OD反推原則確定了標(biāo)識(shí)站選址的約束條件，通過(guò)流量較小的原則建立標(biāo)識(shí)站最優(yōu)選址的目標(biāo)函數(shù)。同時(shí)，提出了基于關(guān)聯(lián)矩陣實(shí)現(xiàn)大型路網(wǎng)標(biāo)識(shí)站最優(yōu)選址的算法。最后，通過(guò)算例闡述了利用模型解決高速公路標(biāo)識(shí)站選址問(wèn)題的求解過(guò)程。計(jì)算結(jié)果表明，該模型能夠?qū)崿F(xiàn)標(biāo)識(shí)站的最優(yōu)選址，符合高速公路聯(lián)網(wǎng)收費(fèi)中通行費(fèi)精確拆分的實(shí)際需求。

高速公路；路徑識(shí)別；標(biāo)識(shí)站選址；生成樹(shù)；關(guān)聯(lián)矩陣

0 引言

隨著聯(lián)網(wǎng)收費(fèi)的推行和高速公路網(wǎng)的形成，如何實(shí)現(xiàn)車輛路徑的識(shí)別成為高速公路聯(lián)網(wǎng)收費(fèi)的核心問(wèn)題。

在國(guó)外，很少對(duì)高速公路實(shí)行收費(fèi)，或者僅對(duì)極少路段或者少數(shù)車型進(jìn)行收費(fèi)，不存在國(guó)內(nèi)對(duì)整個(gè)高速公路網(wǎng)絡(luò)進(jìn)行封閉式收費(fèi)的情況，因此車輛路徑的識(shí)別研究相對(duì)較少，主要集中在衛(wèi)星定位[1]、ETC電子不停車收費(fèi)上[2-4]。

在國(guó)內(nèi)，早前的研究多是以交通分配的理論方法對(duì)車輛進(jìn)行路徑識(shí)別，如最短路徑法[5]、抽樣調(diào)查法[6]、多路徑容量限制法[7]、布瑞爾分配法[8]等。由于這些方法不能精確地獲取每輛車的行駛路徑，往往容易導(dǎo)致各高速公路公司通行費(fèi)拆分不均，存在較大的爭(zhēng)議。

隨著技術(shù)的發(fā)展，為了實(shí)現(xiàn)通行費(fèi)公平、合理拆分，精確識(shí)別車輛行駛路徑已經(jīng)成為實(shí)現(xiàn)聯(lián)網(wǎng)收費(fèi)的重要方法。目前常用的精確識(shí)別技術(shù)主要有基于車輛牌照的識(shí)別技術(shù)[9]、基于RFID標(biāo)簽的識(shí)別技術(shù)[10]、基于衛(wèi)星定位的路徑識(shí)別技術(shù)[11]，最新的一些精確識(shí)別技術(shù)主要有基于LBS定位[12]、基于RFSIM[13]等。這些方法的基本原理是通過(guò)在二義性路徑的必要路段設(shè)置標(biāo)識(shí)站，來(lái)對(duì)車輛的行駛軌跡進(jìn)行識(shí)別。

在精確識(shí)別的方法中，標(biāo)識(shí)站的合理選址是正確識(shí)別車輛行駛路徑、精確收費(fèi)和通行費(fèi)拆分的關(guān)鍵。如何通過(guò)最少的標(biāo)識(shí)站，在最低的投資成本下，實(shí)現(xiàn)車輛的路徑識(shí)別成為路網(wǎng)管理中的重要工作。高潔等[14]運(yùn)用支撐樹(shù)理論，提出了適合大型路網(wǎng)的標(biāo)識(shí)站選址算法和標(biāo)識(shí)站數(shù)量確定方法，但該方法僅對(duì)單一的環(huán)狀路網(wǎng)進(jìn)行了分析，容易造成重要路段標(biāo)識(shí)站數(shù)量不足或冗余的情況。叢浩哲等[15]采用深度優(yōu)先搜索算法實(shí)現(xiàn)了高速公路標(biāo)識(shí)站的選址和標(biāo)識(shí)站數(shù)量的確定。趙艷紅等[16]提出了網(wǎng)狀路網(wǎng)下的多路徑識(shí)別模型和清分算法。但該方法中標(biāo)識(shí)站的選址沒(méi)有從整個(gè)路網(wǎng)來(lái)考慮，且未考慮交通流量等的影響。蘇曉明等[17]提出了一種基于概率模型的二義性路徑標(biāo)識(shí)站設(shè)置方法，用于解決高速公路網(wǎng)二義性路徑標(biāo)識(shí)站設(shè)置數(shù)量和設(shè)置位置的問(wèn)題。該方法需要獲取任一OD點(diǎn)對(duì)中多條競(jìng)爭(zhēng)性路徑的先驗(yàn)概率，對(duì)于大型路網(wǎng)而言，首先需要調(diào)查計(jì)算得到任一OD點(diǎn)對(duì)之間的競(jìng)爭(zhēng)性路徑，獲取各條競(jìng)爭(zhēng)性路徑的先驗(yàn)概率，前期的調(diào)查工作量巨大，適應(yīng)性差，比較適合應(yīng)用于小型路網(wǎng)標(biāo)識(shí)站的選址問(wèn)題。

上述標(biāo)識(shí)站選址的相關(guān)研究中，能夠得到標(biāo)識(shí)站最優(yōu)設(shè)置數(shù)量和標(biāo)識(shí)站的選址布局方案，但并沒(méi)有考慮到復(fù)雜的收費(fèi)網(wǎng)絡(luò)，在最優(yōu)標(biāo)識(shí)站數(shù)量下，標(biāo)識(shí)站的選址布局方案并不是唯一的，存在布局方案的優(yōu)化選擇問(wèn)題。本文提出了基于關(guān)聯(lián)矩陣的高速公路標(biāo)識(shí)站優(yōu)化選址模型和算法，能夠得到標(biāo)識(shí)站的最優(yōu)選址方案，實(shí)現(xiàn)車輛路徑的精確識(shí)別和保證各高速公路公司之間公平合理地進(jìn)行通行費(fèi)拆分。

1 基于路徑識(shí)別的標(biāo)識(shí)站選址原則

高速公路網(wǎng)可以抽象為連通圖G=(V,E)，其中V(G)表示圖G中的節(jié)點(diǎn)集合，E(G)表示圖G中的路段集合。同時(shí)，p(G)表示圖G中的節(jié)點(diǎn)數(shù)量，q(G)表示圖G中邊的數(shù)量，因此高速公路網(wǎng)中標(biāo)識(shí)站的選址問(wèn)題可以轉(zhuǎn)化為在連通圖中尋找合適的邊設(shè)置標(biāo)識(shí)站的問(wèn)題。對(duì)于大型路網(wǎng)的標(biāo)識(shí)站，其選址方案眾多，應(yīng)考慮如下幾點(diǎn)原則。

1.1 流量最小原則

在路網(wǎng)中，標(biāo)識(shí)站對(duì)經(jīng)過(guò)的每一輛車進(jìn)行身份信息（如車牌、車主等）采集，同時(shí)根據(jù)標(biāo)識(shí)站所在的路段信息和車輛的出入口（收費(fèi)站）信息，從而可以正確標(biāo)定車輛的行駛路徑，即需要對(duì)經(jīng)過(guò)標(biāo)識(shí)站的每一輛車進(jìn)行路徑匹配的計(jì)算。如果標(biāo)識(shí)站所在路段車流量較小，對(duì)這些車輛的路徑進(jìn)行匹配計(jì)算的工作量就相對(duì)較少，同時(shí)當(dāng)標(biāo)識(shí)站出現(xiàn)故障時(shí)，能夠保障不能識(shí)別出行駛路徑的車輛數(shù)較小。綜合考慮，標(biāo)識(shí)站應(yīng)設(shè)置在車流量較小的路段上。

1.2 數(shù)量最少原則

考慮到高速公路的投資和運(yùn)營(yíng)維護(hù)管理，在路網(wǎng)中設(shè)置的標(biāo)識(shí)站數(shù)量應(yīng)盡可能少，以減少標(biāo)識(shí)站的投資建設(shè)成本和后期的運(yùn)營(yíng)維護(hù)管理成本。

1.3 OD反推原則

為了保證通行費(fèi)在各路公司之間的精確拆分，需要獲取每一輛車在路網(wǎng)中的行駛路徑，即能夠根據(jù)路網(wǎng)中標(biāo)識(shí)站采集得到的車輛身份信息，結(jié)合車輛的出入口（收費(fèi)站）信息，能夠唯一確定車輛在路網(wǎng)中的行駛路徑。

2 標(biāo)識(shí)站選址相關(guān)定理和指標(biāo)

結(jié)合圖論中的相關(guān)原理，對(duì)余邊集的概念進(jìn)行了定義：對(duì)于連通圖G而言,T為連通圖G的一棵生成樹(shù)，則在圖G中關(guān)于生成樹(shù)T的余邊集RT= E(G)-E(T )，余邊集RT中所含邊的數(shù)量為number (RT)。

定理1：要對(duì)一個(gè)圖G中的車輛進(jìn)行精確的路徑識(shí)別，標(biāo)識(shí)站應(yīng)該設(shè)置在余邊集RT上，且標(biāo)識(shí)站的最優(yōu)數(shù)量為余邊集中邊的數(shù)量number(RT)[14]。

在路網(wǎng)中，設(shè)置標(biāo)識(shí)站的邊，可以看成是兩條不直接相連的邊，標(biāo)識(shí)站可以看成是圖中新加入的兩個(gè)節(jié)點(diǎn)，如圖1所示，在原路網(wǎng)圖G中加入標(biāo)識(shí)站后組成的新圖G′。

圖1 原圖、生成樹(shù)和加標(biāo)識(shí)站的新圖

因此車輛的行駛路徑可以由OD點(diǎn)和標(biāo)識(shí)站的信息進(jìn)行確定。根據(jù)生成樹(shù)的特性，生成樹(shù)中的路段和路徑是唯一確定的，一條已知OD的路徑是由有標(biāo)識(shí)站的路段和沒(méi)有標(biāo)識(shí)站的路段（生成樹(shù)的邊）組成，或者全部由沒(méi)有標(biāo)識(shí)站的路段組成，因此根據(jù)車輛的OD信息和車輛經(jīng)過(guò)標(biāo)識(shí)站的信息，車輛的路徑是唯一確定的。如果標(biāo)識(shí)站的數(shù)量少于number(RT)，則會(huì)導(dǎo)致任意OD點(diǎn)之間的路徑不能唯一被識(shí)別，同時(shí)，當(dāng)標(biāo)識(shí)站的數(shù)量多于number(RT)，雖然任意OD點(diǎn)之間的路徑能夠唯一識(shí)別，但標(biāo)識(shí)站出現(xiàn)冗余，不是最優(yōu)的投資建設(shè)方案。

定理2：在連通圖G的關(guān)聯(lián)矩陣B中，線性相關(guān)的列向量對(duì)應(yīng)的邊不能組合成生成樹(shù)中的邊。

圖G的生成樹(shù)T的邊數(shù)為p(G)-1，其關(guān)聯(lián)矩陣是秩為p(G)-1的[p(G)-1]×[p(G)-1]矩陣，因此生成樹(shù)T的關(guān)聯(lián)矩陣的行向量線性無(wú)關(guān)，同時(shí)列向量也線性無(wú)關(guān)；在[p(G)-1]×[p(G)-1]的矩陣中，如果存在列向量線性相關(guān)，則關(guān)聯(lián)矩陣的秩一定小于p(G)-1，即存在列向量可以被其他列向量表示的情況，因此該關(guān)聯(lián)矩陣中列向量對(duì)應(yīng)的邊不能構(gòu)成一棵生成樹(shù)，充要條件滿足，定理2成立。

指標(biāo)1：根據(jù)標(biāo)識(shí)站數(shù)量最少和OD反推原則，提出標(biāo)識(shí)站數(shù)指標(biāo)：

指標(biāo)2：根據(jù)流量最少原則，提出流量比指標(biāo)：

式中：RT為路網(wǎng)G中生成樹(shù)T的余邊集；E(G)為路網(wǎng)G中邊的集合；qi為路段i上的交通量。

3 標(biāo)識(shí)站優(yōu)化選址模型的建立

根據(jù)數(shù)量最少和OD反推原則，結(jié)合定理1，標(biāo)識(shí)站的選址問(wèn)題可以轉(zhuǎn)化成求路網(wǎng)G中生成樹(shù)T的余邊集RT的問(wèn)題；根據(jù)流量較少的原則，標(biāo)識(shí)站的選址存在最優(yōu)選址的問(wèn)題。因此標(biāo)識(shí)站優(yōu)化選址模型的數(shù)學(xué)描述如下：通過(guò)尋找路網(wǎng)G中的生成樹(shù)T和其對(duì)應(yīng)的余邊集RT，使得設(shè)置標(biāo)識(shí)站路段（余邊集RT）檢測(cè)到的交通量最小，因此模型可以描述如下。

目標(biāo)函數(shù)為：

式中：G為高速公路的路網(wǎng)拓?fù)鋱D；T為圖G的一棵生成樹(shù)；RT為余邊集；E(T)為生成樹(shù)T的邊的集合，即路網(wǎng)中路段的集合；V(T)為生成樹(shù)T的頂點(diǎn)的集合，即路網(wǎng)收費(fèi)站的集合；q(T)為生成樹(shù)T中邊的數(shù)量； p(T)為生成樹(shù)T中頂點(diǎn)的數(shù)量；qk為第k邊上的車輛數(shù)。

4 標(biāo)識(shí)站優(yōu)化選址算法

標(biāo)識(shí)站選址問(wèn)題，可以等價(jià)于求圖的生成樹(shù)問(wèn)題和組合優(yōu)化問(wèn)題。因此可以采用經(jīng)典的求圖中生成樹(shù)的算法，如Prim算法[18]、Kruskal算法[18]、破圈法和避圈法[19]，來(lái)求解標(biāo)識(shí)站選址的問(wèn)題。但這些算法只能求出圖中的部分生成樹(shù)，即只能得到部分余邊集，因此不一定能夠得到最優(yōu)的標(biāo)識(shí)站選址。同時(shí)，選址算法要求求得所有的選址方案，因此存在求解所有生成樹(shù)的問(wèn)題，對(duì)于大型路網(wǎng)而言，這些方法顯然是不適用的。同時(shí)，對(duì)于存在求解所有生成樹(shù)的算法，如對(duì)偶展開(kāi)樹(shù)算法[14]、廣度優(yōu)先搜索和深度優(yōu)先搜索算法[18]等，容易出現(xiàn)系統(tǒng)的堆棧容量限制，遞歸容易溢出的情況。本文提出了一種較為高效的可行方法，能夠適合于大型路網(wǎng)標(biāo)識(shí)站的優(yōu)化選址問(wèn)題。

4.1 算法的基本思想

模型的求解分為兩部分：第一部分是路網(wǎng)中所有余邊集的求解（標(biāo)識(shí)站的選址方案）；第二部分是最優(yōu)余邊集的選擇（最優(yōu)標(biāo)識(shí)站選址）。

路網(wǎng)圖G中余邊集的求解是通過(guò)尋找圖G中不能組合成生成樹(shù)的邊集組合（關(guān)聯(lián)矩陣的線性相關(guān)列向量組），從而通過(guò)間接得到圖G所對(duì)應(yīng)的所有生成樹(shù)來(lái)求解對(duì)應(yīng)的余邊集。

在余邊集的求解中，得到的余邊集全部滿足模型的約束條件，因此僅需找到滿足目標(biāo)函數(shù)的余邊集即可求得最優(yōu)余邊集。

4.2 算法步驟

Step1：構(gòu)造無(wú)向路網(wǎng)圖G的完全關(guān)聯(lián)矩陣Ar：

Step2：將矩陣Ar中的每一列向量中第一個(gè)值為1的元素的取值改為-1，得到新的完全關(guān)聯(lián)矩陣A1。這樣做的目的是保證完全關(guān)聯(lián)矩陣A的秩為p(G)-1，便于后面的矩陣運(yùn)算；

Step3：刪除完全關(guān)聯(lián)矩陣A1中的任意一行，得到關(guān)聯(lián)矩陣A2，矩陣A2的秩為p(G)-1；

Step4：求關(guān)聯(lián)矩陣A2的極大線性無(wú)關(guān)的列向量組H：β1,β2,…,βm（其中m=p-1），剩下的列向量組K：θ1,θ2,…,θn（其中n=q-p+1），對(duì)矩陣A2的列向量重新排序得新的矩陣 A={β1,β2,…, βm,θ1,θ2,…,θn}；

Step5：找出滿足如下條件的系數(shù)項(xiàng)τ1,τ2,…, τm,δ1,δ2,…,δn，可知系數(shù)不為零的列向量對(duì)應(yīng)的邊不能組合成生成樹(shù)，即可以反推得到所有的生成樹(shù)組合；

Step6：根據(jù)余邊集的定義，可以計(jì)算得到所有生成樹(shù)的余邊集；

Step7：最優(yōu)余邊集的選擇：在余邊集的求解中，得到的余邊集全部滿足模型的約束條件，因此僅需找到滿足目標(biāo)函數(shù)的余邊集。

5 實(shí)例分析

在一個(gè)有11個(gè)節(jié)點(diǎn)、16條邊的路網(wǎng)G中，其節(jié)點(diǎn)集V={1,2,3,4,5,6,7,8,9,10,11}，邊集E= {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}，路網(wǎng)G中邊節(jié)點(diǎn)對(duì)應(yīng)的關(guān)系、各路段的權(quán)值（路段的里程，單位：km）和各路段流量如表1、圖2所示。

表1 路網(wǎng)結(jié)構(gòu)及屬性表

圖2 實(shí)例路網(wǎng)G

根據(jù)完全關(guān)聯(lián)矩陣的定義，得到路網(wǎng)G的完全關(guān)聯(lián)矩陣Ar：

將矩陣Ar中的每一列向量中第一個(gè)值為1的元素的取值改為-1，得到新的完全關(guān)聯(lián)矩陣A1，刪除A1任意第n行數(shù)據(jù)，本文取n=11，得到10× 16、秩為10的矩陣A2。

通過(guò)初等行變換，矩陣A2的極大線性無(wú)關(guān)的列向量組H為邊a,b,c,d,e,g,i,j,l,o對(duì)應(yīng)的列向量，剩下的列向量組K為邊f(xié),h,k,m,n,p對(duì)應(yīng)的列向量，通過(guò)對(duì)矩陣A2的列向量重新排序，得矩陣A：

通過(guò)對(duì)矩陣A的列向量進(jìn)行簡(jiǎn)單的線性運(yùn)算，找出邊f(xié),h,k,m,n,p所對(duì)應(yīng)的列向量之間以及與極大線性無(wú)關(guān)組H中列向量的相互線性關(guān)系。通過(guò)計(jì)算得到了不能組合成生成樹(shù)的邊集組合為6 035種，能夠組成生成樹(shù)的邊集組合為1 703種。根據(jù)余邊集的定義，同理可知余邊集的組合為1 703種，即標(biāo)識(shí)站的選址方案為1 703種。

將根據(jù)上述計(jì)算得到的余邊集組合，代入模型的目標(biāo)函數(shù)中，可以得到不同選址方案中標(biāo)識(shí)站檢測(cè)得到的車流量總和，如圖3所示。

圖3 不同方案下標(biāo)識(shí)站車流量總和

從圖3中可以看出，在1 703種選址方案中，不同選址方案下標(biāo)識(shí)站檢測(cè)得到的車流量相差較大，因此需要對(duì)標(biāo)識(shí)站進(jìn)行最優(yōu)選址。最終通過(guò)比選，其中第861號(hào)方案中標(biāo)識(shí)站數(shù)β=6為最優(yōu)標(biāo)識(shí)站數(shù)，流量比η=27.2%在所有選址方案中最小，即該方案為最優(yōu)選址方案，標(biāo)識(shí)站應(yīng)設(shè)置在路段b,e,i,l,m,p上。

從圖中可以得到，最不理想的標(biāo)識(shí)站選址方案為第1 452號(hào)方案，即標(biāo)識(shí)站設(shè)置在路段a,d,l,h, k,n上，檢測(cè)得到的流量最大，共計(jì)37 420輛，流量比η=49.6%。因此在不考慮同一車輛經(jīng)過(guò)多個(gè)標(biāo)識(shí)站的情況，即37 420輛車在路網(wǎng)中需要進(jìn)行路徑匹配，數(shù)據(jù)計(jì)算量較大。當(dāng)標(biāo)識(shí)站設(shè)置在最優(yōu)余邊集路段b,e,i,l,m,p上時(shí)（如圖4所示），標(biāo)識(shí)站檢測(cè)得到的流量最小，共計(jì)20 490輛，流量比η= 27.2%，相對(duì)最不理想的標(biāo)識(shí)站選址，可以減少對(duì)22.4%的車輛進(jìn)行路徑匹配，數(shù)據(jù)計(jì)算量相對(duì)較少。因此，可以看出標(biāo)識(shí)站最優(yōu)選址能夠最大限度地減少路網(wǎng)中需要進(jìn)行路徑匹配的車輛數(shù)，從而提高整個(gè)路網(wǎng)車輛路徑識(shí)別的效率。

圖4 路網(wǎng)標(biāo)識(shí)站最優(yōu)選址方案

6 結(jié)語(yǔ)

隨著公路建設(shè)投資的加大，為保障各高速公路公司的合法權(quán)益，實(shí)現(xiàn)高速公路網(wǎng)通行費(fèi)的精確拆分和車輛行駛路徑的精確識(shí)別已成為必然的發(fā)展趨勢(shì)。本文所建立的高速公路標(biāo)識(shí)站優(yōu)化選址模型和基于關(guān)聯(lián)矩陣的求解算法符合高速公路聯(lián)網(wǎng)收費(fèi)中通行費(fèi)精確拆分的實(shí)際需求，具有較強(qiáng)的通用性，能夠適用于復(fù)雜的高速公路收費(fèi)網(wǎng)絡(luò)，為高速公路標(biāo)識(shí)站的建設(shè)提供理論和技術(shù)上的支持。然而，在標(biāo)識(shí)站的優(yōu)化選址和數(shù)量選擇上，并沒(méi)有考慮標(biāo)識(shí)站損壞、冗余布局及標(biāo)識(shí)站的識(shí)別準(zhǔn)確率對(duì)車輛運(yùn)行路徑匹配的影響，下一步的研究中將加以考慮。

[1] 周崇華.德國(guó)高速公路卡車收費(fèi)政策實(shí)施及成果分析[J].上海公路，2008（3）：56-60.

[2] 強(qiáng)文萍.高速公路聯(lián)網(wǎng)收費(fèi)系統(tǒng)技術(shù)研究[D].西安：長(zhǎng)安大學(xué)，2002.

[3] 陳愛(ài)英.長(zhǎng)三角高速公路ETC聯(lián)網(wǎng)收費(fèi)管理模式研究[D].南京：東南大學(xué)，2005.

[4] 高祥，張曉升.日本高速公路電子收費(fèi)的管理運(yùn)營(yíng)模式[J].中國(guó)交通信息化，2011（1）：24-27.

[5] CHUK C.Decentralized Control of High Speed Vehicle Strings[J].Transportation Research,1974,8(3):362-383.

[6] BARBIERI E.Stability Analysis of a Class of Interconnected System[J].ASME Journal of Dynamic System,Measurements,Control,1993,115(3):546-551.

[7] 劉海濤，白敬.多路徑容量限制法在公路收費(fèi)系統(tǒng)的應(yīng)用[J].天津城市建設(shè)學(xué)院學(xué)報(bào)，2005，11（3）：179-183.

[8] 陳洪星，孫洋.改進(jìn)的布瑞爾交通分配模型在高速公路路徑識(shí)別問(wèn)題中的應(yīng)用[J].交通理論，2008（12）：37-40.

[9] 楊佳莉.基于車牌識(shí)別的高速公路網(wǎng)多路徑精確識(shí)別研究[D].西安：長(zhǎng)安大學(xué)，2014.

[10] 張昊.基于RFID的浙江省高速公路聯(lián)網(wǎng)收費(fèi)多義性路徑識(shí)別研究[D].長(zhǎng)春：吉林大學(xué)，2009.

[11]王東柱，宋向輝，李亞檬.衛(wèi)星定位不停車收費(fèi)中基于決策圈的路徑識(shí)別方法[J].公路交通科技，2011，28（5）：102-107.

[12]陳良.基于移動(dòng)LBS的高速路網(wǎng)多路徑識(shí)別關(guān)鍵技術(shù)研究[D].成都：電子科技大學(xué)，2013.

[13]李瑩，李鴻，陳藝廷.基于RFSIM路徑識(shí)別的高速公路收費(fèi)系統(tǒng)設(shè)計(jì)[J].現(xiàn)代電子技術(shù)，2014，37（1）：60-63.

[14] 高潔，施其洲.高速公路標(biāo)識(shí)站選址模型與算法研究[J].公路交通科技，2008，25（1）：139-141，145．

[15]叢浩哲，姜杰.基于支撐樹(shù)法的高速公路多路徑識(shí)別問(wèn)題研究[J].交通與運(yùn)輸：學(xué)術(shù)版，2007（7）：80-83.

[16]趙艷紅，劉發(fā)勝，任傳祥，等.網(wǎng)狀高速公路網(wǎng)下的多路徑識(shí)別模型與費(fèi)用清分算法[J].公路，2008（5）：110-114．

[17]蘇曉明，徐東彬.基于概率模型的二義性路徑識(shí)別標(biāo)識(shí)站設(shè)置方法[J].公路交通科技，2013，30（4）：119-123.

[18] 李春萍，陶紅艷，金晶，等.數(shù)據(jù)結(jié)構(gòu)與算法教程[M].北京：清華大學(xué)出版社，2007.

[19] HLADOVERS E.Longitudinal Control of Automated Guideway Transit Vehicles Within Platoons[J].Journal of Dynamic System,Measurements,Control,1978,100(4):301-310.

Optimal Locating Model andAlgorithm of Identification Station of Expressway Based onAssociated Matrix

WANG Wo,ZHANG Han,REN Zhong-shan,LIU Jun,PENG Pan,LIN Xiong
（Intelligent Transport System Research Center of Southeast University,Nanjing 210096,China)

In order to further study the location of identification station in expressway routes identification,based on road network topology,the optimal location of identification station were analyzed by using spanning tree.Firstly,the principles were summarized,and location theorem was put forward according to the relevant theoretical basis of graph theory,and the optimal numbers of identification station were given.Then,optimal locating model of identification station was established,the restrictions of identification station location were determined based on the principle of minimum number and O-D estimation,and objective function was established based on the principle of road section with small flow. And based on associated matrix,the algorithm which was suitable for optimal location of identification station in large-scale road network was proposed.Finally,the solving processes applying the optimal locating model to solve the location of expressway identification station were expounded with a numerical example.The results show that the model achieves good effect on the optimal location of identification station,which meets the actual needs of precise toll allocation in networking toll.

expressway;route identification;location of identification station;spanning tree;associated matrix

U491

A

2095-9931（2015）06-0064-07

10.16503/j.cnki.2095-9931.2015.06.011

2015-07-06

王握（1992—），男，湖南益陽(yáng)人，碩士研究生，主要研究方向?yàn)橹悄芙煌?。E-mail：m15850570887@163.com。