一种基于学习的协同进化元启发式方法，用于解决具有类型2模糊时间窗口的集成时间敏感产品生产和交付调度问题

《Swarm and Evolutionary Computation》：A learning-driven co-evolutionary meta-heuristic approach for integrated time-sensitive products production and delivery scheduling problem with type-2 fuzzy time window

　　肖宇刚|郭廷帅|尹富民|吴国华
中南大学交通与运输工程学院，长沙，410075，中国

**摘要**
随着供应链市场竞争的加剧，客户对时间敏感产品的满意度要求越来越高，生产和交付调度问题受到了越来越多的关注，以降低成本和减少能源消耗。同时，作为高度复杂的组合优化问题，能源意识的分布式灵活生产调度问题促进了生产阶段的高效处理。此外，引入了区间型2模糊数（IT2FN）来表示模糊的客户交货时间。本研究探讨了一个集成时间敏感产品生产和交付调度问题（ITPPDSP-TFTW），该问题考虑了分布式异构灵活流水线调度问题和车辆路径问题的综合优化。建立了ITPPDSP-TFTW目标函数的计算模型，以最小化总成本（Cost）和总能耗（TEC）。提出了一种基于学习的协同进化元启发式方法（LCMA）来解决ITPPDSP-TFTW。LCMA结合了基于问题知识的协同初始化策略和四个改进的元启发式算法模块来生成和更新种群。在四个改进的元启发式算法模块中，设计了基于问题知识的六种邻域结构和四种基于迭代贪婪策略的破坏与重建操作符来优化解决方案。设计了一种基于双重决斗深度Q网络（Double Dueling DQN）的学习驱动选择策略，以选择适当的改进元启发式算法模块，从而增强利用能力并避免无效搜索。通过大量实验评估了LCMA的性能，实验结果表明LCMA的所有策略在解决ITPPDSP-TFTW方面均优于现有算法。

**引言**
随着生活水平的提高和现代市场竞争的加剧，供应链管理中对定制化需求的重视程度日益增加，对产品质量和服务水平的关注也越来越高[1]。在现代电子商务物流中，将客户偏好与技术驱动的多目标决策框架相结合对于开发高效、可持续和以用户为中心的最后一公里配送系统具有重要意义[2]。生产和分配被认为是时间敏感产品供应链的关键组成部分，供应链系统的客户满意度取决于它们的效率。由于生产和分配密切相关，因此促进生产和调度之间的协同优化可以降低生产和运输成本，提高客户满意度，并减少生产和运输过程中的能源消耗[3]。时间敏感产品的生产和分配集成调度在新鲜食品的供应链管理中得到了广泛应用[4]。因此，时间敏感产品的生产和调度之间的协同优化对于提升企业竞争力和运营绩效以及提高客户满意度具有重要意义。

随着经济全球化的深入，生产模式正逐渐从传统的集中式转向分布式。分布式制造被认为有助于企业适应不断变化的市场环境，降低管理风险，提高生产效率和资源利用效率，并增强竞争力[5]。在分布式制造环境中，分布式车间调度比传统的单工厂调度更为复杂，因为需要同时确定工厂分配和每个工厂的任务调度。因此，研究人员广泛研究了分布式生产调度[6]。作为近年来研究最广泛的分布式调度问题之一，分布式灵活流水线调度问题（DFFSP）在[6]中以无等待约束进行了建模，并通过各种建设性启发式算法得到解决。随后，研究中考虑了额外的复杂特性，如异质性、无空闲时间、设置时间和运输时间[7]。除了最广泛研究的目标——最大完成时间Cmax外，还研究了其他实际目标，包括总流动时间、总延迟和与能源相关的指标[8]。上述研究仅关注时间和能源目标，而忽略了与成本相关的目标。

