{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7fb27b941602401d91542211134fc71a",
   "metadata": {},
   "source": [
    "# 汽车排序问题\n",
    "\n",
    "**类别：** 排程\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/car-sequencing)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acae54e37e7d407bbb7b55eff062a284",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**汽车排序问题** 涉及安排一组汽车的生产顺序。这些汽车并非完全相同,在基本车型的基础上有不同的配置选项可供选择。装配线上有不同的工作站来安装各种选项(空调、天窗等)。这些工作站有最大产能限制,它们最多能处理装配线上一定比例的车辆。因此,必须将汽车排成一个序列,以使每个工作站的产能都不会被超过。例如,如果某个工作站最多能处理装配线上三分之二的车辆,那么在序列中任意连续 3 辆车的窗口内,至多只能有 2 辆车需要该选项。\n",
    "\n",
    "### 学到的要点\n",
    "\n",
    "- 使用 [列表决策变量](https://optagent.pages.dev/guide/modeling/) 来表示汽车的序列\n",
    "- 区分 [结构性约束与第一优先级目标](https://optagent.pages.dev/guide/modeling/)\n",
    "- 使用 [非线性算子](https://optagent.pages.dev/guide/modeling/) 来计算违规次数\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a63283cbaf04dbcab1f6479b197f3a8",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "我们提供的汽车排序问题实例来自 [CSPLib](http://www.csplib.org/Problems/prob001/)。数据文件的格式如下:\n",
    "\n",
    "- 第 1 行: 车辆数量、选项数量、类别数量\n",
    "- 第 2 行: 对于每个选项,一个块中包含该选项的最大车辆数\n",
    "- 第 3 行: 对于每个选项,该最大车辆数所对应的块大小\n",
    "- 然后,对于每个类别:\n",
    "\n",
    "- 类别的索引\n",
    "- 该类别中的车辆数量\n",
    "- 对于每个选项,该类别是否需要它(1 或 0)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd0d8092fe74a7c96281538738b07e2",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "汽车排序问题的 OptAgent 模型使用一个 [列表决策变量](https://optagent.pages.dev/guide/modeling/) 来表示汽车的序列。列表的第 i 个元素对应于第 i 辆要生产的汽车的索引。使用 [**partition**](https://optagent.pages.dev/guide/modeling/) 算子,可以确保待生产的每辆汽车都出现在装配线上。\n",
    "\n",
    "根据这个序列,我们可以对每个选项和装配线上的每个位置,计算出从该位置开始的窗口中具有该选项的车辆数量。然后我们可以推导出每个选项和每个窗口的违规数量。\n",
    "\n",
    "尽管这个问题是一个纯可行性问题,我们仍然选择添加一个目标,即使所有选项和所有窗口的产能违规次数之和最小化。事实上,无产能违规更像是“业务”约束,而不是结构性约束。如果出现少量违规,装配线会减速但仍可继续运行。相反,在装配线上的某个位置同时放置两辆车在物理上是不可能的:这是一个结构性约束。有关高优先级目标和硬约束之间区别的更多信息,请参阅文档中的 [此章节](https://optagent.pages.dev/guide/modeling/)。\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",
    "\n",
    "\n",
    "def read_integers(filename):\n",
    "    return [\n",
    "        int(value)\n",
    "        for value in Path(filename).read_text(encoding=\"utf-8\").split()\n",
    "    ]\n",
    "\n",
    "\n",
    "def read_instance(instance_file):\n",
    "    file_it = iter(read_integers(instance_file))\n",
    "    nb_positions = next(file_it)\n",
    "    nb_options = next(file_it)\n",
    "    nb_classes = next(file_it)\n",
    "    max_cars_per_window = [next(file_it) for _ in range(nb_options)]\n",
    "    window_size = [next(file_it) for _ in range(nb_options)]\n",
    "    nb_cars = []\n",
    "    options = []\n",
    "    initial_sequence = []\n",
    "\n",
    "    for class_index in range(nb_classes):\n",
    "        next(file_it)\n",
    "        nb_cars.append(next(file_it))\n",
    "        options.append([next(file_it) == 1 for _ in range(nb_options)])\n",
    "        initial_sequence.extend([class_index] * nb_cars[class_index])\n",
    "\n",
    "    return (\n",
    "        nb_positions,\n",
    "        nb_options,\n",
    "        max_cars_per_window,\n",
    "        window_size,\n",
    "        options,\n",
    "        initial_sequence,\n",
    "    )\n",
    "\n",
    "\n",
    "def main(instance_file, output_file=None, time_limit=60):\n",
    "    (\n",
    "        nb_positions,\n",
    "        nb_options,\n",
    "        max_cars_per_window,\n",
    "        window_size,\n",
    "        options_data,\n",
    "        initial_sequence,\n",
    "    ) = read_instance(instance_file)\n",
    "    model = OptModel()\n",
    "    # sequence[i] = j if class initially planned on position j is produced on position i\n",
    "    sequence = model.list(nb_positions)\n",
    "\n",
    "    # sequence is a permutation of the initial production plan, all indexes must appear exactly once\n",
    "    model.constraint(model.partition(sequence))\n",
    "\n",
    "    # Create arrays to be able to access them with \"at\" operators\n",
    "    initial_array = model.array(initial_sequence)\n",
    "    option_array = model.array(options_data)\n",
    "\n",
    "    # Number of cars with option o in each window\n",
    "    nb_cars_windows = [None] * nb_options\n",
    "    for option in range(nb_options):\n",
    "        nb_cars_windows[option] = [None] * nb_positions\n",
    "        for start in range(nb_positions - window_size[option] + 1):\n",
    "            nb_cars_windows[option][start] = model.sum(\n",
    "                option_array[initial_array[sequence[start + offset]]][option]\n",
    "                for offset in range(window_size[option])\n",
    "            )\n",
    "\n",
    "    # Number of violations of option o capacity in each window\n",
    "    nb_violations_windows = [None] * nb_options\n",
    "    for option in range(nb_options):\n",
    "        nb_violations_windows[option] = [None] * nb_positions\n",
    "        for start in range(nb_positions - window_size[option] + 1):\n",
    "            nb_violations_windows[option][start] = model.max(\n",
    "                nb_cars_windows[option][start] - max_cars_per_window[option],\n",
    "                0,\n",
    "            )\n",
    "\n",
    "    total_violations = model.sum(\n",
    "        nb_violations_windows[option][start]\n",
    "        for option in range(nb_options)\n",
    "        for start in range(nb_positions - window_size[option] + 1)\n",
    "    )\n",
    "    model.minimize(total_violations)\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    values = {'violations': total_violations.value, 'sequence': sequence.value}\n",
    "    print(f\"Violations = {values['violations']}; Status = {solution.feasible}\")\n",
    "    sequence_text = \" \".join(\n",
    "        str(initial_sequence[index]) for index in values[\"sequence\"]\n",
    "    )\n",
    "    print(sequence_text)\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(\n",
    "            f\"{int(values['violations'])}\\n{sequence_text}\\n\", encoding=\"utf-8\"\n",
    "        )\n",
    "    return solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10185d26023b46108eb7d9f57d49d2b3",
   "metadata": {},
   "source": [
    "## 本地运行\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8763a12b2bbd4a93a75aff182afb95dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7623eae2785240b9bd12b16a66d81610",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = main(INSTANCE_DIR / \"4_72.in\", time_limit=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "244f67d3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.14.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}