農(nóng)村公路治超站選址與治超車路徑優(yōu)化研究

蔣勁羽，趙 旭，李鋮鈺，楊忠振

(1.大連海事大學(xué) 交通運輸工程學(xué)院，遼寧 大連 116000；2.寧波大學(xué) 海運學(xué)院，浙江 寧波 315800)

0 引 言

目前，對農(nóng)村公路的超載治理主要由超載檢測站即治超站完成。設(shè)置在貨車流量較大且超載現(xiàn)象嚴(yán)重的路段上的治超站，通過對過往的貨車進行稱重檢測，發(fā)現(xiàn)超載行為的貨車，對其進行相應(yīng)的處罰。由于農(nóng)村公路的路網(wǎng)連接復(fù)雜，貨車在農(nóng)村公路上具有豐富的走行路線，導(dǎo)致超載貨車多會繞行躲避治超站。因此，固定治超的模式很難有效的截獲超載貨車，治超效率和治超效果較差。為了提高治超效率和治超效果，筆者提出了依托固定治超站實施移動治超的工作模式，即設(shè)置一定數(shù)量的治超站，治超車以治超站為基地在其周邊農(nóng)村公路上巡游，捕獲超載車輛，從而實施移動治超。

國內(nèi)外研究者對超載治理做了一定研究。S.BAGUI等[1]提出超載對路面造成的額外損害需要超載運輸業(yè)者來補償；E.MORENO-QUINTERO等[2]同時考慮運輸業(yè)者的運輸成本和超載管理者的運營成本，建立了管理者運營方案決策和運輸業(yè)者運輸方案選擇的雙層規(guī)劃模型；李忠奎等[3]分析了企業(yè)利潤與運輸價格、運輸成本、超載罰款等變量之間的互動關(guān)系及企業(yè)獲得最大利潤的條件，對中國治理超載超限運輸提出了解決方案和具體的政策建議；陳蔭三[4]提出了以貨車實際總重和軸載限額為依據(jù)對貨車實施計重收費的思路，采用區(qū)別對待、體現(xiàn)公平、分步推進、累積治理的收費原則，對超載運輸治理的長效性進行了研究。以上均為宏觀層面的對策和策略研究，未涉及具體的治超方案優(yōu)化。筆者從設(shè)施選址-車輛路徑優(yōu)化出發(fā)，對治超站的選址和治超車路徑進行了研究。

選址和路徑聯(lián)合優(yōu)化模型(location routing problem，LRP)是一類反應(yīng)設(shè)施選址和車輛路線決策間相互依賴關(guān)系的模型。傳統(tǒng)的選址-路徑模型和擴展的選址-路徑模型(如：帶時間窗、帶容量限制等的選址-路徑模型)被廣泛地應(yīng)用在多個領(lǐng)域，如配送中心的選址-車輛路徑優(yōu)化問題[5-7]、倉庫的選址-車輛路徑優(yōu)化問題[8，9]、公路設(shè)施的選址和車輛路徑優(yōu)化問題[10]，以及其它設(shè)施的選址-車輛路徑問題[11，12]。選址-路徑問題作為非確定性多項式困難問題(NP-hard)，目前的求解方法主要有精確算法和啟發(fā)式算法[13]。對于候選選址點集合規(guī)模大，需建設(shè)的設(shè)施數(shù)目不確定狀況，TING Chingjung等[14]提出用多層嵌套的蟻群算法來求解大規(guī)模的設(shè)施選址-車輛路徑問題，但由于使用了多個蟻群算法進行求解，計算的隨機性增加，導(dǎo)致算法容易陷入局部最優(yōu)，從而影響其尋優(yōu)精度。

筆者改進了多層嵌套的蟻群算法。首先，在以治超站為基地實施農(nóng)村公路移動治超的工作模式下，為使超載治理的成本達到最少，構(gòu)建了可同時確定治超站數(shù)量、治超站選址及以治超站為基地的治超車巡游路徑優(yōu)化模型，設(shè)計了二級嵌套的蟻群算法，求解具有大規(guī)模候選點集合和最大可設(shè)置設(shè)施數(shù)不確定的選址-路徑問題；然后，為驗證模型和算法的可行性，利用貴陽市農(nóng)村公路上的超載現(xiàn)狀數(shù)據(jù)實施案例分析。結(jié)果表明，治超站被選在礦產(chǎn)資源豐富、施工場地密集的地區(qū)，周邊礦運貨車和渣土車的超載運輸現(xiàn)象明顯，且治超車的巡游路線包含多條貨車流量大的省縣干道；計算結(jié)果驗證了模型和算法的可行性。研究成果可為管理者實施治超站的選址決策和治超車的路徑?jīng)Q策提供參考。

