城市生活垃圾收运路线优化模型及算法研究

王亚洁，贾顺平，蒋金亮

(北京交通大学交通运输学院，北京100044)

城市的高速发展使得人们对于生活环境质量的要求越来越高，生活垃圾问题就成为了人们关注的焦点。合理的收运路线可以使车辆的调度更加高效，减少行驶的距离，也可以有效地降低时间和燃料成本等，增加人力和物力资源利用的有效性。因此垃圾收运工作的重点就是合理地选择车辆收运路线。

车辆路径问题，邮政员问题和旅行商问题是国外车辆路线优化研究的主要内容。1995年，Chang［1］在分析环境与经济之间存在的关系后提出很多不确定因素影响着垃圾收运问题，灰色多目标混合整数规划模型(FIMOMIP)可以用来求解，量化不确定参数可以通过多目标分析结构中的间隔数据来解决。Cordeau，et al(2002)，Simone和 Borenstein(2007)对优化垃圾收运路线进行了计算机工具的模拟，结果证明其研究方法是可行的。2006年，El-Haggar和Badran运用了运筹学的方法研究出一种基于定量组合的计算机技术，使得分配车辆的启发式算法可以得到实现。

近年来，在国外研究成果的基础上，我国学者结合中国的基本情况对路线优化问题进行了大量的研究，从最初单一的目标到多个目标，从简单函数到不确定性多目标的路线模型，优化方法的研究也是不断改进和成熟。盛金良［2］进行了城市生活垃圾收运模式的研究，主要内容是关于收运系统设置中转与否是与哪些因素有关，最终得出影响因素包括垃圾量，车辆载货能力以及垃圾产生源与处理地之间的距离。台湾学者张乃斌［3］研究的是收集车辆路线和调度的问题，他建立了一个多目标混合整数模型，结合先进的GIS技术成功的解决了这个问题。

1 城市生活垃圾收运系统概况

1.1 城市生活垃圾概念及特点

生活垃圾包括两个部分，一部分是在平时生活中产生的或者是为了生活服务所产生的固体废弃物;第二部分是国家法律法规中规定的“固体废弃物视为生活垃圾”。我国城市生活垃圾具有以下特点:

第1，垃圾的成分比较复杂，性质不稳定。

由于人们生活的差异性，产生的垃圾也种类繁多。而且随着科学技术的发展，新产品和材料的产生使得垃圾成分变得复杂。

第2，生活垃圾的产生量、性质与成分与多种因素息息相关。

第3，城市生活垃圾具有很高的经济价值。生活中的很多当垃圾扔掉的物品经过回收后是可以再循环使用的，比如说废旧电池、废纸等。因此生活垃圾存在不可忽视的经济价值。

第4，垃圾量大，产生源分散，范围广。生活垃圾急剧增加的原因一方面是我国人口基数大，另一方面是城市的高速发展。生活垃圾的主要来源是家庭，因此所有的居住区域都是垃圾产生源，分布范围很广而且很分散。

1.2 城市垃圾收运系统

城市垃圾收运是指将垃圾从产生源运到垃圾处理场的整个过程，其中包含了3个阶段:收集、运输和转运［4］。人们将垃圾从产生源放至垃圾桶的过程即为收集阶段;运输阶段指的是车辆从车库出发以后，遵循一定的路线收集区域内的所有收集点的垃圾，然后运往垃圾转运站(有的情况下垃圾车直接运往处理场，不经过转运站);转运站发出较大容量的车辆将压缩后的垃圾运往处理场则是转运过程所包含的内容。

在收运过程中，第一个收集阶段需要调查区域现在的垃圾量及组成成分、垃圾产生源的分布情况等和预测其未来发展规模;清运阶段需要对垃圾车辆的收集路线进行优化设计，最后一个转运阶段需要对垃圾量运输进行优化分配。

图1 城市生活垃圾收运模式泾河特大桥MIDAS/Civil计算模型Fig.1 Municipal Solid Waste collection and transportation mode

城市的快速发展对于现有的环卫设施是一个巨大的挑战。按常住人口配置的环卫设施已经不能满足城市正常运转的需求，主要是由于外来人口的大幅增加，导致了城市垃圾量急剧上升;同时因为垃圾收运设施场地要求严格，所以城市能提供给它的场地有限，越来越远离垃圾处理场地。环保和废物资源化的高要求使得收运系统更加的信息化、规模化和规范化。