灵活流水线调度问题（FFSP）已被证明是一个NP难问题[9]。在FFSP中，n个订单依次通过S个阶段进行处理。每个阶段包含多台并行机器，且每个阶段至少有两台或更多并行机器。张等人[10]研究了具有动态订单和批量调度的FFSP，并开发了一个基于知识和数据的框架来解决问题。随着制造智能的发展，分布式灵活流水线调度问题（DFFSP）引起了学术界的广泛关注。陶等人[11]研究了在新任务到达和机器故障情况下的DFFSP重新调度，并提出了一种基于K均值聚类的新非支配排序遗传算法来优化时间和鲁棒性指标。赵等人[12]研究了具有多重时间约束和批量调度的DFFSP，并设计了一个基于强化学习的算法框架来选择最优的局部搜索操作符。由于分布式制造工厂在机器数量和运营效率上存在差异，因此研究分布式异构灵活流水线调度问题（DHFFSP）尤为重要[13]。崔等人[13]以最小化制造周期为目标研究了DHFFSP，重点关注工厂之间的邻域结构，并设计了一种改进的遗传算法来解决它。轩等人[14]研究了具有缓冲容量约束的DHFFSP，并设计了一种强化学习辅助的估计算法来提高算法的适应性和智能性。邓等人[15]研究了具有设置时间、运输时间和学习效应的组装DHFFSP，并应用Q学习在遗传算法中选择局部搜索操作符以提高算法智能。上述研究仅关注了单一的分布式生产调度，没有考虑分配阶段或运输调度的集成。

随着现代制造业中按订单生产的引入，订单对应于客户需求，集成生产和交付调度（IPDSP）受到了广泛的研究关注，以满足客户的时间要求并降低总体成本[16]。Berghman等人[16]回顾了问题特性、约束和解决方法，分析了集成生产和交付调度及车辆路径问题，并根据生产环境、车辆和运输频率对它们进行了分类。赵等人[17]研究了跨企业生产和运输的集成，旨在提高能源效率和生产绩效，并在设计了一种基于学习的遗传算法中的高效知识驱动自适应变邻域搜索来更新问题。谭等人[18]设计了一种结合多种启发式规则的多目标教学学习优化算法，以解决具有共享运输资源的集成生产和交付调度问题。李等人[19]应用了基于贝叶斯学习的精英策略在非支配排序算法中解决多目标集成生产和运输调度优化。刘等人[20]研究了旨在最小化车辆数量、行驶距离和制造周期的集成生产和运输调度，并设计了一种具有问题特定先验知识的并行优化算法。Masood等人[21]研究了具有运输阶段和订单交付的分布式灵活作业车间调度问题，并应用了一种新的遗传算法变体（TTGA）来解决它。唐等人[22]提出了一种结合双重Q学习机制的改进非支配排序遗传算法，以解决多目标批量调度问题中的集成调度。潘等人[23]研究了具有运输阶段的能源意识分布式灵活作业车间调度问题，并将统计学习与进化学习相结合，形成了一个双重学习协同框架，以确保资源的合理分配。尽管许多研究集中在IPDSP上，但对时间敏感产品的分布式集成生产和交付调度的研究仍然有限，特别是在分布式灵活流水线中。同时，大多数研究忽略了运输阶段的车辆路径规划和能源消耗目标。将经济和环境目标纳入供应链网络优化可以实现更平衡的权衡，并为设计可持续和具有成本效益的供应链提供实际见解[24]。因此，研究集成时间敏感产品生产和交付调度问题（ITPPDSP）是必要的。与分布式灵活流水线调度和单一IPDSP相比，ITPPDSP更为复杂，因为生产阶段包含多个子问题，每个子问题都会影响后续交付阶段的路径规划结果。因此，开发智能高效的方法来解决分布式灵活流水线中的ITPPDSP具有重要意义。