1 選址-路徑模型

1.1 問題描述

在路網(wǎng)內(nèi)，把有超載運輸現(xiàn)象的路段(即超載路段)離散為點，并將這些點組成治超需求點集合。為實施移動治超，每個治超站都需配備相同車型的治超車。治超車攜帶稱重設(shè)備從治超站出發(fā)，行駛到治超需求點，對經(jīng)過的貨車進行超載檢測。巡游過程中，治超車在各需求點的檢測時間固定，每輛治超車能夠巡游的最大時間固定，且每輛治超車都需返回治超站，形成閉合的巡游路徑。治超車的巡游過程如圖1。

圖1 治超車巡游過程示意

研究的問題是在路網(wǎng)形態(tài)、治超需求點集合和候選治超站集合已知的情況下，以最少的成本使治超車能檢測到所有的治超需求點為目的，優(yōu)化治超站的選址和治超車的路徑。

1.2 模型建立

1.2.1 變量及參數(shù)設(shè)置

1)集 合

J為治超站候選點集合；I為需求點集合；K為移動治超車集合。

2)已知參數(shù)

cj為治超站建設(shè)成本；ck為治超車購置成本；cl為治超車巡游成本；cp為人工成本；v為治超車的行駛速度；t為治超車在需求點的固定檢測時間；tmax為治超車每次能夠巡游的最長時間；lii′為任意兩個點之間的距離；n為每輛治超車需配備的移動治超人員數(shù)量。

3)中間變量

D為治超車巡游路徑上的需求點數(shù)量；pk是為治超車k配備的移動治超人員數(shù)量。

4)決策變量

zj為在候選治超站j設(shè)置治超站時為1，反之，為0；zk為選擇治超車輛k進行檢測工作時為1，反之，為0；xii′k為治超車輛k從i到i′時為1，反之，為0。

1.2.2 模 型

(1)

S.T.：zj∈(0,1),j∈J

zk∈(0,1),k∈K

xii′k∈(0,1),i∈I∪J,i′∈I∪J,k∈K

(2)

(3)

(4)

(5)

(6)

pk=n·zk,k∈K

(7)

式中：C為治超成本。

式(1)為目標(biāo)函數(shù)，表示治超成本最低；式(2)可保證治超車的巡游路徑是閉合的；式(3)可保證每個需求點都只能被一輛治超車訪問；式(4)可保證治超車從治超站出發(fā)，最終返回到同一個治超站；式(5)表示只要存在治超車從某個候選治超站出發(fā)到任意需求點，則在該候選點設(shè)置治超站；式(6)可確保每輛治超車的巡游時間不大于其最大巡游時間；式(7)表示治超車配備的移動治超人員人數(shù)。

2 模型求解算法

選址-路徑問題(LRP)屬于NP-hard難題，通常需要用啟發(fā)式算法求解[15]。而蟻群算法作為一種概率型啟發(fā)式算法，經(jīng)常與枚舉法相結(jié)合來求解LRP問題。然而，當(dāng)選址候選集規(guī)模巨大而最大可設(shè)置設(shè)施數(shù)不確定時，潛在選址集合數(shù)會發(fā)生組合性爆炸，用蟻群算法雖可快速求出某選址集合下的最優(yōu)解，但用枚舉法針對組合性爆炸的集合逐個求解選址組合和車輛巡游方案，再從最優(yōu)方案集中篩選成本最小的方案是不現(xiàn)實的。

圖2 二級嵌套蟻群算法流程

2.1 蟻群參數(shù)設(shè)計

