王依蘭，陳 新，徐永能

(南京理工大學(xué) 自動化學(xué)院，江蘇 南京 210094)

0 引言

近年來高速公路不斷建設(shè)發(fā)展，高速公路網(wǎng)結(jié)構(gòu)變得錯綜復(fù)雜。隨著省界收費站的拆除和聯(lián)網(wǎng)收費工作的推進，高速公路結(jié)算路網(wǎng)越來越龐大，環(huán)狀路網(wǎng)、嵌套環(huán)路等情況越來越多，相同的起終點(即OD點)有多條不同的路徑可以選擇，這就導(dǎo)致路徑多義性問題產(chǎn)生[1]。路徑多義性成為高速通行費用合理拆分的阻礙，進而影響高速公路的整體效能和服務(wù)水平的提高。為保證高速公路通行費用的合理拆分，確保道路投資者與使用者利益，車輛路徑識別成為現(xiàn)階段高速公路聯(lián)網(wǎng)收費的關(guān)鍵問題，而車輛的路徑信息識別，標識站的合理選址布局是其中關(guān)鍵的一環(huán)。標識站選址優(yōu)化研究不僅能實現(xiàn)對車輛路徑信息的精準識別，有利于道路投資者和使用者對通行費用無異議，同時有助于節(jié)省標識站的投資建設(shè)成本，以提高標識站的實用性和經(jīng)濟性。

早期高速公路車輛路徑識別方法主要采取概率識別方法，如最短路徑法、抽樣調(diào)查法、布瑞爾分配法等[2-3]。隨著高速公路的迅猛發(fā)展，基于概率的路徑識別方案已不能滿足道路投資者和使用者的利益。為實現(xiàn)高速公路通行費用公平、合理拆分，車輛精準路徑識別是其關(guān)鍵。目前，高速公路多義性路徑精準識別技術(shù)主要包括衛(wèi)星導(dǎo)航(GPS、北斗)[4]、射頻識別(RFID)技術(shù)(433 MHz射頻技術(shù)、5.8 GHz專用短程通信[5-6]等)、車牌識別[7]、車輛電子標識[8]等方法。這些方法實現(xiàn)的基礎(chǔ)是依托于高速公路網(wǎng)中多義性的路段設(shè)置標識站，通過標識站與車輛之間信息的交互，達到識別車輛信息的目的。

標識站的設(shè)置主要是為了標記車輛在高速公路中的路徑行駛信息并及時上傳至高速公路收費站，從而使車輛在到達收費站后，收費系統(tǒng)能及時準確的還原車輛實際行駛的路徑，從而確定車輛的通行費用，并為通行費用的拆分提供依據(jù)。因此標識站的選址受多種因素的影響，如路段流量、建設(shè)成本、標識站識別可靠度和環(huán)境等。叢浩哲等[9]提出了基于深度優(yōu)先搜索算法的標識站選址和數(shù)量的確定。但該方法容易造成缺?；蛘叨褩５那闆r。高潔等[10]提出了基于支撐樹理論的大型路網(wǎng)的標識站選址算法，但該方法僅對單一的封閉環(huán)狀路網(wǎng)進行了分析，對于嵌套路網(wǎng)的布局可能會造成重要路段標識站數(shù)量不足或冗余的現(xiàn)象。蔣貴川等[11]分析了冗余標識站布局與系統(tǒng)整體可靠性之間關(guān)系的研究，提出了簡單重復(fù)布局是標識站數(shù)量最小的布局理念，但并未考慮標識站的影響因素。曲建華等[12]采用最小生成樹理論對河南高速公路標識站設(shè)置進行研究。蘇曉明等[13]提出了基于概率模型的標識站設(shè)置方法，并提出了多階段多候選的標識站選址方法。孫榮[14]通過遺傳算法確定標識站的最優(yōu)布局，并為提高系統(tǒng)的可靠性，提出了分布式布局和簡單重復(fù)布局的方法。王握等[15]分析了標識站選址的影響因素與選址條件，采用關(guān)聯(lián)矩陣算法優(yōu)化了高速公路標識站選址模型。

目前有關(guān)標識站選址布局的相關(guān)文獻中，并沒有考慮復(fù)雜的收費路網(wǎng)，且在最優(yōu)標識站的數(shù)量下，標識站的選址布局存在方案并不唯一，存在布局方案的優(yōu)化問題。標識站的選址應(yīng)在以標識站設(shè)置數(shù)量最小的前提下，達到車輛實際行駛路線的無模糊性，同時標識站的選址應(yīng)以檢測多義性路段車流量最小為目標，降低標識站工作負荷。