2 垃圾路线优化模型的建立

2.1 问题描述和符号说明

垃圾收运问题可以表达为在垃圾收集区域内，垃圾管理部门拥有多辆垃圾收集车辆，每天从车库出发后经过收集点进行垃圾收集，在垃圾量达到车辆的最大运输能力后开往中转站，将垃圾清空后再继续去收集点重复上述的工作，当所有的垃圾都被运往处理场后返回到车库。

一般情况下，垃圾收运路线问题的3个条件为已知，分别是车库、收集点和中转站之间的距离、各个收集点的垃圾量以及每辆垃圾运输车辆的最大载荷，根据这些条件可以求得最佳的车辆运输路线。

路线问题中定义 V={0，1，2，…，n，n+1}，编号0代表车库，收集点的编号则为1，2，3…，n。编号n+1代表转运站。可行解是满足运载能力等约束条件的解的集合。最优解是可行解集合中路线最短的解。

2.2 模型建立

笔者建立的收运路线优化模型是以收运总路线最短为目标函数［5］。建立数学模型中目标函数为:

约束条件的设置如下:

式中:qi为i点的垃圾量;dij为i点到j点的距离;W为垃圾车的最大容量;K为车库的车辆总数;nk为垃圾车k的收集点数(0表示没有使用垃圾车k);Lik为垃圾车k离开i点时车中的垃圾量;M代表无穷大∞。

式中:约束(2)表示车辆从车库出发;约束(3)表示垃圾收集点不会重复收集;约束(4)表示垃圾车k经过的收集点数比总的收集点数少;约束(5)表示不会遗漏垃圾收集点;约束(6)表示车辆的垃圾量不会超载;约束(7)表示车在离开车库和中转站时垃圾量为0;约束(8)表示上一个点离开时的垃圾量加上在该点的垃圾量等于车在下一个收集点离开时的垃圾量。

3 算法设计

3.1 遗传算法简介

随着收集点数的增加，模型的解以指数型的速度增长，传统的计算方法已经无法满足其求解要求，因此人工智能方法成为人们关注的焦点。

遗传算法(Genetic Algorithm，简称GA)作为一种启发式算法最初是由美国密歇根大学的John Holland教授在20世纪60年代提出的［6］，是由自然界生物进化规律衍生出来的一种全局寻优算法。染色体代表可行解，按照“适者生存”的原则，通过交叉和变异两种遗传操作产生出新一代环境适应性更强的染色体，这一过程反复进行直到达到某一收敛标准为止。最后得出环境适应性最强的个体，即最优解。

开始的时候有必要保留在最初最好的染色体。因为最优的染色体不一定是出现在最后，如果在进化后的种群发现更好的染色体的话，则用其来代替之前的最好的染色体，这样就产生了新的染色体。不断重复过程后，得出适应能力最强的染色体，即是最优解。

人工智能算法除了遗传算法之外还包括模拟退火算法(Simulated Annealing，简称SA)、禁忌搜索算法(Tabu Search，简称TS)等。TS算法的优势是所求得的解精确度最高，但是其运算耗费时间最长;SA算法相较于其他两种算法的优势是求解速度非常快，但精确度不高，所以通常用于求解较小规模的问题;而GA算法集合了上述两种方的优点，不仅解的精确度高，而且运算时间也相对较短，所以GA算法能够同时兼顾到精确度和运算时间两个方面，在解决路线优化问题上具有广阔的应用前景，所以本文选用遗传算法进行求解。

3.2 遗传算法设计步骤

3.2.1 初始化

初始化可行解，一般以随机方式产生一个初始可行解向量，记为 x=(bi)，i=1，2，…，n，其中 bi是数据或称为个体，遗传算法的思路是按照一点的规则不断更新个体，尽可能从中选出最优个体，直到找出全局可行解为止。n的取值范围在30～160。

3.2.2 选择操作

以适应度函数的函数值作为“优胜劣汰”的指标来选出更优的可行解，通过不断迭代使得解能够逐渐向全局最优点靠近，式(9)是一个适应度函数，其中bi表示适应度，适应度小的个体，被选择的概率就相应小，还可能是0，也就是个体被淘汰。适应度高的个体被选择的概率大，其繁殖的下一代数量比较大。通过这样的选择方式就可以产生适应能力强的后代。

3.2.3 交叉操作

