雪災背景下的道路積雪清運線路優化問題研究

高杉

（四川大學 災后重建與管理學院，四川 成都610207）

1 概述

雪災是指強降溫和大風伴隨降雪或大風卷起地面積雪的天氣，對道路交通和城市居民生活危害極大。我國北方冬季降雪頻繁，當連續降雪，雪情超出預期時，相關單位需及時清除道路積雪，從而保障城市交通的有序恢復。

本文從路面積雪運輸的角度出發，主要研究在給定服務區域，單車輛的弧路徑問題優化問題。關于如何應對冬季降雪天氣災害，目前學術界的關注點主要是“硬工程”，而不注重“軟優化”。如融雪劑的研發、掃雪車的改進、城市道路規劃，鮮有管理方向上的討論與研究。顯然，管理科學能夠幫助有關部門在一定程度上合理安排清掃車輛的運行線路，幫助提高現有資源的利用水平。

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

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

2 數學模型

積雪清運車輛路徑問題可描述為：某清運車輛從場站出發，對其作業區域內需求邊進行服務，當服務過某些需求邊車輛滿載后，需行駛至指定的消納場傾倒積雪，完成后接著行駛，服務未服務的需求邊，直至該區域內所有需求邊都得到服務，車輛返回車場，此為該車輛行駛的整個路徑。問題就是事先確定該車的行車路徑，在一定約束條件下，實現距離成本最小（也就是時間成本最小）的目標。

該問題基于以下假設：

（1）求解車輛的作業區域已經劃定；

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

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

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

表1 參數及變量定義

目標函數和約束條件如下：

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

3 算法設計

本文的求解算法針對道路積雪清運路徑優化問題，基于蟻群算法，進行了以下算法的設計：

第八步，判斷是否達到最大迭代次數NCmax；

第九步，輸出結果。

算法流程圖如圖1 所示。

圖1 蟻群算法求解積雪清運線路優化問題流程圖

4 算例實驗以及分析

4.1 算例和參數設置

由于蟻群算法是典型的概率算法，所以算法中的參數通常需要由實驗確定。但參數設計不是本文研究重點，所有直接采用以往文獻給出的參考規則。這些規則包括：

（1）節點數量約為螞蟻數量的1.5 倍[7]；

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

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

（4）α、β、ρ 的大小與最大迭代次數呈負相關，最大迭代次數不宜過大或過小[10]。

圖2 距離成本與車輛最大載重量關系折線圖

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

4.2 實驗結果

計算結果如表2 所示。

表2 算例結果

在四組算例中，每組算例的車輛最大載重量作為變量遞減，將該四組的距離成本和Q 的關系用圖2 分別表示，可以看，出當車輛容量越小時，行駛的總成本越高，這是因為容量小意味著容易裝滿，所有前往消納場的次數也就越多，空跑的比重也會增大。

5 結論

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

本文也有很大的改進空間。本文僅僅是針對車輛服務區域劃分完后區域內單車輛弧路徑規劃，之后的研究有必要將區域劃分理論與該研究結合，從更大的整體上優化弧路徑問題，同時，多車輛、多車型、需求可拆分、道路限制等方面都是延伸的重點。