智能垃圾回收下收集中心选址-路径二层优化

马艳芳，贾佳鹏，李宗敏，闫 芳

1.河北工业大学 经济管理学院，天津 300401

2.四川大学 商学院，成都 610064

3.重庆交通大学 经济管理学院，重庆 400074

4.重庆市环卫集团，重庆 401137

《“十四五”城镇生活垃圾分类和处理设施发展规划》指出要加快建立城镇生活垃圾处理系统，并鼓励依托物联网等新兴技术提升垃圾处理能力。国内已有不少公司利用智能垃圾箱开展垃圾回收业务，如“小黄狗”“爱家物联”“绿岛”等智能垃圾箱。物联网技术能够对垃圾箱状态进行跟踪监测[1-2]，将信息传输到在线平台[3]，当垃圾量达到阈值时平台发出预警信号，根据平台信息优化回收路径确保容量不足的智能垃圾箱得到及时清理。而下游收集中心作为回收车辆终点，其位置决定回收系统的有效性，选址不当将产生高额运输成本。因此，收集中心选址和回收路径规划整合研究极大影响垃圾回收的成本和效率。

智能垃圾箱是一种利用物联网等技术获取垃圾桶内相关信息的智能环保设备，如何利用这些信息实现资源高效利用成为亟待解决的问题。为了克服这一问题，Ramos 等[4]提出智能垃圾收集路径（smart waste collection routing，SWCR），依据其收集阈值先选择需要访问的垃圾箱再确定最佳收集顺序。此外，Gutierrez 等[5]依据传感器存储的数据库选择要收集的垃圾桶，采用路径优化算法计算出最优的路径，以使行车距离最小化。Gilardino等[6]根据各收集点垃圾量和每辆车的可用工作时间优化收集路径。物联网背景下智能垃圾箱逐渐普及，优化回收路径时充分利用其信息量大和可预警等特点可实现资源高效利用。

表1 总结了LRP 及其在垃圾回收领域的相关研究。可以看出有关LRP研究多采用双层结构，由不同层次多个参与者参与联合决策，随着服务多样化和专业化的发展，大多企业选择将物流作业外包给第三方企业，如生鲜外包配送[7]，充电基础设施选址-路径问题[8]等。但垃圾回收背景下的LRP相关研究较少，建立双层模型来考虑不同决策主体进行联合优化的研究更少。除此之外，LRP是NP难问题，多数文献都采用启发式算法进行求解[7-15]。其中遗传算法应用尤为广泛，但部分文献遗传操作较为简单[9-10]，多采用单一初始化方式，即随机初始化[7，10-11，15]或启发式初始化[8，14]，采用单点变异[7，11]或单点交叉[10，15]等算子进行交叉变异操作，并通过传统概率复制来选择新种群[10-11，14]。此外，已有文献采用聚类算法分配需求[10，15-16]，但忽视了容量约束。本文提出改进的遗传算法：使用多种初始化方法，在保持种群多样性的同时寻求较优的初始解；引入最优成本路线交叉算子和反向变异算子，减少回收车辆的使用数量，降低总回收成本的同时[17-18]，增加种群多样性避免陷入局部最优；并在此基础上通过精英选择策略保留优质种群加快迭代速度。

表1 相关文献特征Table 1 Characteristics of relevant literature

综上，目前关于LRP 的研究已取得了一定的成果，但在收集中心选址及智能垃圾箱回收路径规划方面仍存在不足之处：一方面，将垃圾处理点选址与回收路径问题整合规划的研究较少，且少有学者研究智能垃圾箱回收问题；另一方面，多数研究基于遗传算法求解双层LRP模型，但存在采用单一初始化方式和个别效果较差的算子等问题，因此有必要对此进行改进。基于此，本文研究智能垃圾回收下带容量约束的双层选址-路径整合优化问题，考虑了上下层不同决策主体之间复杂关系，应用智能垃圾收集路径方式进行路径规划，设计改进的遗传算法进行求解，最后通过算例分析验证了模型和算法的有效性和适用性。

