農村公路治超站選址與治超車路徑優化研究

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

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

0 引 言

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

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

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

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

1 選址-路徑模型

1.1 問題描述

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

圖1 治超車巡游過程示意

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

1.2 模型建立

1.2.1 變量及參數設置

1)集 合

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

2)已知參數

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

3)中間變量

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

4)決策變量

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

2 模型求解算法

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

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

2.1 蟻群參數設計

螞蟻從巢穴(初始點)出發尋找食物時，在路徑上播撒信息素，信息素隨時間的推移會逐漸揮發。在行進過程中，螞蟻依據路徑上的信息素濃度選擇路線，信息素濃度越大的路徑被選擇的概率越大；反之，概率越小[16]。基于此原理，筆者設計了二級嵌套蟻群算法中的螞蟻轉移規則和信息素更新規則。

2.1.1 螞蟻轉移規則

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

(8)

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

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

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

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

(9)

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

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

(10)

2.1.2 信息素更新規則

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

(11)

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

(12)

(13)

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

2.2 算法步驟

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

Step3：采用一級蟻群算法優化選址。

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

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

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

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

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

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

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

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

3 案例分析

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

圖3 貴陽農村公路網與治超需求點的空間分布

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

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

圖4為當治超站從1個增加到8個時，最優路徑的信息素增量隨迭代次數的變化關系。

圖4 路徑優化中的信息素增量-迭代次數關系

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

表1為設置1 ～ 8個治超站時所對應的選址組合、治超車數和每年的治超成本。

表1 建設不同數量的治超站時的治超指標

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

圖5 選址-路徑方案

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

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

圖6 巡游路徑的沿線情況

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

(14)

(15)

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

設置1～8個治超站時，最佳選址方案下的治超車工作效率和利用率的對比如圖7。可以看出，治超車工作效率隨治超站的增加而增加，且上升趨勢逐漸平緩。治超站從1個增加到4個時，治超效率上升顯著，說明該階段治超效率隨治超站的增加而明顯提高。治超站從4個增加到8個時，治超效率變化不明顯，此時雖然治超站數多，但治超車工作效率并未明顯改變。與治超效率不同，治超車的利用率在治超站數量從1個增加到4個時，呈上升趨勢，并在4個時達到最大值，為94.83%。但治超站數量從4個增加到8個時，治超車利用率明顯下降。

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

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

4 結 語

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

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

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