在交付阶段，客户根据个人需求通常要求在特定时间段内交付货物，这被称为客户时间窗口，这一概念最初由Somolon提出[25]。在相关研究中，时间窗口的描述逐渐从最初的硬时间窗口发展到软时间窗口[26]。然而，在实际应用场景中，单一设置软时间窗口或硬时间窗口过于简化，缺乏灵活性，无法充分反映客户对不同时间段服务时间的期望和满意度。因此，一些研究人员基于模糊集理论通过模糊化改进了时间窗口，用模糊数表示时间窗口，并构建了模糊时间窗口，其中服务开始时间的隶属函数量化了客户满意度[27]。对于客户满意度的隶属函数，大多数现有研究采用了梯形模糊时间窗口隶属函数，而三角形模糊时间窗口隶属函数很少用于量化客户满意度。考虑到交付阶段客户交货时间的不确定性显著增加了问题的复杂性，但更符合实际的交付要求。为了解决客户交货时间的不确定性，引入了区间型2模糊数（IT2FN）来表示不确定的处理时间。IT2FN是三角形模糊数的扩展形式，能够有效表示复杂生产系统中高度不确定的处理时间。黄等人[28]应用IT2FN预测和表征绿色灵活作业车间中的处理时间不确定性。杨等人[29]研究了一个结合IT2FN的环境友好型灵活作业车间调度问题，并提出了一种基于分解的遗传算法来解决它。李等人[30]研究了一个环境友好型灵活作业车间调度问题，并应用IT2FN预测时间约束的不确定性，以便更好地模拟实际生产。在考虑IT2FN的绿色灵活作业车间调度问题中，李等人[31]进一步考虑了能源消耗和交付约束，使问题更接近实际生产过程。与这些研究类似，本文应用IT2FN来表示交付阶段的客户模糊交货时间。

元启发式算法在解决各种调度问题方面取得了卓越的性能[32]。Samir等人通过引入蚁群优化算法并结合模糊推理机制，对异构多天线RFID读器的部署和天线选择进行了协调优化，有效提高了覆盖性能，减少了干扰，降低了系统部署成本，从而增强了医院资产跟踪系统的整体效率和可靠性[33]。Mohammad等人应用灰狼优化器（GWO）及其变体对无线传感器网络（WSNs）的聚类和路径优化进行了研究，有效提高了能源效率，减少了通信开销，并延长了网络寿命，展示了元启发式方法在解决复杂大规模网络优化问题方面的潜力[34]。自从首次提出DFFSP以来，许多元启发式算法被设计出来解决它。例如，自适应大邻域搜索算法（ALNS）是一种典型的元启发式优化方法，其核心思想基于大邻域搜索框架，在搜索过程中动态调整操作符选择策略[35]。人工蜂群（ABC）算法是一种受蜜蜂群体觅食行为启发的群体智能算法[36]。遗传算法（GA）是一种经典的进化计算方法，其基本原理源于自然界的“适者生存”机制[37]。受自然界寄生概念的启发，协同进化算法（CEA）被应用于解决各种复杂优化问题。CEA的核心思想是将问题分解为多个子问题，并利用进化算法的分治原则来解决它们。关于CEA的研究清楚地表明，问题特征分析、知识提取与应用以及适当的合作机制对于有效解决复杂的调度问题至关重要[38]。根据上述相关文献的比较综述，本研究的主要研究空白体现在以下几个方面：i) 以往的研究很少考虑使用IT2FN来表示集成时间敏感产品生产和交付调度问题中的时间窗口，忽视了它们对实际生产和企业核心竞争力的影响。ii) 机器的异质性（如新旧程度不同）在集成时间敏感产品生产和交付调度问题中很少被考虑。然而，同时考虑机器异质性和模糊时间窗口有助于降低机器能耗、提高客户满意度，并使企业能够应对实际生产挑战。iii) 首次引入了一种比传统DDQN更有效的Double Dueling DQN技术来解决ITPPDSP-TFTW问题，并用于指导元启发式算法的选择机制，这使其区别于传统的基于邻域的选择策略。因此，本研究提出了一种基于学习的协同进化元启发式方法来解决具有类型2模糊时间窗口（ITPPDSP-TFTW）的集成时间敏感产品生产和交付调度问题，目标是最小化总成本和总能耗。建立了一个用于问题目标的计算模型，并开发了三个启发式规则来生成初始种群。对于ITPPDSP-TFTW，设计了四个改进的元启发式算法模块来更新种群。基于Double Dueling DQN开发了一种学习驱动的选择策略来合理组织这四个元启发式算法。设计了六种基于问题知识的邻域结构和四种基于迭代贪婪策略的破坏与重建操作符来更新调度方案。最后，将种群的帕累托解集存储在精英档案中。本研究的主要贡献如下：(1) 首次研究了具有类型2模糊时间窗口（ITPPDSP-TFTW）的集成时间敏感产品生产和交付调度问题，并建立了问题目标的计算公式以计算成本和TEC。(2) 设计了四个改进的元启发式算法模块来更新种群，并设计了一种基于Double Dueling DQN的学习驱动选择策略来有效组织这些模块，避免无效搜索。(3) 提出了一种基于学习的协同进化元启发式方法来解决ITPPDSP-TFTW问题。设计了六种基于问题知识的邻域结构和四种基于迭代贪婪策略的破坏与重建操作符来探索解空间并优化解决方案。以下部分系统地组织如下：第2节提供了ITPPDSP-TFTW及其相关概念IT2FN的全面阐述。第3节详细介绍了用于处理ITPPDSP-TFTW的LCMA。第4节包括计算实验的执行及其相应的分析结果。第5节总结了关键发现、实际意义以及后续研究的建议方向。

