一种基于知识传递的膜进化算法，用于解决具有时效性要求的大规模分类垃圾收集问题

《Swarm and Evolutionary Computation》：A knowledge transfer-based membrane evolutionary algorithm for solving large-scale sorted waste collection problem with timeliness

大规模定时分类废物收集问题的求解需突破传统算法在维度高、计算成本大时的局限。本文提出知识传递膜进化算法（KTMEA），通过构建原始问题与简化问题的双层膜结构，实现知识高效迁移与并行求解，显著提升大规模场景下的解优效率与稳定性。实验验证其优于现有方法，并证实膜操作规则与知识传递机制的有效性。

　　

张文学|高博全|Aldy Gunawan|牛云云|肖建华

南开大学物流研究中心，天津，300071，中国

摘要

由于不同类型废物的时效性要求各不相同，分类收集城市固体废物已成为一种有效的废物管理策略，这引发了基于时效性的废物收集这一关键研究挑战。尽管现有算法主要针对该问题的小规模版本，但解决大规模基于时效性的废物收集问题仍然具有相当大的难度。为了解决这一问题，本文提出了一种基于知识转移的膜进化算法。具体而言，原始问题和简化问题分别在不同的“膜”中构建，并将知识转移学习机制融入膜进化算法中，从而实现原始问题膜与简化问题膜之间的有效信息交换，高效获得高质量解决方案。在大量大规模基准实例上的实验表明，所提出的算法优于其他最先进方法。此外，消融实验进一步验证了膜操作规则和知识转移机制的有效性。

引言

废物收集对于市政当局来说正变得越来越复杂，众多研究表明废物分类能够带来经济、社会和生态效益[1]、[2]、[3]、[4]，这促使许多学者提出各种启发式算法来解决分类废物收集中的车辆路径问题。[5]开发了一种高效的混合变邻域搜索算法，用于具有垃圾桶清洗功能的分类废物收集。[6]设计了一种混合遗传算法和粒子群优化算法，以解决动态的城市分类固体废物收集问题，同时考虑了废物产生的波动和运输系统的变化。[7]提出了一种自适应变邻域搜索算法，用于高效解决分类废物收集中的异构电动汽车路径问题。传统的分类废物收集问题没有考虑废物的收集时效性，而不同类型的废物由于其独特的物理和化学性质，具有不同的收集时效性[8]、[9]。因此，[10]开发了一种自适应大邻域搜索算法，用于解决具有时效性约束的多周期分类废物收集路径问题，尽管他们的方法仅适用于小规模场景。

目前，随着城市区域的不断扩张和废物收集点的增加[11]，以及大数据时代的到来，其特征是大量数据的持续生成和数据规模的不断扩大[12]、[13]，具有时效性约束的多周期分类废物收集问题已不再局限于小规模场景。通常，当全局优化问题的决策变量超过100个，甚至达到数千个[14]时，它就被视为大规模优化问题。在数据规模爆炸性增长的情况下，解决具有时效性的大规模分类废物收集问题（LSWCT）已成为一个研究热点。然而，大规模优化问题中决策变量的指数级增加往往导致搜索空间的维度急剧上升，从而增加了计算成本和解决时间[15]。因此，设计能够解决具有时效性的大规模分类废物收集问题的算法已成为一个亟需突破的关键挑战。

与此同时，膜进化算法最初由[16]提出，已成功应用于解决各种复杂的大规模优化问题，并展示了显著的计算性能。具体来说，[17]开发了一种多目标膜搜索算法，用于解决电力系统中的超大规模综合经济-排放调度问题，证明了其在处理大规模问题方面的优越空间搜索能力。此外，[18]提出了一种受膜启发的混合算法，用于解决具有时间窗口的大规模绿色开放车辆路径问题，结果表明该算法与其他基线方法相比具有很强的竞争力。这些实际应用共同表明，膜进化算法不仅保留了启发式算法固有的适应性和自学习特性，还具有显著的分布性和并行性。这使得它能够通过时空权衡策略有效解决复杂问题[19]。因此，本研究也采用膜进化算法来解决具有时效性约束的大规模分类废物收集问题。通过充分利用其分布式和并行计算优势，我们的方法在某些膜结构中优化原始问题，同时在其他结构中解决原始问题的简化版本。这种方法确保了全局最优解的存在，同时利用了简化问题的快速搜索能力。