1 问题描述

本文研究一个具有双决策主体的容量有限的选址-路径多主体优化问题（capacitated location-routing problem，CLRP），建立了双层规划模型来描述该问题。在该模型中，上层决策者依据给定的收集中心备选点进行选址决策；下层决策者首先确定需要收集的智能垃圾箱，当垃圾箱内垃圾量大于阈值说明垃圾箱容量不足亟待收集，反之则不需收集，其次依照上层决策来规划收集路线以确保整体优化。

在实际生活中，由于智能回收企业的业务布局范围较广，如“小黄狗”和“爱家物联”分别进驻48、36个城市等，故多是负责智能垃圾箱运营和维护等工作，而清理收运则多是雇佣当地的物流运输公司来负责。智能回收企业在建立回收系统过程中要均衡各方面成本以实现总成本最低，而外包物流公司只关心其运输相关成本，故而在进行收集中心选址和回收路径规划决策的过程中，存在两个决策主体，分别是智能回收企业（上层决策者）和外包物流公司（下层决策者），但二者间存在复杂的冲突合作关系，如图1所示。

首先，智能回收企业决定收集中心的位置，将直接影响外包物流公司的回收路线计划。智能回收企业做出选址决定后，外包物流公司才能根据阈值确定容量不足的智能垃圾箱，从而规划最优的收集路线以确保运输相关成本最小化。其次，外包物流公司的路径规划又将反作用于智能回收企业的选址决策。外包物流公司规划好回收路径，将会产生运输成本和车辆启动成本等，这又将会影响企业总经济目标的实现，从而影响选址决策。显然，双层CLRP模型中两个主体决策行为相互影响。虽然智能回收企业和外包物流公司都寻求独立地最小化其目标，但又都受到彼此行为的影响，这些决策的相互影响既体现在目标函数中，也体现在约束条件中。

依据Baldacci 等[19]提出的双商品流公式，建立多仓库的选址-车辆路径模型。其中车辆每条路线都涉及两种流：一种是车辆从收集中心出发，最终到达其副本时的负载，另一种是同一车辆上对应的空载。将该公式引入VRP 模型，可提高精确算法或启发式算法求解的收敛速度[20-21]，也可用于建立LRP模型，如爆炸性废物回收系统的选址-路径问题[22]。

双商品流动公式中所提出的基本流动规律如图2所示，其中车辆容量Q=1 000，9 个待收集的智能垃圾箱、两辆车和一个收集中心。双商品流公式使用两个流变量yij和yji来模拟车辆穿过边(i,j)时所携带的废弃物的流，即每条路线由两条路径定义：一条由表示车辆载荷的yij流变量表示从节点0到节点n+1 的路径P1；从节点n+1 到节点0的第二条路径P2由表示车辆空白区域的流变量yji表述。因此，两种流的总和等于车辆容量，例如y36+y63=1 000。具体来说，以节点1、3、6和8 之间的流动为例，可以注意到：（1）节点3 的总流出量减去总流入量等于该节点产生的废弃物量的两倍，即(y31+y36)-(y13+y63)=2m3；（2）收集中心副本n+1 的总流出等于剩余车辆容量，即y(n+1)8=Q-y8(n+1)；（3）收集中心副本n+1 的总流入量等于装载的废物总量，即y8(n+1)=m1+m3+m6+m8；（4）yij和yji变量取可行值，其中y13+y31=Q×x131×g1。

图2 双商品流示意图Fig.2 Two-commodity flow formulation representation

2 模型建立

针对以上描述，介绍了建立模型所需的假设条件和参数符号，并给出数学模型。

2.1 模型假设

建立双层选址-路径问题的数学模型所需假设条件如下所示：

（1）候选收集中心的数量、地理位置、固定成本已知。

