文/张燕红

1.引言

随着城市规模的不断扩大和经济水平的逐步提高，我国生活垃圾清运量增长迅速[1]。在国内外学者的研究中，有诸多算法[2-5]可用于解决垃圾收集阶段的车辆路径优化问题。本文通过比较扫描算法和遗传算法的计算效果，从两者中选择较优的一方，作为将来在研究垃圾收集阶段车辆路径问题的求解算法。其中，本文的优化区域共计10个转运站，它们负责服务多个收集点。求解时，采用两阶段算法，先使用整数规划将收集点指派给转运站，再分别使用扫描算法和遗传算法计算其车辆的运输总路程。

2.扫描算法

将扫描算法应用于本文的城市生活垃圾收运问题，根据调研得知，运输车辆通常从一次转运站出发访问各收集点，则对应的起始点为各一次转运站，约束条件是垃圾收集车车辆的限重，满足约束条件的收集点则加入当前组中，直到垃圾收集车辆载重达到限定值后，建立一个新组，只有当所有的收集点都归入相应组时算法停止。这样，每一个组便形成了一条大致路径，即垃圾收集车辆可以从一次转运站出发，按顺序经过每组中的各收集点，最后返回一次转运站。

3.遗传算法

将遗传算法运用到本文所研究的垃圾收集阶段的收运路径问题中，以200个收集点，10个转运站为例，进行算法构造的处理细节如下：（1）编码方式的设计。本文采用实数编码方法，垃圾收集点用序号1~200表示，垃圾一次转运站用序号201~210表示，且序号具有唯一性。（2）初始群体的确定。完成上述编码及其他相关数据设置后，接着根据一次转运站和垃圾收集点的数量、地理位置以及垃圾收运能力或垃圾产生量等因素，使用整数规划理论求解出各个转运站服务的收集点。而后，将各转运站服务的收集点序号随机排列生成个体，且每个个体不出现相同的自然数。本文的群体规模确定为20。（3）适应度评估。个体的适应度是用来评估其方案优劣程度的，此处的目标函数值是运输路程长度，当目标函数值越小时，它的适应度反而越大。因此，本文的适应度函数F（x）与目标函数f（x）的关系为：maxF（x）=min（-f（w））。（4）选择操作。将种群中的多个个体根据其从大到小的适应度进行排名，选出排名靠前的20名留下作为下一次迭代的父代，同时，将较劣的路径方案舍去。其中排名第一的个体在性能上是最佳的。（5）交叉操作。对于之前已通过选择操作才生成的新种群，此处采用0.8的交叉概率，使用类似OX法的一种交叉方法，随机在父代个体中选择交配区域[37]。（6）变异操作。自然界中，变异是后代基因根据小概率改动的变化。在遗传算法中，为模拟自然界的变异故将种群突变的情况设置为小概率事件，可能会使群体中小部分个体发生改变。本文中取0.1的突变概率，即对于每一个父代（染色体），生成1个0~1之间的随机数，若该数小于突变概率，则父代执行变异操作，且每次改变其位值的基因数只有两个，变异时基因换位次数取1。（7）终止判断。本文选取的终止准则为迭代次数限制，当迭代次数未达到设定代数时，运算继续循环；反之，则运算停止。

4.结果分析

根据上述提到的扫描算法和遗传算法运用到垃圾收运问题的具体步骤，使用专业求解软件编程分别计算重庆市主城区10个一次转运站各自的垃圾收运总路程，得到的结果见表1所示。

表1 扫描算法和遗传算法计算结果比较

从表1可以看出，在扫描算法的计算结果中，最小的是13.71km，最大的是795.37km；在遗传算法的计算结果中，最小的是11.1km，最大的是656.3km。其中第一个转运站服务的收集点较少，因而使用两种算法计算得出的运行总路程均较小；而第七个转运站服务的收集点较多且部分收集点位于面积较广的风景区，因此其运行总路程对于其他几个转运站而言最大。同时，可以发现对于一次转运站至收集点的垃圾收运工作路径安排，采用遗传算法计算得出的运输总路程相较于扫描算法计算得出的运输总路程而言更少，且大多数转运站的优化比例超过10%，其中有两个转运站的优化比例在20%左右，优化效果较好。

5.结论

综上所述，采用遗传算法能够有效解决垃圾收运路径问题，减少垃圾收运车辆运输总路程，从而降低在途运输时间，从而为缓解道路交通压力、助力“生态文明城市”建设贡献力量。

引用出处

[1]中华人民共和国国家统计局.中国统计年鉴[M].北京:中国统计出版社,2015-2021.

[2]赵红霞,刘高森,李愈.基于随机游走的分类垃圾回收最优路径规划[J].交通运输工程与信息学报,2018,16(3):103-108.

[3]Nowakowski P,Szwarc K,Boryczka U.Vehicle route planning in e-waste mobile collection on demand supported by artificial intelligence algorithms[J].Transportation Research Part D:Transport and Environment,2018,63:1-22.

[4]张玉州,张子为.基于合作协同进化的多回收站点垃圾收运问题求解[J].中国科学技术大学学报,2020,50(5):695-704.

[5]朱明华,范秀敏,刘炳凯,等.上海浦东新区城市生活垃圾收运路线优化研究[J].资源科学,2009,31(9):1612-1618.