{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 订单拣选问题\n",
    "\n",
    "**类别：** 路径优化\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/order-picking-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**订单拣选问题** 描述如下：需要拣选一组订单。拣货员从初始位置出发，拣取订单后返回初始位置卸货。我们考虑一个普通的矩形仓库，其中有一个用于卸货的单一仓库起点。该仓库起点也作为拣货员的初始位置。需要拣取的订单位于垂直通道的两侧，两侧均可到达。垂直通道由水平横向通道环绕，拣货员可通过水平横向通道在仓库内移动。拣货员可以纵向和横向移动。任意两个订单之间的距离使用曼哈顿距离计算。问题的目标是找到使完成订单所需距离（或时间）最小的拣选顺序。\n",
    "\n",
    "### 建模要点\n",
    "\n",
    "- 添加一个 [list 决策变量](https://optagent.pages.dev/guide/modeling/) 来建模拣选顺序\n",
    "- 定义一个 [lambda 函数](https://optagent.pages.dev/guide/modeling/) 来计算行驶距离\n",
    "- 获取 [list 变量](https://optagent.pages.dev/guide/modeling/) 的值\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "我们提供的订单拣选问题实例来自 [Theys et al. 基准](https://repository.uantwerpen.be/desktop/irua)。数据文件的格式如下：\n",
    "\n",
    "- 第一行：订单数量\n",
    "- 接下来若干行：任意两个订单（包括索引 0 处的初始位置）之间的距离矩阵。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "在订单拣选问题的 OptAgent 模型中，我们使用一个 list 决策变量表示拣选顺序。我们也将初始点视为一个待拣选订单。对 list 大小的约束确保所有订单都被拣取。\n",
    "\n",
    "目标是最小化拣取所有订单所需的距离。为了计算该距离，我们使用一个 lambda 函数返回从一个订单到下一个订单的距离。我们通过对该 lambda 函数在所有订单位置上的求和来计算目标值。\n",
    "\n",
    "由于拣货员的行驶路径是一个回路，因此不需要将 list 中的第一个元素约束为初始点。这可以在求解后的后处理阶段完成。为此，我们在模型声明中使用 **index** 算子来恢复 list 中元素 0 的位置。然后我们可以将拣选顺序保存到文件中，从初始点开始。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_elem(filename):\n",
    "    return Path(filename).read_text(encoding=\"utf-8\").split()\n",
    "\n",
    "\n",
    "def read_instance(filename):\n",
    "    file_iterator = iter(read_elem(filename))\n",
    "    nb_orders = int(next(file_iterator)) + 1\n",
    "    distances_data = [\n",
    "        [int(next(file_iterator)) for _ in range(nb_orders)]\n",
    "        for _ in range(nb_orders)\n",
    "    ]\n",
    "    return nb_orders, distances_data\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=10):\n",
    "    nb_orders, distances_data = read_instance(input_file)\n",
    "    model = OptModel()\n",
    "\n",
    "    # A full-length list models the permutation of all orders, including node 0.\n",
    "    picking_list = model.list(nb_orders)\n",
    "    model.constraint(model.count(picking_list) == nb_orders)\n",
    "\n",
    "    distances_matrix = model.array(distances_data)\n",
    "    distance_to_next_order = model.lambda_function(\n",
    "        lambda position: distances_matrix[\n",
    "            picking_list[position // 1], picking_list[(position + 1) // 1]\n",
    "        ]\n",
    "    )\n",
    "    objective = model.sum(\n",
    "        model.range(0, nb_orders - 1), distance_to_next_order\n",
    "    ) + distances_matrix[\n",
    "        picking_list[(nb_orders - 1) // 1], picking_list[0]\n",
    "    ]\n",
    "    index_initial_position = model.index(picking_list, 0)\n",
    "    model.minimize(objective)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    order = list(picking_list.value)\n",
    "    start = index_initial_position.value\n",
    "    cyclic_order = [\n",
    "        order[(start + offset) % nb_orders] for offset in range(nb_orders)\n",
    "    ]\n",
    "    result_text = f\"Total distance = {objective.value}\\nOrder: {' '.join(map(str, cyclic_order))}\"\n",
    "    print(result_text)\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(\n",
    "            f\"{objective.value}\\n{' '.join(map(str, cyclic_order))}\\n\",\n",
    "            encoding=\"utf-8\",\n",
    "        )\n",
    "    return solution\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "在 notebook 所在目录执行以下 cell，即可调用一个小型订单拣选实例。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_order_picking = main(\n",
    "    INSTANCE_DIR / \"Instance_5_3_15_Random_Central_0.txt\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}