基于關聯矩陣的高速公路標識站優化選址模型與算法研究

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

（東南大學 智能運輸系統研究中心，江蘇 南京 210096）

基于關聯矩陣的高速公路標識站優化選址模型與算法研究

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

（東南大學 智能運輸系統研究中心，江蘇 南京 210096）

為了進一步研究高速公路路徑識別中標識站選址問題，以路網拓撲結構為基礎，采用生成樹理論對標識站的優化選址進行了分析。首先，給出了標識站選址原則，并根據圖論的相關理論基礎，提出了標識站的選址定理，確定了標識站的最優數量。然后，建立了標識站選址的優化模型，根據數量最少和OD反推原則確定了標識站選址的約束條件，通過流量較小的原則建立標識站最優選址的目標函數。同時，提出了基于關聯矩陣實現大型路網標識站最優選址的算法。最后，通過算例闡述了利用模型解決高速公路標識站選址問題的求解過程。計算結果表明，該模型能夠實現標識站的最優選址，符合高速公路聯網收費中通行費精確拆分的實際需求。

高速公路；路徑識別；標識站選址；生成樹；關聯矩陣

0 引言

隨著聯網收費的推行和高速公路網的形成，如何實現車輛路徑的識別成為高速公路聯網收費的核心問題。

在國外，很少對高速公路實行收費，或者僅對極少路段或者少數車型進行收費，不存在國內對整個高速公路網絡進行封閉式收費的情況，因此車輛路徑的識別研究相對較少，主要集中在衛星定位[1]、ETC電子不停車收費上[2-4]。

在國內，早前的研究多是以交通分配的理論方法對車輛進行路徑識別，如最短路徑法[5]、抽樣調查法[6]、多路徑容量限制法[7]、布瑞爾分配法[8]等。由于這些方法不能精確地獲取每輛車的行駛路徑，往往容易導致各高速公路公司通行費拆分不均，存在較大的爭議。

隨著技術的發展，為了實現通行費公平、合理拆分，精確識別車輛行駛路徑已經成為實現聯網收費的重要方法。目前常用的精確識別技術主要有基于車輛牌照的識別技術[9]、基于RFID標簽的識別技術[10]、基于衛星定位的路徑識別技術[11]，最新的一些精確識別技術主要有基于LBS定位[12]、基于RFSIM[13]等。這些方法的基本原理是通過在二義性路徑的必要路段設置標識站，來對車輛的行駛軌跡進行識別。

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

上述標識站選址的相關研究中，能夠得到標識站最優設置數量和標識站的選址布局方案，但并沒有考慮到復雜的收費網絡，在最優標識站數量下，標識站的選址布局方案并不是唯一的，存在布局方案的優化選擇問題。本文提出了基于關聯矩陣的高速公路標識站優化選址模型和算法，能夠得到標識站的最優選址方案，實現車輛路徑的精確識別和保證各高速公路公司之間公平合理地進行通行費拆分。

1 基于路徑識別的標識站選址原則

高速公路網可以抽象為連通圖G=(V,E)，其中V(G)表示圖G中的節點集合，E(G)表示圖G中的路段集合。同時，p(G)表示圖G中的節點數量，q(G)表示圖G中邊的數量，因此高速公路網中標識站的選址問題可以轉化為在連通圖中尋找合適的邊設置標識站的問題。對于大型路網的標識站，其選址方案眾多，應考慮如下幾點原則。

1.1 流量最小原則

在路網中，標識站對經過的每一輛車進行身份信息（如車牌、車主等）采集，同時根據標識站所在的路段信息和車輛的出入口（收費站）信息，從而可以正確標定車輛的行駛路徑，即需要對經過標識站的每一輛車進行路徑匹配的計算。如果標識站所在路段車流量較小，對這些車輛的路徑進行匹配計算的工作量就相對較少，同時當標識站出現故障時，能夠保障不能識別出行駛路徑的車輛數較小。綜合考慮，標識站應設置在車流量較小的路段上。

1.2 數量最少原則

考慮到高速公路的投資和運營維護管理，在路網中設置的標識站數量應盡可能少，以減少標識站的投資建設成本和后期的運營維護管理成本。

1.3 OD反推原則

為了保證通行費在各路公司之間的精確拆分，需要獲取每一輛車在路網中的行駛路徑，即能夠根據路網中標識站采集得到的車輛身份信息，結合車輛的出入口（收費站）信息，能夠唯一確定車輛在路網中的行駛路徑。

2 標識站選址相關定理和指標

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

定理1：要對一個圖G中的車輛進行精確的路徑識別，標識站應該設置在余邊集RT上，且標識站的最優數量為余邊集中邊的數量number(RT)[14]。

在路網中，設置標識站的邊，可以看成是兩條不直接相連的邊，標識站可以看成是圖中新加入的兩個節點，如圖1所示，在原路網圖G中加入標識站后組成的新圖G′。

圖1 原圖、生成樹和加標識站的新圖

因此車輛的行駛路徑可以由OD點和標識站的信息進行確定。根據生成樹的特性，生成樹中的路段和路徑是唯一確定的，一條已知OD的路徑是由有標識站的路段和沒有標識站的路段（生成樹的邊）組成，或者全部由沒有標識站的路段組成，因此根據車輛的OD信息和車輛經過標識站的信息，車輛的路徑是唯一確定的。如果標識站的數量少于number(RT)，則會導致任意OD點之間的路徑不能唯一被識別，同時，當標識站的數量多于number(RT)，雖然任意OD點之間的路徑能夠唯一識別，但標識站出現冗余，不是最優的投資建設方案。

