多品类生活垃圾收运的车辆路径优化问题研究

贾焙皓

摘 要：近年来随着中国逐步制定并开展垃圾分类的政策法规，多品类生活垃圾分类收运问题就逐步凸显出来。国内使用多车舱车辆收运多品类生活垃圾的研究还较少，针对这一需求，本文基于生活垃圾分类利用多车舱垃圾收运车辆同时收运多品类生活垃圾的收运问题，以降低城市生活垃圾收运成本为目标，构建考虑车辆收运成本的多品类垃圾收运车辆的路径优化模型，并进行仿真实验，用蚁群算法对算例进行求解，验证了算法模型的良好寻优效果，为新式垃圾车辆的投产使用提供参考。

关键词： 生活垃圾收运;多品类;车辆路径优化;蚁群算法

文章编号： 2095-2163（2021）01-0114-06 中图分类号：X799.3 文献标志码：A

【Abstract】In recent years， as China has gradually formulated and implemented waste classification policies and regulations， the problem of the classification and transportation of multi-category domestic waste has gradually become prominent. Domestic research on the use of multi-cabin vehicles to collect and transport multi-category domestic waste is still rare. In response to this demand， this article is based on the classification of domestic waste and uses multi-cabin waste collection and transportation vehicles to simultaneously collect and transport multi-category domestic waste to alleviate the problem of collection and transportation. The cost of collection and transportation of municipal solid waste is the goal. The route optimization model of multi-category waste collection and transportation vehicles considering the cost of vehicle collection and transportation is constructed， and simulation experiments are carried out. The ant colony algorithm is used to solve the example， which verifies the good optimization of the algorithm model. The effect provides a reference for the production and use of new garbage vehicles.

【Key words】domestic waste collection and transportation; multi-category; vehicle routing optimization; ant colony algorithm

0 引 言

自从2017年国家发展和改革委员会、住房和城乡建设部出台《生活垃圾分类制度实施方案》[1]以来，垃圾分类已经在北京、上海、广州等地成功实施，但是随着垃圾分类时代的来临，传统的垃圾处理能力与垃圾分类处理能力之间的问题日趋凸显，如何将多品类城市生活垃圾做到分类收集运输，促进后端垃圾资源化处理是当下亟需解决的问题。

由于中国城市生活垃圾分类处理才刚刚起步[2～3]，许多城市在垃圾分类、经费投入、管理体系等方面还存在不足，在分类收运方法上仍处于不断探索之中。中国宁波市鄞州区环卫部门为了适应街道定时定点分类投放的新政策，改装了一种两类一体垃圾收运车辆，实现厨余垃圾和其他垃圾同步收运，既减少车辆和人员的投入，又可实现居民一次性投递，大大提升了居民和管理部门的满意度。

1 文献综述

城市多品类生活垃圾收运模式是一种有载重限制的逆向车辆路径问题，与经典的车辆调度问题存在一定的差别，目前国内外研究成果较少。仅就国内来说，大量的学者从垃圾收运主体（环卫部门和垃圾收运公司）入手，将垃圾车辆收运调度问题方面需考虑的主要因素，分为2个方面，即：固定成本和收运路径成本。其中，固定成本包括工人工作成本和车辆使用成本;收运路径成本则重点涉及2个方面，就是：时间成本和距离成本。具体来说，在时间成本上，主要从垃圾收集的频次[4]、中转站排队时间[5]、装卸时间[6]以及其他的影响上述因素的效率惩罚成本等方面进行拓展研究;在距离成本上，主要是从车辆的行驶成本、碳排放成本、车辆故障维修成本[7～9]等方面进行了研究探索。在同时使用多隔间的车辆问题上，研究还并不充分，且研究焦点大多集中在：生产车间调度[10]和零售货物的配送[11]上。現行的货物调度运输情况都是以各类物品单独运送为主，都是以多车型多品类的货物调度为研究对象，对多品类货物的同时调度研究较少。

基于垃圾分类-多品类生活垃圾收运的车辆路径问题，是属于多车厢车辆路径问题（Multi-Compartment Vehicle Routing Problem，MC-VRP）。国外早在1979年就证实该问题具有实际意义，且2006年Fallahi等人[12]解决了仓库库存的配送问题，即：m种不同的产品必须由一组相同的车辆交付给客户，每辆车都带有m容量有限的隔间，其与多隔间垃圾收集问题不同，允许不同的车辆向同一客户交付不同的产品。在国内的冷链物流中，运用多隔间多温共配模式较多，陈婧怡等人[13]采用多温区冷藏车， 构建考虑运输成本、货损成本、制冷成本的路径优化模型， 利用遗传算法对算例进行求解， 借助ArcGIS规划最短路径，取得较好的成效，证明了多隔间收运模式的可行性。

