基于随机游走的分类垃圾回收最优路径规划

赵红霞，刘高森，李愈



基于随机游走的分类垃圾回收最优路径规划

赵红霞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.