{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "df68dd27",
   "metadata": {},
   "source": [
    "# CVRP\n",
    "\n",
    "In a capacitated vehicle routing problem (CVRP), we are given a set of locations $N = \\{ 0, ..., n-1 \\}$ where $0$ is the depot and $\\{ 1, ..., n-1 \\}$ are customers.\n",
    "We need to pick up commodities from the customers using $m$ vehicles with capacity $q$, which start from and return to the depot.\n",
    "By visiting customer $i$, the load of vehicle increases by weight $d_i$.\n",
    "Visiting customer $j$ from $i$ incurs the travel cost $c_{ij}$.\n",
    "The objective is to find a set of tours for the vehicles that visit all customers while minimizing the total travel cost.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "Consider constructing tours for the vehicles one by one.\n",
    "Let $k$ be the number of used vehicles (including the current vehicle), $U$ be the set of unvisited customers, $i$ be the current location of the vehicle, and $l$ be the load of the vehicle.\n",
    "Customer $j$ can be visited by the current vehicle if $l + d_i \\leq q$.\n",
    "Otherwise, we need to return to the depot and use a new vehicle to visit $j$, which is possible only if $k < m$.\n",
    "Let $V(U, i, l, k)$ be the minimum cost to visit customers $U$ from $i$ with the load $l$ using $m - k + 1$ vehicles.\n",
    "We have the following DP model:\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(N \\setminus \\{ 0 \\}, 0, 0, 1) \\\\\n",
    "    & V(U, i, l, k) = \\begin{cases}\n",
    "        \\min\\left\\{ \\min\\limits_{j \\in U : l + d_i \\leq q} c_{ij} + V(U \\setminus \\{ j \\}, j, l + d_i, k), \\min\\limits_{j \\in U} c_{i0} + c_{0j} + V(U \\setminus \\{ j \\}, j, d_i, k + 1) \\right\\} & \\text{if } k < m \\\\\n",
    "        \\min\\limits_{j \\in U : l + d_i \\leq q} c_{ij} + V(U \\setminus \\{ j \\}, j, l + d_i, k) & \\text{if } k = m \\\\\n",
    "        c_{i0} + V(U, 0, k, l) & \\text{if } U = \\emptyset \\land i \\neq 0 \\\\\n",
    "        0 & \\text{if } U = \\emptyset \\land i = 0.\n",
    "    \\end{cases}\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "When two states $(U, i, l, k)$ and $(U, i, l', k')$ have the same set of unvisited customers $U$ and the same location $i$, if $l \\leq l'$ and $k \\leq k'$, $(U, i, l, k)$ leads to a better solution. Threfore,\n",
    "\n",
    "$$\n",
    "    V(U, i, l, k) \\leq V(U, i, l', k') \\text{ if } l \\leq l' \\land k \\leq k'.\n",
    "$$\n",
    "\n",
    "The sum of the capacity of the remaining vehicles, $q - l + (m - k) q$, must be greater than or equal to the sum of the weights of the remaining commodities, $\\sum_{j \\in U} d_j$.\n",
    "Otherwise, the state does not lead to a solution.\n",
    "Therefore,\n",
    "\n",
    "$$\n",
    "    V(U, i, l, k) = \\infty \\text{ if } (m - k + 1)q - l < \\sum_{j \\in U} d_j.\n",
    "$$\n",
    "\n",
    "The lowest possible travel cost 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 cost 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, k, l) \\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, k, l) \\geq \\sum_{j \\in (U \\cup \\{ i \\}) \\setminus \\{ 0 \\} } \\min_{k \\in N \\setminus \\{ j \\}} c_{jk}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab126f9b",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "82147f5f",
   "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": "f227e9d0",
   "metadata": {},
   "source": [
    "# Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9ed2c425",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of locations\n",
    "n = 4\n",
    "# Number of vehicles\n",
    "m = 2\n",
    "# Capacity of a vehicle\n",
    "q = 5\n",
    "# Weights\n",
    "d = [0, 2, 3, 3]\n",
    "# Travel cost\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": "33c9f1f2",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "76a7e2d4",
   "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",
    "# l\n",
    "load = model.add_int_resource_var(target=0, less_is_better=True)\n",
    "# k\n",
    "vehicles = model.add_int_resource_var(target=1, less_is_better=True)\n",
    "\n",
    "weight = model.add_int_table(d)\n",
    "distance = model.add_int_table(c)\n",
    "\n",
    "model.add_base_case([unvisited.is_empty(), location == 0])\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 + weight[j]),\n",
    "        ],\n",
    "        preconditions=[unvisited.contains(j), load + weight[j] <= q],\n",
    "    )\n",
    "    model.add_transition(visit)\n",
    "\n",
    "for j in range(1, n):\n",
    "    visit_via_depot = dp.Transition(\n",
    "        name=\"visit {} with a new vehicle\".format(j),\n",
    "        cost=distance[location, 0] + distance[0, j] + dp.IntExpr.state_cost(),\n",
    "        effects=[\n",
    "            (unvisited, unvisited.remove(j)),\n",
    "            (location, j),\n",
    "            (load, weight[j]),\n",
    "            (vehicles, vehicles + 1),\n",
    "        ],\n",
    "        preconditions=[unvisited.contains(j), vehicles < m],\n",
    "    )\n",
    "    model.add_transition(visit_via_depot)\n",
    "\n",
    "return_to_depot = dp.Transition(\n",
    "    name=\"return\",\n",
    "    cost=distance[location, 0] + dp.IntExpr.state_cost(),\n",
    "    effects=[(location, 0)],\n",
    "    preconditions=[unvisited.is_empty(), location != 0],\n",
    ")\n",
    "model.add_transition(return_to_depot)\n",
    "\n",
    "model.add_state_constr((m - vehicles + 1) * q - load >= weight[unvisited])\n",
    "\n",
    "min_distance_to = model.add_int_table(\n",
    "    [min(c[k][j] for k in range(n) if j != k) for j in range(n)]\n",
    ")\n",
    "model.add_dual_bound(\n",
    "    min_distance_to[unvisited] + (location != 0).if_then_else(min_distance_to[0], 0)\n",
    ")\n",
    "\n",
    "min_distance_from = model.add_int_table(\n",
    "    [min(c[j][k] for k in range(n) if j != k) for j in range(n)]\n",
    ")\n",
    "model.add_dual_bound(\n",
    "    min_distance_from[unvisited]\n",
    "    + (location != 0).if_then_else(min_distance_from[location], 0)\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b5ce9dc",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5036843a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "visit 1\n",
      "visit 3\n",
      "visit 2 with a new vehicle\n",
      "return\n",
      "\n",
      "Cost: 20\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
}