基于隨機游走的分類垃圾回收最優路徑規劃

趙紅霞，劉高森，李愈

?

基于隨機游走的分類垃圾回收最優路徑規劃

趙紅霞1，劉高森2，李愈1

（1.西南交通大學，交通運輸與物流學院，成都 610031；2.成都鐵路局，調度所，成都 610081）

分類垃圾回收是逆向物流的重要研究內容, 物流路徑越短意味著回收成本越少。在垃圾分類回收過程中, 通過對垃圾的回收路徑進行合并可以共享運輸資源從而達到節約成本的作用, 故本文將垃圾分類回收的路徑規劃問題假設為多源多目標的路徑規劃問題, 并給出了路徑集合中不含重復邊的總長度優化模型。當網絡規模增長到一定程度時, 通過精確計算方法得到模型的最優值幾乎是不可能的, 為此提出了一種基于隨機游走的最優路徑集合選取算法。模擬實驗驗證了該方法的有效性和高效性, 與基于Dijkstra算法的最短路徑求和算法相比不僅準確性高, 而且具有很高的執行效率。

物流路徑; 優化方法; 隨機游走; 網絡采樣

0 引 言

在中國，城鎮化以及城市經濟的快速發展加速了城市固體垃圾的產生，這些固體垃圾的管理與回收成為當前逆向物流面臨的嚴峻挑戰之一[1]。縱觀全世界，美國、日本、德國、新加坡等發達國家已經對城市垃圾的管理與回收建立了相應的法律法規[2]。在城市垃圾的管理與回收中，對垃圾的分類回收是關鍵環節之一。通過對垃圾進行分類回收可以提高資源的重復使用，并減小有毒有害物質帶來的污染。

在垃圾回收的研究中，回收路徑的選擇是最重要的研究內容之一[3]。城市的交通是由網狀結構組成，各種不同類型的垃圾分布在網狀結構的任意角落，而垃圾回收點往往按照回收垃圾的種類分布在網絡中的多個節點。在垃圾回收過程中，不僅要考慮運輸的成本，還要考慮時間因素，如垃圾的最佳處理時間，腐爛變質帶來的潛在危害等[4]。在垃圾回收中，最直接的方法是尋找垃圾點和回收站點之間的最短路徑，這種方法導致的結果是單個站點的回收路徑最短，而所有站點的路徑之和不是最短的，因而增加了垃圾回收的代價。此外，隨著城市交通往往越來越復雜，以及回收站點的種類不斷增多，這給垃圾回收路徑的選擇帶來了巨大的困難。

本文將垃圾分類回收建立了一個包含多終點的最優路徑選取模型。不同種類的垃圾分布在城市的每一個角落，將多種類垃圾設定一個回收站點，通過合并每個垃圾的回收路徑使得垃圾回收的路徑之和達到最小，從而節約垃圾回收的成本。

1 分類回收最優路徑模型

路徑集合中包含的邊的集合為

《無機鹽工業》(月刊)是全國中文核心期刊，是國家科委批準的無機化工行業公開發行的科技刊物，1960年創刊，國內外公開發行，主要報道國內外無機化工行業最新科技成果與技術進展，以及新技術、新工藝、新設備、新產品、新用途等方面的動態及商品信息、市場行情等。內設綜述與專論、研究與開發、工業技術、環境·健康·安全、化工分析與測試、化工標準化、化工裝備與設計、催化材料、電池材料、綜合信息等欄目，是無機化工行業必不可少的良師益友。

2 基于隨機游走的最優路徑組合選取

在對公式（3）的計算過程中，采用枚舉所有路徑組合的方式求最小的路徑組合是不可行的。因為網絡中兩點之間的路徑數量隨著網絡的規模呈指數級增長[5]。此外，在垃圾回收過程中，垃圾的數量往往與網絡的節點個數有著相同的數量級，這使得路徑的組合個數變成了雙指數的數量級。

圖1 簡單的路徑合并實例

為了能夠用較短的時間得到優化的結果，本文基于隨機游走的思想提出了一種最優路徑組合優化算法。

（1）以初始點開始隨機游走；

（3）重復第2步直到產生長度為的隨機游走鏈。

圖2 始點至終點過程的路徑陣列

3 實驗結果與分析

本文采用了模擬的數據集對算法的準確性和性能進行評估。實驗環境為一臺個人筆記本電腦，配置為Intel Core i5雙核CPU，頻率為2.5GHz，內存為4GB。

3.1 實驗數據的產生

為了對本文提出的最優路徑規劃算法進行評估，實驗模擬產生了某地區的垃圾產生地點和回收站點分布圖（見圖3），并模擬產生了該地區的交通網絡圖（見圖4）。

圖3 生成的節點分布圖

圖4 模擬的交通分布圖

為了模擬點與點之間的交通路徑，模擬產生了相應的交通圖。對于該區域內的每個點，隨機選擇3或4條路線，其中這些路線的另一端為距離該點直線距離最近的點。選擇3或4條路線的理由是現實的交通路線大都為十字路口或者三岔路口。在邊的生成中，選擇兩個端點之間的直線距離。圖4為圖3生成的節點分布圖的交通示意圖，垃圾經過該交通圖回收到相應的垃圾回收站點。