定理2：在連通圖G的關聯矩陣B中，線性相關的列向量對應的邊不能組合成生成樹中的邊。

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

指標1：根據標識站數量最少和OD反推原則，提出標識站數指標：

指標2：根據流量最少原則，提出流量比指標：

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

3 標識站優化選址模型的建立

根據數量最少和OD反推原則，結合定理1，標識站的選址問題可以轉化成求路網G中生成樹T的余邊集RT的問題；根據流量較少的原則，標識站的選址存在最優選址的問題。因此標識站優化選址模型的數學描述如下：通過尋找路網G中的生成樹T和其對應的余邊集RT，使得設置標識站路段（余邊集RT）檢測到的交通量最小，因此模型可以描述如下。

目標函數為：

式中：G為高速公路的路網拓撲圖；T為圖G的一棵生成樹；RT為余邊集；E(T)為生成樹T的邊的集合，即路網中路段的集合；V(T)為生成樹T的頂點的集合，即路網收費站的集合；q(T)為生成樹T中邊的數量； p(T)為生成樹T中頂點的數量；qk為第k邊上的車輛數。

4 標識站優化選址算法

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

4.1 算法的基本思想

模型的求解分為兩部分：第一部分是路網中所有余邊集的求解（標識站的選址方案）；第二部分是最優余邊集的選擇（最優標識站選址）。

路網圖G中余邊集的求解是通過尋找圖G中不能組合成生成樹的邊集組合（關聯矩陣的線性相關列向量組），從而通過間接得到圖G所對應的所有生成樹來求解對應的余邊集。

在余邊集的求解中，得到的余邊集全部滿足模型的約束條件，因此僅需找到滿足目標函數的余邊集即可求得最優余邊集。

4.2 算法步驟

Step1：構造無向路網圖G的完全關聯矩陣Ar：

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

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

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

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

Step6：根據余邊集的定義，可以計算得到所有生成樹的余邊集；

Step7：最優余邊集的選擇：在余邊集的求解中，得到的余邊集全部滿足模型的約束條件，因此僅需找到滿足目標函數的余邊集。

5 實例分析

在一個有11個節點、16條邊的路網G中，其節點集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}，路網G中邊節點對應的關系、各路段的權值（路段的里程，單位：km）和各路段流量如表1、圖2所示。

表1 路網結構及屬性表

圖2 實例路網G

根據完全關聯矩陣的定義，得到路網G的完全關聯矩陣Ar：

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

通過初等行變換，矩陣A2的極大線性無關的列向量組H為邊a,b,c,d,e,g,i,j,l,o對應的列向量，剩下的列向量組K為邊f,h,k,m,n,p對應的列向量，通過對矩陣A2的列向量重新排序，得矩陣A：

通過對矩陣A的列向量進行簡單的線性運算，找出邊f,h,k,m,n,p所對應的列向量之間以及與極大線性無關組H中列向量的相互線性關系。通過計算得到了不能組合成生成樹的邊集組合為6 035種，能夠組成生成樹的邊集組合為1 703種。根據余邊集的定義，同理可知余邊集的組合為1 703種，即標識站的選址方案為1 703種。

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

圖3 不同方案下標識站車流量總和

從圖3中可以看出，在1 703種選址方案中，不同選址方案下標識站檢測得到的車流量相差較大，因此需要對標識站進行最優選址。最終通過比選，其中第861號方案中標識站數β=6為最優標識站數，流量比η=27.2%在所有選址方案中最小，即該方案為最優選址方案，標識站應設置在路段b,e,i,l,m,p上。

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

圖4 路網標識站最優選址方案

6 結語

隨著公路建設投資的加大，為保障各高速公路公司的合法權益，實現高速公路網通行費的精確拆分和車輛行駛路徑的精確識別已成為必然的發展趨勢。本文所建立的高速公路標識站優化選址模型和基于關聯矩陣的求解算法符合高速公路聯網收費中通行費精確拆分的實際需求，具有較強的通用性，能夠適用于復雜的高速公路收費網絡，為高速公路標識站的建設提供理論和技術上的支持。然而，在標識站的優化選址和數量選擇上，并沒有考慮標識站損壞、冗余布局及標識站的識別準確率對車輛運行路徑匹配的影響，下一步的研究中將加以考慮。

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

[2] 強文萍.高速公路聯網收費系統技術研究[D].西安：長安大學，2002.

[3] 陳愛英.長三角高速公路ETC聯網收費管理模式研究[D].南京：東南大學，2005.

[4] 高祥，張曉升.日本高速公路電子收費的管理運營模式[J].中國交通信息化，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] 劉海濤，白敬.多路徑容量限制法在公路收費系統的應用[J].天津城市建設學院學報，2005，11（3）：179-183.

[8] 陳洪星，孫洋.改進的布瑞爾交通分配模型在高速公路路徑識別問題中的應用[J].交通理論，2008（12）：37-40.

[9] 楊佳莉.基于車牌識別的高速公路網多路徑精確識別研究[D].西安：長安大學，2014.

[10] 張昊.基于RFID的浙江省高速公路聯網收費多義性路徑識別研究[D].長春：吉林大學，2009.

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

[12]陳良.基于移動LBS的高速路網多路徑識別關鍵技術研究[D].成都：電子科技大學，2013.

[13]李瑩，李鴻，陳藝廷.基于RFSIM路徑識別的高速公路收費系統設計[J].現代電子技術，2014，37（1）：60-63.

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

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

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

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

[18] 李春萍，陶紅艷，金晶，等.數據結構與算法教程[M].北京：清華大學出版社，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—），男，湖南益陽人，碩士研究生，主要研究方向為智能交通。E-mail：m15850570887@163.com。