此外，传统的智能优化算法存在局限性，如对先前知识的学习不足和收敛速度慢，尤其是在解决大规模问题时更为明显。许多学者引入了知识转移策略，并提出了基于知识转移的各种智能算法来克服这些局限性，取得了有希望的结果。例如，[20]提出了一种双层知识转移协同进化框架，用于解决大规模多目标优化问题，该方法能够完美解决该应用。同样，[21]开发了一种基于知识转移的优化算法，用于解决大规模长期优化问题，并证明了稀疏知识转移策略的有效性。因此，本文也将知识转移机制融入膜算法中，促进了原始问题膜与简化问题膜之间的有效信息交换，从而实现了高质量解决方案的快速获取。

本文的主要贡献如下：

• 1.
  本文采用膜进化算法作为框架，构建了原始问题膜和简化问题膜，并引入知识转移作为学习机制，不同类型的膜之间可以进行信息交流。它提出了一种基于知识转移的膜进化算法（KTMEA），用于解决具有时效性的大规模分类废物收集问题。
• 2.
  具体来说，膜进化算法结合了进化、溶解和分割规则。原始问题膜和简化问题膜都可以使用进化规则进行更新。溶解规则可以消除劣质的简化问题膜，而分割规则有助于生成新的简化问题膜。
• 3.
  与其他最先进方法相比，KTMEA算法在解决大规模问题时具有更高的解决方案质量和更好的稳定性。此外，消融实验验证了膜操作规则和知识转移的有效性。

本文的其余部分组织如下。第2节回顾了相关文献并阐述了LSWCT问题的构建。第3节提供了所提出的KTMEA算法的详细信息。第4节进行了各种数值实验，以验证KTMEA算法的竞争力。第5节提出了结论和未来工作。

章节片段

相关工作与问题构建

在本节中，我们简要回顾了相关文献，然后提供了LSWCT问题的正式定义。

基于知识转移的膜进化算法

本节介绍了基于知识转移的膜进化算法的详细过程。第3.1节主要讨论了基于知识转移的膜进化算法的框架，第3.2节详细阐述了大规模简化车辆路径问题膜的构建过程，第3.3节详细解释了知识转移学习机制，第3.4节描述了进化过程的详细步骤

实验结果

本研究中的所有编程均使用Python 3.11在PyCharm 2024.2（社区版）开发环境中进行，运行在Windows 11系统上。实验硬件配置包括Intel(R) Core(TM) i7-13700K CPU @ 3.40 GHz（16核/24线程）和32 GB内存。除非另有说明，所有实验都在没有GPU加速的单台机器上进行。实现过程中没有使用显式并行编程技术。

结论

废物收集对于市政当局来说正变得越来越复杂，然而，设计算法来解决具有时效性的大规模、多周期分类废物收集车辆路径问题已成为一个棘手的问题。本文充分利用了膜进化算法的并行性和分布式优势，以及知识转移在解决大规模问题方面的优势。在KTMEA算法中，原始问题搜索

CRediT作者贡献声明

张文学：撰写 – 审稿与编辑，撰写 – 原始草稿，软件，方法论，概念化。高博全：验证，软件，调查，数据管理。Aldy Gunawan：监督。牛云云：撰写 – 审稿与编辑。肖建华：监督，项目管理，资金获取。

利益冲突声明

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：肖建华报告称获得了中国国家自然科学基金的支持。肖建华报告称获得了教育部哲学与社会科学实验室专项基金的支持。如果还有其他作者，他们声明没有已知的财务利益或个人

致谢

本工作得到了中国国家自然科学基金 [资助编号 62573245, 62172373] 和 教育部哲学与社会科学实验室专项基金 [资助编号 H0125795, H0124709] 的支持。