（2）各收集中心容量已知，分配给各收集中心的总需求量不能超过设施的容量限制。

（3）配送车辆均为同质车辆，固定成本和容量已知，各运输路径上车辆载重不能超过容量限制。

（5）每处收集点（需要收集的智能垃圾柜）的地理位置和所产垃圾量已知。

（6）各节点间距离按照欧氏距离计算，运输车辆单位距离运输成本已知。

（7）每个站点每次只能被一辆车收集一次，收集车辆从收集中心出发并最终返回收集中心。

2.2 参数符号

集合

I：智能垃圾箱集合I={1,2,…,n}；

C：收集中心备选位置集合C={1,2,…,c}；

：收集中心的复制点{1,2,…}；

G：智能垃圾箱和收集中心的集合G=I⋃C⋃

V：同质车辆的集合；

指标和参数

i/j/m：智能垃圾箱站点和收集中心的索引i,j,m∈G；

k：车辆的索引k∈V；

n：智能垃圾箱总数，即垃圾产生站点总数；

c：备选收集中心总数；

l：同质运输车辆总数；

mi：智能垃圾箱i处所产生垃圾的质量i∈I；

Q0：收集中心的额定容量；

Q：车辆的额定载重质量；

FCi：收集中心i的固定开放成本i∈C；

VCi：收集中心i的每单位垃圾的处理成本i∈C；

FVk：启用车辆k的固定成本；

c0：所用车辆的单位运输费率；

dij：节点i和节点j之间的距离；

φi：智能垃圾箱回收阈值。

决策变量

hi：0-1变量，如果候选收集中心i∈C开放，则为1，否则为0；

gk：0-1变量，如果车辆启用k∈V，则为1，否则为0；

zik：0-1变量，如果车辆k∈V访问点i∈I，则为1，否则为0；

yij：表示点i到点j的流量，为非负数；

xijk：0-1变量，如果车辆k访问边(i,j)，则为1，否则为0。

2.3 数学模型

2.3.1 上层规划

上层规划由智能回收企业确定收集中心选址，确保由收集中心的开设成本、运营成本、车辆运输成本和车辆固定成本组成的总成本最小化。上层公式如下：

目标函数（1）是总经济成本最小化，包括收集中心开放成本、操作运营成本、车辆运输成本和车辆固定成本。由于每个行程都被定义为包含两条路径的车辆路线，因此车辆运输成本需要除以2以获得真实的运输成本。约束（2）保证收集中心的总数至少为一个，且满足约束（3）确保解满足收集中心容量限制。

2.3.2 下层规划

经过分析，下层模型是一个车辆路径规划问题。因此，车辆运输相关成本最小化是外包物流公司的目标，包括车辆运输成本和车辆固定成本。其数学公式描述如下：

目标函数式（5）表示外包物流公司的总运输成本最低；约束（6）确保每个点的流出量减去流入量等于每个点中废弃物量的两倍；约束（7）确保复制点n+1 的总流入等于所收集的智能垃圾箱中总废物量；约束（8）确保复制点总流出量等于车队的剩余容量；约束（9）保证实际路径的装载总量小于或等于车队的运力；约束（10）和（11）根据回收阈值筛选容量不足的智能垃圾箱，并确保这些需要收集的智能垃圾箱仅由一辆车提供服务，本文根据智能垃圾箱i前10 天垃圾投放平均值来估计其每日预期投放量αi，并定义回收阈值φi=(1-αi/q0)×q0，其中q0为智能垃圾箱额定容量，当智能垃圾箱现存垃圾量mi大于φi时，其容量不足难以容纳次日投放量，故该智能垃圾箱需要进行收集；反之则不需收集该垃圾箱；约束（12）表示每个点都有两条路径；约束（13）确保车辆离开收集中心时是空载；约束（14）表示车辆必须完全清空它访问的所有垃圾箱；约束（15）确保启用的车辆数量不超过车队总数；约束（16）连接了变量yij和xijk，表示保证如果有车辆访问边(i,j)，其流量之和必须等于车辆的通行能力；约束（17）～（20）避免产生非可行解；约束（4）和（21）～（24）给出变量的定义域。

