基于油耗和低碳的垃圾收集路径优化研究

王 瑞，单而芳

（上海大学 管理学院， 上海 200444）

基于油耗和低碳的垃圾收集路径优化研究

王 瑞，单而芳

（上海大学 管理学院， 上海 200444）

随着我国城市垃圾产量的日渐增多，如何使垃圾收运过程无害化、节能化，已成为综合治理环境的新挑战.垃圾收运费用在整个垃圾处理系统中占很大比例，同时随着人们生活水平的提高，人们对生活环境和身体健康更加关注.因此，本文将油耗和碳排放因素考虑到垃圾收集问题中，建立了以运输距离、油耗和碳排放相结合的多目标垃圾收集问题模型，并采用基于插入算法的文化基因算法进行求解，通过标准算例说明了该算法的有效性和实用性.

WCVRP 问题；油耗；低碳；文化基因算法；城市生活垃圾

对于 WCVRP问题，目前国际上还没有将油耗作为目标函数进行优化，而 WCVRP问题与 VRP问题一样：服务过程中会产生大量的油耗.因此，本文考虑总路程、能源和环境等多方面因素，建立了WCVRP问题的数学模型，采用基于插入算法的文化基因算法进行求解，通过实例求解验证了该算法解决实际问题的可行性和有效性.

1 问题描述和符号说明

1.1 问题描述

WCVRP问题的收运过程可以描述为：垃圾收运车辆从车库出发，在规定的时间内到达垃圾点收集垃圾，直至车辆达到容量限制，就运到处理厂卸空垃圾.车辆卸空后，再返回继续收集，如此重复，直到服务完所有的垃圾收集点，车辆卸空后返回车库.

具体描述为：在满足载重和时间约束的前题下，如何合理安排车辆路线，在满足每个垃圾点被收集且只收集一次的同时，使运输距离、油耗、碳排放量最小.

1.2 符号说明

