基于路段流量相關性的檢測器優化布設*

王殿海 徐程 祁宏生 金盛

(1.吉林大學交通學院，吉林長春130022;2.浙江大學建筑工程學院，浙江杭州310058)

路網交通信息對于長期規劃及短期預測都具有重要意義，路網交通信息的有效獲取是實現交通管理與控制的前提與基礎.目前，固定檢測器依然是獲取路網交通信息的重要手段之一，固定檢測器的布設密度及位置都會直接影響采集交通信息的數量與質量.一方面，密集的檢測器布設策略可以獲取更多的交通信息，實現更加精細化的交通管理;另一方面，由于路網規模的不斷擴大及交通基礎設施的建設成本要求，路網檢測器布設規模受到制約.因此，如何通過固定檢測器的優化布設，用最少成本完成必要交通信息的采集就成為一個重要的研究方向.其核心思想就是:基于路網中各路段交通參數(特別是流量信息)之間存在相關性的事實，利用部分路段交通信息來推算全路網交通信息，以此達到優化檢測器布設的目的，從而節約投資成本.

近年來，國內外許多學者致力于研究通過部分路段檢測器信息獲取全路網交通信息，以達到優化固定檢測器布設的目的.根據獲取信息類型的不同，可將現有研究成果主要分為兩類，第一類是以獲取起訖點(OD)信息為目的的檢測器優化布設方法.在這方面，周晶等［1］提出了交通檢測點合理分布的4種規則，并在已知OD對間有效出行路徑的條件下，建立了確定最佳檢測點的數學規劃模型，提出了有效的啟發式算法;Yang等［2］提出了基于Screen-Line方法的檢測器布設模型及運算法則，分析了在給定檢測器數量條件下如何布設能覆蓋最多的OD對以及能覆蓋所有OD對的檢測器最佳數量及布設位置.Mínguez等［3］提出了不同情況(如完備路徑識別性、最大路徑識別性等)下用于推算OD信息的檢測器最佳布設方法.第二類是以獲取全路網流量信息為目的的檢測器優化布設方法.在這方面，Bianco等［4］提出了一種為獲得全路網交通流量所需檢測器的最少數量及布設位置的方法，并確定了任意給定路網檢測器布設數量的最高及最低限;伍建國等［5］通過對城市道路網基本路段交通流量的相似性分析，建立了路網交通檢測器優化布點的數學模型;Castillo等［6-7］提出了基于貝葉斯網絡的交通流預測方法及避免路徑列舉的檢測器布設方法.這些研究成果為路網固定檢測器優化布設提供了完善的理論支持，但由于上述方法需要較多的先驗信息，且模型較為復雜，難以在實際中應用.

文中以獲取路網流量信息為目標，在考慮路網拓撲結構和出行路徑選擇對檢測器優化布設影響的基礎上，提出了一種基于路段間流量相關性［8］的檢測器優化布設方法，綜合考慮檢測器布設的多種影響因素(重點考慮路徑覆蓋率、道路等級、道路長度以及配套設施對布設結果的影響)，通過多目標優化獲得檢測器最優布設路段組，達到用最少的檢測器獲得全路網流量信息的目的，使之更加符合實際情況.

1 模型的建立

交通路網是一個由若干個路段及路網節點(交叉口)組成的有機整體.由于路網中的車輛在每個交叉口處的流向不同，每個路段的交通量存在差異性.但是，每個路段上的流量都是由經過此路段的所有路徑流量組成.因此，各個路段間的流量會存在一種線性相關性.如果某些路段流量可以由其他路段流量線性表示，那么這些路段就不需布設檢測器，而由其他路段流量推算得出其流量.因此，文中的研究重點就是確定需要布設檢測器的路段集合，這里稱之為關鍵路段集合.

1.1 交通路網描述模型

通常，一個典型的交通網絡可表示為G(V，E).其中V表示路網內節點的集合，V={v1，v2，…，vs}，s為節點數;E表示路網中所有路段的集合，即E= {e1，e2，…，en}，n為路段數;W表示路網中OD對的集合，W={w1，w2，…，wt}，t為OD對數量;R為OD對間所有有效路徑的集合，R={r1，r2，…，rm}，m為有效路徑的數量.這里定義的有效路徑都為簡單路徑［9］，即序列中頂點不重復出現的路徑.R'為優選路徑的集合，即每個OD對間出行費用最小的k條最短路徑的集合，且R'?R.