2.3.3 全局模型

垃圾收集的选址路径问题可以分为两个层次：智能回收企业为上层决策者，外包物流公司为下层决策者。在BP 问题中，底层模型也是全局模型的约束。根据2.3.1和2.3.2小节，可以得到全局模型如下：

在全局模型中，智能回收企业决定开设哪个收集中心（决策变量hm），以实现总成本的全局最小化。外包物流公司先根据阈值确定亟待收集的智能垃圾箱，进而在智能回收企业决策的基础上进行路径规划。然而，路径规划对智能回收企业的成本最小化目标有着重要的影响。全局模型描述了垃圾回收选址-路径模型中存在冲突和协调的智能回收企业与外包物流公司之间的相互影响。

2.4 公式有效性

由于双商品流公式仅用于下层路径模型，故而本节证明将该公式引入CVRP模型的有效性。

首先，证明CVRP 的解可满足双商品流公式。当CVRP 求解得到回收路线时，其变量xijk和yij满足如下约束：

不妨将不属于上述CVRP解的边都设置成xijk=0，yij=yji=0，此时上述所定义的两个变量显见是双商品流公式的可行解。

3 求解算法

选址路径多主体优化问题求解难度非常大，属于强NP难问题。目前大多采用启发式算法[7-15]求解，如遗传算法，粒子群算法等，本文提出了一种改进的遗传算法来求解双层规划问题。首先，结合多种初始化方式以获得初始解，上层聚类获得初始选址方案，下层采用随机和节约里程算法获得初始路径，确保种群多样性同时寻求更优良的初始解；其次，将最优成本路线交叉、反向变异和精英选择相结合，改善算法局部搜索能力的同时检查可行性约束。

3.1 编码与解码

上述问题包含垃圾收集中心选址和回收路径两个子问题，用三个向量来表示一个完整的解，第一个向量为车辆向量，第二个是顺序向量，第三个表示车辆所属收集中心向量。假设有8 个备选配送中心，编号为1，2，…，8；可支配车辆4 辆，编号为1、2、3、4；待收集的智能垃圾箱16个，编号为1，2，…，16，回收方案如下：

首先，收集中心向量表示上层选址方案，即选择2和6，且车辆1、3 从收集中心2 出发，车辆2、4 从收集中心6 出发。其次，确定需要收集的智能垃圾箱，不难看出编号为7和13的智能垃圾箱未达回收阈值，不需要回收。最后，在上层决策的基础上进行回收路径规划，智能垃圾箱编号对应位置的车辆向量值表示收集该垃圾箱的车辆，如客户1、6 和16 由车辆4 收集；车辆向量对应的顺序向量值表示车辆收集的先后顺序，如车辆4先收集垃圾箱1，其次是垃圾箱6，最后是垃圾箱16。因此，上层解码后得到选址方案为收集中心2和6；下层解码后得到回收路线，整合上下层解码得到最终问题的解如下：

3.2 初始化与适应度函数

上层采用聚类算法确定初始选址方案，下层则采用随机和节约里程算法生成初始车辆路径，其中80%的初始种群是随机的，另外20%用节约里程算法生成[23]。Jammeli 等[16]采用“聚类优先，路径其次”的分层方法来求解回收过程中的分配和路径方案，Mendoza等[24]使用节约里程算法生成初始路径方案来加速算法收敛。在前人研究的基础上，采用多种初始化方法以期得到一个良好的初始化种群，尽量避免计算资源的浪费，也希望种群具有良好的多样性，降低算法复杂度且不易陷入局部最优。