3.2 實驗結果

圖5 總的路徑長度隨著節點規模的變化（α=0.8）

圖6 總的路徑長度隨著垃圾回收節點數量的變化（k=300）

表1 算法的運行時間隨著節點規模的變化（=0.8）

Tab.1 The running time of the algorithm varies with the node size

表2 算法的運行時間隨著垃圾數量的變化（=300）

Tab.2 The running time of the algorithm varies with the amount of garbage

綜上所述，本文提出的基于隨機游走的分類垃圾回收路徑優化方法在垃圾的分類回收中可以對回收的路徑進行合并，從而減小了回收所有垃圾所需的總路徑長度。此外，由于隨機游走是一種采樣方法，該方法使用很少的采樣數便可以得到理想的采樣結果，因此執行效率非常高。

4 結束語

本文研究了分類垃圾回收中的路徑優化問題。城市垃圾回收運行運行線路如果不進行合理規劃，將導致成本過高。本文通過對垃圾回收過程中的物流路徑進行合并，在共享運輸資源的情況下減少回收成本。在分類垃圾回收中，不同種類的垃圾對應垃圾回收站點，將垃圾分類回收的路徑規劃問題建模為多源多目標的路徑規劃問題，并給出了路徑集合中不含重復邊的總長度的優化模型。為了提高該模型的計算效率，提出了一種基于隨機游走的最優路徑集合選取算法。模擬實驗表明，本文提出的方法與基于Dijkstra算法的最短路徑求和算法相比不僅準確性高，而且具有很高的執行效率。

[1] 石玉峰, 門志強. 基于模糊多目標決策理論的軍事運輸路徑優化研究[J]. 交通運輸工程與信息學報, 2004, 2(1): 112-116.

[2] 李湘洲. 國外城市垃圾回收利用與管理的新動向[J]. 再生資源與循環經濟, 2010, 3(9): 41-44.

[3] BEULLENS P. Reverse logistics in effective recovery of products from waste materials[J]. Reviews in Environmental Science and Bio/Technology, 2004, 3(4): 283-306.

[4] 李進龍, 劉紅星, 謝文杰, 等. 基于改進蟻群和免疫算法融合的多配送中心路徑優化[J]. 交通運輸工程與信息學報, 2017, 15(4): 87-94.

[5] ZHANG Y M, HUANG G H, He L. An inexact reverse logistics model for municipal solid waste management systems[J]. Journal of Environmental Management, 2011, 92(3): 522-530.

[6] 羅耀波, 孫延明, 劉小龍. 多約束選址—路徑問題的改進混合遺傳算法研究[J]. 計算機應用研究, 2013, 30(8): 2283-2287.

[7] WANG H, XIAO G, WEI Z. Optimizing route for hazardous materials logistics based on hybrid ant colony algorithm[J]. Discrete Dynamics in Nature and Society, 2013(1): 1-6.

[8] 張維澤, 林劍波, 吳洪森, 等. 基于改進蟻群算法的物流配送路徑優化[J]. 浙江大學學報: 工學版, 2008, 42(4): 574-578.

[9] 胡佳, 趙佳虹, 胡鵬. 考慮風險公平性的無能力約束條件下危險廢物回收路徑優化問題[J]. 交通運輸工程與信息學報, 2014, (1): 55-61.

[10] 楊帆. 單親遺傳算法的改進及用于城市垃圾回收路線優化[J]. 科技創新與應用, 2017(23): 77-77.

（中文編輯：劉娉婷，英文審改：梁宏斌）

Optimization Method of Logistics Paths Planning for Categorical Waste Recycling Based on Random Walk

ZHAO Hong-xia1，LIU Gao-sen2，LI Yu1

（1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China； 2. The Central Dispatching Station, Chengdu Railway Bureau, Chengdu 610081, China）

Categorical waste recycling is an important research issue in reverse logistics field, the shorter the logistics paths are, the lower cost of recycling is. During the processing of categorical waste recycling, the recycling cost could be reduced according to sharing transportation by merging recycling paths of waste. In this paper, we transform the problem of path planning for categorical waste recycling into the problem of path planning for multiple sources and targets, and present a total length optimization model that doesn’t contain any edge multiple times in the path set. When the scale of network extends to some degree, it is impossible to calculate the accurate optimal resolution of the model. So we propose a random walk based optimal choosing algorithm of path set. The proposed algorithm can reduce the total path length by merging common edges in different paths, and is more accurate and efficient than the Dijkstra based algorithm for summing up all lengths of the shortest paths. Finally, we validate the effective and efficiency of the proposed algorithm by simulation experiments.

logistics path; optimization method; random walk; network sampling

1672-4747（2018）03-0103-06

N945

A

10.3969/j.issn.1672-4747.2018.03.015

2017-03-30

趙紅霞（1980—），女，遼寧錦州人，碩士，西南交通大學交通運輸與物流學院講師，研究方向為物流系統規劃。

李愈（1976—），女，四川仁壽人，碩士，西南交通大學交通運輸與物流學院講師，研究方向為交通運輸規劃與管理。

趙紅霞，劉高森，李愈. 基于隨機游走的分類垃圾回收最優路徑規劃[J]. 交通運輸工程與信息學報, 2018, 16(3): 103-108.