基因的交叉操作是指可行解域内的任意两个个体将以一定的概率Pc被选择，并交换相同位置上的数据，即进行基因交换重组，得到新的个体，根据经验，交叉概率Pc的一般取值范围为0.4～0.99。

3.2.4 变异操作

基因的变异操作指的是对可行解本身进行操作，可行解域内的任意个体将以一定的变异概率Pm发生某些数据位的变化，从而得到新解。这样的变异过程可以增加种群的多样性，染色体之间差异性的提高可以避免种群规模有限而导致的进化终止。根据经验，变异概率 Pm取值在0.001～0.1。

3.2.5 算法停止准则的设计

算法必须是收敛的，不能一直无休止的进行下去，即在经过可数步长之后算法应该能够自动停止。根据不同的需要可以选取不同的收敛标准，设计不同的停止准则，一般常用的是选取指定步长的方法，但是步长的大小对结果有较大的影响，所以需要反复试验以确定合理的步长大小。一般建议的终止代数范围为100～1000。

4 案例分析

4.1 背景设计

先说明本案例的垃圾收集方式，在此垃圾收集区域，居民将垃圾装入垃圾袋后送往收集容器内，车辆将垃圾收集后运至中转站，再由转运站的压缩垃圾运输车将压缩过的垃圾运往填埋场。

在本区域里，只有一个车库，它的编号为0，车库有一辆垃圾收集车，垃圾收集车的载重量为5 t，垃圾收集点为 i，i={1，2，…，8}，垃圾中转站的编号为9。车库、收集点和中转站之间的距离(km)以及各个垃圾收集点的垃圾量(t)如表1。

表1 垃圾收集点信息Table 1 information of waste collection point

4.2 优化结果分析

运用MATLAB软件进行遗传算法编程，经过10次计算，结果如表2:在10次的优化结果中，有两条路径为最短路径，长度为26 km，路径1为车库0→收集点7→收集点8→收集点6→收集点1→中转站9→收集点5→收集点4→收集点2→收集点3→中转站9→车库0;路径2为车库0→收集点2→收集点7→收集点6→收集点1→收集点3—中转站9→收集点5→收集点4→收集点8→中转站9→车库0。10次的优化结果平均值为29.6 km，标准偏差为2%，说明运算结果具有良好的稳定性，运算时间在4～5 s，说明遗传算法收敛速度较快。所以遗传算法能兼顾时间和效率两个方面，由此可以看出遗传算法在路线优化方面具有很强的可行性，具有很好的研究和发展前景。

表2 遗传算法计算结果Table 2 results of genetic algorithms

5 结论

笔者介绍了一种人工智能启发式算法——遗传算法，并通过MATLAB程序进行了遗传算法编程实现了模型的求解。最后通过实例进行了验证，遗传算法在车辆路线优化的计算中较为简便，通过计算机程序实现较为容易，具有很强的可行性。

但是文中还存在着很多的不足之处，在实际的收运路线问题中面临更多更为复杂的基于现实的细节性要求，而且遗传算法对参数设置和遗传算子表现出较强的依赖性，不恰当的参数及算子设计往往导致算法的早熟或不收敛，依据遗传算法的缺点，结合其他人工智能算法的特点，构造出混合算法来进行求解是算法未来的发展方向。

［1］Nibin Chang.Managerial fuzzy optimal planning for solid waste management systems［J］.Journal of the Environmental Engineering，ASCE，1996，122(7):649-657.

［2］盛金良，曹春华.城市生活垃圾收运模式设计［J］.环境卫生工程，2000，8(2):85-87.Sheng Jinliang，Cao Chunhua.Design of municipal solid waste collection and transport system［J］.Environmental Sanitation Engineering，2000，8(2):85-87.

［3］王芳芳.基于改进蚁群算法的城市生活垃圾收运路线优化研究［D］.北京:北京工业大学，2011.

［4］王康乐.垃圾收运车辆路线的优化及其应用［D］.南京:东南大学，2005.

［5］路玉龙，赵扶摇，韩靖，等.城市生活垃圾收运路线优化的数学模型与算法［J］.环境科学与管理，2010(6):46-50.Lu Yulong，Zhao Fuyao，Han Jing，et al.Mathematical model and algorithm for route optimization of municipal domestic waste collection and transportation［J］.Environment Science and Management，2010(6):46-50.

［6］王文梅.基于单亲遗传算法的城市垃圾收运路线优化研究［D］.成都:西南交通大学，2005.