上层采用聚类算法确定初始选址方案，将多收集中心路径问题转化为单收集中心路径问题，从而大幅降低问题的复杂度。比较常用的方法是根据智能垃圾箱与收集中心间的距离进行分类，但这种方法没有考虑收集中心容量约束，导致结果质量偏低。为解决这一问题，本文聚类算法考量收集中心容量约束，具体步骤如下：

（1）计算所需最少收集中心个数knum，在C中随机选取knum作为收集中心，其中。

（2）计算各智能垃圾箱i∈I到knum个收集中心的距离，并将其分配给最近的收集中心记为Cknum。

（3）计算每个集合Cknum中的智能垃圾箱数量，并按降序排序。选择排名最高且未被选中的收集中心开放。

（4）根据收集中心容量回收智能垃圾箱。依次累计计算智能垃圾箱i∈Cknum的垃圾量直到超过收集中心容量；Cknum中未被分配的客户将被分配到下一个开放的收集中心。

节约里程数的计算公式为ΔCij=C0i+C0j-Cij。公式的意思是i到j的节约里程数为收集中心到i的距离加上收集中心到j的距离减去i到j的距离。节约里程法计算步骤如下：

（1）作运输里程表，列出收集中心到用户及用户间的最短距离。

（2）按节约里程计算公式求得相应的节约里程数ΔCij。

（3）把节约的行程值从大到小排序，放到list中。

（4）检查各连接点可行性，按照list的顺序连接各客户结点，最终确定配送线路。

适应度函数要结合求解问题本身而定，每个染色体的适应度值反映目标值，据此判断个体的优劣，从而来进行选择操作。上层决策目标为建造、服务和运输总成本最小，每个备选点的建设成本已知，下层目标为运输相关成本最小，根据双层规划理论，上层决策者在决策中占主导地位，上层目标是双层规划中的主导目标。当满足各约束时，目标函数如公式（1）。

考虑到车辆和收集中心容量约束，对超出容量约束的染色体添加一个足够大的惩罚值，避免生成非可行解。此外，由于模型为最小化组合优化问题，目标函数值越小，对应的染色体适应度越高，解越优良。因此，以上层目标函数值与惩罚函数值之和的倒数作为适应度函数。适应度函数如下：

其中，fi表示第i条染色体的适应度值，F1i表示对应的目标函数值，P1和P2分别表示车辆超载或收集中心容量不足时产生的足够大的惩罚值，当满足约束时，P1=0,P2=0。

3.3 算法流程

改进的GA算法在标准遗传算法基础上进行改进，引入最优成本路线交叉算子和反向变异算子确保种群多样性的同时增加算法的搜索能力，结合精英策略避免优秀个体丢失。改进GA算法流程如图3所示。

图3 GA-pro算法流程图Fig.3 Flowchart of GA-pro

算法步骤概括如下：

步骤1输入计算数据，设置交叉率、变异率等参数，并初始化种群。其中，初始化种群分为两部分。上层依据备选智能垃圾箱信息应用聚类算法获得初始收集中心选址方案；下层依据回收阈值选定亟待收集的智能垃圾箱，再通过随机和节约里程算法获得初始回收路径。

步骤2计算各个个体的适应度值，进行选择、交叉和变异操作，并应用精英策略形成新种群防止最优解退化。其中，对交叉和变异操作进行改进，采用最优成本路线交叉算子和反向变异算子来增加算法的局部搜索能力。

最优成本路线交叉：由于交叉操作过程中父代随机删除一条路径，并在满足容量约束的前提下将删除的基因重新插入到局部最优位置，最后将所得基因按顺序替换父代染色体基因确保编码为0 的位置不变从而得到子代，因此，该算子可在最小化车辆数量和成本的同时检查容量约束[17-18]。用规模为11 的任意问题实例来解释该交叉过程，如图4 所示。首先，根据所给父代P1 和P2确定各个车辆路径，如步骤（a）所示P1有三条车辆路线，即3→4→2、6→8→1、5→7，从父代中随机各选择一条路径。在本例中，选择P1包含垃圾箱5和7的第三条路径，以及P2 中包含垃圾箱2 和4 的第二条路径。其次，从P1 中移除P2 所选路径包含的垃圾箱。如图4 步骤（b）所示，从P1 中移除2 和4，从P2 中移除5 和7。随后，将被删除的垃圾箱在不违背容量约束的情况下，一个接一个地重新插入到局部最优位置如步骤（c），以使整个行程的总成本最小化，其间，插入的顺序是随机进行的。最后，确保0 位置不变的情况下，将得到的染色体按顺序替换父代染色体基因获得子代染色体。