為了描述路徑及路段之間流量的相關性，采用路徑流量矩陣、路段流量矩陣進行表達.路徑流量矩陣定義為P=(p1，p2，…，pm)，pi(i=1，2，…，m)表示第i條路徑的流量;路段流量矩陣定義為F=(f1，f2，…，fn)，fj(j=1，2，…，n)表示第j條路段的流量;路段鄰接關系矩陣定義為As×s，矩陣中元素axy定義為

式中:ρ為出行費用;x，y=1，2，…，s.

路徑－路段發生矩陣Lm×n定義為

式中:lij=1表示路徑i經過路段j，lij=0表示路徑i不經過路段j.

通過上述路徑－路段發生矩陣的建立，就可以描述路徑流量與路段流量之間的相關性.

1.2 關鍵路段數量的確定

假設關鍵路段(即布設檢測器的路段)的集合為EI，關鍵路段間的流量線性無關.非關鍵路段的集合為ENI，它的流量可通過關鍵路段檢測出的流量推算而得.且E=EI∪ENI，路徑與關鍵路段的發生矩陣為，路徑與非關鍵路段的發生矩陣為，b為關鍵路段的數量.

在線性代數中，對于向量組A:α1，α2，…，αn，如果存在A的部分向量組A0:αj1，αj2，…，αjr，滿足A0線性無關A中任一向量可用A0線性表示，則稱A0是A的一個極大線性無關向量組，簡稱極大無關組.極大無關組所含向量個數r稱為A的秩［10］.通過這個定義可知，由于關鍵路段上的流量線性無關，路徑與關鍵路段的發生矩陣中的列向量線性無關，路徑與非關鍵路段的發生矩陣中的任意列向量均可由中的列向量線性表示，所以關鍵路段的數量就等于路徑－路段發生矩陣的秩，且路徑－路段發生矩陣的任一極大無關組即為此路網的一個關鍵路段組.

因此，將路徑－路段發生矩陣Lm×n進行初等變換，可得到簡化后的矩陣為

