{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7fb27b941602401d91542211134fc71a",
   "metadata": {},
   "source": [
    "# 旅行商问题 (TSP)\n",
    "\n",
    "**类别：** 路径优化\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/traveling-salesman-problem-tsp)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acae54e37e7d407bbb7b55eff062a284",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**旅行商问题 (TSP)** 定义如下：给定 n 个城市以及每对城市之间的距离，寻找一条总长度最短的环游路径，使其恰好访问每个城市一次。从城市 i 到城市 j 的距离与从城市 j 到城市 i 的距离可能不同。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 使用 list 决策变量建模城市的排列\n",
    "- 使用 lambda 函数计算相邻城市之间的行驶距离\n",
    "- 求解后读取 list 决策变量的城市访问顺序\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a63283cbaf04dbcab1f6479b197f3a8",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "所提供的旅行商问题 (TSP) 实例来自 [TSPLib](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) 非对称 TSP 数据库，采用 TSPLib 显式格式。城市数量在关键字 “DIMENSION:” 之后定义，完整的距离矩阵在关键字 “EDGE_WEIGHT_SECTION” 之后给出。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd0d8092fe74a7c96281538738b07e2",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "该 OptAgent 模型基于一个 list 决策变量表示城市访问顺序。list 变量的第 i 个元素对应路径中第 i 个访问城市的索引。首先约束该 list 包含所有城市，以确保每个城市恰好访问一次。随后通过二维模型数组按决策表达式索引距离矩阵，使用 lambda 函数对相邻城市之间的距离求和，再加上从最后一个城市返回第一个城市的闭环距离。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8edb47106e1a46a883d545849b8ab81b",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "10185d26023b46108eb7d9f57d49d2b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_tokens(filename):\n",
    "    return Path(filename).read_text(encoding=\"utf-8\").split()\n",
    "\n",
    "\n",
    "def read_instance(filename):\n",
    "    file_it = iter(read_tokens(filename))\n",
    "    # The input files follow the TSPLib \"explicit\" format\n",
    "    for token in file_it:\n",
    "        if token == \"DIMENSION:\":\n",
    "            nb_cities = int(next(file_it))\n",
    "        if token == \"EDGE_WEIGHT_SECTION\":\n",
    "            break\n",
    "\n",
    "    # Distance from i to j\n",
    "    distance_data = [[int(next(file_it)) for _ in range(nb_cities)] for _ in range(nb_cities)]\n",
    "    return nb_cities, distance_data\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=5):\n",
    "    nb_cities, distance_data = read_instance(input_file)\n",
    "    model = OptModel()\n",
    "\n",
    "    # A list variable: cities[i] is the index of the ith city in the tour\n",
    "    cities = model.list(nb_cities)\n",
    "\n",
    "    # All cities must be visited\n",
    "    model.constraint(model.count(cities) == nb_cities)\n",
    "\n",
    "    # A model array supports indexing with city decision expressions.\n",
    "    distance_matrix = model.array(distance_data)\n",
    "\n",
    "    # Minimize the total distance\n",
    "    distance_to_next_city = model.lambda_function(\n",
    "        lambda position: distance_matrix[cities[(position - 1) // 1], cities[position // 1]]\n",
    "    )\n",
    "    objective = (\n",
    "        model.sum(model.range(1, nb_cities), distance_to_next_city) + distance_matrix[cities[nb_cities - 1], cities[0]]\n",
    "    )\n",
    "    model.minimize(objective)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    if not solution.feasible:\n",
    "        print(f\"No feasible tour found; Status = {solution.status}\")\n",
    "        return solution\n",
    "\n",
    "    tour = list(cities.value)\n",
    "    result_text = f\"Total distance = {objective.value}; Status = {solution.status}\\nTour: {' '.join(map(str, tour))}\"\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, tour))}\\n\",\n",
    "            encoding=\"utf-8\",\n",
    "        )\n",
    "    return solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8763a12b2bbd4a93a75aff182afb95dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7623eae2785240b9bd12b16a66d81610",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_br17 = main(INSTANCE_DIR / \"br17.atsp\", time_limit=1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}