图4 最优成本路线交叉Fig.4 Best cost route crossover operator

反向变异：随机选择两个位于亲本染色体上的变异位置，然后将两个位点之间的所有基因进行反转，得到一个新的后代染色体，以维持种群的多样性，改善遗传算法的局部搜索能力[25]。

步骤3判断是否满足终止条件，满足则输出最优解，否则返回步骤2。

4 基准案例测试

首先，选用两组LRP 经典基准案例集Prins 等[26]和Barreto等[27]进行测试来验证改进的GA算法（GA-pro）性能，两个案例集均可在http：//prodhonc.free.fr/Instances/instances下载；其次，结合模拟实际案例，证明双层模型的合理性。本文构建的数学模型与算法用MATLAB R2014b 编码，在Lenovo 小新-14API 2019 计算机运行，具体配置为2.10 GHz Ryzen 5-3500U 处理器，操作系统为Windows 10 64位。

GA算法涉及的参数主要有迭代次数、种群规模、交叉概率、变异概率等参数。通过一定的实验测试和文献参考[7]，设置迭代次数为500 代，种群规模为50，变异概率为0.2，交叉概率为0.75。

选取Prins 等提出的算例中客户数为20、50、100 三种规模大小的总计24 个案例和Barreto 所提出的12 个算例进行测试，并与求解结果较好的GAPSO[7]和BSA算法[28]进行对比分析，且调整算法目标成本与各案例中目标成本相匹配以更具备可比性，求解结果如表2和表3所示。BKS为基准案例已知最优解，GA-pro所得结果为将各案例运行10次的最优结果，Gap为各算法最优解与BKS的差距百分比。

表2 Prins案例求解结果Table 2 Solution results of instance Prins

表3 Barreto案例求解结果Table 3 Solution results of instance Barreto

表2 为Prins 的24 个LRP 基准案例求解结果，其中GA-pro在12个案例中求得了最优解，另12个案例绝大多数也可获得近似最优解。当顾客规模小于100 时，GAPSO均能求得最优解，而GA-pro稍逊。而在顾客规模等于100 的12 个案例中，BSA 有4 个案例求得最优解，3个案例结果较另两个算法更优；GAPSO和GA-pro仅求得一个最优解，且各有2、3个案例求解结果优于另两种算法。GA-pro在大中小规模案例中的表现均介于两种对比算法之间，且与最优解BKS 的差距均值仅为0.419%，由此可见，GA-pro可以在一定程度上较好地解决CLRP问题。

由表3 可以看出，BSA 算法整体表现良好，在大规模算例中求得结果更为接近BKS。相比之下，GA-pro求解大规模算例的能力相对较弱，当顾客规模小于50时都能找到最优解，在中大规模算例中虽不能全部找到最优解，但是与其他算法差距不大。从整体来看，GA-pro 在中小规模案例中表现优于BSA，在大规模案例中表现优于GAPSO，具备一定的竞争力。

5 模拟案例

5.1 案例描述

为验证本文模型的合理性和适用性，拟选用4个备选收集中心，以满足50 处智能垃圾箱的回收需求。备选收集中心的位置、容量和建设成本如表4所示。智能垃圾箱位置、需求量和回收阈值如表5 所示，仅列出前15个智能垃圾箱相关信息为例。根据实际情况和社会经验，使用的其他参数设置如下：车辆容量为1 000 kg，每辆固定成本为400 元，每千米运输费用为0.75 元，其他参数设置同第4章。

