1.2.1

下载 Notebook 下载完整案例

货架装箱问题¶

类别： 装箱

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

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

问题描述¶

在 Shelf Packing Problem 中，一组具有已知重量和已知类别的物品必须被分配到位于货架上的、具有统一容量的箱子中。货架上的总重量以及属于给定类别的物品数量均受到限制。目标是最小化用于放置所有物品的货架数量（第一个目标函数），然后最小化箱子数量（第二个目标函数）。该问题是 Bin Packing Problem (BPP) 的一个变种，因此是 NP-hard 的。

学习要点¶

• 使用 OptAgent 的 set 决策变量建模箱子的内容
• 使用 union 表达货架上所有箱子的物品并集
• 使用 partition 确保每个物品恰好放入一个箱子
• 使用 lambda_function 计算箱子和货架的总重量

数据¶

Shelf Packing Problem 实例是随机生成的 JSON 文件。它们由以下元素组成：

• “nbItems”
• “nbShelves”
• “nbCategories”
• “binCapacity”
• “shelfCapacity”
• “itemWeights”
• “itemCategories”
• “limitCategories”：limitCategories[c] 是货架 s 上类别 c 的最大物品数量
• “binsAssignment”：binsAssignment[s] 是分配给货架 s 的箱子列表

Python 示例使用标准库 json 读取实例数据。

建模思路¶

此处实现的 OptAgent 模型使用 set 决策变量。

每个货架上有若干箱子。对每个货架，我们使用 union 定义其中所有箱子的物品并集。

对于每个箱子，我们定义一个 set 来描述分配到该箱子中的物品。这些集合通过 partition 约束形成分区，确保每个物品恰好被分配到一个箱子。 分配到一个箱子中的物品的重量之和不得超过箱子容量。 货架上所有物品的重量之和不得超过货架容量。 在任何货架上，给定类别的物品数量不得超过设定的限制。为此，我们对货架物品集合与该类别的物品数组执行 intersection，并将交集数量限制在 limitCategories[c] 以内。

目标是首先最小化使用的货架数量（第一个目标），然后最小化使用的箱子数量（第二个目标）。

Python 实现¶

import json
from pathlib import Path

from optagent import OptModel, solve


def read_instance(instance_filename):
    with open(instance_filename, encoding="utf-8") as f:
        return json.load(f)


def main(input_file, output_file=None, time_limit=60):
    data = read_instance(input_file)
    nb_items = data["nbItems"]
    nb_categories = data["nbCategories"]
    nb_shelves = data["nbShelves"]
    bin_capacity = data["binCapacity"]
    shelf_capacity = data["shelfCapacity"]
    weights_data = data["itemWeights"]
    categories_data = data["itemCategories"]
    limit_categories = data["limitCategories"]
    bins_assignment = data["binsAssignment"]
    nb_max_bins = nb_items

    model = OptModel()

    # bins[k] is the set of items assigned to bin k.
    bins = [model.set(nb_items) for k in range(nb_max_bins)]

    # A shelf contains the union of the bins assigned to it by the instance.
    shelves = [
        model.union(bins[b] for b in bins_assignment[s])
        for s in range(nb_shelves)
    ]

    # Every item must be assigned to exactly one bin.
    model.constraint(model.partition(model.array(bins)))

    weights = model.array(weights_data)
    weight_lambda = model.lambda_function(lambda item: weights[item // 1])

    bin_weights = [model.sum(bin_items, weight_lambda) for bin_items in bins]
    for k, bin_weight in enumerate(bin_weights):
        model.constraint(bin_weight <= bin_capacity)
    bins_used = [model.count(bin_items) > 0 for bin_items in bins]

    shelves_weights = [model.sum(shelf, weight_lambda) for shelf in shelves]
    for s, shelf_weight in enumerate(shelves_weights):
        model.constraint(
            shelf_weight <= shelf_capacity,
        )

    # Limit the number of items of each category on every shelf.
    for c in range(nb_categories):
        items_per_category = [
            i for i in range(nb_items) if categories_data[i] == c
        ]
        items_per_category_array = model.array(items_per_category)
        for s, shelf in enumerate(shelves):
            category_count = model.count(
                model.intersection(shelf, items_per_category_array)
            )
            model.constraint(
                category_count <= limit_categories[c],
            )

    shelves_used = [model.count(shelf) > 0 for shelf in shelves]
    total_shelves_used = model.sum(shelves_used)
    total_bins_used = model.sum(bins_used)

    # Objectives are optimized lexicographically in declaration order.
    model.minimize(total_shelves_used)
    model.minimize(total_bins_used)

    solution = solve(model, time_limit_s=float(time_limit))
    if not solution.feasible:
        print(f"No feasible packing found; Status = {solution.status}")
        return solution

    lines = [
        f"Shelves used = {total_shelves_used.value}; "
        f"Bins used = {total_bins_used.value}; Status = {solution.status}"
    ]
    for s in range(nb_shelves):
        if not shelves_used[s].value:
            continue
        lines.append(
            f"Shelf {s} total weight: {shelves_weights[s].value}/{shelf_capacity}"
        )
        for k in bins_assignment[s]:
            if bins_used[k].value:
                items = " ".join(f"#{item}" for item in sorted(bins[k].value))
                lines.append(
                    f"> Bin {k} weight: {bin_weights[k].value}/{bin_capacity} | "
                    f"Items: {items}"
                )

    result_text = "\n".join(lines)
    print(result_text)
    if output_file is not None:
        Path(output_file).write_text(result_text + "\n", encoding="utf-8")
    return solution

本地运行¶

Notebook 直接调用 main 并显式传入 JSON 实例路径。以下代码格相互独立，可以按需要单独运行；调整 time_limit 可以控制每个实例的求解时间。

INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)

solution_0 = main(
    INSTANCE_DIR / "instance_0.json",
    time_limit=1,
)

solution_1 = main(
    INSTANCE_DIR / "instance_1.json",
    time_limit=1,
)

solution_2 = main(
    INSTANCE_DIR / "instance_2.json",
    time_limit=1,
)

solution_3 = main(
    INSTANCE_DIR / "instance_3.json",
    time_limit=1,
)

solution_4 = main(
    INSTANCE_DIR / "instance_4.json",
    time_limit=1,
)