notebooks/routing/python/cpdptw_intra-factory_transport.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2cb694f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "from cuopt import routing\n",
    "from cuopt import distance_engine\n",
    "import cudf\n",
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9326712e",
   "metadata": {},
   "source": [
    "# Intra-factory Transport\n",
    "## Capacitated Pickup and Delivery Problem with Time Windows"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "382afbd9",
   "metadata": {},
   "source": [
    "Factory automation allows companies to raise the quality and consistency of manufacturing processes while also allowing human workers to focus on safer, less repetitive tasks that have higher cognitive and creative demands.\n",
    "\n",
    "In this scenario we have a set of intra-factory transport orders to move products at various stages in the assembly process from one processing station to another. Each station represents a particular type of manufacturing process and a given product may need to visit each processing station more than once. Multiple autonomous mobile robots (AMRs) with a fixed capacity will execute pickup and delivery orders between target locations, all with corresponding time_windows."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3bc4ad4",
   "metadata": {},
   "source": [
    "### Problem Details:\n",
    "- 4 Locations each with an associated demand\n",
    "    - 1 Start Location for AMRs\n",
    "\n",
    "    - 3 Process Stations\n",
    "\n",
    "- 3 AMRs with associated capacity"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6090764",
   "metadata": {},
   "source": [
    "- Hours of operation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5d12f05d",
   "metadata": {},
   "outputs": [],
   "source": [
    "factory_open_time = 0\n",
    "factory_close_time = 100"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e67a05ed",
   "metadata": {},
   "source": [
    "![waypoint_graph.png not found](./notebook_utils/images/waypoint_graph.png \"Waypoint Graph\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d90ba90d",
   "metadata": {},
   "source": [
    "### Waypoint Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6febdb57",
   "metadata": {},
   "source": [
    "#### Compressed Sparse Row (CSR) representation of above weighted waypoint graph.\n",
    "For details on the CSR encoding of the above graph see the [cost_matrix_creation.ipynb](cost_matrix_creation.ipynb) notebook."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c824c99",
   "metadata": {},
   "outputs": [],
   "source": [
    "offsets = np.array([0, 1, 3, 7, 9, 11, 13, 15, 17, 20, 22])\n",
    "edges =   np.array([2, 2, 4, 0, 1, 3, 5, 2, 6, 1, 7, 2, 8, 3, 9, 4, 8, 5, 7, 9, 6, 8])\n",
    "weights = np.array([2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbfcfa33",
   "metadata": {},
   "source": [
    "#### Select specific waypoints in the graph as target locations\n",
    "In this case we would like the AMRs to begin from waypoint 0 and service locations 4, 5, and 6."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e08f664",
   "metadata": {},
   "outputs": [],
   "source": [
    "target_locations = np.array([0, 4, 5, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7af883ad",
   "metadata": {},
   "source": [
    "### Cost Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "52bdc1d0",
   "metadata": {},
   "source": [
    "#### Use cuOpt to calculate the corresponding cost matrix\n",
    "Here we will be using a single cost matrix representing time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9975bf1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "waypoint_graph = distance_engine.WaypointMatrix(\n",
    "    offsets,\n",
    "    edges,\n",
    "    weights\n",
    ")\n",
    "time_matrix = waypoint_graph.compute_cost_matrix(target_locations)\n",
    "target_map = {v:k for k, v in enumerate(target_locations)}\n",
    "index_map = {k:v for k, v in enumerate(target_locations)}\n",
    "print(f\"Waypoint graph node to time matrix index mapping \\n{target_map}\\n\")\n",
    "print(time_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ed911ff",
   "metadata": {},
   "source": [
    "### Transport Orders"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4265c03a",
   "metadata": {},
   "source": [
    "Setup Transport Order Data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7d7536d",
   "metadata": {},
   "source": [
    "The transport orders dictate the movement of parts from one area of the factory to another.  In this example nodes 4, 5, and 6 represent the processing stations that parts must travel between and deliveries to node 0 represent the movement of parts off the factory floor."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "72b715c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "transport_order_data = cudf.DataFrame({\n",
    "    \"pickup_location\":       [4,  5,  6,  6,  5,  4],\n",
    "    \"delivery_location\":     [5,  6,  0,  5,  4,  0],\n",
    "    \"order_demand\":          [1,  1,  1,  1,  1,  1],\n",
    "    \"earliest_pickup\":       [0,  0,  0,  0,  0,  0],\n",
    "    \"latest_pickup\":         [10, 20, 30, 10, 20, 30],\n",
    "    \"pickup_service_time\":   [2,  2,  2,  2,  2,  2],\n",
    "    \"earliest_delivery\":     [0,  0,  0,  0,  0,  0],\n",
    "    \"latest_delivery\":       [45, 45, 45, 45, 45, 45],\n",
    "    \"delivery_serivice_time\":[2,  2,  2,  2,  2,  2]\n",
    "})\n",
    "transport_order_data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f2aaf28a",
   "metadata": {},
   "source": [
    "### AMR Data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a4e5e749",
   "metadata": {},
   "source": [
    "Set up AMR fleet data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e17e899",
   "metadata": {},
   "outputs": [],
   "source": [
    "n_robots = 2\n",
    "robot_data = {\n",
    "    \"robot_ids\": [i for i in range(n_robots)],\n",
    "    \"carrying_capacity\":[2, 2]\n",
    "}\n",
    "robot_data = cudf.DataFrame(robot_data).set_index('robot_ids')\n",
    "robot_data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31db9053",
   "metadata": {},
   "source": [
    "### cuOpt DataModel View"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "731fdcbe",
   "metadata": {},
   "source": [
    "Setup the routing.DataModel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2e765325",
   "metadata": {},
   "outputs": [],
   "source": [
    "n_locations = len(time_matrix)\n",
    "n_vehicles = len(robot_data)\n",
    "\n",
    "# a pickup order and a delivery order are distinct with additional pad for the depot with 0 demand\n",
    "n_orders = len(transport_order_data) * 2\n",
    "\n",
    "data_model = routing.DataModel(n_locations, n_vehicles, n_orders)\n",
    "data_model.add_cost_matrix(time_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f8f10e8",
   "metadata": {},
   "source": [
    "\n",
    "#### Set the per order demand\n",
    "\n",
    "From the perspective of the cuOpt solver_settings, each distinct transaction (pickup order or delivery order) are treated separately with demand for pickup denoted as positive and the corresponding delivery treated as negative demand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c936b137",
   "metadata": {},
   "outputs": [],
   "source": [
    "# This is the number of parts that needs to be moved\n",
    "raw_demand = transport_order_data[\"order_demand\"]\n",
    "\n",
    "# When dropping off parts we want to remove one unit of demand from the robot\n",
    "drop_off_demand = raw_demand * -1\n",
    "\n",
    "# Create pickup and delivery demand\n",
    "order_demand = cudf.concat([raw_demand, drop_off_demand], ignore_index=True)\n",
    "\n",
    "order_demand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "87c2d9f8",
   "metadata": {},
   "outputs": [],
   "source": [
    "# add the capacity dimension\n",
    "data_model.add_capacity_dimension(\"demand\", order_demand, robot_data['carrying_capacity'])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "48706e31",
   "metadata": {},
   "source": [
    "#### Setting Order locations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "281bcd93",
   "metadata": {},
   "source": [
    "set the order locations and pickup and delivery pairs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1d325f4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "pickup_order_locations = cudf.Series([target_map[loc] for loc in transport_order_data['pickup_location'].to_arrow().to_pylist()])\n",
    "delivery_order_locations = cudf.Series([target_map[loc] for loc in transport_order_data['delivery_location'].to_arrow().to_pylist()])\n",
    "order_locations = cudf.concat([pickup_order_locations, delivery_order_locations], ignore_index=True)\n",
    "\n",
    "print(order_locations)\n",
    "\n",
    "# add order locations\n",
    "data_model.set_order_locations(order_locations)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9389060b",
   "metadata": {},
   "source": [
    "#### Mapping pickups to deliveries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "064978ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "# IMPORTANT NOTE : pickup and delivery pairs are indexed into the order locations array.\n",
    "npair_orders = int(len(order_locations)/2)\n",
    "pickup_orders = cudf.Series([i for i in range(npair_orders)])\n",
    "delivery_orders = cudf.Series([i + npair_orders for i in range(npair_orders)])\n",
    "# add pickup and delivery pairs.\n",
    "data_model.set_pickup_delivery_pairs(pickup_orders, delivery_orders)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8b35777",
   "metadata": {},
   "source": [
    "#### Precedence Constraints"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c4b288e",
   "metadata": {},
   "source": [
    "We have decided to model the deliveries to index 0 as removing items from the factory floor.  In some cases it may be necessary which operations are complete prior to exiting.  Here we set precedence constraints on specific deliveries which must occur before parts can exit the factory floor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "116ce6ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "data_model.add_order_precedence(8, cudf.Series([6,7]))\n",
    "data_model.add_order_precedence(11, cudf.Series([9,10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef21d42d",
   "metadata": {},
   "source": [
    "#### Time Windows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3f328e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# create earliest times\n",
    "vehicle_earliest_time = cudf.Series([factory_open_time] * n_vehicles)\n",
    "order_time_window_earliest = cudf.concat([transport_order_data[\"earliest_pickup\"], transport_order_data[\"earliest_delivery\"]], ignore_index=True)\n",
    "\n",
    "# create latest times\n",
    "vehicle_latest_time = cudf.Series([factory_close_time] * n_vehicles)\n",
    "order_time_window_latest = cudf.concat([transport_order_data[\"latest_pickup\"], transport_order_data[\"latest_delivery\"]], ignore_index=True)\n",
    "\n",
    "# create service times\n",
    "order_service_time = cudf.concat([transport_order_data[\"pickup_service_time\"], transport_order_data[\"delivery_serivice_time\"]], ignore_index=True)\n",
    "\n",
    "# add time window constraints\n",
    "data_model.set_order_time_windows(order_time_window_earliest, order_time_window_latest)\n",
    "data_model.set_order_service_times(order_service_time)\n",
    "data_model.set_vehicle_time_windows(vehicle_earliest_time, vehicle_latest_time)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0d06888",
   "metadata": {},
   "source": [
    "### CuOpt SolverSettings"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3e08235",
   "metadata": {},
   "source": [
    "Set up routing.SolverSettings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a6babc11",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "solver_settings = routing.SolverSettings()\n",
    "\n",
    "# set number of climbers that will try to search for an optimal routes in parallel\n",
    "solver_settings.set_number_of_climbers(128)\n",
    "\n",
    "# solver_settings will run for given time limit.  Larger and/or more complex problems may require more time.\n",
    "solver_settings.set_time_limit(0.05)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "854e9519",
   "metadata": {},
   "source": [
    "### Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28a05ace",
   "metadata": {},
   "outputs": [],
   "source": [
    "routing_solution = routing.Solve(data_model, solver_settings)\n",
    "if routing_solution.get_status() == 0:\n",
    "    print(\"Cost for the routing in time: \", routing_solution.final_cost)\n",
    "    print(\"Vehicle count to complete routing: \", routing_solution.vehicle_count)\n",
    "    print(routing_solution.route)\n",
    "else:\n",
    "    print(\"NVIDIA cuOpt Failed to find a solution with status : \", routing_solution.get_status())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f6c5067",
   "metadata": {},
   "source": [
    "#### Converting solution to waypoint graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1dbba138",
   "metadata": {},
   "source": [
    "Because we maintained the mapping between cost matrix indices and locations in the waypoint graph we can now convert our solution to reference the nodes in the waypoint graph corresponding to the selected target locations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e0d98709",
   "metadata": {},
   "outputs": [],
   "source": [
    "target_loc_route = [index_map[loc] for loc in routing_solution.route['location'].to_arrow().to_pylist()]\n",
    "routing_solution.route['order_array_index'] = routing_solution.route['route']\n",
    "routing_solution.route['route'] = target_loc_route\n",
    "print(routing_solution.route)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bba4accd",
   "metadata": {},
   "source": [
    "#### Convert routes from target location based routes to waypoint level routes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c13cfbf3",
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "unique_robot_ids = routing_solution.route['truck_id'].unique()\n",
    "all_routes = routing_solution.get_route()\n",
    "\n",
    "for robot in unique_robot_ids.to_arrow().to_pylist():\n",
    "    route = all_routes[all_routes['truck_id']==robot]\n",
    "    unique_target_locs = all_routes[all_routes['truck_id']==robot]['route'].unique().to_numpy()\n",
    "    \n",
    "    waypoint_route = waypoint_graph.compute_waypoint_sequence(unique_target_locs, route)\n",
    "    print(f\"Target location level route for robot {robot}:\\n{all_routes[all_routes['truck_id']==robot]['route']}\\n\\n\")\n",
    "    print(f\"Waypoint level route for robot {robot}:\\n{waypoint_route}\\n\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cb94aa7",
   "metadata": {},
   "source": [
    "_____\n",
    "\n",
    "#### SPDX-FileCopyrightText: Copyright (c) 2022 NVIDIA CORPORATION & AFFILIATES. All rights reserved.\n",
    "\n",
    "#### SPDX-License-Identifier: MIT\n",
    "\n",
    "Permission is hereby granted, free of charge, to any person obtaining a\n",
    "copy of this software and associated documentation files (the \"Software\"),\n",
    "to deal in the Software without restriction, including without limitation\n",
    "the rights to use, copy, modify, merge, publish, distribute, sublicense,\n",
    "and/or sell copies of the Software, and to permit persons to whom the\n",
    "Software is furnished to do so, subject to the following conditions:\n",
    "The above copyright notice and this permission notice shall be included in\n",
    "all copies or substantial portions of the Software.\n",
    "\n",
    "THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\n",
    "IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\n",
    "FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL\n",
    "THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\n",
    "LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING\n",
    "FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER\n",
    "DEALINGS IN THE SOFTWARE.\n",
    "\n",
    "---"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "0f29e496949dc4ef652a1afa2d601ce2913fc84758b70efb060a954cb0e2d83f"
  },
  "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.9.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}