但是在生活垃圾资源化回收利用这种逆向物流问题中，利用多隔间的收运车辆进行收运的研究还不多。本文是在基于垃圾分类的情况下，来研究新式多品类城市生活垃圾收运车辆的路径优化问题，该研究与现有的垃圾路线优化问题的区别主要体现在： 考虑了垃圾收运资源化的分类特性;考虑了多品类生活垃圾实际收运过程中的同时性。并与传统“一类一车”的各品类单独分开收运模式作对比分析，研究多品类生活垃圾同时收运模式下相对于传统的收运系统的优劣，为中国垃圾分类收运的推进提供参考。

2 问题提出

研究问题描述：在一个收运区域内，有一个停车场，一个垃圾中转站和多个垃圾收集点，车场有多辆同类型的车辆，每台车辆都有多个容量大小固定的车箱隔室，不同车箱隔室的容量可以不同;每个垃圾收集点都有多种垃圾品类，不同品类的垃圾需要放在不同的隔室进行收运，同时每个收集点需要在一次服务中完全满足。假设已知如下条件：

（1）每个垃圾收集点的各类垃圾量已知。

（2）车场和收集点、收集点和收集点、收集点和中转站、中转站和车场的距离已知。

（3）每辆车每个隔间的额定载重限制已知。

（4）垃圾收运车辆匀速行驶且速度已知。

研究可知，垃圾车辆的收运过程可概述为：收运车辆均从停车场出发，对垃圾收集点进行服务，当收运车辆任一隔间满载或完成最后一个收集点时，返回至中转站卸载，重复上述过程，直至服务完成所有点的垃圾收运工作后，车辆重新返回车场，完成收运工作，其收运过程示意图如图1所示。

该问题在运筹优化领域就是一个图论求解。文中用G表示整个垃圾收运区域，G=（V，A），其中，V=Vd∪Vf∪Ve，且节点Vd={0}表示车场，Vf={1，2，3，…，n}表示n个垃圾收集点，节点Ve={n+1}表示中转站;A={（i，j），i，j∈V，i≠j} 表示不同节点之间的弧集。

3 基于垃圾分类下多品类垃圾收运的处理

建立基于垃圾分类收运下，多品类生活垃圾同时收运的数学模型为：

决策变量为：

需要指出，本文采用了三下标的决策变量进行建模，其中，xijk=1表示第k辆车经过弧路径（i，j），否则xijk=0;dij表示收集点i到收集点j之间的距离;C表示单位距离运输成本;qmi为垃圾收集点i的第 m=1，2，3，…，M 类垃圾量;Qmk表示第k辆车装载第m类垃圾的最大载重限制。

目标函数（1）表示最小化垃圾收运的费用;约束（2）表示决策变量，为整数变量0或1;约束（3）表示每辆车都由车场出发;约束（4）表示每辆车收运完成后都返回车场;约束（5）保证每个收集点被服务且只被服务一次;公式（6）表示车辆到达一个点的同时必须离开这个点，保证车辆的路径始终为环形;公式（7）表示第n个隔间的载重限制，不能超出其核定载重量;公式（8）和公式（9）表示从车场出发和最后返回车场时均为空车。

4 算法设计

目前，对于生活垃圾收运车辆路径这类NP-hard问题，求解的主要方法是：粒子群算法[5] 、遗传算法[9]等智能启发式优化算法，群智能优化算法是根据生物的生活特性，创造出最优可行解的寻找方法，不同算法的最大不同特点，就是其将解空间映射为算法寻优的特殊行为。蚁群算法（Ant Colony Optimization， ACO），最早是由Dorigo[14]于1992年提出并设计的一种群智能搜索算法，其在路径选择问题的求解上具有天然的优势，因此本文选择最具特点的蚁群算法作为求解方案。

4.1 垃圾收运路线的蚁群优化算法方案

本文在生活垃圾收运问题中的车辆选择居民垃圾收集点部分，应用蚂蚁寻找食物的思想来设计蚁群优化算法方案。每一只蚂蚁的行走路线在解空间中表示一个可行解，即表示一个可行路径方案，每个食物点表示一个未服务的居民垃圾收集点，车辆收集垃圾的过程就相当于蚂蚁觅食的过程。

在初始时刻，所有的蚂蚁都在车场坐标出发，各条路径上的信息素初始值相等。在移动过程中，下一個收集点的选择借鉴了文献[15]随机性选择与确定性选择相结合的选择策略，根据每条路径上的信息素浓度σij、能见度φij、车辆的载重限制，并结合确定规则和随机选择相结合的策略来寻找下一个待访问的收集点j，利用如下公式来表示上述的转移规则：

依据如下概率Pki并应用轮盘赌法选择j点