表4 备选收集中心信息表Table 4 Information sheet for alternative collection center

表5 智能垃圾箱部分信息表Table 5 Information sheet for some smart bins

5.2 主从二层结果分析

5.2.1 智能垃圾收集模式

基于上述数据，应用智能垃圾收集模式，即先根据阈值确定需要收集的垃圾箱再对其进行路径规划的方式，并运用前文提出的改进遗传算法求解本案例，运行算法30次，选择其中最佳优化结果。结果显示，开放编号为3 和4 的收集中心，当日待收集垃圾箱共24 个，收集中心3 发出两辆车，收集中心4 则发出一辆车进行收集，总计成本约为79 437 元，解码后，上下层路径优化方案如下：

5.2.2 传统收集模式

本文还求解相同条件下传统收集方式的选址路径方案（即每日收集全部垃圾箱）。传统收集方式选择开放编号为1和4的收集中心，且各发出两辆车，总计成本约为88 700元，解码后，上下层的路径优化方案如下：

5.2.3 两种模式对比分析

观察以上结果可以看出两种收集模式下所开放收集中心不同，尽管收集中心1的建造成本及单位运营成本在所有备选中心中最低，但在智能垃圾收集模式下显然不是最佳选择，无法使总成本达到最小。这是由于所设阈值是依据各处垃圾箱往日投放量来计算，而每处垃圾箱容量相同，使得一部分垃圾箱收集次数较为频繁，而收集中心3相比于收集中心1处于此类垃圾箱较为密集的位置，更大可能降低运输成本。

两种收集模式各成本对比如表6 所示，经比较可知，智能垃圾收集模式相比于传统收集模式节约成本约9 263元。智能垃圾收集模式下仅开放成本比传统收集模式高，但其余三项成本皆低于传统收集模式，其中运输成本尤为显著，这是由于每日需要收集的垃圾箱减少，使得处理量和运输距离获得不同程度的减少，从而降低总成本。

表6 两种收集模式下成本对比Table 6 Cost comparison under two collection modes单位：元

这也表明决策过程中两个决策主体之间产生了一定冲突，但由于智能回收企业不仅需要考虑建设成本和运营成本，还需要权衡运输成本来保证总成本最优，因此是下层企业的决策牵制了上层的决策行为。综上所述，本文模型应用智能垃圾收集路径方式，依据阈值筛选需要收集的智能垃圾箱，再求解回收路径最优方案，能够很大程度降低总成本，减少资源浪费。

5.3 算法性能分析

为验证提出的改进GA 算法对于求解带容量约束的双层选址路径模型的性能，将GA-pro 求得的最优结果与标准遗传算法（GA）、粒子群算法（PSO）和GAPSO混合算法求解结果进行对比分析，每种算法的种群大小为50，最大迭代次数为800，运行算法30次，选择其中最佳优化结果如表7 所示，算法迭代效果对比如图5 所示。基于这些图表，从收敛速度、求解精度以及运算复杂度三个方面对算法性能进行对比分析。

图5 算法迭代对比图Fig.5 Comparison for convergence curves

表7 四种算法最优结果对比Table 7 Optimal results for four algorithms

（1）观察图5可以看出，GA-pro收敛速度最快，PSO次之，标准GA收敛速度最慢。GA-pro算法于100代左右已收敛到最优值附近，在390代左右逐渐收敛于最优值；而PSO于120代左右开始收敛于最优值附近，在400代左右才逐渐收敛于最优值；GAPSO 虽然较早收敛于最优值，但其收敛速度较慢。

相比于标准GA 算法，GA-pro 迭代速度更快，最优解更佳，这是由于最优成本路线交叉算子能够在确保容量约束的前提下将基因插入到局部最优位置，尽量避免非可行解产生的同时获得更优的子代，反向变异算子反转两个随机点位间所有基因可增加种群多样性，有效提升算法的搜索性能，且精英选择策略确保优良个体能传递至下一代，故GA-pro收敛性能远优于标准遗传算法。