螞蟻從巢穴(初始點)出發(fā)尋找食物時，在路徑上播撒信息素，信息素隨時間的推移會逐漸揮發(fā)。在行進過程中，螞蟻依據(jù)路徑上的信息素濃度選擇路線，信息素濃度越大的路徑被選擇的概率越大；反之，概率越小[16]?；诖嗽恚P者設(shè)計了二級嵌套蟻群算法中的螞蟻轉(zhuǎn)移規(guī)則和信息素更新規(guī)則。

2.1.1 螞蟻轉(zhuǎn)移規(guī)則

蟻群算法中，螞蟻的轉(zhuǎn)移與節(jié)點間的信息素濃度和期望有關(guān)，對于節(jié)點i來說，螞蟻選擇節(jié)點j的概率按式(8)計算：

(8)

式中：τij為路線ij的信息素濃度；ηij為路線ij的期望；α、β分別為信息素濃度和期望的啟發(fā)式因子；S為可行的節(jié)點集合。

選址優(yōu)化中，假設(shè)a、b為任意2個選址候選點，路線ab的選擇期望ηab的確定過程如下：

1)基于治超車的最大可能巡游時間，計算各候選點能覆蓋的需求點集合，并定義為覆蓋范圍。

2)根據(jù)式(9)，用相似度表示候選點間重復(fù)覆蓋范圍的大小：

(9)

式中：Sab為當(dāng)前候選點a與其他候選點b的相似度；Lab為當(dāng)前候選點a與其他候選點b重復(fù)檢測到的需求點個數(shù)；La為當(dāng)前候選點a檢測到的治超需求點個數(shù)。

3)把期望ηab定義為候選點之間相似度的倒數(shù)，如式(10)：

(10)

2.1.2 信息素更新規(guī)則

當(dāng)螞蟻完成一次搜索后，采用式(11)的信息素更新方法對節(jié)點間的信息素進行更新：

(11)

選址優(yōu)化信息素增量Δτe1和路徑優(yōu)化中信息素增量Δτe2分別按式(12)、式(13)計算：

(12)

(13)

式中：E1、E2分別為選址優(yōu)化、路徑優(yōu)化中的螞蟻集合；e1、e2分別為選址優(yōu)化、路徑優(yōu)化中的任意一只螞蟻；Q1、Q2分別為選址優(yōu)化、路徑優(yōu)化中的信息素總量；Ce1為第e1只螞蟻所對應(yīng)的治超站建設(shè)成本和針對第e1只螞蟻所選擇的治超站而優(yōu)化得到的最小移動治超成本之和；Le2為第e2只螞蟻的路徑長度。

2.2 算法步驟

Step1：輸入治超站候選點的總數(shù)M、治超需求點的總數(shù)N、每輛治超車最大可能的巡游時間tmax、各點之間的距離矩陣B。

Step3：采用一級蟻群算法優(yōu)化選址。

1)設(shè)螞蟻數(shù)為M，并將螞蟻編號為1,2,3,…,M。候選點間的初始信息素設(shè)為1，選擇期望按式(9)計算。每只螞蟻隨機選擇一個候選點開始構(gòu)造路徑。

2)按式(8)計算每個候選點的選擇概率。為避免陷入局部最優(yōu)，用輪盤賭選擇法增加選擇候選點的隨機性[17]。具體過程為：取隨機數(shù)ε,ε∈(0,1)，按候選點編號順序依次累加可行候選點的選擇概率pab，當(dāng)∑pab≥ε時，選擇編號最大的候選點作為螞蟻的下一節(jié)點。當(dāng)螞蟻路徑上的候選點數(shù)量等于H時，轉(zhuǎn)到3)。

3)m為一級蟻群中螞蟻的編號，設(shè)m=1。

Step4：對螞蟻m選擇到的治超站進行路徑優(yōu)化。如果選擇到的治超站的數(shù)量大于1，則將多治超站的車輛路徑問題轉(zhuǎn)化為單治超站的車輛路徑問題，即用一個虛擬治超站代替所有選擇的治超站[18]。

1)假設(shè)所有治超車都以虛擬治超站為起訖點，治超需求點i與虛擬治超站之間的距離用治超需求點i到最近的治超站的距離di表示。

2)設(shè)二級蟻群算法中的螞蟻數(shù)為N，治超需求點間的初始信息素為1，治超需求點和虛擬治超站間的初始信息素也設(shè)為1。

