基于隨機(jī)游走的分類垃圾回收最優(yōu)路徑規(guī)劃

趙紅霞，劉高森，李愈

?

基于隨機(jī)游走的分類垃圾回收最優(yōu)路徑規(guī)劃

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

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

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

物流路徑; 優(yōu)化方法; 隨機(jī)游走; 網(wǎng)絡(luò)采樣

0 引 言

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

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

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

1 分類回收最優(yōu)路徑模型

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

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

2 基于隨機(jī)游走的最優(yōu)路徑組合選取

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

圖1 簡單的路徑合并實例

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

（1）以初始點開始隨機(jī)游走；

（3）重復(fù)第2步直到產(chǎn)生長度為的隨機(jī)游走鏈。

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

3 實驗結(jié)果與分析

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

3.1 實驗數(shù)據(jù)的產(chǎn)生

為了對本文提出的最優(yōu)路徑規(guī)劃算法進(jìn)行評估，實驗?zāi)M產(chǎn)生了某地區(qū)的垃圾產(chǎn)生地點和回收站點分布圖（見圖3），并模擬產(chǎn)生了該地區(qū)的交通網(wǎng)絡(luò)圖（見圖4）。

圖3 生成的節(jié)點分布圖

圖4 模擬的交通分布圖

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

3.2 實驗結(jié)果

圖5 總的路徑長度隨著節(jié)點規(guī)模的變化（α=0.8）

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

表1 算法的運行時間隨著節(jié)點規(guī)模的變化（=0.8）

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

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

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

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

4 結(jié)束語

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

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

[2] 李湘洲. 國外城市垃圾回收利用與管理的新動向[J]. 再生資源與循環(huán)經(jīng)濟(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ìn)龍, 劉紅星, 謝文杰, 等. 基于改進(jìn)蟻群和免疫算法融合的多配送中心路徑優(yōu)化[J]. 交通運輸工程與信息學(xué)報, 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ìn)混合遺傳算法研究[J]. 計算機(jī)應(yīng)用研究, 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ìn)蟻群算法的物流配送路徑優(yōu)化[J]. 浙江大學(xué)學(xué)報: 工學(xué)版, 2008, 42(4): 574-578.

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

[10] 楊帆. 單親遺傳算法的改進(jìn)及用于城市垃圾回收路線優(yōu)化[J]. 科技創(chuàng)新與應(yīng)用, 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—），女，遼寧錦州人，碩士，西南交通大學(xué)交通運輸與物流學(xué)院講師，研究方向為物流系統(tǒng)規(guī)劃。

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

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