（2）由表7 可知，四种算法都可以得到各自最优结果。GA-pro 算法求解结果比标准GA 算法优化了3.58%，比PSO 算法优化了0.08%，与GAPSO 最优解差距仅为0.05%。可见GA-pro 算法求解精度明显高于标准遗传算法，且相比于结果最优的GAPSO 混合算法差距不大。

（3）在算法复杂度方面，由于遗传算法的复杂度可由适应度函数被调用的次数得出，而适应度函数的调用次数与种群数量、种群迭代次数、交叉率以及变异率相关[29]。以上变量均为外生给定，且GA-pro 仅在标准遗传算法基础上进行改进，没有增加额外的复杂操作，故而在算法复杂度并没有改变。

由上述对比分析可知，GA-pro 采用多种初始化方法，引入最优成本路线交叉算子、反向变异算子和精英选择策略没有增加算法复杂度的同时提高了搜索性能。综上，GA-pro 对于求解智能垃圾回收下带容量约束的双层选址路径问题是可行且有效的。

5.4 模型分析

为进一步验证双商品流选址-路径模型的有效性，将结果与传统选址-路径模型的求解结果进行对比，如表8所示。采用相同数据的情况下，双商品流选址-路径模型在最优目标函数值和计算时间方面都较传统模型有所提升。相比于使用GA-pro求解传统模型，表7中标准GA 求解双商品流选址-路径模型的结果优化了1.66%，计算时间也减少了17.71%，这表明仅使用标准GA 求解引入双商品流公式的选址-路径模型也能求得良好的结果。

表8 模型结果对比Table 8 Comparison of model results

6 结论

本文研究智能垃圾回收下容量有限的双层选址-路径整合优化问题。上层智能回收企业以总成本最小为目标做收集中心选址决策；下层外包物流公司以运输相关成本最小为目标，依据回收阈值选定容量不足的智能垃圾箱进行路径规划。设计改进的遗传算法进行求解，GA 算法改进如下：（1）运用多种方法生成初始种群，上层采用聚类算法处理选址初始化，下层采用随机和节约里程算法生成初始车辆路径；（2）结合精英选择策略，保留优秀个体；（3）采用最优成本路线交叉算子和反向变异算子维持种群多样性。

选取Prins 和Barreto 提出的经典LRP 基准案例，验证GA-pro求解CLRP的能力。将GA-pro结果与GAPSO和BSA 两种算法求解结果进行对比分析，结果表明，GA-pro 在求解小规模问题时都能找到最优解，对于中大规模问题能求得近似最优解，整体求得结果与最优解的差距Gap均值分别为0.42%和1.63%，表现介于两种对比算法之间，且Prins 算例的大规模算例中有三个案例的求解结果优于另两个算法。此外，为探究本文模型与算法的适用性，基于模拟数据进一步测试。最终结果表明：（1）智能垃圾收集路径方式，即先依据阈值确定亟待收集的垃圾箱再对其规划回收路径可有效降低成本，减少资源浪费；（2）GA-pro与其他三种算法的收敛性对比显示，GA-pro 具有更优良的初始解，降低运行时间，具备良好的收敛性能；（3）引入双商品流公式的选址-路径模型在求解性能方面明显优于传统的选址-路径模型。

综上，本文可为智能垃圾回收下有容量限制的垃圾收集中心选址和路径规划问题提供决策支持。考虑不同决策主体间的复杂关系，引入双商品流公式建立双层选址-路径模型，改进遗传算法进行求解，并验证智能垃圾收集路径方式能够有效降低回收成本，对规划智能垃圾回收选址-路径方案具有一定的参考意义。但是也存在一定的局限性，没有考虑环境影响和多车型混合回收问题，这些将是下一步的研究方向。