高速公路路徑標(biāo)識(shí)站選址優(yōu)化模型與算法研究

王依蘭，陳 新，徐永能

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

0 引言

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

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

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

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

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

1 高速公路標(biāo)識(shí)站選址問(wèn)題分析

1.1 生成樹理論

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

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

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

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

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

1.2 模型假設(shè)

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

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

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

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

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

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

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

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

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

(1)

V85=0.497v限+36.754。

(2)

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

(3)

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

(4)

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

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

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

(5)

(2)約束條件

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

(6)

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

(7)

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

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

(8)

式中N為標(biāo)識(shí)站的數(shù)量。

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

n(T)≤n(G)。

(9)

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

m(T)≤m(G)。

(10)

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

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

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

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

(11)

(3)信息素更新策略

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

(12)

(13)

①Ant-Cycle模型

(14)

②Ant-Density模型

(15)

③Ant-Quantity模型

(16)

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

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

高速公路標(biāo)識(shí)站選址優(yōu)化問(wèn)題算法流程圖如圖2所示。

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

3 算法驗(yàn)證

假設(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所示，其對(duì)應(yīng)關(guān)系，各路段的里程及流量如表1所示。

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

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

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

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

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

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

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

4 結(jié)論

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

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

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