3)螞蟻從虛擬治超站出發(fā)，按式(8)和輪盤賭選擇法選擇下一節(jié)點。假設(shè)選擇到的第1個節(jié)點為需求點i′，距離i′最近的一個治超站為o。

4)對于螞蟻的巡游時間t及最大巡游時間tmax，要使得t≯tmax，需約束巡游時間：如果螞蟻在節(jié)點i選擇到的下一點為j，設(shè)螞蟻從o點到j(luò)點的巡游時間為to→j。判斷to→j+bjo/v與tmax的大小，其中bjo/v表示螞蟻從j點到o點的時間，當(dāng)to→j+bjo/v≤tmax時，則把j納入到螞蟻的行程中，螞蟻繼續(xù)按照4)選擇下一點；當(dāng)to→j+bjo/v>tmax時，則放棄j點，螞蟻從當(dāng)前節(jié)點返回到治超站o，同時設(shè)螞蟻的巡游時間t=0，返回3)。

3 案例分析

筆者調(diào)查得到貴陽市農(nóng)村公路有63條超載嚴(yán)重的路段，把這些路段離散成63個治超需求點，并設(shè)定為治超站選址候選點集合，其空間分布如圖3。

圖3 貴陽農(nóng)村公路網(wǎng)與治超需求點的空間分布

設(shè)每輛治超車需配備3名工作人員，走行速度為40 km/h，在1個治超需求點停車檢測需0.5 h，每輛治超車的最大可能巡游時間為5 h。每個治超站建設(shè)的固定成本為250萬元，使用年限為10年，則每年每個治超站的折舊成本為25萬元；每年每人的人工成本為4.8萬元；治超車按每輛10萬元購置，使用年限為10年，則每年每輛治超車的折舊成本為1萬元；每公里每輛治超車的燃油成本為1元，按每輛治超車每年需移動治超120次的標(biāo)準(zhǔn)，則每年每輛治超車每公里的燃油成本為120元。

根據(jù)圖3的農(nóng)村路網(wǎng)數(shù)據(jù)(包括交叉點、路段等數(shù)據(jù))，先使用最短路算法(Floyd算法)計算治超需求點的距離矩陣，再將治超需求點的距離矩陣和治超車數(shù)量等參數(shù)輸入到蟻群算法中，優(yōu)化治超站的選址和治超車的路徑。

圖4為當(dāng)治超站從1個增加到8個時，最優(yōu)路徑的信息素增量隨迭代次數(shù)的變化關(guān)系。

圖4 路徑優(yōu)化中的信息素增量-迭代次數(shù)關(guān)系

由圖4可知：不同治超站數(shù)量下的信息素增量均隨迭代次數(shù)的增加而增加，但增速逐漸減小直至收斂，表明對應(yīng)不同的治超站數(shù)量都有一個最少的治超成本。當(dāng)設(shè)置4個治超站時，信息素增量的收斂值是8種情況中的最大值，表明此時的治超成本最小。

表1為設(shè)置1 ～ 8個治超站時所對應(yīng)的選址組合、治超車數(shù)和每年的治超成本。

表1 建設(shè)不同數(shù)量的治超站時的治超指標(biāo)

從表1可知，設(shè)置4個治超站時，選址點分別設(shè)在24、28、45和54號點。各治超車的巡游路徑如圖5(閉合黑折線表示1輛治超車的巡游路徑)，這些巡游路徑經(jīng)過多條省縣級農(nóng)村公路。

圖5 選址-路徑方案

由圖5可見，4個治超站共需購置12輛治超車，其中，45和54號治超站分別擁有3輛，24號治超站擁有2輛，28號治超站擁有4輛。24、28、45和54號治超站分別位于花溪區(qū)的孟關(guān)鄉(xiāng)、息烽縣青山鄉(xiāng)、烏當(dāng)區(qū)羊昌鎮(zhèn)、清鎮(zhèn)市衛(wèi)城鎮(zhèn)。這些治超站周邊礦產(chǎn)資源豐富、施工現(xiàn)場密集，運礦卡車和渣土車等大型車多超載運輸，治超站的設(shè)置對途經(jīng)的運輸車輛進行超載檢測，可對周圍路段上的運輸車輛起到威懾作用。

