{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8b30f8e2",
   "metadata": {},
   "source": [
    "# TSPTW\n",
    "\n",
    "In the traveling salesperson problem with time windows (TSPTW), we are given a set of locations $N = \\{ 0, ..., n-1 \\}$.\n",
    "The salesperson starts from the depot $0$, visit each customer $i \\in \\{ 1, ..., n-1 \\}$ exactly once, and returns to the depot.\n",
    "The traveling time from $i$ to $j$ is $c_{ij}$.\n",
    "Each customer $i$ must be visited within time window $[a_i, b_i]$, and the salesperson must wait until $a_i$ if arriving at $i$ before $a_i$.\n",
    "The objective is to minimize the total travel time (not including the waiting time).\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "Let $U \\subseteq N$ be the set of unvisited customers, $i \\in N$ be the current location of the salesperson, and $t$ be the current time.\n",
    "Let $V(U, i, t)$ be the optimal cost to visit customers $U$ and return to the depot starting from $i$ with time $t$.\n",
    "When customer $j \\in U$ is visited next, the problem is reduced to visiting customers $U \\setminus \\{ j \\}$ from location $j$ at time $\\max \\{ t + c_{ij}, a_j \\}$.\n",
    "When all customers are visited, the salesperson must return to the depot from location $i$. We have the following DP formulation.\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(N \\setminus \\{ 0 \\}, 0, 0) \\\\ \n",
    "    & V(U, i, t) = \\begin{cases}\n",
    "         \\min\\limits_{j \\in U : t + c_{ij} \\leq b_j} c_{ij} + V(U \\setminus \\{ j \\}, j, \\max \\{ t + c_{ij}, a_j \\})  & \\text{else if } U \\neq \\emptyset \\\\\n",
    "         c_{i0} + V(U, 0, t + c_{i0}) & \\text{else if } U = \\emptyset \\land i \\neq 0 \\\\\n",
    "         0 & \\text{else if } U = \\emptyset \\land i = 0.\n",
    "    \\end{cases}.\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "The earliest arrival time at customer $j$ is $t + c_{ij}$ (assuming the triangle inequality). If $\\exists j \\in U, t + c_{ij} > b_j$, the state does not lead to a solution.\n",
    "\n",
    "$$\n",
    "    V(U, i, t) = \\infty \\text{ if } \\exists j \\in U, t + c_{ij} > b_j.\n",
    "$$\n",
    "\n",
    "When two states $(U, i, t)$ and $(U, i, t')$ have the same set of unvisited customers $U$ and the same location $i$ and $t \\leq t'$, $(U, i, t)$ leads to a better solution. Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, i, t) \\leq V(U, i, t') \\text{ if } t \\leq t'.\n",
    "$$\n",
    "\n",
    "The lowest possible travel time to visit customer $j$ is $\\min_{k \\in N \\setminus \\{ j \\}} c_{kj}$.\n",
    "Because we need to visit all customers in $U$, the total travel time is at least $\\sum_{j \\in U} \\min_{k \\in N \\setminus \\{ j \\}} c_{kj}$. Furthermore, if the current location $i$ is not the depot, we need to visit the depot.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, i, t) \\geq \\sum_{j \\in (U \\cup \\{ 0 \\}) \\setminus \\{ i \\} } \\min_{k \\in N \\setminus \\{ j \\}} c_{kj}.\n",
    "$$\n",
    "\n",
    "Similarly, we need to depart from each customer in $U$ and the current location $i$ if $i$ is not the depot.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, i, t) \\geq \\sum_{j \\in (U \\cup \\{ i \\}) \\setminus \\{ 0 \\} } \\min_{k \\in N \\setminus \\{ j \\}} c_{jk}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0f197b27",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ced536c2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: didppy in /home/kuro/tidel/code/didp-rs/didppy/.venv/lib/python3.10/site-packages (0.7.1)\r\n"
     ]
    }
   ],
   "source": [
    "!pip install didppy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a109fcf6",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "08d61921",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of locations\n",
    "n = 4\n",
    "# Ready time\n",
    "a = [0, 5, 0, 8]\n",
    "# Deadline\n",
    "b = [100, 16, 10, 14]\n",
    "# Travel time\n",
    "c = [\n",
    "    [0, 3, 4, 5],\n",
    "    [3, 0, 5, 4],\n",
    "    [4, 5, 0, 3],\n",
    "    [5, 4, 3, 0],\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2b0fcb3",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e2e3b222",
   "metadata": {},
   "outputs": [],
   "source": [
    "import didppy as dp\n",
    "\n",
    "model = dp.Model()\n",
    "\n",
    "customer = model.add_object_type(number=n)\n",
    "\n",
    "# U\n",
    "unvisited = model.add_set_var(object_type=customer, target=list(range(1, n)))\n",
    "# i\n",
    "location = model.add_element_var(object_type=customer, target=0)\n",
    "# t\n",
    "time = model.add_int_resource_var(target=0, less_is_better=True)\n",
    "\n",
    "travel_time = model.add_int_table(c)\n",
    "\n",
    "for j in range(1, n):\n",
    "    visit = dp.Transition(\n",
    "        name=\"visit {}\".format(j),\n",
    "        cost=travel_time[location, j] + dp.IntExpr.state_cost(),\n",
    "        preconditions=[unvisited.contains(j)],\n",
    "        effects=[\n",
    "            (unvisited, unvisited.remove(j)),\n",
    "            (location, j),\n",
    "            (time, dp.max(time + travel_time[location, j], a[j])),\n",
    "        ],\n",
    "    )\n",
    "    model.add_transition(visit)\n",
    "\n",
    "return_to_depot = dp.Transition(\n",
    "    name=\"return\",\n",
    "    cost=travel_time[location, 0] + dp.IntExpr.state_cost(),\n",
    "    effects=[\n",
    "        (location, 0),\n",
    "        (time, time + travel_time[location, 0]),\n",
    "    ],\n",
    "    preconditions=[unvisited.is_empty(), location != 0],\n",
    ")\n",
    "model.add_transition(return_to_depot)\n",
    "\n",
    "model.add_base_case([unvisited.is_empty(), location == 0])\n",
    "\n",
    "for j in range(1, n):\n",
    "    model.add_state_constr(\n",
    "        ~unvisited.contains(j) | (time + travel_time[location, j] <= b[j])\n",
    "    )\n",
    "\n",
    "min_to = model.add_int_table(\n",
    "    [min(c[k][j] for k in range(n) if k != j) for j in range(n)]\n",
    ")\n",
    "\n",
    "model.add_dual_bound(min_to[unvisited] + (location != 0).if_then_else(min_to[0], 0))\n",
    "\n",
    "min_from = model.add_int_table(\n",
    "    [min(c[j][k] for k in range(n) if k != j) for j in range(n)]\n",
    ")\n",
    "\n",
    "model.add_dual_bound(\n",
    "    min_from[unvisited] + (location != 0).if_then_else(min_from[location], 0)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5684895",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c818fbe6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "visit 2\n",
      "visit 3\n",
      "visit 1\n",
      "return\n",
      "\n",
      "Cost: 14\n"
     ]
    }
   ],
   "source": [
    "solver = dp.CABS(model, quiet=True)\n",
    "solution = solver.search()\n",
    "\n",
    "print(\"Transitions to apply:\")\n",
    "print(\"\")\n",
    "\n",
    "for t in solution.transitions:\n",
    "    print(t.name)\n",
    "\n",
    "print(\"\")\n",
    "print(\"Cost: {}\".format(solution.cost))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": ".venv"
  },
  "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}