{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "93c0a0de",
   "metadata": {},
   "source": [
    "# m-PDTSP\n",
    "\n",
    "In a multi-commodity pick-and-delivery traveling salesperson problem (m-PDTSP), we are given the set of location $N = \\{ 0, ..., n - 1 \\}$ and the set of edges $A \\subseteq N \\times N$.\n",
    "A vehicle with the capacity $q$ starts from $0$, visit all customers $\\{ 1, ..., n - 2 \\}$, and stops at $n - 1$.\n",
    "Visiting customer $j$ from $i$ is possible only if $(i, j) \\in A$ and incurs the travel cost $c_{ij}$.\n",
    "There are commodities $M = \\{ 0, ..., m - 1 \\}$, and commodity $k \\in M$ with weight $w_k$ is picked up at customer $p_k \\in N$ and delivered to customer $d_k \\in N$.\n",
    "We want to find a tour to visit all customers while picking up and delivering all commodities and minimizing the total travel cost.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "When the vehicle visits customer $j$, the net change of the load is\n",
    "\n",
    "$$\n",
    "    \\delta_j = \\sum_{k \\in M : p_k = j} w_k - \\sum_{k \\in M : d_k = j} w_k.\n",
    "$$\n",
    "\n",
    "Because we need to pick up before delivery, the set of customers that must be visited before $j$ is\n",
    "\n",
    "$$\n",
    "    P_j = \\{ p_k \\mid k \\in M : d_k = j \\}.\n",
    "$$\n",
    "\n",
    "Let $U$ be the set of customers that are not visited yet, $i$ be the current location of the vehicle, and $l$ be the current load of the vehicle.\n",
    "Then, the set of customers that can be visited next is\n",
    "\n",
    "$$\n",
    "    R(U, i, l) = \\{ j \\in U \\mid (i, j) \\in A \\land l + \\delta_j \\leq q \\land P_j \\cap U = \\emptyset \\}.\n",
    "$$\n",
    "\n",
    "Let $V(U, i, l)$ be the minimum cost to visit all customers in $U$ from $i$ with the load $l$.\n",
    "We have the following DP model:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(N \\setminus \\{ 0, n - 1 \\}, 0, 0) \\\\\n",
    "    & V(U, i, l) = \\begin{cases}\n",
    "        \\min\\limits_{j \\in R(U, i, l)} c_{ij} + V(U \\setminus \\{ j \\}, j, l + \\delta_j) & \\text{if } U \\neq \\emptyset \\\\\n",
    "        c_{i, n - 1} + V(U, n - 1, l) & \\text{if } U = \\emptyset \\land (i, j) \\in A \\\\\n",
    "        0 & \\text{if } U = \\emptyset \\land i = n - 1.\n",
    "    \\end{cases}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "When two states $(U, i, l)$ and $(U, i, l')$ have the same set of unvisited customers $U$ and the same location $i$, if $l \\leq l'$, $(U, i, l)$ leads to a better solution. Threfore,\n",
    "\n",
    "$$\n",
    "    V(U, i, l) \\leq V(U, i, l') \\text{ if } l \\leq l'.\n",
    "$$\n",
    "\n",
    "The lowest possible travel cost to visit customer $j$ is $\\min_{k \\in N : (k, j) \\in A} c_{kj}$.\n",
    "Because we need to visit all customers in $U$, the total travel cost is at least $\\sum_{j \\in U} \\min_{k \\in N : (k, j) \\in A } c_{kj}$. Furthermore, if the current location $i$ is not $n + 1$, we need to visit $n - 1$.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, i, k, l) \\geq \\sum_{j \\in (U \\cup \\{ n - 1 \\}) \\setminus \\{ i \\} } \\min_{k \\in N : (k, j) \\in A} c_{kj}.\n",
    "$$\n",
    "\n",
    "Similarly, we need to depart from each customer in $U$ and the current location $i$ if $i \\neq n + 1$.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, i, k, l) \\geq \\sum_{j \\in (U \\cup \\{ i \\}) \\setminus \\{ n - 1 \\} } \\min_{k \\in N : (j, k) \\in A} c_{jk}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ec26803",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9ae8059b",
   "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": "9d65c136",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6e77ead1",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of locations\n",
    "n = 5\n",
    "# Edges\n",
    "a = {\n",
    "    (0, 1), (0, 2), (0, 3),\n",
    "    (1, 2), (1, 3), (1, 4),\n",
    "    (2, 1), (2, 3), (2, 4),\n",
    "    (3, 1), (3, 2), (3, 4),\n",
    "}\n",
    "# Number of commodities\n",
    "m = 2\n",
    "# Capacity of the vehicle\n",
    "q = 5\n",
    "# Weights\n",
    "w = [3, 4]\n",
    "# Pick up points\n",
    "p = [3, 2]\n",
    "# Delivery points\n",
    "d = [2, 1]\n",
    "# Travel cost\n",
    "c = [\n",
    "    [0, 3, 4, 5, 0],\n",
    "    [3, 0, 5, 4, 3],\n",
    "    [4, 5, 0, 3, 4],\n",
    "    [5, 4, 3, 0, 5],\n",
    "    [0, 3, 4, 5, 0],\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "911f61d5",
   "metadata": {},
   "source": [
    "## Preprocessing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "01f5453b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Net change\n",
    "delta = [0] * n\n",
    "# Predecessors\n",
    "capital_p = [set() for _ in range(n)]\n",
    "\n",
    "for k in range(m):\n",
    "    delta[p[k]] += w[k]\n",
    "    delta[d[k]] -= w[k]\n",
    "    capital_p[d[k]].add(p[k])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "550c8509",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a194e7da",
   "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 - 1)))\n",
    "# i\n",
    "location = model.add_element_var(object_type=customer, target=0)\n",
    "# l\n",
    "load = model.add_int_resource_var(target=0, less_is_better=True)\n",
    "\n",
    "connected = model.add_bool_table(\n",
    "    [[(i, j) in a for j in range(n)] for i in range(n)]\n",
    ")\n",
    "predecessors = model.add_set_table(capital_p, object_type=customer)\n",
    "distance = model.add_int_table(c)\n",
    "\n",
    "for j in range(1, n):\n",
    "    visit = dp.Transition(\n",
    "        name=\"visit {}\".format(j),\n",
    "        cost=distance[location, j] + dp.IntExpr.state_cost(),\n",
    "        effects=[\n",
    "            (unvisited, unvisited.remove(j)),\n",
    "            (location, j),\n",
    "            (load, load + delta[j]),\n",
    "        ],\n",
    "        preconditions=[\n",
    "            unvisited.contains(j),\n",
    "            connected[location, j],\n",
    "            load + delta[j] <= q,\n",
    "            unvisited.isdisjoint(predecessors[j]),\n",
    "        ],\n",
    "    )\n",
    "    model.add_transition(visit)\n",
    "\n",
    "finish = dp.Transition(\n",
    "    name=\"finish\",\n",
    "    cost=distance[location, n - 1] + dp.IntExpr.state_cost(),\n",
    "    effects=[(location, n - 1)],\n",
    "    preconditions=[unvisited.is_empty(), connected[location, n - 1]],\n",
    ")\n",
    "model.add_transition(finish)\n",
    "\n",
    "model.add_base_case([unvisited.is_empty(), location == n - 1])\n",
    "\n",
    "min_distance_to = model.add_int_table(\n",
    "    [0] + [min(c[k][j] for k in range(n) if (k, j) in a) for j in range(1, n)]\n",
    ")\n",
    "model.add_dual_bound(\n",
    "    min_distance_to[unvisited]\n",
    "    + (location != n - 1).if_then_else(min_distance_to[n - 1], 0)\n",
    ")\n",
    "\n",
    "min_distance_from = model.add_int_table(\n",
    "    [min(c[j][k] for k in range(n) if (j, k) in a) for j in range(n - 1)] + [0]\n",
    ")\n",
    "model.add_dual_bound(min_distance_from[unvisited] + min_distance_from[location])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ca29b85b",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d1d2d947",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "visit 3\n",
      "visit 2\n",
      "visit 1\n",
      "finish\n",
      "\n",
      "Cost: 16\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
}