基于模拟退火算法的校园垃圾清运最优线路研究

张睿涵

摘要：目前，垃圾清理问题已经成为阻碍社会发展的一大重要因素，往往清理垃圾的成本与垃圾问题的解决本身有着密切的关联，合理的清运线路既能节约成本又能提高效率。本文以北京师范大学校园为例，旨在运用数学建模方法实现校园垃圾回收最优方案。首先基于模拟退火算法得到理想模型中不考虑道路实际情况的垃圾清运路线，然后使用MATLAB进行元胞自动机模拟仿真得到实际路线信息，最后将实际路线信息替换理想模型中的距离信息，最终建立求解最优垃圾清运路线的数学模型，同时给出北师大校园垃圾的最优清理方案。

关键词：模拟退火算法 元胞自动机模拟仿真

1问题的分析

垃圾清运指垃圾的收集和运输，校园垃圾收运系统包括垃圾的收集、运输和转运三个部分，在这其中收集和运输是每个系统共有的，而转运过程则视垃圾产生源至垃圾处理场的运输距离及收集车辆状况而改变。

为了达到节约成本、提高效率的目的，我们针对北京师范大学校园的垃圾管理现状，力求设计出一个合理的清运线路以满足北师大校园中所有垃圾桶的清运工作，同时假设垃圾清运车只在规定道路行驶。

2模型的建立

2.1绘制道路信息

首先，我们通过实地勘察绘制出北师大校园地形图并在地图中标出各个垃圾桶的位置坐标，在此过程中我们将距离较近的几个垃圾桶位置合并为同一个垃圾清运点，从而节省效率。随后，我们对北师大的校园地图进行合理的简化与建模，将长约为814m，宽约为787m的校园简化为110维矩阵，其中非道路部分、道路部分、垃圾清运点分别用0、l、2表示，相邻矩阵点之间代表约8米步长。

利用Matlab构建出地图矩阵，见图1.

2.2计算垃圾清运时间

在我们的模型中，垃圾车总花费时间T分为行驶时间T，和清理垃圾时间T。，有T=Tr+Te，其中总花费时间Te=∑Te，而每个垃圾桶清理花费时间Tei可由每日统计规律可以求得，我们不妨假设为120s/个，计垃圾桶的数量为rirub。对于行驶时间Tr=∑vij，我们不妨假设在每个区域有Vij≤Vave，其中Vave为校园内车辆上限速度，故可得行驶时间T，=sr/vave，此时，求解总时间最短的问题转化为求路程S.最小的问题，即对应清运垃圾的最优顺序。

对于坐标图G=（V，E），其中V是顶点集，E是边集，设S一（S。）是顶点1和顶点j之间距离所组成的距离矩阵，s，即为一条通过所有顶点且每个顶点只通过一次的最短路径回路。我们要对每一组垃圾桶序号v={V1，v2，…U}求得一个清理顺序，记为T={t1，t.，t2…tn}，其中t、∈V（i=l，2，3…n）.所以我们应先对每两个垃圾桶之间的距离Sij进行估计，再利用模拟退火算法求出最短路径S，及其最优顺序path，即可得到关于垃圾车总花费时间最小值的数学模型.

由前面的分析可知，理想模型与实际模型的根本不同点就在于对Srij估计方法的不同，下面我们就Srij的不同估计方法展开讨论。

2.3估计距离参数

2.3.1理想模型中Srij的估计

在理想模型中，我们直接考虑不同垃圾清运点间的直线距离，忽略具体的道路情况，将垃圾转运问题转化为一个简单的旅行商问题。但是考虑到北师大校园较小，所以我们修正了模拟退火算法中的距离求解方法，将原本根据经纬度计算距离的公式替换为欧式距离，故可以通过以下公式求得，

其中（xi，yi），（xj，yj）为第i个和第j个垃圾桶的坐标。

2.3.2实际模型中Srij的估计

在实际模型中，我们需要考虑不同清运点之间的真实行驶距离，对此采用元胞自动机的方法进行模拟。我们对垃圾桶按“先列后行”的规则进行编号，若要对第i个垃圾桶到第j个垃圾桶的距离Srij进行估计，则计算模拟垃圾车在两点之间运行的步长，这里根据计数方法的不同介绍两种估计方法。

八领域（Around8）计数法：我们将垃圾车不可走的方向赋予无穷大（inf）的值，同时还要求垃圾车以一定概率（不妨设为0.7）向终点距离（Aroundlen）的最小值方向移动一格，如果生成的随机数大于此概率，则在Aroundlen

拐点计数法：在进行元胞自动机模拟之前，我们要先在道路矩阵中设置出所有拐点（crossing）.同时，在八领域计数法的基础上，找出所有介于pointA和pointB之间的拐点并计算其位置（trace），紧接着再按照如下步骤找出一组拐点序列trace作为临时终点pointC，最后让垃圾车逐步从pointA走到pointB并计数，步骤如下：

第一步，先设置法向量N= （Ypoints - YpointA，XpoauA - XpointB），对trace按列位置分组。

第二步，对第]组（trim），第点位置为（Xtrlin（i），Ytrlin（i）），按∣N*（Xtrlin（i）- XpointB，Ytrlin（i）- YpointB）排序，取其中最小的作為第j个临时终点trace（j）.

借助这两套方法可以求出第1个垃圾桶到第]个垃圾桶之间的真实距离，再取两者最小值作为Srij，如此处理的原因是当垃圾桶数量很大时不可能枚举所有路径，所以要通过简化算法来实现对Srij的估计。第二种方法优势在于可以最快地找出比较好的路径且很稳定，但是由于没有随机性，求出来的解可能不是最优解，所以需要第一种方法补充。

2.4模拟退火寻求最优路径

在得到Srq的值后，先指定一条行驶顺序path，通过随机调换path中垃圾桶的清理顺序，计算路程改变量df，如果df<0则认为得到了更优的清理顺序，从而将此作为新的path，而如果df≥O则采取。

的概率（T=1）接受这种改变。最终计算迭代L=20000次后所求得的path，这时最优顺序即为path.

3模型的求解

理想模型中，使用Matlab进行2000次模拟仿真计算后得到S，ii=584个单位。而实际模型中，计算得到Srij的结果为Srij=631个单位。

将上述结果用北师大校园实际道路体现即为图2：

图2校园道路路线

最后结合调查结果得知校园限速内为5km/h，从而v-ave≈2.47单位/秒。

故理想模型中清运垃圾车花费总时间为

Tsum= Tr+∑T.=Sr/Vave+∑TC，≈237+∑Tcis=4557s

实际模型中垃圾车花费总时间为

4结论

该模型较好地解决了校园垃圾最优清运路线的规划问题，同时适用于多分支结构和网状结构分布，例如同城市物流网点分布、总子公司分布、通信领域的网点分布等。另外一个优点是算法简单容易实现，而且借助了模拟退火算法，比较容易理解。

同时模型也存在着一些不足，比如该问题在站点众多，运输半径较大的情况下，垃圾运输车运量的不足可能会造成无法满足其中任一点的垃圾清运工作，此时模型可能需要改进。

参考文献

[1]司守奎、孙兆亮，现代优化算法，数学建模算法与应用，12 （1）：323 329