以54號治超站為例，治超車巡游路徑的沿線情況如圖6。由圖6可以看出，3輛治超車的巡游路徑上有：犁倭鎮(zhèn)、流長鄉(xiāng)、王莊鄉(xiāng)、衛(wèi)城鎮(zhèn)、站街鎮(zhèn)、谷堡鎮(zhèn)、麥格鄉(xiāng)、百花湖鄉(xiāng)、清鎮(zhèn)市9個城鎮(zhèn)和紅楓湖等的3個風(fēng)景區(qū)，以及多個煤礦開采地。主要覆蓋的道路有S310、S106、S211、S210等4條連接城鎮(zhèn)的省級公路，道路等級較高，貨車流量大，以及X068、X198、X063、Y012、Y020等多條縣鄉(xiāng)級農(nóng)村公路。這些路段周邊礦產(chǎn)資源豐富，運礦卡車超載現(xiàn)象嚴(yán)重。

圖6 巡游路徑的沿線情況

表1中8個選址方案的治超車工作效率W和利用率U可分別用式(14)、式(15)來表示：

(14)

(15)

式中：N為需求點數(shù)；tk為治超車k的實際巡游時間；K為所有治超站配備的治超車集合；tmax為每輛治超車最大能夠的巡游時間。

設(shè)置1～8個治超站時，最佳選址方案下的治超車工作效率和利用率的對比如圖7?？梢钥闯?，治超車工作效率隨治超站的增加而增加，且上升趨勢逐漸平緩。治超站從1個增加到4個時，治超效率上升顯著，說明該階段治超效率隨治超站的增加而明顯提高。治超站從4個增加到8個時，治超效率變化不明顯，此時雖然治超站數(shù)多，但治超車工作效率并未明顯改變。與治超效率不同，治超車的利用率在治超站數(shù)量從1個增加到4個時，呈上升趨勢，并在4個時達到最大值，為94.83%。但治超站數(shù)量從4個增加到8個時，治超車?yán)寐拭黠@下降。

圖7 不同數(shù)量治超站治超車的工作效率和利用率

綜上，當(dāng)分別在24、28、45和54號點設(shè)置治超站時，按照圖5的巡游方案，所有超載點都可被檢測到，且治超成本最低，此時得到的治超站選址、治超車配備和巡游路徑是最優(yōu)的，由圖7可知最優(yōu)方案下的治超車的利用率最高。

4 結(jié) 語

針對以治超站為基地實施農(nóng)村公路移動治超的工作模式，在治超站候選點集合規(guī)模巨大和最大設(shè)置數(shù)量不確定的情況下，以治超成本最小為目標(biāo)，以治超車巡游時間不大于最大巡游時間和所有超載點都被檢測到為約束條件，建立治超站選址-治超車路徑優(yōu)化模型，并設(shè)計二級嵌套蟻群搜索算法求解。

基于貴陽市農(nóng)村公路實際數(shù)據(jù)的研究表明，在優(yōu)化的治超站選址-治超車路徑方案下，治超站被選在礦產(chǎn)資源豐富、施工場地密集的地區(qū)，周邊礦運貨車和渣土車的超載現(xiàn)象明顯，治超站的設(shè)置不僅可對途經(jīng)的貨車進行超載檢測，對周圍路段上的貨車也起到了威懾作用。治超車的巡游路線包含多條省縣干道，貨車流量大，保證治超車可以有效攔截貨車，而且治超車的利用率為94.83%，達到最高，工作效率為1.107，治超車工作效率較好。結(jié)果表明：筆者提出的模型和算法能有效幫助決策者科學(xué)合理地進行治超站選址決策和治超車路徑選擇決策。

值得說明的是，筆者未考慮治超需求點的運輸車流量隨時間的分布情況，優(yōu)化的結(jié)果中缺少治超車的出發(fā)時間。為使治超車在巡游時間內(nèi)能更多的截獲到運輸車輛，在治超車路徑優(yōu)化的后續(xù)研究中，有必要考慮治超需求點處交通流在時間上的分布特征，根據(jù)不同時段的流量情況，優(yōu)化治超車的出發(fā)時間和巡游路徑。