Solving the Paint Shop Problem with Flexible Management of Multi-Lane Buffers Using Reinforcement Learning and Action Masking

📄 arXiv: 2504.02644v2 📥 PDF

作者: Mirko Stappert, Bernhard Lutz, Janis Brammer, Dirk Neumann

分类: cs.LG, math.OC

发布日期: 2025-04-03 (更新: 2026-01-05)

DOI: 10.1016/j.ejor.2025.12.017

💡 一句话要点

提出基于强化学习和动作掩码的多通道缓冲柔性管理方法，解决喷涂车间问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 喷涂车间问题 强化学习 动作掩码 多通道缓冲 排序优化

📋 核心要点

  1. 现有喷涂车间问题解决方法，如贪婪算法，在存储和检索操作的灵活性方面存在不足。
  2. 论文提出基于强化学习的方法，结合动作掩码，优化存储和检索策略，最小化颜色变化。
  3. 实验结果表明，该方法在不同规模和颜色分布的问题上，显著优于现有方法，并具有鲁棒性。

📝 摘要（中文）

在喷涂车间问题中，需要对分配了不同颜色的无序车辆序列进行重排，以最小化颜色变化次数。为了重排输入序列，制造商可以使用先进先出多通道缓冲系统，该系统允许存储和检索操作。以往的研究主要集中于简单的决策启发式方法，如贪婪算法或简化的允许存储和检索操作不具备完全灵活性的问题变体。本研究提出了一种强化学习方法，以最小化灵活问题变体的颜色变化，其中存储和检索操作可以以任意顺序执行。在证明了贪婪检索是最优的之后，我们使用动作掩码将这一发现纳入模型中。基于包含2-8个缓冲通道和5-15种颜色的170个问题实例的评估表明，与现有方法相比，我们的方法显著减少了颜色变化，具体减少幅度取决于问题规模。此外，我们还证明了我们的方法对于不同的缓冲大小和不平衡的颜色分布具有鲁棒性。

🔬 方法详解

问题定义：喷涂车间问题旨在最小化车辆喷涂过程中的颜色切换次数。车辆以无序序列到达，每个车辆需要喷涂不同的颜色。为了优化喷涂顺序，可以使用多通道缓冲系统对车辆进行重新排序。现有方法，如贪婪算法，在处理复杂的存储和检索操作时缺乏灵活性，导致颜色切换次数较多。

核心思路：论文的核心思路是利用强化学习来学习最优的存储和检索策略。通过强化学习，智能体可以根据当前缓冲区的状态和车辆序列，动态地选择存储和检索操作，从而最小化颜色切换次数。此外，论文证明了贪婪检索策略是最优的，并将这一结论融入到强化学习模型中，以提高学习效率。

技术框架：该方法采用强化学习框架，智能体与环境进行交互。环境包括多通道缓冲区和车辆序列。智能体根据当前状态（缓冲区状态和车辆序列）选择动作（存储或检索车辆）。环境根据智能体的动作更新状态，并返回奖励（颜色切换次数的负值）。智能体通过不断学习，优化其策略，以最大化累积奖励。

关键创新：该方法的关键创新在于将强化学习应用于喷涂车间问题，并结合了动作掩码技术。动作掩码用于限制智能体的动作空间，使其只选择有效的动作。例如，当缓冲区已满时，智能体不能选择存储操作。通过动作掩码，可以提高学习效率，并避免无效的探索。此外，证明贪婪检索策略最优也是一个重要的理论贡献。

关键设计：该方法使用深度Q网络（DQN）作为强化学习算法。DQN的输入是缓冲区状态和车辆序列，输出是每个动作的Q值。损失函数采用均方误差损失函数。动作掩码用于限制智能体的动作空间。奖励函数是颜色切换次数的负值。实验中，对DQN的超参数进行了调整，以获得最佳性能。

📊 实验亮点

实验结果表明，该方法在包含2-8个缓冲通道和5-15种颜色的170个问题实例上，与现有方法相比，显著减少了颜色变化。具体而言，该方法在不同问题规模上均优于现有方法，并且对于不同的缓冲大小和不平衡的颜色分布具有鲁棒性。例如，在某些问题实例上，颜色切换次数减少了10%以上。

🎯 应用场景

该研究成果可应用于汽车制造、涂料生产等需要优化颜色切换顺序的工业领域。通过优化喷涂顺序，可以减少颜色切换次数，降低生产成本，提高生产效率。此外，该方法还可以推广到其他类似的排序优化问题，例如，仓库拣货、任务调度等。

📄 摘要（原文）

In the paint shop problem, an unordered incoming sequence of cars assigned to different colors has to be reshuffled with the objective of minimizing the number of color changes. To reshuffle the incoming sequence, manufacturers can employ a first-in-first-out multi-lane buffer system allowing store and retrieve operations. So far, prior studies primarily focused on simple decision heuristics like greedy or simplified problem variants that do not allow full flexibility when performing store and retrieve operations. In this study, we propose a reinforcement learning approach to minimize color changes for the flexible problem variant, where store and retrieve operations can be performed in an arbitrary order. After proving that greedy retrieval is optimal, we incorporate this finding into the model using action masking. Our evaluation, based on 170 problem instances with 2-8 buffer lanes and 5-15 colors, shows that our approach reduces color changes compared to existing methods by considerable margins depending on the problem size. Furthermore, we demonstrate the robustness of our approach towards different buffer sizes and imbalanced color distributions.