{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "---------------\n", "\n", "**If any part of this notebook is used in your research, please cite with the reference found in** **[README.md](https://github.com/pysal/spaghetti#bibtex-citation).**\n", "\n", "----------------\n", "\n", "## The Traveling Sales(man)(person) Problem — TSP\n", "### Integrating pysal/spaghetti and [pulp](https://github.com/coin-or/pulp) for optimal routing\n", "\n", "**Author: James D. Gaboardi** ****\n", "\n", "**This notebook provides a use case for:**\n", "\n", "1. Introducing the TSP\n", "2. Declaration of a solution class and model parameters\n", "3. Solving the TSP for an optimal tour" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:22.129349Z", "start_time": "2021-06-28T23:35:22.118110Z" } }, "outputs": [], "source": [ "%config InlineBackend.figure_format = \"retina\"" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:22.169760Z", "start_time": "2021-06-28T23:35:22.132511Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Last updated: 2021-06-28T19:35:22.152252-04:00\n", "\n", "Python implementation: CPython\n", "Python version : 3.9.4\n", "IPython version : 7.24.1\n", "\n", "Compiler : Clang 11.1.0 \n", "OS : Darwin\n", "Release : 20.5.0\n", "Machine : x86_64\n", "Processor : i386\n", "CPU cores : 8\n", "Architecture: 64bit\n", "\n" ] } ], "source": [ "%load_ext watermark\n", "%watermark" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:23.619071Z", "start_time": "2021-06-28T23:35:22.172965Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Watermark: 2.2.0\n", "\n", "spaghetti : 1.6.2\n", "pulp : 2.4\n", "libpysal : 4.4.0\n", "numpy : 1.20.3\n", "json : 2.0.9\n", "matplotlib_scalebar: 0.7.2\n", "matplotlib : 3.4.2\n", "geopandas : 0.9.0\n", "\n" ] } ], "source": [ "import geopandas\n", "from libpysal import examples\n", "import matplotlib\n", "import matplotlib_scalebar\n", "from matplotlib_scalebar.scalebar import ScaleBar\n", "import numpy\n", "import pulp\n", "import spaghetti\n", "\n", "%matplotlib inline\n", "%watermark -w\n", "%watermark -iv" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "-----------------------------\n", "\n", "### 1 Introduction\n", "#### Scenario\n", "Detective George B. Königsberg thought he needed to visit **7** crimes scenes in one area of City X this afternoon in order to collect evidence. However, his lieutenant, Anna Nagurney just told him he needs to double that to **14**. He really wants to wrap up early so he can get home to watch the 2012 mathematical thriller, [Travelling Salesman by Timothy Lanzone](https://en.wikipedia.org/wiki/Travelling_Salesman_(2012_film)), with his cat and dog, Euler and Hamilton. Therefore, he decides on calculating an optimal route so that he can visit all **14** crime scenes in one tour while covering the shortest distance. Det. Königsberg utilizes an integer linear programming formulation of the traveling salesperson problem (TSP) to find his best route.\n", "\n", "--------------------------------\n", "\n", "#### Integer Linear Programming Formulation based on Miller, Tucker, and Zemlin (1960).\n", "\n", "$\\begin{array}\n", "\\displaystyle \\normalsize \\textrm{Minimize} & \\displaystyle \\normalsize \\sum_{0 \\leq i \\\\ i \\neq j}^n \\sum_{j \\leq n \\\\ j \\neq i}^n c_{ij}x_{ij} & & & & \\normalsize (1) \\\\\n", "\\normalsize \\textrm{Subject To} & \\displaystyle \\normalsize \\sum_{i=0}^n x_{ij}=1 & \\normalsize j=1,...,n, & \\normalsize j\\neq i; & &\\normalsize (2)\\\\\n", "& \\displaystyle \\normalsize \\sum_{j=0}^n x_{ij}=1 & \\normalsize i=1,...,n, & \\normalsize i\\neq j; & &\\normalsize (3) \\\\\n", "& \\displaystyle \\normalsize u_i - u_j + p x_{ij} \\leq p - 1 & \\normalsize i=1,...,n, & \\normalsize 1 \\leq i \\neq j \\leq n; & &\\normalsize (4) \\\\\n", "& \\normalsize x_{ij} \\in \\{0,1\\} & \\normalsize i=1,...,n, & \\normalsize j=1,...,n; & &\\normalsize (5)\\\\\n", "& \\normalsize u_{i} \\in \\mathbb{Z} & \\normalsize i=1,...,n. & & &\\normalsize (6)\\\\\n", "\\end{array}$\n", "\n", "$\\begin{array}\n", "\\displaystyle \\normalsize \\textrm{Where} & \\small x_{ij} & \\small = & \\small \\begin{cases}\n", " 1, & \\textrm{if node } i \\textrm{ immediately precedes node } j \\textrm{ in the tour}\\\\\n", " 0, & \\textrm{otherwise}\n", " \\end{cases} &&&&\\\\\n", "& \\small c_{ij} & \\small = & \\small \\textrm{distance matrix between all } i,j \\textrm{ pairs} &&&& \\\\\n", "& \\small n & \\small = & \\small \\textrm{the total number of nodes in the tour} &&&&\\\\\n", "& \\small i & \\small = & \\small \\textrm{each potential origin node} &&&&\\\\\n", "& \\small j & \\small = & \\small \\textrm{each potential destination node} &&&&\\\\\n", "& \\small u_i & \\small = & \\small \\textrm{continuous, non-negative real numbers} &&&&\\\\\n", "& \\small p & \\small = & \\small \\textrm{allowed visits prior to return (}n = p \\textrm{ in this formulation)} &&&&\\\\\n", "\\end{array}$\n", "\n", "\n", "---------------------------------\n", "\n", "**References**\n", "\n", "* **Cummings, N.** (2000) [*A brief History of the Travelling Salesman Problem*](https://www.theorsociety.com/about-or/or-methods/heuristics/a-brief-history-of-the-travelling-salesman-problem/). The Operational Research Society. Accessed: 01/2020.\n", "* **Dantzig, G., Fulkerson, R., and Johnson, S.** (1954) *Solution of a Large-Scale Traveling-Salesman Problem*. Journal of the Operational Research Society of America. 2(4)393-410.\n", "* **Flood, Merrill M.** (1956) *The Traveling-Salesman Problem*. 4(1)61-75.\n", "* **Gass, S. I. and Assad, A. A.** (2005) *An Annotated Timeline of Operations Research: An Informal History*. Springer US.\n", "* **Miller, C. E., Tucker, A. W., and Zemlin, R. A.** (1960) *Integer Programming Formulation of Traveling Salesman Problems*. Journal of Association for Computing Machinery. 7(4)326-329.\n", "* **Miller, H. J. and Shaw, S.-L.** (2001) *Geographic Information Systems for Transportation: Principles and Applications*. New York. Oxford University Press.\n", "* **Nemhauser, G. L. and Wolsey, L. A.** (1988) *Integer and Combinatorial Optimization*. John Wiley & Sons, Inc.\n", "\n", "-------------------------------------\n", "\n", "### 2. A model, data and parameters\n", "#### Solution class" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:23.677748Z", "start_time": "2021-06-28T23:35:23.621338Z" } }, "outputs": [], "source": [ "class MTZ_TSP:\n", " def __init__(self, nodes, cij, xij_tag=\"x_%s,%s\", ui_tag=\"u_%s\", display=True):\n", " \"\"\"Instantiate and solve the Traveling Salesperson Problem (TSP)\n", " based the formulation from Miller, Tucker, and Zemlin (1960).\n", " \n", " Parameters\n", " ----------\n", " nodes : geopandas.GeoSeries\n", " All nodes to be visited in the tour.\n", " cij : numpy.array\n", " All-to-all distance matrix for nodes.\n", " xij_tag : str\n", " Tour decision variable names within the model. Default is\n", " 'x_%s,%s' where %s indicates string formatting.\n", " ui_tag : str\n", " Arbitrary real number decision variable names within the model.\n", " Default is 'u_%s' where %s indicates string formatting.\n", " display : bool\n", " Print out solution results.\n", " \n", " Attributes\n", " ----------\n", " nodes : geopandas.GeoSeries\n", " See description in above.\n", " p : int\n", " The number of nodes in the set. \n", " rp_0n : range\n", " Range of node IDs in nodes from 0,...,p.\n", " rp_1n : range\n", " Range of node IDs in nodes from 1,...,p.\n", " id : str\n", " Column name for nodes.\n", " cij : numpy.array\n", " See description in above.\n", " xij_tag : str\n", " See description in above.\n", " ui_tag : str\n", " See description in above.\n", " tsp : pulp.LpProblem\n", " Integer Linear Programming problem instance.\n", " xij : numpy.array\n", " Binary tour decision variables (pulp.LpVariable).\n", " ui : numpy.array\n", " Continuous arbitrary real number decision variables\n", " (pulp.LpVariable).\n", " cycle_ods : dict\n", " Cycle origin-destination lookup keyed by origin with\n", " destination as the value.\n", " tour_pairs : list\n", " OD pairs comprising each abstract tour arc.\n", " \"\"\"\n", "\n", " # all nodes to be visited and the distance matrix\n", " self.nodes, self.cij = nodes, cij\n", " # number of nodes in the set\n", " self.p = self.nodes.shape[0]\n", " # full and truncated range of nodes (p) in the set\n", " self.rp_0n, self.rp_1n = range(self.p), range(1, self.p)\n", " # column name for node IDs\n", " self.id = self.nodes.name\n", " # alpha tag for decision and dummy variable prefixes\n", " self.xij_tag, self.ui_tag = xij_tag, ui_tag\n", "\n", " # instantiate a model\n", " self.tsp = pulp.LpProblem(\"MTZ_TSP\", pulp.LpMinimize)\n", " # create and set the tour decision variables\n", " self.tour_dvs()\n", " # create and set the arbitraty real number decision variables\n", " self.arn_dvs()\n", " # set the objective function\n", " self.objective_func()\n", " # node entry constraints\n", " self.entry_exit_constrs(entry=True)\n", " # node exit constraints\n", " self.entry_exit_constrs(entry=False)\n", " # subtour prevention constraints\n", " self.prevent_subtours()\n", " # solve\n", " self.tsp.solve()\n", " # origin-destination lookup\n", " self.get_decisions(display=display)\n", " # extract the sequence of nodes to construct the optimal tour\n", " self.construct_tour()\n", "\n", " def tour_dvs(self):\n", " \"\"\"Create the tour decision variables - eq (5).\"\"\"\n", "\n", " def _name(_x):\n", " \"\"\"Helper for naming variables\"\"\"\n", " return self.nodes[_x].split(\"_\")[-1]\n", "\n", " xij = numpy.array(\n", " [\n", " [\n", " pulp.LpVariable(self.xij_tag % (_name(i), _name(j)), cat=\"Binary\")\n", " for j in self.rp_0n\n", " ]\n", " for i in self.rp_0n\n", " ]\n", " )\n", "\n", " self.xij = xij\n", "\n", " def arn_dvs(self):\n", " \"\"\"Create arbitrary real number decision variables - eq (6).\"\"\"\n", " ui = numpy.array(\n", " [pulp.LpVariable(self.ui_tag % (i), lowBound=0) for i in self.rp_0n]\n", " )\n", "\n", " self.ui = ui\n", "\n", " def objective_func(self):\n", " \"\"\"Add the objective function - eq (1).\"\"\"\n", " self.tsp += pulp.lpSum(\n", " [\n", " self.cij[i, j] * self.xij[i, j]\n", " for i in self.rp_0n\n", " for j in self.rp_0n\n", " if i != j\n", " ]\n", " )\n", "\n", " def entry_exit_constrs(self, entry=True):\n", " \"\"\"Add entry and exit constraints - eq (2) and (3).\"\"\"\n", " if entry:\n", " for i in self.rp_0n:\n", " self.tsp += (\n", " pulp.lpSum([self.xij[i, j] for j in self.rp_0n if i != j]) == 1\n", " )\n", " # exit constraints\n", " else:\n", " for j in self.rp_0n:\n", " self.tsp += (\n", " pulp.lpSum([self.xij[i, j] for i in self.rp_0n if i != j]) == 1\n", " )\n", "\n", " def prevent_subtours(self):\n", " \"\"\"Add subtour prevention constraints - eq (4).\"\"\"\n", " for i in self.rp_1n:\n", " for j in self.rp_1n:\n", " if i != j:\n", " self.tsp += (\n", " self.ui[i] - self.ui[j] + self.p * self.xij[i, j] <= self.p - 1\n", " )\n", "\n", " def get_decisions(self, display=True):\n", " \"\"\"Fetch the selected decision variables.\"\"\"\n", " cycle_ods = {}\n", " for var in self.tsp.variables():\n", " if var.name.startswith(self.ui_tag[0]):\n", " continue\n", " if var.varValue > 0:\n", " if display:\n", " print(\"%s: %s\" % (var.name, var.varValue))\n", " od = var.name.split(\"_\")[-1]\n", " o, d = [int(tf) for tf in od.split(\",\")]\n", " cycle_ods[o] = d\n", " if display:\n", " print(\"Status: %s\" % pulp.LpStatus[self.tsp.status])\n", "\n", " self.cycle_ods = cycle_ods\n", "\n", " def construct_tour(self):\n", " \"\"\"Construct the tour.\"\"\"\n", " tour_pairs = []\n", " for origin in self.rp_0n:\n", " tour_pairs.append([])\n", " try:\n", " tour_pairs[origin].append(next_origin)\n", " next_origin = self.cycle_ods[next_origin]\n", " tour_pairs[origin].append(next_origin)\n", " except NameError:\n", " next_origin = self.cycle_ods[origin]\n", " tour_pairs[origin].append(origin)\n", " tour_pairs[origin].append(next_origin)\n", "\n", " tour_pairs = {idx: sorted(tp) for idx, tp in enumerate(tour_pairs)}\n", " self.tour_pairs = tour_pairs\n", "\n", " def extract_tour(self, paths, id_col, leg_label=\"leg\"):\n", " \"\"\"Extract the tour (the legs in the journey) as a \n", " geopandas.GeoDataFrame of shapely.geometry.LineString objects.\n", " \n", " Parameters\n", " ----------\n", " paths : geopandas.GeoDataFrame\n", " Shortest-path routes between all observations.\n", " id_col : str\n", " ID column name.\n", " leg_label : str\n", " Column name for the tour sequence. Default is 'leg'.\n", " \n", " Returns\n", " -------\n", " tour : geopandas.GeoDataFrame\n", " Optimal tour of self.nodes sequenced by leg_label that\n", " retains the original index of paths.\n", " \"\"\"\n", "\n", " paths[leg_label] = int\n", " # set label of journey leg for each OD pair.\n", " for leg, tp in self.tour_pairs.items():\n", " paths.loc[paths[id_col] == tuple(tp), leg_label] = leg\n", "\n", " # extract only paths in the tour\n", " tour = paths[paths[leg_label] != int].copy()\n", " tour.sort_values(by=[leg_label], inplace=True)\n", "\n", " return tour" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Streets" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:24.028051Z", "start_time": "2021-06-28T23:35:23.679995Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
IDLengthgeometry
01.0244.116229LINESTRING (222007.131 267348.711, 222007.159 ...
12.0375.974828LINESTRING (222006.951 267549.880, 222007.131 ...
23.0400.353405LINESTRING (221420.428 267804.889, 221411.402 ...
34.0660.000000LINESTRING (220875.116 268353.388, 220803.948 ...
45.0660.000000LINESTRING (220802.426 268398.824, 220917.000 ...
\n", "
" ], "text/plain": [ " ID Length geometry\n", "0 1.0 244.116229 LINESTRING (222007.131 267348.711, 222007.159 ...\n", "1 2.0 375.974828 LINESTRING (222006.951 267549.880, 222007.131 ...\n", "2 3.0 400.353405 LINESTRING (221420.428 267804.889, 221411.402 ...\n", "3 4.0 660.000000 LINESTRING (220875.116 268353.388, 220803.948 ...\n", "4 5.0 660.000000 LINESTRING (220802.426 268398.824, 220917.000 ..." ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "streets = geopandas.read_file(examples.get_path(\"streets.shp\"))\n", "streets.crs = \"esri:102649\"\n", "streets = streets.to_crs(\"epsg:2762\")\n", "streets.head()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Crimes" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:24.353681Z", "start_time": "2021-06-28T23:35:24.031618Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
POLYID2POLYIDgeometry
011POINT (221868.432 266920.497)
122POINT (220923.246 266933.298)
233POINT (221709.326 266960.731)
344POINT (221900.131 266962.255)
455POINT (221750.169 266962.864)
\n", "
" ], "text/plain": [ " POLYID2 POLYID geometry\n", "0 1 1 POINT (221868.432 266920.497)\n", "1 2 2 POINT (220923.246 266933.298)\n", "2 3 3 POINT (221709.326 266960.731)\n", "3 4 4 POINT (221900.131 266962.255)\n", "4 5 5 POINT (221750.169 266962.864)" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "all_crimes = geopandas.read_file(examples.get_path(\"crimes.shp\"))\n", "all_crimes.crs = \"esri:102649\"\n", "all_crimes = all_crimes.to_crs(\"epsg:2762\")\n", "all_crimes.head()" ] }, { "cell_type": "markdown", "metadata": { "ExecuteTime": { "end_time": "2020-01-21T04:22:00.659016Z", "start_time": "2020-01-21T04:22:00.655646Z" } }, "source": [ "#### Detective Königsberg's cases" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:24.384179Z", "start_time": "2021-06-28T23:35:24.356736Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
POLYID2POLYIDgeometry
566POINT (221652.328 266963.169)
111212POINT (220775.113 266968.350)
484949POINT (220962.565 267281.381)
626363POINT (220772.979 267387.147)
888989POINT (220797.363 267546.558)
114115115POINT (221501.452 267698.654)
120121121POINT (220474.580 267731.267)
132133133POINT (221677.932 267762.053)
169170170POINT (221154.590 267920.549)
184185185POINT (221853.497 268049.786)
211212212POINT (220775.723 268150.369)
234235235POINT (220473.361 268198.223)
269270270POINT (220515.423 268478.944)
279280280POINT (222084.231 268591.723)
\n", "
" ], "text/plain": [ " POLYID2 POLYID geometry\n", "5 6 6 POINT (221652.328 266963.169)\n", "11 12 12 POINT (220775.113 266968.350)\n", "48 49 49 POINT (220962.565 267281.381)\n", "62 63 63 POINT (220772.979 267387.147)\n", "88 89 89 POINT (220797.363 267546.558)\n", "114 115 115 POINT (221501.452 267698.654)\n", "120 121 121 POINT (220474.580 267731.267)\n", "132 133 133 POINT (221677.932 267762.053)\n", "169 170 170 POINT (221154.590 267920.549)\n", "184 185 185 POINT (221853.497 268049.786)\n", "211 212 212 POINT (220775.723 268150.369)\n", "234 235 235 POINT (220473.361 268198.223)\n", "269 270 270 POINT (220515.423 268478.944)\n", "279 280 280 POINT (222084.231 268591.723)" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "numpy.random.seed(1960)\n", "koenigsberg_cases = 7 * 2\n", "subset_idx = numpy.random.choice(all_crimes.index, koenigsberg_cases, replace=False)\n", "crimes_scenes = all_crimes[all_crimes.index.isin(subset_idx)].copy()\n", "crimes_scenes" ] }, { "cell_type": "markdown", "metadata": { "ExecuteTime": { "end_time": "2020-01-21T04:39:16.711389Z", "start_time": "2020-01-21T04:39:16.702359Z" } }, "source": [ "#### Instantiate a network object" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:24.643613Z", "start_time": "2021-06-28T23:35:24.386119Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idgeometrycomp_label
00POINT (222007.131 267348.711)0
11POINT (222007.159 267317.431)0
22POINT (222006.951 267549.880)0
33POINT (221420.428 267804.889)0
44POINT (221411.402 267921.993)0
\n", "
" ], "text/plain": [ " id geometry comp_label\n", "0 0 POINT (222007.131 267348.711) 0\n", "1 1 POINT (222007.159 267317.431) 0\n", "2 2 POINT (222006.951 267549.880) 0\n", "3 3 POINT (221420.428 267804.889) 0\n", "4 4 POINT (221411.402 267921.993) 0" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ntw = spaghetti.Network(in_data=streets)\n", "vertices, arcs = spaghetti.element_as_gdf(ntw, vertices=True, arcs=True)\n", "vertices.head()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2021-06-28T23:35:24.655357Z", "start_time": "2021-06-28T23:35:24.645124Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
idgeometrycomp_label
0(0, 1)LINESTRING (222007.131 267348.711, 222007.159 ...0
1(0, 2)LINESTRING (222007.131 267348.711, 222006.951 ...0
2(1, 110)LINESTRING (222007.159 267317.431, 222081.565 ...0
3(1, 127)LINESTRING (222007.159 267317.431, 221805.991 ...0
4(1, 213)LINESTRING (222007.159 267317.431, 222007.338 ...0
\n", "