{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7fb27b941602401d91542211134fc71a",
   "metadata": {},
   "source": [
    "# 卡车装载问题\n",
    "\n",
    "**类别：** 装箱\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/truck-loading-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acae54e37e7d407bbb7b55eff062a284",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "在**卡车装载问题**中，给定的一组物品需要装载到卡车中。因此，每件物品必须恰好被分配到一辆卡车。\n",
    "\n",
    "每辆卡车有两层：底层和上层。每一层具有相同的物品位置数量，每辆卡车也具有相同的载重能力。因此，分配给某辆卡车的物品总重量不得超过该载重能力。\n",
    "\n",
    "除重量外，物品还可能存在堆放限制：\n",
    "\n",
    "- 类型 1 物品必须放置在底层，并且其上方不能再放置其他物品，称为 “Alone（独占）” 物品。\n",
    "- 类型 2 物品必须放置在底层，但其上方可以再放置其他物品，称为 “Floor（底层）” 物品。\n",
    "- 类型 3 物品没有任何堆放限制，称为 “No-restriction（无限制）” 物品。\n",
    "- 类型 4 物品上方不能再放置其他物品，但可以放在底层或上层，称为 “Delicate（易碎）” 物品。\n",
    "\n",
    "此外，卡车的上层只有在底层被装满时才能使用。目标是最小化所使用的卡车数量。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 使用 set 决策变量建模各卡车中所装物品\n",
    "- 使用 lambda 函数计算卡车总重量并强制执行堆放限制\n",
    "- 在后处理函数中使用 OptAgent 找到的解生成具体摆放\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a63283cbaf04dbcab1f6479b197f3a8",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "所提供的卡车装载问题实例改编自 [BPPLIB](https://site.unibo.it/operations-research/en/research/bpplib-a-bin-packing-problem-library) 中的 Falkenauer 实例。数据文件的格式如下：\n",
    "\n",
    "- 第一行包含一个整数：物品数量。\n",
    "- 第二行包含两个整数：每辆卡车的载重能力以及卡车每层的物品位置数。\n",
    "- 之后每行使用两个整数描述一件物品：\n",
    "- 首先是其重量，\n",
    "\n",
    "- 然后是一个介于 1 到 4（含）之间的整数，指定其类型：\n",
    "- 1 表示 “Alone（独占）” 物品，\n",
    "\n",
    "- 2 表示 “Floor（底层）” 物品，\n",
    "\n",
    "- 3 表示 “No-restriction（无限制）” 物品，\n",
    "\n",
    "- 或 4 表示 “Delicate（易碎）” 物品。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd0d8092fe74a7c96281538738b07e2",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "卡车装载问题的 OptAgent 模型使用 set 决策变量表示分配给每辆卡车的物品集合。约束这些 set 变量构成 partition（划分），以确保每件物品恰好属于一辆卡车。\n",
    "\n",
    "我们使用对集合的 **sum（求和）** 运算符以及一个返回指定物品索引对应重量的 lambda 函数来计算每辆卡车的总重量。需要注意的是，该求和的项数在搜索过程中会随着集合大小变化而变化。然后约束总重量不超过卡车的载重能力。\n",
    "\n",
    "“Alone” 和 “Floor” 物品必须位于其所在卡车的底层。因此，模型保证在任何卡车中它们都不超过每层的可用位置数。接着我们对 “Alone” 和 “Delicate” 物品添加类似的约束，因为它们上方不能再放置其他物品。\n",
    "\n",
    "“Alone” 物品必须放置在底层，并且由于其上方不能再放置物品，因此会同时占用对应的上方位置。也就是说，它们占用两个位置单位而非一个。然后模型保证每辆卡车中被占用的位置数不超过总位置数。\n",
    "\n",
    "我们使用 count（计数）运算符计算使用的卡车总数，该运算符返回集合中元素的数量。\n",
    "\n",
    "该模型仅给出每辆卡车所装载的物品集合。物品在卡车内的具体摆放则由一个后处理函数另行计算。该函数先装载 “Alone” 和 “Floor” 物品以确保它们位于底层，然后装载 “No-restriction” 物品，最后装载必然位于最上层的 “Delicate” 物品。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72eea5119410473aa328ad9291626812",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8edb47106e1a46a883d545849b8ab81b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_integers(filename):\n",
    "    return [int(value) for value in Path(filename).read_text(encoding=\"utf-8\").split()]\n",
    "\n",
    "\n",
    "def read_instance(filename):\n",
    "    file_it = iter(read_integers(filename))\n",
    "    nb_items = next(file_it)\n",
    "    truck_weight_capacity = next(file_it)\n",
    "    level_spots_count = next(file_it)\n",
    "\n",
    "    item_weights = []\n",
    "    item_categories = []\n",
    "    item_volumes = []\n",
    "    for _ in range(nb_items):\n",
    "        weight = next(file_it)\n",
    "        category = next(file_it)\n",
    "        item_weights.append(weight)\n",
    "        item_categories.append(category)\n",
    "        # An Alone item blocks a floor position and the position above it.\n",
    "        item_volumes.append(2 if category == 1 else 1)\n",
    "\n",
    "    return (\n",
    "        nb_items,\n",
    "        truck_weight_capacity,\n",
    "        level_spots_count,\n",
    "        item_weights,\n",
    "        item_categories,\n",
    "        item_volumes,\n",
    "    )\n",
    "\n",
    "\n",
    "# Insert an item into the next free slot in the truck.\n",
    "def place_first_available_pos(positions, item, level_spots_count):\n",
    "    if len(positions[0]) < level_spots_count:\n",
    "        positions[0].append(item)\n",
    "    else:\n",
    "        positions[1].append(item)\n",
    "\n",
    "\n",
    "# The model assigns items to trucks; this builds a feasible two-level placement.\n",
    "def inside_truck(truck_set, item_categories, level_spots_count):\n",
    "    # Split the items assigned to the truck by category\n",
    "    set_a = []  # Type 1: floor level and nothing above. Called \"Alone\" items\n",
    "    set_f = []  # Type 2: floor level. Called \"Floor\" items\n",
    "    set_n = []  # Type 3: no restriction. Called \"No-restriction\" items\n",
    "    set_d = []  # Type 4: nothing above. Called \"Delicate\" items\n",
    "\n",
    "    for i in truck_set:\n",
    "        category = item_categories[i]\n",
    "        if category == 1:\n",
    "            set_a.append(i)\n",
    "        elif category == 2:\n",
    "            set_f.append(i)\n",
    "        elif category == 3:\n",
    "            set_n.append(i)\n",
    "        else:\n",
    "            set_d.append(i)\n",
    "\n",
    "    # Initialize the two-level position list: positions[0] represents the floor level, and positions[1] the upper level\n",
    "    positions = [[], []]\n",
    "\n",
    "    #\n",
    "    # Assign positions to items, from the most constraining category to the least constraining one: A -> F -> N -> D\n",
    "    #\n",
    "\n",
    "    # Place all \"Alone\" items on the floor, and leave the corresponding upper positions empty (represented by -1)\n",
    "    for i in set_a:\n",
    "        positions[0].append(i)\n",
    "        positions[1].append(-1)\n",
    "\n",
    "    # Place all \"Floor\" items on the floor\n",
    "    for i in set_f:\n",
    "        positions[0].append(i)\n",
    "\n",
    "    # Place all \"No-restriction\" items at the first available position\n",
    "    for i in set_n:\n",
    "        place_first_available_pos(positions, i, level_spots_count)\n",
    "\n",
    "    # Place all \"Delicate\" items at the first available position\n",
    "    for i in set_d:\n",
    "        place_first_available_pos(positions, i, level_spots_count)\n",
    "\n",
    "    return positions\n",
    "\n",
    "\n",
    "def pad_left(x, width):\n",
    "    return (\" \" if x == -1 else str(x)).rjust(width)\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=10):\n",
    "    (\n",
    "        nb_items,\n",
    "        truck_weight_capacity,\n",
    "        level_spots_count,\n",
    "        item_weights,\n",
    "        item_categories,\n",
    "        item_volumes,\n",
    "    ) = read_instance(input_file)\n",
    "\n",
    "    # Bounds on the number of used trucks\n",
    "    nb_min_trucks = (sum(item_weights) + truck_weight_capacity - 1) // truck_weight_capacity\n",
    "    nb_max_trucks = nb_items\n",
    "\n",
    "    model = OptModel()\n",
    "\n",
    "    # trucks[k] is the set of items assigned to truck k.\n",
    "    trucks = [model.set(nb_items) for truck in range(nb_max_trucks)]\n",
    "\n",
    "    # Each item must be assigned to exactly one truck.\n",
    "    model.constraint(model.partition(trucks))\n",
    "\n",
    "    weights = model.array(item_weights)\n",
    "    categories = model.array(item_categories)\n",
    "    volumes = model.array(item_volumes)\n",
    "\n",
    "    weight_lambda = model.lambda_function(lambda item: weights[item // 1])\n",
    "    volume_lambda = model.lambda_function(lambda item: volumes[item // 1])\n",
    "    floor_lambda = model.lambda_function(lambda item: model.or_(categories[item // 1] == 1, categories[item // 1] == 2))\n",
    "    delicate_lambda = model.lambda_function(\n",
    "        lambda item: model.or_(categories[item // 1] == 1, categories[item // 1] == 4)\n",
    "    )\n",
    "\n",
    "    truck_weights = []\n",
    "    trucks_used = []\n",
    "    for truck, truck_items in enumerate(trucks):\n",
    "        truck_weight = model.sum(truck_items, weight_lambda)\n",
    "        truck_weights.append(truck_weight)\n",
    "\n",
    "        model.constraint(\n",
    "            truck_weight <= truck_weight_capacity,\n",
    "        )\n",
    "        model.constraint(\n",
    "            model.sum(truck_items, volume_lambda) <= 2 * level_spots_count,\n",
    "        )\n",
    "        model.constraint(\n",
    "            model.sum(truck_items, floor_lambda) <= level_spots_count,\n",
    "        )\n",
    "        model.constraint(\n",
    "            model.sum(truck_items, delicate_lambda) <= level_spots_count,\n",
    "        )\n",
    "        trucks_used.append(model.count(truck_items) > 0)\n",
    "\n",
    "    total_used_trucks = model.sum(trucks_used)\n",
    "    model.minimize(total_used_trucks)\n",
    "\n",
    "    solution = solve(\n",
    "        model,\n",
    "        time_limit_s=float(time_limit),\n",
    "        objective_threshold={0: nb_min_trucks},\n",
    "    )\n",
    "    if not solution.feasible:\n",
    "        print(f\"No feasible loading found; Status = {solution.status}\")\n",
    "        return solution\n",
    "\n",
    "    print_width = len(str(nb_items - 1)) + 2\n",
    "    lines = [f\"Number of used trucks: {total_used_trucks.value}\", \"\"]\n",
    "    for truck in range(nb_max_trucks):\n",
    "        if not trucks_used[truck].value:\n",
    "            continue\n",
    "\n",
    "        positions = inside_truck(trucks[truck].value, item_categories, level_spots_count)\n",
    "        separator = \"-\" * (level_spots_count * print_width)\n",
    "        lines.extend(\n",
    "            [\n",
    "                f\"Truck weight: {truck_weights[truck].value}\",\n",
    "                separator,\n",
    "                \"\".join(pad_left(item, print_width) for item in positions[1]),\n",
    "                \"\".join(pad_left(item, print_width) for item in positions[0]),\n",
    "                separator,\n",
    "                \"\",\n",
    "            ]\n",
    "        )\n",
    "\n",
    "    result_text = \"\\n\".join(lines) + \"\\n\"\n",
    "    print(f\"Status = {solution.status}\")\n",
    "    print(result_text, end=\"\")\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(result_text, encoding=\"utf-8\")\n",
    "    return solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "10185d26023b46108eb7d9f57d49d2b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8763a12b2bbd4a93a75aff182afb95dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_t60_00 = main(INSTANCE_DIR / \"t60_00.txt\", time_limit=1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}