高杉

（四川大學(xué) 災(zāi)后重建與管理學(xué)院，四川 成都610207）

1 概述

雪災(zāi)是指強(qiáng)降溫和大風(fēng)伴隨降雪或大風(fēng)卷起地面積雪的天氣，對道路交通和城市居民生活危害極大。我國北方冬季降雪頻繁，當(dāng)連續(xù)降雪，雪情超出預(yù)期時(shí)，相關(guān)單位需及時(shí)清除道路積雪，從而保障城市交通的有序恢復(fù)。

本文從路面積雪運(yùn)輸?shù)慕嵌瘸霭l(fā)，主要研究在給定服務(wù)區(qū)域，單車輛的弧路徑問題優(yōu)化問題。關(guān)于如何應(yīng)對冬季降雪天氣災(zāi)害，目前學(xué)術(shù)界的關(guān)注點(diǎn)主要是“硬工程”，而不注重“軟優(yōu)化”。如融雪劑的研發(fā)、掃雪車的改進(jìn)、城市道路規(guī)劃，鮮有管理方向上的討論與研究。顯然，管理科學(xué)能夠幫助有關(guān)部門在一定程度上合理安排清掃車輛的運(yùn)行線路，幫助提高現(xiàn)有資源的利用水平。

弧路徑問題是路徑優(yōu)化問題最重要的類別之一，主要包括中國郵遞員問題、鄉(xiāng)村郵遞員問題和容量約束弧路徑問題（Capacitated Arc Routing Problem, CARP）[1]三大類。CARP 由Golden 和 Wong (1981)[2]提出, 作者同時(shí)證明了 CARP 是NP-hard 問題。對于這類問題，在解決大規(guī)模應(yīng)用實(shí)例時(shí)，通常不選用精確解算法，而是采用近似解算法。Liu 等人[3]對求解CARP 的近似解算法進(jìn)行了回顧。

蟻群算法是最熱門的仿生優(yōu)化算法之一，在NP-hard 問題的求解過程中被不斷改進(jìn)、創(chuàng)新。在容量約束弧路徑問題的研究上，Lacomme 等人(2004)[4]提出了蟻群優(yōu)化算法求解CARP 問題。Santos 等人(2010)[5]對蟻群算法的初始種群、螞蟻決策規(guī)則和局域搜索程序進(jìn)行了修改，更好地求解CARP 問題。

2 數(shù)學(xué)模型

積雪清運(yùn)車輛路徑問題可描述為：某清運(yùn)車輛從場站出發(fā)，對其作業(yè)區(qū)域內(nèi)需求邊進(jìn)行服務(wù)，當(dāng)服務(wù)過某些需求邊車輛滿載后，需行駛至指定的消納場傾倒積雪，完成后接著行駛，服務(wù)未服務(wù)的需求邊，直至該區(qū)域內(nèi)所有需求邊都得到服務(wù)，車輛返回車場，此為該車輛行駛的整個(gè)路徑。問題就是事先確定該車的行車路徑，在一定約束條件下，實(shí)現(xiàn)距離成本最小（也就是時(shí)間成本最?。┑哪繕?biāo)。

該問題基于以下假設(shè)：

（1）求解車輛的作業(yè)區(qū)域已經(jīng)劃定；

（2）各邊的距離成本、需求量已知；

（3）消納場的容量不限。

模型中涉及的參數(shù)及變量定義如表1 所示。

表1 參數(shù)及變量定義

目標(biāo)函數(shù)和約束條件如下：

目標(biāo)函數(shù)（1）表示積雪清運(yùn)車輛路線的總距離成本最小。式（2）表示車輛從Vi進(jìn)，也要從Vi出。式（3）表示需求邊必須被服務(wù)一次。式（4）表示每條邊的訪問次數(shù)不能小于其被服務(wù)的次數(shù)。式（5）表示每個(gè)行程的容量限制。式（6）表示如果車輛經(jīng)過邊(Vi,Vj)，那么離開Vj時(shí)的剩余容量等于進(jìn)入Vi時(shí)的剩余容量減去邊(Vi,Vj)的需求量。式（7）表示整條路線，車輛從車場出發(fā)一次。式（8）表示整條路線，車輛最后回到車場。式（9）表示清運(yùn)車輛的最后一次行程必須空載返回車場。式（10）和（11）表示消除子回路。式（12）和（13）表示決策變量的取值范圍。

3 算法設(shè)計(jì)

本文的求解算法針對道路積雪清運(yùn)路徑優(yōu)化問題，基于蟻群算法，進(jìn)行了以下算法的設(shè)計(jì)：

第八步，判斷是否達(dá)到最大迭代次數(shù)NCmax；

第九步，輸出結(jié)果。

算法流程圖如圖1 所示。

圖1 蟻群算法求解積雪清運(yùn)線路優(yōu)化問題流程圖

4 算例實(shí)驗(yàn)以及分析

4.1 算例和參數(shù)設(shè)置

由于蟻群算法是典型的概率算法，所以算法中的參數(shù)通常需要由實(shí)驗(yàn)確定。但參數(shù)設(shè)計(jì)不是本文研究重點(diǎn)，所有直接采用以往文獻(xiàn)給出的參考規(guī)則。這些規(guī)則包括：

（1）節(jié)點(diǎn)數(shù)量約為螞蟻數(shù)量的1.5 倍[7]；

（2）α 在1 附近，β 在5 附近，ρ 在0.7 左右[8]；

（3）常數(shù)Q 對算法的性能沒有明顯的影響[9]；

（4）α、β、ρ 的大小與最大迭代次數(shù)呈負(fù)相關(guān)，最大迭代次數(shù)不宜過大或過小[10]。

圖2 距離成本與車輛最大載重量關(guān)系折線圖

因此，以上算法參數(shù)取值分別定為：m=30；α=1；β=5；ρ=0.7；Q=1；NCmax=100。

4.2 實(shí)驗(yàn)結(jié)果

計(jì)算結(jié)果如表2 所示。

表2 算例結(jié)果

在四組算例中，每組算例的車輛最大載重量作為變量遞減，將該四組的距離成本和Q 的關(guān)系用圖2 分別表示，可以看，出當(dāng)車輛容量越小時(shí)，行駛的總成本越高，這是因?yàn)槿萘啃∫馕吨菀籽b滿，所有前往消納場的次數(shù)也就越多，空跑的比重也會(huì)增大。

5 結(jié)論

本文研究了路面積雪清除線路優(yōu)化的問題，設(shè)計(jì)了相應(yīng)的弧路徑優(yōu)化模型和蟻群算法進(jìn)行求解。在大范圍內(nèi)對車輛路徑進(jìn)行理論化求解，可以輔助人工作業(yè)，彌補(bǔ)經(jīng)驗(yàn)偏差，使得工作更有效率。

本文也有很大的改進(jìn)空間。本文僅僅是針對車輛服務(wù)區(qū)域劃分完后區(qū)域內(nèi)單車輛弧路徑規(guī)劃，之后的研究有必要將區(qū)域劃分理論與該研究結(jié)合，從更大的整體上優(yōu)化弧路徑問題，同時(shí)，多車輛、多車型、需求可拆分、道路限制等方面都是延伸的重點(diǎn)。