**IT2FN的相关概念**
在本文中，IT2FN被用来表示客户不确定的交付时间窗口。因此，本节提出了基本的IT2FN概念[39]。
**概念1：** 设T为一个类型2模糊集，用T表示，通常由隶属函数μT?(x,μ)表示，其中x∈X且μ∈[0,1]。集合T?可以表示为(t1,t2,t3,t4,t5)。相应的IT2FN如图1所示。基于μT(x,μ)，定义了区间类型2模糊数（IT2FN）。

**基于学习的协同进化元启发式方法**
在本节中，设计了LCMA来解决以成本和TEC为两个目标的ITPPDSP-TFTW问题，如图3所示。受协同进化算法思想的启发，设计了四种改进的基于问题特征的元启发式算法来更新ITPPDSP-TFTW的解决方案。LCMA的核心思想是设计了一种学习驱动机制来组织这些改进的元启发式算法，以提高它们的效率。首先，基于...

**实验比较与分析**
在本节中，进行了一系列实验来评估LCMA的性能。首先，介绍了用于处理ITPPDSP-TFTW的测试实例和评估指标。其次，提出了参数设置以确定LCMA的最佳参数组合。然后，测试了LCMA的每一项改进的有效性，以评估其性能。与其他最先进算法的比较证明了LCMA的优越性。

**讨论**
图10、图11、图12、图13中的图形结果显示，LCMA具有显著的优化能力，表现为HV值显著较高且IGD值较低，优于竞争方法。这种优越性归因于创新的LCMA框架，它在保持四个元启发式模块之间的最佳平衡的同时，在进化过程中保留了优秀的候选解决方案。其出色的收敛特性体现在持续较低的IGD值上。

**结论与未来工作**
在供应链竞争加剧和分布式制造广泛应用的背景下，本研究探讨了一个具有类型2模糊时间窗口的集成时间敏感产品生产和交付调度问题，该问题结合了分布式异构柔性流水线调度和车辆路径优化。为了最小化总成本和总能耗，构建了目标函数的计算模型，并采用了一种基于学习的...

**CRediT作者贡献声明**
肖宇刚：软件、方法论、资金获取、数据管理、概念化。
郭廷淮：撰写——原始草稿、验证、软件、项目管理、方法论、调查。
尹富民：撰写——原始草稿、验证、软件、资源管理、调查。
吴国华：撰写——审阅与编辑、监督、资金获取、数据管理、概念化。