1.2.2

下载 Notebook 下载完整案例

切割下料问题¶

类别： 装箱

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

在切割下料问题中,我们必须从具有固定尺寸的大卷材(或板材)上切割出宽度和高度各不相同的矩形物品。切割遵循一个结构化的两级切断模式:

• 条带 (Bands):具有相同宽度的物品沿其高度方向并排排列,形成水平条带。每个条带具有固定的宽度(即该物品的共同宽度),其总长度等于所有物品高度之和。
• 卷材 (Rolls):条带随后被垂直堆叠在卷材内。一个卷材内所有条带的总宽度不能超过卷材的宽度。同样地,每个条带的长度必须能放入卷材的长度内。

目标是最小化所使用的卷材数量。

学到的要点¶

• 使用 两层集合决策变量 来建模一个分层装箱结构(物品放入条带,条带放入卷材)
• 对集合使用 distinct 算子 配合一个 lambda,以强制一个条带内的所有物品共享相同的宽度
• 用三元运算符保护对集合的 max 操作(count(s) > 0 ? max(s, ...) : 0)以避免空集上的 NaN 问题

数据¶

我们提供的切割下料实例来自 2DPackLib 中的 A 类实例。数据文件的格式如下:

• 第一行:物品种类数
• 第二行:卷材宽度、卷材长度
• 对每种物品类型:宽度、高度、需求

建模思路¶

切割下料问题的 OptAgent 模型使用两层 集合决策变量。在第一层,对于每个条带,我们定义一个集合变量来表示分配到该条带的物品。在第二层,对于每个卷材,我们定义一个集合变量来表示分配到该卷材的条带。两层都使用 partition 约束以确保每个物品恰好属于一个条带,且每个条带恰好属于一个卷材。

在每个条带内,所有物品必须共享相同的宽度。这通过 distinct 算子配合一个 lambda 函数来强制:distinct(bands[b], (i) => rawWidth[i]) 返回该条带中不同的宽度集合,我们将其数量约束为不超过 1。我们使用可变参 sum 算子将物品高度累加作为条带长度,并约束每个条带的长度不超过卷材长度。在卷材层,我们使用可变参 sum 算子对卷材的条带集合配合返回每个条带宽度的 lambda 函数来计算条带的总宽度,并约束其不超过卷材宽度。

模型对卷材数量计算一个简单的下界(物品总面积除以卷材面积),并使用 objective threshold 在达到该下界时提前停止。

Python 实现¶

import math
from pathlib import Path

from optagent import OptModel, solve



def read_integers(filename):
    with Path(filename).open(encoding="utf-8") as file:
        return [int(value) for value in file.read().split()]


def read_instance(filename):
    values = read_integers(filename)
    iterator = iter(values)
    types, roll_width, roll_length = next(iterator), next(iterator), next(iterator)
    widths, lengths = [], []
    for _ in range(types):
        width, length, demand = next(iterator), next(iterator), next(iterator)
        widths.extend([width] * demand)
        lengths.extend([length] * demand)
    return roll_width, roll_length, widths, lengths


def main(instance_file, output_file=None, time_limit=10):
    roll_width, roll_length, widths_data, lengths_data = read_instance(instance_file)
    n = len(widths_data)
    nb_max_bands = n
    nb_max_rolls = n
    min_number_of_rolls = math.ceil(
        sum(widths_data[i] * lengths_data[i] for i in range(n))
        / (roll_width * roll_length)
    )

    model = OptModel()
    bands = [model.set(n) for index in range(nb_max_bands)]
    rolls = [model.set(nb_max_bands) for index in range(nb_max_rolls)]
    model.constraint(model.partition(bands))
    model.constraint(model.partition(rolls))
    widths, lengths = model.array(widths_data), model.array(lengths_data)
    band_widths, band_lengths = [], []
    for band in bands:
        # 条带内物品总长度不能超过卷材长度
        length = model.sum(band, model.lambda_function(lambda item: lengths[item]))
        model.constraint(length <= roll_length)
        # 一个条带里的所有物品宽度都相同
        distinct = model.distinct(band, model.lambda_function(lambda item: widths[item]))
        model.constraint(model.count(distinct) <= 1)
        band_widths.append(model.iif(
            band.count() > 0,
            model.max(band, model.lambda_function(lambda item: widths[item])),
            0,
        ))
        band_lengths.append(length)
    band_width_array = model.array(band_widths)
    roll_used, total_width = [], []
    for roll in rolls:
        # 条带宽度总和不能超过卷材宽度
        width = model.sum(roll, model.lambda_function(lambda band: band_width_array[band]))
        model.constraint(width <= roll_width)
        total_width.append(width)
        roll_used.append(roll.count() > 0)
    used_rolls = model.sum(*roll_used)
    model.minimize(used_rolls)
    solution = solve(
        model,
        time_limit_s=float(time_limit),
        objective_threshold={0: min_number_of_rolls},
    )
    values = {'used_rolls': used_rolls.value, **{f'band_{i}': band.value for i, band in enumerate(bands)}, **{f'roll_{i}': roll.value for i, roll in enumerate(rolls)}, **{f'band_width_{i}': width.value for i, width in enumerate(band_widths)}, **{f'band_length_{i}': length.value for i, length in enumerate(band_lengths)}, **{f'roll_width_{i}': width.value for i, width in enumerate(total_width)}}
    lines = []
    for index in range(nb_max_rolls):
        bands_in_roll = sorted(int(band) for band in values[f"roll_{index}"])
        if not bands_in_roll:
            continue
        lines.append(f"Roll {index} | width: {int(values[f'roll_width_{index}'])}/{roll_width}")
        for band_index in bands_in_roll:
            items = sorted(int(item) for item in values[f"band_{band_index}"])
            if items:
                lines.append(
                    f"  Band width={int(values[f'band_width_{band_index}'])} "
                    f"length={int(values[f'band_length_{band_index}'])} | Items: "
                    + " ".join(str(item) for item in items)
                )
    header = (
        f"Number of rolls used: {int(values['used_rolls'])}; "
        f"Min rolls: {min_number_of_rolls}; Status = {solution.feasible}"
    )
    print(header)
    for line in lines:
        print(line)
    if output_file is not None:
        Path(output_file).write_text(header + "\n" + "\n".join(lines) + "\n", encoding="utf-8")
    return solution

本地运行¶

INSTANCE_DIR = Path.cwd() / "instances"

solution = main(INSTANCE_DIR / "A1.txt", time_limit=10)