distance_optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3299999f-5ee7-4eb1-bd1f-e1b312dcb7a5",
   "metadata": {},
   "source": [
    "# Problem Definition"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0eaa90f9-d60c-46d1-9d13-abb7cef793b6",
   "metadata": {},
   "source": [
    "##### Let the non-negative x-coordinate of door offset, and 14 items as follow:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78df6f88-5e0b-473a-9348-c7e97378e794",
   "metadata": {},
   "source": [
    "$$\\begin{bmatrix} \\text{door offset} \\\\ \\text{Billy} \\\\ \\text{Poang} \\\\ ... \\\\ \\text{Dvala} \\end{bmatrix} = \\begin{bmatrix} X_{0} \\\\ X_{1} \\\\ ... \\\\ X_{14} \\end{bmatrix} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b122131-d996-4333-ae80-6f90a8d70b5d",
   "metadata": {},
   "source": [
    "##### The objective function needs to be optimized is (15 variables):"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c0b7f2e-c643-4982-9988-5a019341f702",
   "metadata": {},
   "source": [
    "$$\\begin{align}\n",
    "\\text{argmin}\n",
    "\\sum \\limits _{order=1} ^{m} \\big(\\sum \\limits _{i=1} ^{n - 1} \\big\\lvert{X_{i+1} - X_{i}}\\big\\rvert + \\big\\lvert{X_{n} - X_{0}}\\big\\rvert \\big)\n",
    "\\end{align}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dae329bc-b4d8-4982-9edf-ac4354a482f3",
   "metadata": {},
   "source": [
    "where:\n",
    "- $X_{i}$: X-coordinate of item $i$. <br>\n",
    "- $X_0$: Door offset <br>\n",
    "- $m$: Total order (in this case study $m = 50$) <br>\n",
    "- $n$: Article list per order<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a5a52acf-0b1f-4b5a-88f8-71a3ad93aecd",
   "metadata": {},
   "source": [
    "##### Constraints. Since all items are placed as closely as possible, the constraints can be described:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ac3801f-2866-407c-9914-3858956aad5b",
   "metadata": {},
   "source": [
    "$\\begin{align}\n",
    "\\frac{1}{2}(w_{i} + w_{j}) \\leq \\big\\lvert{X_i - X_j}\\big\\rvert \\leq W - \\frac{1}{2}(w_{i} + w_{j}) \\newline\n",
    "\\frac{1}{2}w_{i} \\leq X_{i} \\leq W - \\frac{1}{2}w_{i} \\newline\n",
    "\\frac{1}{2}min(w_{i}) \\leq X_{0} \\leq W - \\frac{1}{2}min(w_{i})\n",
    "\\end{align}\n",
    "$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "552afe45-263c-4ae9-ab91-03153062d3ba",
   "metadata": {},
   "source": [
    "where:\n",
    "- $w_{i}, w_{j}$: width of item $i$ $\\neq$ $j$. <br>\n",
    "- $W$: Total width of all 14 items <br>\n",
    "- $min(w_{i})$: Smallest width value <br>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f72c71c6-a837-47fd-92fc-ef5f034064ab",
   "metadata": {},
   "source": [
    "##### Since the result is absolute coordinate, and we want the first item to be at 0. So the output needs to substract the minimal absolute coordinates. Items x-coordinate is:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc2915c1-97c8-46d1-baed-0056c700d614",
   "metadata": {},
   "source": [
    "'Malm': 0.0 <br>\n",
    "'Dvala': 2.98 <br>\n",
    "'Ribba': 3.5 <br>\n",
    " 'Lack': 4.25 <br>\n",
    " 'Ektorp': 7.1 <br>\n",
    " 'Billy' and door_offset: 10.9 <br>\n",
    " 'Fargrik': 12.55 <br>\n",
    " 'Klippan': 14.3 <br>\n",
    " 'Stockholm': 17.15 <br>\n",
    " 'Poang': 18.85 <br>\n",
    " 'Frakta': 19.6 <br>\n",
    " 'Docksta': 21.15 <br>\n",
    " 'Kallax': 23.3 <br>\n",
    " 'Raskog': 24.75 <br>\n",
    " Total Distance  = 1754.1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccf27843-0b9b-417f-8320-363e4e06649d",
   "metadata": {},
   "source": [
    "##### Improvement. The above result is assumed the sequence per order is fixed. But we can actually permute the sequence to optimize the walking distance for each order (>= 2 item in sequence). This can be done at following simple algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5598374d-c38f-4960-b87a-b1c05b63291b",
   "metadata": {},
   "source": [
    "FUNCTION NextItem <br>\n",
    "> Helper Recursive function to find the next nearest item of the given item <br>\n",
    "\n",
    "FOR each order <br>\n",
    "  > IF order has at least 2 items THEN <br>\n",
    "      >> COMPUTE default distance of sequence <br>\n",
    "      >> FOR item on sequence <br>\n",
    "          >>> SET item first in the sequence <br>\n",
    "          >>> CALL NextItem <br>\n",
    "          >>> COMPUTE Distance of sequence <br>\n",
    "      >> REPLACE default sequence by sequence with minimal distance <br>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35357c7b-afae-41ee-8bb2-879543781798",
   "metadata": {},
   "source": [
    "##### order sequence is changed at {1, 2, 5, 6, 9, 10, 12, 21, 22, 26, 27, 29, 32, 34, 37, 38, 45, 46, 48, 50}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65a7d24f-ab98-46ec-a865-8c54f81fa6e5",
   "metadata": {},
   "source": [
    "##### Total distance = 1440.35"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "18b39b24-8c6d-466e-9829-7136cbca5a2d",
   "metadata": {},
   "source": [
    "# CODE IMPLEMENTATION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b3b249d3-ad98-4ae2-8c02-3ea6689040b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functions import load_data, write_solution, total_distance, distance\n",
    "from scipy.optimize import NonlinearConstraint, Bounds, minimize\n",
    "# Load the problem data\n",
    "items, item_widths, orders = load_data(\"data.json\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dba80a8b-1225-49c7-9c47-deb3de5b0acb",
   "metadata": {},
   "source": [
    "##### OBJECTIVE FUNCTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "07b0c113-21ef-4169-93ce-75d5650f3d8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def walking_distance(x: list, \n",
    "                     order: list, \n",
    "                     item_widths: dict, \n",
    "                     items: list) -> float:\n",
    "    items_dict = dict()\n",
    "    for variable_order, name_item in enumerate(items):\n",
    "        items_dict[name_item] = variable_order+1\n",
    "    order_dist = 0\n",
    "    for order in orders:\n",
    "        for i, product in enumerate(order):\n",
    "            if i == 0:\n",
    "                # From the door to the first item\n",
    "                order_dist += abs(x[items_dict[product]] - x[0])\n",
    "            else:\n",
    "                # The following items\n",
    "                prev_product = order[i-1]\n",
    "                order_dist += abs(x[items_dict[product]] - x[items_dict[prev_product]])\n",
    "        # Return to the door\n",
    "        order_dist +=  abs(x[items_dict[product]] - x[0])    \n",
    "    return order_dist"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2bdfe17-c062-479d-9278-04caf2fe789f",
   "metadata": {},
   "source": [
    "##### CONSTRAINTS AND BOUNDARY"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "efbc0a70-a3b0-42cf-82e1-cab7225610f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "items_dict = dict()\n",
    "for variable_order, name_item in enumerate(items):\n",
    "    items_dict[name_item] = variable_order+1\n",
    "total_width = sum(item_widths.values())\n",
    "width_list = list(item_widths.values())\n",
    "# min and max width value\n",
    "min_width = min(width_list)\n",
    "max_width = max(width_list)\n",
    "constraints_list = []\n",
    "# Boundary for door offset first\n",
    "bound_list = [(min_width/2, total_width - min_width/2)] \n",
    "for i in range(1, len(item_widths)+1):\n",
    "    # Pairwise distance between item i, j\n",
    "    for j in range(i+1, len(item_widths)+1):\n",
    "        condition = lambda x, i=i, j=j: abs(x[i] - x[j])\n",
    "        lower_bound = width_list[i-1]/2 + width_list[j-1]/2\n",
    "        upper_bound = total_width - width_list[i-1] / 2 - width_list[j-1] / 2\n",
    "        constraints = NonlinearConstraint(condition, lower_bound, upper_bound)\n",
    "        constraints_list.append(constraints)\n",
    "    bound_i = (width_list[i-1] / 2, total_width - width_list[i-1] / 2)\n",
    "    bound_list.append(bound_i)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d5a5670-eb4c-4dcb-8f3b-abab2fc9eaf6",
   "metadata": {},
   "source": [
    "##### OPTIMIZING"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9989ea92-08ea-45dd-a21d-1b37be48cac4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimization terminated successfully    (Exit mode 0)\n",
      "            Current function value: 1754.1000010886908\n",
      "            Iterations: 15\n",
      "            Function evaluations: 283\n",
      "            Gradient evaluations: 15\n",
      "[13.50000027 13.5        21.45        2.6        25.9        19.75\n",
      "  6.85        9.7        23.75       16.9        15.15        6.1\n",
      " 22.2        27.35        5.575     ]\n"
     ]
    }
   ],
   "source": [
    "# Define x0 is an iterative process\n",
    "x0 = [16.32555298, 13.4999999, 21.4499999, 2.5999999, 25.8999999, 19.7499999,\n",
    "      6.8499999, 9.6999999, 23.7499999, 16.8999999, 15.1499999, 6.0999999,\n",
    "      22.1999999, 27.3499999, 5.5749999]\n",
    "res = minimize(walking_distance, \n",
    "               x0, \n",
    "               args=(orders, item_widths, items), \n",
    "               method=\"SLSQP\",\n",
    "               bounds=tuple(bound_list),\n",
    "               constraints=constraints_list,\n",
    "              options={\"disp\": True,\n",
    "                       \"maxiter\": 1000}\n",
    "              )\n",
    "if res.success:\n",
    "    print(res.x)\n",
    "    door_offset = res.x[0]\n",
    "    coordinator = {}\n",
    "    for i, (item, x) in enumerate(items_dict.items()):\n",
    "        coordinator[item] = res.x[i+1]\n",
    "    best_sequence = dict(sorted(coordinator.items(), key=lambda item: item[1]))\n",
    "    metrics = total_distance(item_sequence=list(best_sequence.keys()),\n",
    "                             door_offset=door_offset,\n",
    "                             item_widths=item_widths,\n",
    "                             orders=orders)\n",
    "else:\n",
    "    raise(\"Not convergence. Try again\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3cb69527-6c67-43d8-a9de-b657889ea031",
   "metadata": {},
   "source": [
    "##### SHIFT THE VALUES SUCH THAT THE FIRST ITEM IS PLACED AT 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "2e378f44-27b7-420e-bbf9-d1dd01d3cdc9",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "item_coordinate\n",
      " {'Malm': 0.0, 'Dvala': 2.9750000000045014, 'Ribba': 3.4999999999958598, 'Lack': 4.249999999993355, 'Ektorp': 7.099999999997147, 'Billy': 10.899999999989912, 'Fargrik': 12.549999999977654, 'Klippan': 14.29999999998146, 'Stockholm': 17.14999999997403, 'Poang': 18.849999999974028, 'Frakta': 19.59999999998141, 'Docksta': 21.149999999973954, 'Kallax': 23.299999999975196, 'Raskog': 24.74999999997148}\n",
      "door_offset 10.900000272823924\n"
     ]
    }
   ],
   "source": [
    "min_coordinate = min(list(best_sequence.values()))\n",
    "item_coordinate = {}\n",
    "for k, v in best_sequence.items():\n",
    "    item_coordinate[k] = v - min_coordinate\n",
    "door_offset = door_offset - min_coordinate\n",
    "print(\"item_coordinate\\n\", item_coordinate)\n",
    "print(\"door_offset\", door_offset)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a37a2ea3-fa1e-4505-a0a7-a560f3bac51a",
   "metadata": {},
   "source": [
    "##### EVALUATE TOTAL DISTANCE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fcc6b309-6d60-45b5-9302-d592ad59bc59",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Score = 1754.1\n"
     ]
    }
   ],
   "source": [
    "walking_distance = total_distance(item_sequence=list(item_coordinate.keys()),\n",
    "                                 door_offset=door_offset,\n",
    "                                 item_widths=item_widths,\n",
    "                                 orders=orders)\n",
    "print(f\"Score = {round(walking_distance, 2)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5efbd1c7-27ea-4527-a154-b84cc42c7dfb",
   "metadata": {},
   "source": [
    "### Now, permute the order sequence to further improve"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2eae5ceb-ecf6-495d-acf1-056505aec196",
   "metadata": {},
   "source": [
    "##### HELPER FUNCTION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "81f84820-2eba-41b1-b9ee-6d21d4be5865",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Distance for a order\n",
    "def order_dist(order: dict, \n",
    "               coordinate: dict,\n",
    "               door_offset: float) -> float:\n",
    "    \n",
    "    dist = 0\n",
    "    for i, product in enumerate(order):\n",
    "        if i==0:\n",
    "            # From the door to the first item\n",
    "            dist += distance(coordinate[order[i]], door_offset)\n",
    "        else:\n",
    "            # Distance Between items\n",
    "            dist += distance(coordinate[order[i]], coordinate[order[i-1]])\n",
    "    # From the last item back to the door\n",
    "    dist += distance(coordinate[order[-1]], door_offset)   \n",
    "    return dist\n",
    "\n",
    "# Find the nearest item (in the sequence) for a given item\n",
    "def next_item(initial_item: list,\n",
    "              rest_item: list,\n",
    "              item_coordinate: dict) -> None:\n",
    "    \n",
    "    if len(rest_item) == 1:\n",
    "        # Finish and append the last item in the list\n",
    "        return initial_item.append(rest_item[0])\n",
    "    # Distance of the rest item respective to the given item (initial_item)\n",
    "    dist_rest_item = {product: abs(item_coordinate[product] - item_coordinate[initial_item[-1]]) \n",
    "                      for product in rest_item}\n",
    "    # Nearest item with minimal distance to the given item (initial_item)\n",
    "    nearest_item = min(dist_rest_item, key=dist_rest_item.get)\n",
    "    # Update initial_item list\n",
    "    initial_item.append(nearest_item)\n",
    "    # Update rest_item list\n",
    "    rest_item = [item for item in order if item not in initial_item]\n",
    "    return next_item(initial_item,\n",
    "                     rest_item,\n",
    "                     item_coordinate)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dea4c2d-e4c3-4dbe-8583-3c2be539d10e",
   "metadata": {},
   "source": [
    "##### START PERMUTATION"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "a927bf4f-c70a-4ff9-8e61-dea156751c57",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Change at 1th order\n",
      "['Stockholm', 'Dvala', 'Poang', 'Malm']: 66.04999999988712 --->\n",
      "['Dvala', 'Malm', 'Stockholm', 'Poang']: 37.699999999948055\n",
      "\n",
      "Change at 2th order\n",
      "['Poang', 'Docksta', 'Dvala', 'Ribba', 'Billy', 'Fargrik']: 39.64999945424637 --->\n",
      "['Dvala', 'Ribba', 'Billy', 'Fargrik', 'Poang', 'Docksta']: 36.3499999999389\n",
      "\n",
      "Change at 5th order\n",
      "['Fargrik', 'Ektorp', 'Frakta', 'Docksta']: 31.399999454261074 --->\n",
      "['Ektorp', 'Fargrik', 'Frakta', 'Docksta']: 28.099999999953614\n",
      "\n",
      "Change at 6th order\n",
      "['Frakta', 'Fargrik', 'Poang', 'Raskog', 'Malm']: 63.59999999995047 --->\n",
      "['Fargrik', 'Poang', 'Frakta', 'Raskog', 'Malm']: 49.49999999994296\n",
      "\n",
      "Change at 9th order\n",
      "['Docksta', 'Frakta', 'Klippan', 'Poang', 'Kallax', 'Dvala']: 54.349999999926375 --->\n",
      "['Dvala', 'Klippan', 'Poang', 'Frakta', 'Docksta', 'Kallax']: 40.649999999941386\n",
      "\n",
      "Change at 10th order\n",
      "['Dvala', 'Billy', 'Kallax', 'Lack', 'Ektorp']: 53.950000545602535 --->\n",
      "['Dvala', 'Lack', 'Ektorp', 'Billy', 'Kallax']: 40.649999999941386\n",
      "\n",
      "Change at 12th order\n",
      "['Stockholm', 'Poang', 'Dvala', 'Kallax', 'Lack', 'Ribba']: 71.34999999989772 --->\n",
      "['Dvala', 'Ribba', 'Lack', 'Stockholm', 'Poang', 'Kallax']: 40.649999999941386\n",
      "\n",
      "Change at 21th order\n",
      "['Poang', 'Ektorp', 'Dvala', 'Malm', 'Klippan', 'Stockholm']: 50.19999945424827 --->\n",
      "['Ektorp', 'Dvala', 'Malm', 'Klippan', 'Stockholm', 'Poang']: 37.699999999948055\n",
      "\n",
      "Change at 22th order\n",
      "['Stockholm', 'Ektorp', 'Dvala', 'Billy', 'Fargrik']: 31.649999454246515 --->\n",
      "['Dvala', 'Ektorp', 'Billy', 'Fargrik', 'Stockholm']: 28.349999999939055\n",
      "\n",
      "Change at 26th order\n",
      "['Klippan', 'Billy', 'Ribba', 'Kallax', 'Frakta', 'Ektorp']: 53.9999999999273 --->\n",
      "['Ribba', 'Ektorp', 'Billy', 'Klippan', 'Frakta', 'Kallax']: 39.59999999995867\n",
      "\n",
      "Change at 27th order\n",
      "['Stockholm', 'Fargrik', 'Raskog', 'Billy', 'Dvala', 'Poang']: 68.6499994542269 --->\n",
      "['Stockholm', 'Poang', 'Raskog', 'Fargrik', 'Billy', 'Dvala']: 43.54999999993396\n",
      "\n",
      "Change at 29th order\n",
      "['Fargrik', 'Ektorp', 'Billy', 'Lack', 'Klippan']: 30.999999454269208 --->\n",
      "['Ektorp', 'Lack', 'Billy', 'Fargrik', 'Klippan']: 20.099999999976212\n",
      "\n",
      "Change at 32th order\n",
      "['Stockholm', 'Klippan', 'Billy', 'Kallax', 'Raskog']: 40.19999945426334 --->\n",
      "['Klippan', 'Stockholm', 'Kallax', 'Raskog', 'Billy']: 27.699999999963133\n",
      "\n",
      "Change at 34th order\n",
      "['Lack', 'Ektorp', 'Billy', 'Malm']: 35.10000054564097 --->\n",
      "['Malm', 'Lack', 'Ektorp', 'Billy']: 21.800000545647844\n",
      "\n",
      "Change at 37th order\n",
      "['Dvala', 'Docksta', 'Lack', 'Stockholm', 'Ektorp']: 69.7500005455538 --->\n",
      "['Dvala', 'Lack', 'Ektorp', 'Stockholm', 'Docksta']: 36.3499999999389\n",
      "\n",
      "Change at 38th order\n",
      "['Malm', 'Fargrik', 'Docksta', 'Billy', 'Kallax']: 67.09999999991847 --->\n",
      "['Malm', 'Billy', 'Fargrik', 'Docksta', 'Kallax']: 46.599999999950384\n",
      "\n",
      "Change at 45th order\n",
      "['Ektorp', 'Poang', 'Ribba', 'Docksta', 'Klippan']: 58.79999999990994 --->\n",
      "['Ektorp', 'Ribba', 'Klippan', 'Poang', 'Docksta']: 35.299999999956185\n",
      "\n",
      "Change at 46th order\n",
      "['Fargrik', 'Billy', 'Raskog', 'Frakta', 'Docksta', 'Kallax']: 38.399999454258165 --->\n",
      "['Billy', 'Fargrik', 'Frakta', 'Docksta', 'Kallax', 'Raskog']: 27.699999999963133\n",
      "\n",
      "Change at 48th order\n",
      "['Lack', 'Poang', 'Ektorp', 'Klippan', 'Billy']: 43.60000054559799 --->\n",
      "['Lack', 'Ektorp', 'Billy', 'Klippan', 'Poang']: 29.199999999961346\n",
      "\n",
      "Change at 50th order\n",
      "['Poang', 'Frakta', 'Kallax', 'Malm', 'Stockholm']: 59.0999994542506 --->\n",
      "['Malm', 'Stockholm', 'Poang', 'Frakta', 'Kallax']: 46.599999999950384\n"
     ]
    }
   ],
   "source": [
    "best_orders = []\n",
    "for k, order in enumerate(orders):\n",
    "    if len(order) == 1:\n",
    "        # Do nothing\n",
    "        best_orders.append(order)\n",
    "        continue\n",
    "    # Store all possible sequence distances\n",
    "    all_distance = {}\n",
    "    default_dist = order_dist(order, \n",
    "                              item_coordinate,\n",
    "                              door_offset)\n",
    "    all_distance[\" \".join(order)] = default_dist\n",
    "    for product in order:\n",
    "        new_order = [product]\n",
    "        rest_item = [item for item in order if item not in new_order]\n",
    "        # find the next nearest item in the sequence\n",
    "        next_item(new_order,\n",
    "                  rest_item,\n",
    "                  item_coordinate)\n",
    "        # Compute new distance for new sequence\n",
    "        new_dist = order_dist(new_order, \n",
    "                              item_coordinate,\n",
    "                              door_offset)\n",
    "        new_key = \" \".join(new_order)\n",
    "        if new_key not in all_distance.keys():\n",
    "            all_distance[new_key] = new_dist\n",
    "    # Find the minimum distance sequence\n",
    "    order_change = min(all_distance, key=all_distance.get)\n",
    "    new_dist = all_distance[order_change]\n",
    "    order_change = order_change.split(\" \")\n",
    "    if new_dist < 0.99 * default_dist:\n",
    "        # Find better sequence\n",
    "        print(f\"\\nChange at {k}th order\")\n",
    "        print(f\"{order}: {default_dist} --->\")\n",
    "        print(f\"{order_change}: {new_dist}\")\n",
    "        best_orders.append(order_change)\n",
    "    else:\n",
    "        # Nothing change\n",
    "        best_orders.append(order)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b66ab514-d0de-4ed3-96ff-cdd1e1c0f43a",
   "metadata": {},
   "source": [
    "##### NEW DISTANCE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "8c8b7795-65d2-430c-bee6-eac71058e2ec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Score = 1440.35\n"
     ]
    }
   ],
   "source": [
    "best_item_sequence = list(item_coordinate.keys())\n",
    "best_door_offset = door_offset\n",
    "new_walking_distance = total_distance(item_sequence=best_item_sequence,\n",
    "                                     door_offset=best_door_offset,\n",
    "                                     item_widths=item_widths,\n",
    "                                     orders=best_orders)\n",
    "print(f\"Score = {round(new_walking_distance, 2)}\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}