其中，r是[0，1]的随机变量;r0为用来控制蚂蚁寻找规则的参数，在这里取0.5;Nki表示车辆k从i点出发可以访问的所有收集点j（满足车辆各个隔间的载重约束且未被服务）的集合。

以上就是作为个体的蚂蚁路径选择的规则，而蚁群算法是一个借助群体信息交流的智能优化算法，信息素的更新规则就显得尤为重要，在信息素更新时，本研究采用了最大—最小蚂蚁系统的信息素更新方式。

4.2 算法的编码解码

本文参考文献[4]对解空间采用实数编码进行编码、解码等行为，用数字n=1，2，3，…，N表示居民区垃圾收集点，数字0表示中转站，N+1表示车场。

例如：对于解空间ans={2，4，18，24，10，7，1，9}，客户点对应垃圾品类1的产生量为Q1={0.3，0.4，0.9，0.8，0.7，0.6，0.6，0.5}，垃圾品类2的产生量为Q2={0.1，0.2，0.1，0.2，0.1，0.2，0.1，0.1}，车辆的最大载重重量为3，品类1的占比为80%，品类2的占比为20%，则解码后的结果为{0，2，4，18，24，0，10，7，1，9，0}，这表示在正常的收运过程中，第一辆车从中转站卸载完毕后出发进行下一次收运，服务完收集点2，3，18，24四个点后，车辆的任一隔间满足车辆载重限制后，再折返中转站卸载;同理，第二辆车的行驶路线是服务收集点10，7，1，9四个点后，由于品类1的隔间到达载重上限，需要返回中转站处理后继续下一次任务的安排。

4.3 算法实现步骤

结合以上的算法方案，多品类垃圾收运路线优化的基本步骤如下：

Step 1 初始化蚁群数量Num、迭代步数iter=1、信息素浓度Tau是元素全为1、且行列数为该系统所有服务点个数的矩阵、各个隔间的车辆载重限制Q等算法参数，读取收集点的数据，并将所有蚂蚁的起始位置都放在车场。

Step 2 让一只蚂蚁从车场出发，采用顺序构建解的方式，如果蚂蚁在该收集点收集完成后，超出其任一车厢的载重限制，则该点即不进行收运，要返回中转站进行卸载处理后，再进行下一次任务的安排。

Step 3 按照Step 2以及规则（10）构建出所有蚂蚁的可行收运路线R，并用元胞数据格式存储。

Step 4 按照目标函数（1）求各个蚂蚁的收运成本，计算出最小成本，并记录下该代的最佳路径Rbest以及最小成本。

Step 5 更新迭代信息素。按照最大最小蚂蚁系统的信息素更新方式更新。

Step 6 iter=iter+1，若iter

5 仿真实验

为了验证本文设计的多品类生活垃圾收运问题的数学模型和算法的有效性，设计了仿真算例，进行了数据的数值仿真实验，并对结果进行了分析。

5.1 仿真算例

随机生成30个居民生活垃圾收集点，一个垃圾收运中转站的坐标为（4.91，5.06），一个停车场的坐标为（4，8.51），坐标单位为km。设车场共有10辆同类型多隔间生活垃圾收运车辆，所有车辆从同一停车场出发，并最终回到停车场。单位距离的收运成本C=10元/km;每辆车最大载重量Q=3t。仿真算例中生活垃圾收集点的坐标信息以及垃圾数量见表1。

5.2 参数设置及算法比较

本文采用Matlab编程，在Windows7系统上，i3处理器的电脑上进行运算验证。将蚁群算法和生活垃圾收运车辆调度的遗传算法进行比对，来验

证改进的蚁群算法在生活垃圾车辆调度问题方面求解的性能。人工蚁群的参数设置：最大迭代次数500，蚁群数量为50只，信息素重要程度因子alpha=1;启发函数重要程度因子beta=3;用来控制转移规则的参数r0=0.5;信息素挥发因子rh0=0.85;更新信息素浓度的常数Q=5;对比遗传算法，采用的是改进的自适应遗传算子，其参数设置：进化代数为500，种群规模为50，选择概率为0.1，自适应算子的概率参数为0.0025。为了对比算法求解性能的优劣，设置车辆上品类1的装载容量占比（α=品类1载重/总载重）α=20%，40%，60%，80%，共4组参数，对每组参数分别采用蚁群算法和遗传算法连续进行10次实验。实验结果数据见表2，结果曲线如图2、图3所示。

通过图2、图3可知，在选择合适的算法参数时，蚁群算法求解多品类生活垃圾同时分类收运问题具有比较好的寻优求解效果。无论是最优值，还是在平均值上，都优于遗传算法，因此本文采用蚁群算法进行求解分析。

5.3 实验及结果分析

采用改进的人工蚁群算法对模拟仿真算例进行求解，为验证多品类共同分类收运方案的有效性，将其与单品类收运方案的收运成本进行了对比，结果见表2。