因此，在已有研究的基礎(chǔ)上，同時考慮到車流量和路段權(quán)值對標識站選址的影響，本研究采用生成樹理論確定高速公路標識站的數(shù)量和選址位置，由于生成樹的不唯一性，導(dǎo)致余邊集的組成也存在多種可能，因此標識站位置選址方案并不唯一。通過以多義性路段權(quán)值最小和車流量最大為優(yōu)化目標，構(gòu)建了標識站選址優(yōu)化模型。同時考慮到蟻群算法在路徑搜索問題中具有很大的優(yōu)勢，因此本研究利用蟻群算法求解模型。

1 高速公路標識站選址問題分析

1.1 生成樹理論

高速公路車輛的實際行駛路徑可以根據(jù)高速公路的出入口和標識站的信息確定。根據(jù)圖論中樹的特點，在樹中路徑不具有環(huán)路，路段和路徑具有唯一性，只要把圖變成樹，便可消除存在歧義的路徑。

因此高速公路網(wǎng)可以抽象為連通圖G=(V,E)，其中V(G)為連通圖G中節(jié)點集合，V(G)={V1,V2,…,Vn}；E(G)為連通圖G中路段集合，E(G)={E1,E2,…,Em}，若邊ek的頂點為i和j，則記ek=(i,j)；用n(G)為節(jié)點的個數(shù)，m(G)為邊的數(shù)量。高速公路網(wǎng)中標識站數(shù)量問題可以轉(zhuǎn)化為求解連通圖中標識站的問題。對于大型高速路網(wǎng)中，標識站數(shù)量的確定可以結(jié)合圖論相關(guān)知識分析。

根據(jù)圖論中生成樹的相關(guān)原理。余邊集：連通圖G，若T為連通圖G的一棵生成樹，RG為生成樹的余邊集，m(RG)為余邊集RG中所含邊的數(shù)量，且m(RG)=m(G)-n(G)+1[16]。

定理1：對高速公路網(wǎng)G=(V,E)中的車輛進行精準路徑識別，標識站的位置應(yīng)設(shè)置在余邊集RG上，且標識站的最佳數(shù)量為余邊集邊的數(shù)量m(RG)。

給定圖1的連通圖G，它的生成樹的邊數(shù)為n(G)-1，節(jié)點數(shù)為n，標識站設(shè)立在余邊集上，即：生成樹的邊數(shù)m(T)=5-1=4，標識站的數(shù)量為m(RG)=6-4=2，布設(shè)(非最優(yōu)標識站的布設(shè))在圖G的余邊集上。

1.2 模型假設(shè)

在采用圖論生成樹理論對標識站數(shù)量問題進行分析后，確定來標識站的設(shè)置數(shù)量及標識站的布設(shè)方案，結(jié)合數(shù)學(xué)建模中的優(yōu)化理論，即可建立高速公路標識站的優(yōu)化布局模型，但因標識站的設(shè)置需考慮到多種因素的影響，模型建立及求解過程相對復(fù)雜，為簡化其問題分析，需要在模型建立之處做出模型假設(shè)。

(1)高速公路的交通路網(wǎng)為互通立交，即V(G)表示為高速公路與高速公路之間的交點集合。

(2)E(G)為路網(wǎng)連通圖G中的路段，設(shè)E1(G)為有標識站的路段；E2(G)為未設(shè)標識站的路段，則E1(G)∪E2(G)=E(G)且E1(G)∩E2(G)=?。

(3)標識站的設(shè)置僅考慮其時間因素和路段車流量因素。

1.3 標識站優(yōu)化布設(shè)模型建立

標識站的優(yōu)化布設(shè)問題可以轉(zhuǎn)化為求大型高速公路路網(wǎng)G中最小生成樹和對應(yīng)余邊集的求解問題。標識站優(yōu)化布設(shè)模型的數(shù)學(xué)描述為：通過針對標識站設(shè)置主要影響因素之間不同權(quán)重比尋找最小目標函數(shù)，求解出路網(wǎng)G上的最小生成樹，結(jié)合定理1確定標識站的最優(yōu)布設(shè)。

根據(jù)研究內(nèi)容，模型的目標函數(shù)如下：

(1)目標函數(shù)：

道路運行速度的特征值可以體現(xiàn)車輛在道路上的整體運行概況[17]，由

(1)

V85=0.497v限+36.754。

(2)

則求解最少時間的出行者路徑選擇可轉(zhuǎn)化為求解最小路段里程的目標函數(shù)。

(3)

在保證路網(wǎng)車輛路徑全覆蓋的原則下，為減少標識站識別車輛路徑信息的工作量，同時也可預(yù)防標識站出現(xiàn)故障時，不能識別行駛路徑的車輛數(shù)較小，建立基于車流量因素的目標函數(shù)如下：

(4)

式中，Tij為邊(i,j)路段的行駛時間；V85為道路運行速度的特征指標；v限為高速公路的限制速度；xij為生成樹(i,j)的邊；lij為節(jié)點i到節(jié)點j之間路段的里程；qij為節(jié)點i到節(jié)點j之間路段上的車流量。

