高速公路路徑標識站選址優化模型與算法研究

王依蘭，陳 新，徐永能

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

0 引言

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

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

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

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

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

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

1.1 生成樹理論

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

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

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

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

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

1.2 模型假設

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

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

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

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

1.3 標識站優化布設模型建立

標識站的優化布設問題可以轉化為求大型高速公路路網G中最小生成樹和對應余邊集的求解問題。標識站優化布設模型的數學描述為：通過針對標識站設置主要影響因素之間不同權重比尋找最小目標函數，求解出路網G上的最小生成樹，結合定理1確定標識站的最優布設。

根據研究內容，模型的目標函數如下：

(1)目標函數：

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

(1)

V85=0.497v限+36.754。

(2)

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

(3)

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

(4)

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

為得到模型的最終優化目標，引入權重系數ω1和ω2，且ω1+ω2=1，則模型的最終優化目標函數為：

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

(5)

(2)約束條件

①所求解應滿足樹的要求，約束條件為：

(6)

②生成樹中應不產生任何子回路，約束條件為：

(7)

式中，|P|為集合P中所含圖G的節點個數。

③路段上標識站的設置數量應小于等于余邊集邊的數量，約束條件表示為：

(8)

式中N為標識站的數量。

④路網G中應包含所有生成樹的邊，約束條件表示為：

n(T)≤n(G)。

(9)

⑤路網G中應含有所有生成樹的節點，約束條件表示為：

m(T)≤m(G)。

(10)

2 標識站布局優化選址算法

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

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

(2)狀態轉移概率函數

(11)

(3)信息素更新策略

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

(12)

(13)

①Ant-Cycle模型

(14)

②Ant-Density模型

(15)

③Ant-Quantity模型

(16)

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

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

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

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

3 算法驗證

假設路網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},路網A如圖3所示，其對應關系，各路段的里程及流量如表1所示。

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

圖3 算例路網AFig.3 An example of road network A

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

表2 計算結果Tab.2 Calculation result

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

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

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

4 結論

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

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

圖4 適應度進化曲線Fig. 4 Fitness evolution curve