多品类共同分类收运成本的变化趋势如图4所示。

通过表2以及图4的多品类共同收运的成本变化，显然就可以看出：对于垃圾收运点垃圾量为静态已知的情况下，随着各个垃圾品类隔间载重比的变化，收运成本的改变是显著的，说明车辆各个隔间的载重比例对多品类垃圾同时分类收运的成本影响比较大。

从垃圾量总体数据上来看，品类1和品类2的总量比例接近4：1，当垃圾收运车辆隔间比例与真实的垃圾总量比例差距较大的情况下，收运成本反而不如各品类单独收运;相反对于比例适当的情况下，利用多隔间车厢同时分类收运，能够降低收运成本。由此可知，根据垃圾总量的规律设计合适的车厢隔间比例能够大幅提升垃圾收運系统的收运效率，节省收运成本。

在做实验的过程中，为了验证多品类垃圾收运车辆各个品类隔间的比例与实际垃圾产生量的关系，分别在不同比例的垃圾总量下，进行了模拟实验，垃圾点的位置坐标不变，垃圾点的量发生变化，由于篇幅限制，只展示实验参数和结果见表3。

从表3的结论可知，多品类收运车厢隔间的最优配比与垃圾总量的配比成正相关。因此要想投入使用新式垃圾收运车辆来分类收运多品类生活垃圾，需要对各品类生活垃圾总量做好统计调查，适当的车箱载重配比能有效减少收运成本。

由以上模拟实验，可以得知在表1的仿真数据下，2个品类的车厢隔间载重最佳配比为4：1，也就是品类1的载重占比为80%，采用多品类共同分类收运的模式比单品类分开收运更节省成本，其最优收运方案见表4。

6 结束语

针对街道商铺的定时定点分类投放收运的政策，多品类垃圾收运车辆同时收运能有效减少车辆的收运距离，减少居民投放垃圾的次数，提高了垃圾收运系统的收运效率，从而有效减少城市生活垃圾收运的成本。本文通过对多品类生活垃圾同时分类收运的收运模式，进行数学建模，设计改进的蚁群算法进行求解。求解结果与数值分析表明，与传统的单独收运模式相比，多隔间车辆收运多品类生活垃圾，能有效降低城市生活垃圾收运成本;不同的垃圾总量比例，影响到车辆舱室容量的比例，不同的车舱容量比例对收运成本的影响较大。本研究为多品类城市生活垃圾同时收运提供理论指导，决策者可以基于不同的垃圾量使用不同的车舱容量比例，得到相应的优化路线。

参考文献

[1]佚名. 生活垃圾分类制度实施方案[J].中华环境，2017（8）：20-21.

[2]杨艳梅.国外城市垃圾处理经验及对我国的启示[J].环境保护与循环经济，2014，34（4）：15-18.

[3]何花.建立城市生活垃圾分类收集新模式[J].环境保护与循环经济，2012，32（5）：15-17.

[4]王雨帆.基于蟻群算法的多频率垃圾收运路径优化研究[J].物流工程与管理，2016，38（5）：205-206.

[5]王晨頔，穆东.考虑排队等待时间的北京市城市生活垃圾清运车辆调度优化[J].物流工程与管理，2018，40（5）：68-70，51.

[6]张多雨.引入装卸时间的垃圾收运路线优化[J].物流工程与管理，2016，38（7）：125-127.

[7]雷悦，杨若凡，马慧民.垃圾收运路线问题的蜂群优化算法研究[J].计算机仿真，2014，31（9）：441-444.

[8]孟凡婷. 考虑节能减排的物流配送车辆路径优化问题研究[D]. 北京：北京交通大学，2017.

[9]王瑞明，马慧民.生活垃圾收运车辆预防性维修分析[J].物流科技，2019，42（1）：36-40.

[10]徐东洋，李昆鹏，郑飘，等.多车场多车型多品类供需未匹配与可任意拆分取送货车辆路径问题优化[J].管理学报，2020，17（7）：1086-1095.

[11]栾玉麟，郭鹏，王丽敏.时尚行业零售网点多品类取送货车辆路径优化研究[J].工业工程与管理，2020，25（4）：41-49.

[12]FALLAHI A E， PRINS C， CALVO R W. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem[J]. Computers and Operations Research，2006，35（5）：1725-1741.

[13]陈婧怡，邱荣祖.基于ArcGIS的多温区冷藏车辆路径优化[J].上海海事大学学报，2019，40（1）：8-13.

[14]DORIGO M. Optimization， Learning and Natural Algorithms（in Italian）[D]. Politecnico di Milano， Italy：Dipartimento di Elettronica， 1992.

[15]李琳，刘士新，唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策，2010，25（9）：1379-1383.