為得到模型的最終優(yōu)化目標，引入權(quán)重系數(shù)ω1和ω2，且ω1+ω2=1，則模型的最終優(yōu)化目標函數(shù)為：

minf=ω1f1(x)+ω2f2(x)。

(5)

(2)約束條件

①所求解應(yīng)滿足樹的要求，約束條件為：

(6)

②生成樹中應(yīng)不產(chǎn)生任何子回路，約束條件為：

(7)

式中，|P|為集合P中所含圖G的節(jié)點個數(shù)。

③路段上標識站的設(shè)置數(shù)量應(yīng)小于等于余邊集邊的數(shù)量，約束條件表示為：

(8)

式中N為標識站的數(shù)量。

④路網(wǎng)G中應(yīng)包含所有生成樹的邊，約束條件表示為：

n(T)≤n(G)。

(9)

⑤路網(wǎng)G中應(yīng)含有所有生成樹的節(jié)點，約束條件表示為：

m(T)≤m(G)。

(10)

2 標識站布局優(yōu)化選址算法

為提高搜索效率，本研究采用的蟻群算法(Ant System, AS)來求解標識站的選址優(yōu)化問題[17-19]，并根據(jù)模型特點對信息素的更新做出相適應(yīng)的改進。模型求解過程如下：

(1)參數(shù)信息初始化。設(shè)置螞蟻數(shù)目m,信息素系數(shù)α,期望啟發(fā)系數(shù)β,信息素揮發(fā)系數(shù)ρ,Nc為循環(huán)次數(shù)。

(2)狀態(tài)轉(zhuǎn)移概率函數(shù)

(11)

(3)信息素更新策略

在搜索最優(yōu)路徑時，當m個螞蟻在移動的過程中，每條邊都留下了信息素。設(shè)Δτij為m個螞蟻完成一次搜索后邊(i,j)上信息素增量，則路徑eij上信息素含量在邊(i,j)刻按照如下進行更新調(diào)整：

(12)

(13)

①Ant-Cycle模型

(14)

②Ant-Density模型

(15)

③Ant-Quantity模型

(16)

式中，Q為單個螞蟻所留軌跡強度常數(shù)；fk為第k個螞蟻在當前循環(huán)中所得目標函數(shù)的值；qij為邊(i,j)上的車流量。

(4)每個螞蟻依次進行Ncmax次循環(huán)后，便可得到問題的一個最優(yōu)解。

高速公路標識站選址優(yōu)化問題算法流程圖如圖2所示。

圖2 高速公路標識站選址優(yōu)化問題算法流程圖Fig.2 Flowchart of algorithm of optimal location of expressway path identification station

3 算法驗證

假設(shè)路網(wǎng)A，其中m(A)=11，n(G)=16,V={1,2,3,4,5,6,7,8,9,10},E={e1,e2,…e16,e1,e2,…e15},路網(wǎng)A如圖3所示，其對應(yīng)關(guān)系，各路段的里程及流量如表1所示。

取參數(shù)K=50，α=1，β=5，ρ=0.1，Nc=0，Ncmax=200。針對不同ω1和ω2，在滿足約束條件，對上述模型在MATLAB中進行優(yōu)化計算，得到最優(yōu)解。計算結(jié)果如表2所示。

圖3 算例路網(wǎng)AFig.3 An example of road network A

表1 路段里程及車流量Tab.1 Section mileage and traffic volume

表2 計算結(jié)果Tab.2 Calculation result

根據(jù)所得的最優(yōu)解，圖G最小生成樹路徑以及標識站的分布如表3所示。

影響標識站的因素有很多，本研究重點討論的基于出行時間的路徑選擇對標識站選址的影響和基于標識站最少識別車輛數(shù)標識站影響因素，通過分配不同的權(quán)重比，得出不同權(quán)重比下標識站的最優(yōu)選址。

根據(jù)上述模型在MATLAB求解之下得到最小目標函數(shù)，迭代次數(shù)如圖4所示。該算法在進行到50次時，目標函數(shù)迭代到了最優(yōu)值，具有快速尋優(yōu)能力。其次在進行多目標優(yōu)化時，根據(jù)所選擇權(quán)值的不同，所得到的最優(yōu)解也是不同的。

4 結(jié)論

本研究通過采用基于生成樹-蟻群算法對高速公路標識站選址問題進行分析研究，得到優(yōu)化后路網(wǎng)中標識站的選址分布，同時通過對比標識站影響因素之間的不同占比，得出不同影響因素的占比不同，標識站的選址也是不同的。模型具有較強的通用性，能滿足通行費用精確拆分的實際需要。然而，本研究未考慮標識站建設(shè)成本、老化、損壞及識別精度等其他因素對標識站選址影響的問題，下一步的研究中將加以考慮。

表3 圖G最小生成樹路徑以及標識站的分布Tab.3 Layouts of figure G minimum spanning tree path and identification stations

圖4 適應(yīng)度進化曲線Fig. 4 Fitness evolution curve