則關鍵路段的數量b=rank(L'm×n)即為此路徑－路段發生矩陣的秩，而αi，i=1對應的路段即為關鍵路段，此矩陣的極大無關組即為關鍵路段組.根據線性代數中的知識可知，構成極大無關組的列向量個數是一定的(即秩數)，而矩陣的極大無關組不是唯一的［10］.因此，需要通過一定的規則篩選出所需的唯一極大無關組，那么這個路網中關鍵路段的數量和位置就能夠確定.

1.3 關鍵路段數的影響因素分析

不同的路網規模及拓撲結構、不同的出行路徑選擇行為都會對關鍵路段的數量(即路徑－路段發生矩陣的秩)產生影響.本節通過分析網絡規模、網絡連通性、OD對數量t及路徑數量對關鍵路段數的影響，為路網檢測器優化布設提供參考依據.

1.3.1 網絡規模

網絡規模是指路網內所含節點(交叉口)及路段的數量.對于同一種路網拓撲結構，節點數或者路段數的不同都會對關鍵路段的數量產生影響.為說明問題，此處以表1所示“田”字網絡為例.網絡規模越大，網絡越復雜，路徑的覆蓋率越大，路段間流量的相關性越強，所以關鍵路段與總路段的比例b/ n減小.網絡中的OD對集合為W={v1－v9，v9－v1}.

表1 網絡規模與關鍵路段數的關系Table 1 Effect of network scale on the number of key links

1.3.2 網絡連通性

連通性是圖論中的一個重要概念.如果圖G中存在vx－vy路徑，則認為兩個頂點vx和vy在G中是連通的.如果G中的每對頂點之間都至少存在一條路徑，則圖G是連通的.在圖論中，與頂點vx關聯的邊數稱為vx的度，記為d(vx)［9］.

在交通網絡中，連通性對關鍵路段的數量具有影響，尤其是OD點的連通性對關鍵路段數的影響更為明顯.為說明問題，此處以“田”字網絡為例，如表2所示.對于同一種網絡拓撲結構，當網絡的連通性增強時，特別是當OD點間的連通性增強時，路段間流量的相關性也加強，因此關鍵路段的數量減少，關鍵路段與總路段的比例b/n也相應減小.網絡中的OD對集合為W={v1－v9，v9－v1}.

表2 網絡連通性與關鍵路段數的關系Table 2 Effect of network connectivity on the number of key links

1.3.3 網絡中OD對的數量

在交通網絡中，OD對的數量是個非常重要的因素.OD對越多，可選擇的路徑數量越多，路段之間的相關性越復雜.因此，OD對的數量對關鍵路段的影響尤為重要.對于同一種網絡，當只改變OD對數量時，關鍵路段的數量隨著OD對數量的增加而增加，關鍵路段與總路段的比例b/n也相應增大.此處以表3所示“田”字網絡為例.當OD對數量足夠多時，關鍵路段的數量會趨于某個定值b=19，即此網絡固定檢測器的最佳布設數量為19.

表3 網絡中OD對的數量與關鍵路段數的關系Table 3 Effect of the number of OD pairs on the number of key links

1.3.4 網絡中OD對間路徑的數量

在實際路網中，節點(交叉口)及路段的數量往往很多，道路網的拓撲結構也很復雜，因此每個OD對間的出行路徑會很多.在用此方法給實際路網布設檢測器時，如果將每一個OD對間的所有有效路徑都挑選出來，則計算量太大，運算時間過長.文中考察OD對間選擇的路徑數量對關鍵路段數的影響，目的在于驗證此方法運用于實際路網時是否可以選擇每對OD對間最短的k條路徑，以獲得最優的布設方案.

在選擇路徑時，優先選擇最短路徑.如表4所示，方案1為選擇每個OD對間最短的兩條路徑，方案2為選擇每個OD對間最短的4條路徑，依次遞推，直至選擇所有有效路徑為止.在此列舉的為一“田”字型網絡，OD對的數量為6，有效路徑總數為66.當選擇的路徑較少時，關鍵路段的數量也較少.因為選擇的路徑不能經過網絡中的所有路段，那些未被經過的路段就相當于被剔除掉了.當選擇的路徑數量增加時，關鍵路段的數量也相應增加，最后達到一個定值b=19，此定值即為這個交通網絡的檢測器布設最佳數量.因此，從這個影響因素可以得知，此方法正確及最優的前提是保證路網中的每一條路段都被走過一次.當OD對數量較多時，可以選擇最短的k條路徑進行檢測器布設，減少運算復雜度，也更加貼合實際，k值可根據實際路網情況選取.網絡中的OD對集合為 W=.

表4 路徑數與關鍵路段數的關系Table 4 Effect of path number on the number of key links

1.4 最優關鍵路段組的確定

在確定關鍵路段的數量之后，重點在于如何在眾多關鍵路段組集中確定最優關鍵路段組來布設檢測器，這樣就需要一些規則對關鍵路段組集進行篩選以確定最優的布設方案.在實際路網中布設檢測器時，很多因素都會對最后的布設結果產生影響.例如，對于高等級路段或者高流量的路段，都希望盡量在這些路段上鋪設檢測器直接采集數據，以提高關鍵路段的數據檢測精度;對于附近有配套設施的路段，也希望能盡量在該路段布設檢測器，以便能充分利用現有資源，降低成本［5］.除此之外，道路長度、網絡的拓撲結構、道路的敏感程度、檢測數據的用途等都會對檢測器的布設產生影響.因此，對于最優關鍵路段的選擇，需要考慮多因素的影響.文中提出了考慮路徑覆蓋率、道路等級、道路長度、配套設施4種影響因素的多目標優化模型來確定最優布設方案，也可根據實際情況增加影響因素.

1.4.1 多目標優化模型

最優關鍵路段組的多目標優化函數為

式中:z1為路徑覆蓋率，即所選關鍵路段集經過的路徑數量和與路網中所有路段經過的路徑數量和之比，可以表示為

z2為道路等級比.即所選關鍵路段集中應包含盡量多的高等級路段.以城市路網為例，當關鍵路段^j為快速路或主干路時，γ^j=1;當關鍵路段^j為次干路時，γ^j=0.5;當路段^j為支路時，γ^j=0.

z3為道路長度比，即關鍵路段集中應盡量包含較長的路段，其中L^j為第^j條關鍵路段的長度.

z4為配套設施比，即所選關鍵路段組中含配套設施的路段數量與總關鍵路段數量之比.當關鍵路段^j上有配套設施時，λ^j=1;否則λ^j=0.

1.4.2 多目標優化模型的簡化求解

對于多目標優化問題，如果要求若干目標同時實現最優往往是很難的.目前有很多方法將較復雜的多目標問題轉化為較容易求解的單目標或雙目標問題，例如主要目標法、線性加權和法、分層序列法等.考慮到實際情況，將路徑覆蓋率最大作為主要目標函數，將其他目標函數轉化成約束條件，從而將這個多目標函數轉化成一個較為簡單的單目標函數求解.具體目標函數描述如下:

通過模型的簡化，可以將多目標優化問題轉化為簡單的線性單目標優化問題，并通過遺傳算法、螞蟻算法等進行求解.其中ε1、ε2、ε3的值根據實際路網情況確定.

1.5 由關鍵路段組流量推算全網流量

通過式(9)可以優化得到最佳關鍵路段組，下面以關鍵路段組流量為基礎，分析推算其他路段流量的方法.假設路段流量矩陣為F1×n，路徑流量矩陣為Pm×1，路徑－路段發生矩陣為Lm×n，則

完備性 通過矩陣F1×n，任意非關鍵路段上的流量都可由關鍵路段上的流量推出.

證明 假設b=rank(Lm×n)，則路網中存在b條關鍵路段.為路徑與關鍵路段的發生矩陣，為路徑與非關鍵路段的發生矩陣，;則 Lm×n=［LILNI］.那么

在線性代數中，若α1，α2，…，αr線性無關，α1，α2，…，αr，β線性相關，則β可由α1，α2，…，αr線性表示，且表示法唯一［10］.由此定理可知，關鍵路段的發生矩陣LI中每個列向量都是線性無關的，因此非關鍵路段的發生矩陣LNI中的任一列向量都可由LI中的列向量線性表示，即

則任意非關鍵路段上的流量可表示為

唯一性 不同的關鍵路段組推出的全網流量是唯一的.

證明 假設選取不同的關鍵路段組布設檢測器，則路徑與非關鍵路段的發生矩陣分別為LNI1、LNI2，所對應的路段流量矩陣為F1、F2，根據式(10)可得

假設第1組的發生矩陣L1中的第i(i＜b)列與第j(b＜j＜n)列交換后組成了第2組的關系矩陣L2，由線性代數的定理可知，若α1，α2，…，αr線性無關，α1，α2，…，αr，β線性相關，則β可由α1，α2，…，αr線性表出，且表示法唯一［10］.故第一組中第j條路段的流量Fj可求出且表示唯一，即Fi=PTLI1，Fj=PTLNT1j;同理，交換后的第j條路段的流量F'j可求出且表示唯一，即由于第i條路段與第j條路段流量不變，故

對于LI和LNI中的所有列向量都可進行交換，因此不同的關鍵路段組推算出的全網流量是唯一的.

2 實例分析

下面以Nguyen-Dupuis網絡為例，對提出的模型進行驗證.Nguyen-Dupuis網絡中節點數量s=13，路段數量n=19，OD對集合W={va－vc，va－vd，vb－vc，vb－vd}.各路段的道路等級及道路長度如圖1所示，其中箭頭表示路段車流方向，箭頭上方的數字表示所對應的路段的長度.且每個路段都設有配套設施.

圖1 Nguyen-Dupuis網絡道路等級及路段長度分布圖Fig.1 Link grades and lengths in Nguyen-Dupuis network

2.1 算法步驟

(1)初始化，輸入Nguyen-Dupuis網絡的拓撲結構及OD對的分布情況;

(2)用k最短路算法通過鄰接關系矩陣A13×13選擇OD對間最優的m條路徑，組成優選路徑集合R';

(3)生成路徑－路段發生矩陣Lm×n，并確定關鍵路段的數量b及若干關鍵路段組;

(4)通過多目標優化函數確定最優關鍵路段組;

(5)由關鍵路段測得的流量推算全網流量.

2.2 Nguyen-Dupuis網絡中關鍵路段的確定

在以上步驟中，用k最短路算法選擇每個OD對間路徑時，以出行費用最小為目標可選出m條優選路徑.當k=3時，生成的路徑－路段發生矩陣的秩為8;當k=4時，生成的發生矩陣的秩為10;當k=5時，生成的發生矩陣的秩為10.可以看出，當k=3時，所選路徑無法覆蓋整個網絡，所以關鍵路段的數量較少;當k=4時，所選路徑已可以覆蓋整個網絡，所以Nguyen-Dupuis網絡中關鍵路段的數量b=10.根據路網實際情況，將ε1、ε2、ε3的值分別代入式(9)，并用Matlab編程對優化目標函數進行求解，其結果如表5所示.

表5 優化目標函數求解結果Table 5 Results of optimized objective function

2.3 Nguyen-Dupuis網絡全網流量的推算過程

以方案二的關鍵路段組為例對Nguyen-Dupuis網絡布設檢測器，初始 OD量為{va－vc，va－vd，vb－vc，vb－vd}={40，80，60，20}.圖2所示為關鍵路段分布及全網流量圖，圖中虛線代表布設檢測器的路段，虛線上方的數字為檢測器測得的關鍵路段流量.實線代表未布設檢測器的路段，實線上方的數字為通過關鍵路段測得的流量及路段間流量的相關性推算出的非關鍵路段流量，括號內的數字為實際非關鍵路段的流量.從圖2中可以看出，該方法可以有效地推算未布設檢測器的流量，并具有很高的精度.

圖2 Nguyen-Dupuis網絡中的關鍵路段分布及全網流量圖Fig.2 Key links and link flows in Nguyen-Dupuis network

3 結語

文中主要根據交通路網中路段間流量的線性相關性，提出了一種檢測器優化布設方法，以獲得全網流量.此方法無需OD流量、路徑流量、先驗矩陣等前提假設條件，也不需要過多考慮出行者的路徑選擇行為，模型較為簡單，且在篩選關鍵路段組時考慮了路徑覆蓋率、道路等級、道路長度、配套設施4種影響因素，能有效運用于實際交通路網.文中還以Nguyen-Dupuis網絡為例驗證了方法的有效性.此方法不僅適用于小型網絡，對于大型地圖匹配網絡同樣適用.由于該方法基于路徑－路段流量的相關性假設，主要適用于靜態或穩定交通流狀態下的檢測器優化布設，對于動態變化情況下的檢測器優化布設效果還有待進一步的研究.

［1］ 周晶，盛昭瀚，何建敏，等.交通檢測點分布規則及其數學模型［J］.東南大學學報，1998，28(6):59-63. Zhou Jing，Sheng Zhao-han，He Jian-min，et al.Location rule and modeling of traffic counting points［J］.Journal of Southeast University，1998，28(6):59-63.

［2］ Yang Hai，Yang Chao，Gan Li-ping.Models and algorithms for the screen line-based trafflc-counting location problems［J］.Computers＆Operations Research，2006，33(3):836-858.

［3］ Mínguez R，Sánchez-Cambronero S，Castillo E，et al.Optimal trafflc plate scanning location for OD trip matrix and route estimation in road networks［J］.Transportation Research Part B:Methodological，2010，44(2):282-298.

［4］ Bianco Lucio，Confessor Giuseppe，Pierfrancesco Reverberi.A network based model for traffic sensor location with implications on O/D matrix estimates［J］.Transportation Science，2001，35(1):50-60.

［5］ 伍建國，王峰.城市道路交通數據采集系統檢測器優化布設點研究［J］.公路交通科技，2004，21(2):88-98.Wu Jian-guo，Wang Feng.Study on optimal layout of traffic detector for traffic data collection system in urban area［J］.Journal of Highway and Transportation Research and Development，2004，21(2):88-98.

［6］ Castillo Enrique，Menéndez José María，Sánchez-Cambronero Santos.Predicting traffic flow using Bayesian networks［J］.Transportation Reasearch Part B:Methodological，2008，42(5):482-509.

［7］ Castillo Enrique，Menéndez José María，Sánchez-Cambronero Santos.Traffic estimation and optimal counting location without path enumeration using Bayesian networks［J］.Computer-Aided Civil and Infrastructure Enginee-ring，2008，23(3):189-207.

［8］ Hu Shou-Ren，Peeta Srinivas，Chu Chun-Hsiao.Identification of vehicle sensor locations for link-based network traffic applications［J］.Transportation Reasearch Part B: Methodological，2009，43(8/9):873-894.

［9］ 殷劍宏，吳開亞.圖論及其算法［M］.合肥:中國科學技術大學出版社，2003.

［10］ 戴天時，陳殿友.線性代數［M］.北京:高等教育出版社，2004.