WCVRP问题意为图 G=(V,A),V=VdYVfYVc，其中：车库 Vd={0}，为了方便，车库节分为开始和结束{0,0'}，m个垃圾处理站 Vf={1,…m}，n个垃圾收集点Vc=(m+1,…,m+n)弧 A={(i,j)|i,j∈V,i≠j}.一共 K种车型（k=1,2,…k），k车型的数目为 gk，车容量为 qk，tij、为车型 k在弧(i,j)相应的运输时、运输距离，sij、[ai, bi]是垃圾点 i∈V相应的服务时间和时间窗，qi为垃圾点 i∈Vc的垃圾收集量，变量}当且仅当车型 k的第 g辆车从 i到 j时当且仅当任务 i由 k车型的第 g辆车服务∈{0,1}当且仅当车型 k能收集 i点时，表示型 k的第 g辆车收集到垃圾点 i时，已累计收集的垃圾量表示车型 k的第 g辆车开始收集垃圾点 i的时间，hk表示第 k型车的碳 -排放因子.

1.3 建立模型

一般在给定车型的情况下，油耗与载重有关，本文假设二者成正比关系表示 k型车空载时的单位油耗，Qk表示 k型车满载时的单位油耗，ri表示服务完 i后车辆实载率，则 k型车服务弧(i,j)的单位油耗量为：

WCVRP问题的数学模型可建为：

（1）目标函数

（2）约束条件

目标函数为运输距离、油耗量、CO2排放量最小，公式（1）、（2）保证所有车辆必须从车库出发，完成任务后回到车库，公式（3）所有垃圾收集点必须且仅收集一次，公式（4）、（5）是对车辆的服务时间和时间窗的限定，公式（6）车辆从车库出发和回到车库要保持车是空载，公式（7）保证每个垃圾点只有一种相容车型的一辆车收集，公式（8）、（9）表示两个变量间的约束关系，公式（10）是对多类型车辆车容的限制，公式（11）、（12）非负二元变量.

2 算法设计

WCVRP问题是大规模车辆路径问题，需要处理的垃圾点往往很多.文献[11]中提到的文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体，通过局部搜索提高个体适应度，使以后的操作种群变小，进而提高算法的效率.本文局部搜索采用爬山法，全局搜索采用遗传算法.文化基因算法首先通过插入算法得到一个初始种群，然后通过选择、交叉、突变和适应来一代一代淘汰不良个体，选出最优解.

2.1 初始种群

为了得到初始种群，我们采用所罗门的插入算法.该算法路线选择基于两个标准：距离当前点最近和时间窗最早.如：从车库开始选择距离车库最近且时间窗允许的的垃圾点收集，收集完后，选择距离当前垃圾点最近的垃圾点收集，当车达到额定容量的时候，到最近的垃圾处理厂卸空垃圾.再返回收集，直至服务完所有的垃圾收集点.车辆到垃圾处理站卸空后，回到车库.路线顺序为[车库、垃圾点、垃圾处理厂、车库].因此，所有的垃圾收集点都被服务完，就得到了初始种群.

2.2 适应度函数

基于目标函数，适应度函数可以表示为：

θ1，θ2，θ3：为权重表示每个目标的重要程度.根据每个目标的重要性，给予权重相应的值.

2.3 交叉和突变

用染色体表示的顶点序列代表每个个体，由于车库和垃圾处理厂不需要被服务，所以，进行交叉和突变时，要将车库和垃圾处理厂在顶点序列中删除.交叉是繁殖下一代的主要部分，它的操作对象是两个个体.随机选择两个个体作为父代，两个染色体之间部分基因先互换，然后选择一个或多个基因（顶点序列）进行交叉.图 1阐述了两个个体 P1，P2位置 1、2以及位置 6-9的基因互换，然后，P1的位置 4、7和第 P2的位置 7、10上的基因交叉.两个新的个体 O1,O2就产生了.

图1 交叉程序步骤

突变操作的对象是一个个体，它交换一个染色体的两个或多个基因.图2阐述了孩子这一代O1的染色体位置3与位置7的基因，位置9和位置10的基因交换，形成新的突变后的个体.

图2 突变操作随机交换例子

由于进行交叉和突变时，把车库和垃圾处理厂删除了，为了保持路线的完整性，要把车库和垃圾处理厂插入.当染色体的下一步违反约束时，就将合适的垃圾处理厂插入解中.违反的约束被删除，继续进行下一步.如：车辆收集了垃圾点 7-9-11后，达到了车辆的额定车容，则在垃圾点 11后插入一个距离垃圾点11最近的垃圾处理厂，卸完垃圾后，再继续收集垃圾.最后，把车库加在染色体的头和尾，形成一个车辆完整的路线.如：路线 0-7-9 -11-1-8-5-3-6-4-2-10-13-12-0，其中 0为车库，1、2为垃圾处理厂，其余为垃圾点.

2.4 停止条件

定义每代种群的适应度函数为：

zi(pop)：评估发展中的第 i代种群；

avgi(pop)：种群中第 i代所有个体的平均值；

maxi(pop)：种群中第 i代所有个体的最大值；

如果 zi(pop)的值在第 i+1代后不再发展，且发生了 n次，则算法结束.

3 数据分析

本文采用标准算例 1（数据来源于 http://www. hec.ca/chairedistributique/data/)，算法采用 matlab编程实现.算例有 3种车型，2个垃圾处理厂，16个垃圾收集点，车辆信息：车型 1：数量 3、车容 10m3、载重 30Kg、碳排放因子 hk2.78Kg/L、空车油耗 Q0k0.09L/Km、满载油耗 Qk0.15L/Km；车型 2：数量 5、车容 8m3、载重 60Kg、碳排放因子 hk2.54Kg/L、空车油耗 Q0k0.07/Km、满载油耗 Qk0.13L/Km；车型 3：数量8、车容 5m3、载重 30Kg、碳排放因子 hk2.25Kg/L、空车油耗 Q0k0.05L/Km、满载油耗 Qk0.10L/Km.

采用上述算法，设置基本参数为：最大迭代次数 T=150，种群规模 G=50，θ1=0.5,θ2=0.3，θ3=0.2.在MATLAB平台上运行的结果为：

具体表述为详细路径即：路径 1：车库 0→垃圾点 9→垃圾点 12→垃圾点 17→垃圾点 15→垃圾处理厂 2→车库 0，使用车型 1.路径 2：车库 0→垃圾点 3→垃圾点 6→垃圾点 11→垃圾点 10→垃圾点7→垃圾处理厂 2→车库 0，使用车型 3.路径 3：车库 0→垃圾点:4→垃圾点 14→垃圾点 16→垃圾点18→垃圾处理厂 1→垃圾点 5→垃圾点 13→垃圾点 8→垃圾处理厂 1→车库 0，使用车型 2.得到满意解 13512.00.

表1 结果比较

以车辆总路程为目标和以车辆总路程、油耗量、co2排放量为目标进行优化的结果进行比较由表 1得出：以车辆总路程、油耗量、co2排放量为目标与车辆总路程相比，虽然总路程有一些增加，但油耗量和 co2的排放量明显减少.减少了能源消耗，减轻了环境污染，对城市可持续发展和人民身体健康有积极作用.

4 结论

为了保证市容、市貌，垃圾处理是市政当局急需解决的问题.垃圾收运是垃圾处理的关键环节，因此，对垃圾收集路线进行优化，可以减少成本、节约能源、降低环境污染.本文针对垃圾车型号相同造成的车辆利用率低的现状同时考虑油耗和环境污染等因素，提出了基于油耗和低碳的多车型垃圾收集路线优化方案.采用文化基因算法对该问题进行求解，得到了问题的满意解.这开辟了对垃圾收运问题研究的新思路，研究垃圾收运路线时考虑节能和环境保护问题具有理论价值和现实意义.

〔1〕路玉龙,赵扶摇,韩靖,张鸿雁.城市生活垃圾收运路线优化的数学模型与算法[J].环境科学与管理,2010,30(5):46-50.

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

O242；X799

A

1673-260X（2014）08-0026-03