一维装箱/板材切割优化：石膏板墙面覆盖建模改进咨询

业务场景与约束 #

• 属于一维装箱（1D bin packing）/板材切割（sheet cutting）变体：核心需求是优化带梁架干墙的石膏板覆盖方案，确定最优的板材数量与尺寸
• 硬约束：
  • 石膏板必须严格从梁的位置开始、到梁的位置结束
  • 石膏板之间不能重叠
• 软约束：使用的板材总数越少越好（优先选择大尺寸单块板材）

当前实现与存在的问题 #

当前方案 #

1. 预生成所有可能的石膏板规格，作为问题事实传入求解器
2. 通过可空规划变量让求解器从预生成集合中选择最优子集
3. 算法组合：首次适应递减（First Fit Decreasing）+ 模拟退火（Simulated Annealing）

遇到的问题 #

• 即使是6米左右的小型墙面（可选板材不足20种），求解耗时也需要数分钟
• 仅能得到可行解，几乎无法达到最优解
• 领域模型存在缺陷：规划实体Assignment仅存储选中物料，无差异化属性，无法基于实体难度做优化，当前模型代码如下：

data class Assignment(

    @PlanningId
    private val id: Long? = null,

    @PlanningVariable(
        valueRangeProviderRefs = ["materials"],
        strengthComparatorClass = MaterialStrengthComparator::class,
        nullable = true
    )
    var material: Material? = null
)

data class Material(
    val start: Double,
    val stop: Double,
)

更优建模与优化建议 #

1. 重构领域模型，以墙面分段为核心规划实体 #

放弃预生成所有Material的思路，把墙面的梁间分段作为规划实体，规划变量改为选择覆盖该分段（或连续分段组合）的标准石膏板规格。示例代码：

// 墙面的梁间分段，作为规划实体
data class WallSegment(
    @PlanningId
    val id: Long,
    val startPosition: Double, // 该分段的起始梁位置
    val length: Double, // 分段自身长度
    // 规划变量：选择覆盖当前分段（或合并相邻分段）的标准石膏板
    @PlanningVariable(valueRangeProviderRefs = ["standardPanelSizes"])
    var selectedPanel: StandardPanel? = null,
    // 辅助标记：是否已被合并到相邻分段的石膏板中
    var isMerged: Boolean = false
)

// 标准石膏板规格（固定问题事实）
data class StandardPanel(
    val maxLength: Double // 比如1.2m、2.4m、3.6m等行业标准尺寸
)

这种模型下，每个规划实体有明确的位置、长度属性，可以基于分段长度、位置顺序做实体难度排序（比如优先处理长分段），大幅提升求解效率。

2. 动态生成可行覆盖方案，避免解空间爆炸 #

预生成所有Material会导致解空间指数级膨胀，改为：

• 仅传入标准石膏板规格作为问题事实
• 通过约束动态验证：选中的石膏板必须覆盖整数个连续梁间分段，且起始/结束位置严格对齐梁
• 用链式约束处理分段合并：如果相邻分段选择了同规格石膏板，且总长度不超过板材最大尺寸，则允许合并为一块板材，直接减少总板材数量

3. 调整算法策略 #

• 替换首次适应递减为最佳适应递减（Best Fit Decreasing）：优先用最大规格板材覆盖最长的连续分段，减少无效碎片
• 调优模拟退火参数：降低初始温度、加快降温速率，或改用禁忌搜索（Tabu Search），更高效地探索解空间
• 启用构造启发式优化：基于实体难度（长分段优先）和变量强度（大尺寸板材优先）排序，快速生成高质量初始解，再用元启发式算法迭代优化

4. 强化约束建模 #

• 硬约束：
  • 确保所有墙面分段都被覆盖（无遗漏）
  • 石膏板覆盖范围严格对齐梁位置，且无重叠
• 软约束：
  • 直接以板材总数量作为核心评分指标，数量越少评分越高
  • 可选：增加“减少板材切割次数”的辅助软约束（如果允许切割标准板材）

内容的提问来源于stack exchange，提问作者whiskeysierra