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

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

0 引 言

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

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

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

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

1 選址-路徑模型

1.1 問(wèn)題描述

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

圖1 治超車巡游過(guò)程示意

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

1.2 模型建立

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

1)集 合

J為治超站候選點(diǎn)集合；I為需求點(diǎn)集合；K為移動(dòng)治超車集合。

2)已知參數(shù)

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

3)中間變量

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

4)決策變量

zj為在候選治超站j設(shè)置治超站時(shí)為1，反之，為0；zk為選擇治超車輛k進(jìn)行檢測(cè)工作時(shí)為1，反之，為0；xii′k為治超車輛k從i到i′時(shí)為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)可保證每個(gè)需求點(diǎn)都只能被一輛治超車訪問(wèn)；式(4)可保證治超車從治超站出發(fā)，最終返回到同一個(gè)治超站；式(5)表示只要存在治超車從某個(gè)候選治超站出發(fā)到任意需求點(diǎn)，則在該候選點(diǎn)設(shè)置治超站；式(6)可確保每輛治超車的巡游時(shí)間不大于其最大巡游時(shí)間；式(7)表示治超車配備的移動(dòng)治超人員人數(shù)。

2 模型求解算法

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

圖2 二級(jí)嵌套蟻群算法流程

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

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

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

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

(8)

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

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

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

2)根據(jù)式(9)，用相似度表示候選點(diǎn)間重復(fù)覆蓋范圍的大?。?/p>

(9)

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

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

(10)

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

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

(11)

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

(12)

(13)

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

2.2 算法步驟

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

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

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

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

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

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

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

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

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

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

3 案例分析

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

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

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

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

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

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

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

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

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

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

圖5 選址-路徑方案

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

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

圖6 巡游路徑的沿線情況

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

(14)

(15)

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

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

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

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

4 結(jié) 語(yǔ)

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

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

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