diff options
Diffstat (limited to 'test')
| -rw-r--r-- | test/mitsuo.ipynb | 771 |
1 files changed, 771 insertions, 0 deletions
diff --git a/test/mitsuo.ipynb b/test/mitsuo.ipynb new file mode 100644 index 0000000..653663c --- /dev/null +++ b/test/mitsuo.ipynb @@ -0,0 +1,771 @@ +{ + "cells": [ + { + "cell_type": "markdown", + "id": "956275e8-e4e6-4a03-afe5-31eca1c3272b", + "metadata": {}, + "source": [ + "# Testing possible algorithms to solve MDHVRPTW" + ] + }, + { + "cell_type": "markdown", + "id": "234feb6e-4c52-443c-a3d6-6da8e903dd5c", + "metadata": { + "tags": [] + }, + "source": [ + "Travelling salesman problem\n", + "\n", + "TSP es *casi* MDHVRPTW (*Multi-Depot Heterogeneous VRP with Time Windows) *del profe* pero:\n", + "- Solo 1 camion\n", + "- Todos los ciudades (aka. almacenes pequeños) tienen al menos 1 pedido\n", + "- Capacidad infinita (1 solo tipo de vehiculo)\n", + "- Sin ventanas de tiempo (aka. plazos de entrega)\n", + "- Solo 1 deposito\n", + "- No hay entregas parciales\n", + " - Relajar la restriccion de que la demanda de los \"customers\" debe ser satisfecha al 100% por\n", + " un solo camion. Entonces, si un \"customer\" requiere 8 paquetes, se le puede entregar solo 5,\n", + " y quedan pendientes 3. **Esto modifica la solucion, ahora es una lista donde los nodos a visitar\n", + " ya no son unicos**. Se debe terminar la solucion cuando ya no hayan pedidos pendientes (paquetes por entregar > 0).\n", + "- No hay \"trasvaces\"\n", + " - F\n", + "\n", + "Cambios identificados, necesarios para adaptar el TSP a nuestro caso:\n", + "- Tramos no conectados -> distancia grande entre ellos\n", + "- Distancias no son euclidianas, usar \"geodistance\"\n", + "- [...]" + ] + }, + { + "cell_type": "markdown", + "id": "6ce403ac-eb32-4f74-ae8d-41cb70fe4a20", + "metadata": { + "tags": [] + }, + "source": [ + "## Posibilidades\n", + "\n", + "Una manera de implementar \n", + "\n", + "- [scikit-opt](https://github.com/guofei9987/scikit-opt)" + ] + }, + { + "cell_type": "markdown", + "id": "98fe5cbb-4fb3-478b-b22f-c14a0408e638", + "metadata": { + "tags": [] + }, + "source": [ + "## NetworkX to find all_pairs_shortest_path" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "4b854709-fe5c-4c5a-8a05-b2e438c92a1a", + "metadata": {}, + "outputs": [], + "source": [ + "import networkx as nx\n", + "G = nx.Graph()\n", + "G.add_edge(1, 2) # default edge data=1\n", + "G.add_edge(2, 3, weight=0.9) # specify edge data" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "44bf2120-1e55-4c1d-b806-3e66227483a3", + "metadata": {}, + "outputs": [], + "source": [ + "import math\n", + "G.add_edge('y', 'x', function=math.cos)\n", + "G.add_node(math.cos) # any hashable can be a node" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "2ed6d6e2-921a-4376-8f8e-c6731385d561", + "metadata": {}, + "outputs": [], + "source": [ + "elist = [(1, 2), (2, 3), (1, 4), (4, 2)]\n", + "G.add_edges_from(elist)\n", + "elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]\n", + "G.add_weighted_edges_from(elist)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "16aad098-3702-4d81-889b-3dc8b3e46ca7", + "metadata": {}, + "outputs": [], + "source": [ + "import matplotlib.pyplot as plt\n", + "#G = nx.cubical_graph()\n", + "subax1 = plt.subplot(121)\n", + "nx.draw(G) # default spring_layout" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "1cc6e56b-3dcf-45fe-9127-0cd63f01ccec", + "metadata": {}, + "outputs": [], + "source": [ + "print(G.adj)" + ] + }, + { + "cell_type": "markdown", + "id": "bad6e2e8-cff5-4a7d-9e3f-f37bae5dff2d", + "metadata": {}, + "source": [ + "## Pre-processing" + ] + }, + { + "cell_type": "markdown", + "id": "22af16ef-7df6-49c8-8e55-157069c03830", + "metadata": {}, + "source": [ + "La data del profe es muy tedioso de leer. Formato raro. Pasar primero a csv.\n", + "\n", + "Distancia entre nodos:" + ] + }, + { + "cell_type": "code", + "execution_count": 8, + "id": "db46bd0b-46c7-4125-bfff-33205c578e27", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "'/home/mitsuo/docs/courses/2022-1/INF226_DP1/project/code/DP_project/test'" + ] + }, + "execution_count": 8, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "%pwd" + ] + }, + { + "cell_type": "code", + "execution_count": 1, + "id": "b87961d0-f9b4-417e-9138-3db1b0a36d2f", + "metadata": {}, + "outputs": [], + "source": [ + "import numpy as np\n", + "\n", + "import csv\n", + "import math\n", + "import random\n", + "\n", + "import networkx as nx\n", + "import matplotlib.pyplot as plt" + ] + }, + { + "cell_type": "code", + "execution_count": 2, + "id": "aeca1be3-1394-4ae1-b488-6abe8bd1e808", + "metadata": {}, + "outputs": [], + "source": [ + "def degreesToRadians(degrees):\n", + " return degrees * math.pi / 180\n", + "\n", + "def distanceInKmBetweenEarthCoordinates(lat1, lon1, lat2, lon2):\n", + " earthRadiusKm = 6371 # Avg. radius\n", + "\n", + " dLat = degreesToRadians(lat2-lat1)\n", + " dLon = degreesToRadians(lon2-lon1)\n", + "\n", + " lat1 = degreesToRadians(lat1)\n", + " lat2 = degreesToRadians(lat2)\n", + "\n", + " a = math.sin(dLat/2) * math.sin(dLat/2) \\\n", + " + math.sin(dLon/2) * math.sin(dLon/2) * math.cos(lat1) * math.cos(lat2)\n", + " c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a));\n", + " return earthRadiusKm * c\n" + ] + }, + { + "cell_type": "code", + "execution_count": 3, + "id": "80a0fef2-ae25-40e3-94ab-e3d07b9b60c0", + "metadata": {}, + "outputs": [], + "source": [ + "class Node:\n", + " \"\"\"\n", + " \n", + " Attributes\n", + " ----------\n", + " lat : float\n", + " Latitud (angulo de los Paralelos) en grados sexagesimales\n", + " lon : float\n", + " Longitud (angulo de los Meridianos) en grados sexagesimales\n", + " x : float\n", + " Aproximacion local, en Km respecto (\"Lima\": -12.04591952,-77.03049615 (lat, long))\n", + " x = (longitud - (-77.03049615)) * (pi / 180) * earthRadiusKm\n", + " y : float\n", + " Aproximacion local, en Km respecto (\"Lima\")\n", + " y = (latitud - (-12.04591952)) * (pi / 180) * earthRadiusKm\n", + " demand : float\n", + " Cantidad de paquetes (facil cambiar a int)\n", + " *_time : float\n", + " Cantidades de tiempo en minutos\n", + " \n", + " Notes\n", + " -----\n", + " Web Mercator projection (BAD):\n", + " \n", + " x = floor(256 / (2 * math.pi) * 2**(zoom_level) * (lon + math.pi))\n", + " y = floor(265 / (2 * math.pi) * 2**(zoom_level) * (math.pi - math.ln(math.tan( math.pi / 4 + lat / 2 ))))\n", + " \n", + " x = R * lon\n", + " y = R * ln(tan(pi/4 + lat/2)\n", + " \n", + " Both `lon` and `lat` in radians.\n", + " \n", + " \"Lima\": -12.04591952,-77.03049615 (lat, long)\n", + " \"\"\"\n", + " def __init__(self, id: int, ubigeo, lat, lon, is_depot,\n", + " demand, ready_time, due_time, service_time):\n", + " super()\n", + " self.id = id\n", + " self.ubigeo = ubigeo\n", + "\n", + " if is_depot:\n", + " self.is_depot = True\n", + " else:\n", + " self.is_depot = False\n", + " \n", + " earthRadiusKm = 6371 # Avg. radius\n", + " zoom_level = 1\n", + " lima_lat = (-12.04591952)\n", + " lima_lon = (-77.03049615)\n", + " \n", + " self.lat = lat\n", + " self.lon = lon\n", + " self.x = (lon - lima_lon) * (math.pi / 180) * earthRadiusKm\n", + " self.y = (lat - lima_lat) * (math.pi / 180) * earthRadiusKm\n", + " #self.lat *= (math.pi / 180)\n", + " #self.lon *= (math.pi / 180)\n", + " #self.x = 256 / (2 * math.pi) * 2**(zoom_level) * (self.lon + math.pi)\n", + " #self.y = 256 / (2 * math.pi) * 2**(zoom_level) * (math.pi - math.log(math.tan( math.pi / 4 + self.lat / 2 )))\n", + " self.x = round(self.x, 3)\n", + " self.y = round(self.y, 3)\n", + " self.demand = demand\n", + " self.ready_time = 0 #ready_time\n", + " self.due_time = due_time\n", + " self.service_time = service_time" + ] + }, + { + "cell_type": "code", + "execution_count": 10, + "id": "fd72a504-3538-4b43-9e90-bef4299ca83d", + "metadata": {}, + "outputs": [], + "source": [ + "nodes = []\n", + "\n", + "with open('data/VRPTW_python/inf226.oficinas_mod.csv', newline='') as csvfile:\n", + " orders = csv.reader(csvfile)\n", + " count = 1\n", + " id = 0\n", + " for row in orders:\n", + " if count >= 2:\n", + " ubigeo, dept, prov, latitud, longitud, region_natural, is_depot = row[:7]\n", + " demand, ready_time, due_time, service_time = row[7:]\n", + " nodes.append(Node(\n", + " id, ubigeo, float(latitud), float(longitud), int(is_depot),\n", + " #int(100 * random.random()), 0, int(5000 + 500 * (1.5 - random.random())), service_time=60\n", + " demand=float(demand), ready_time=0, due_time=float(due_time), service_time=60\n", + " ))\n", + " id += 1\n", + " count += 1" + ] + }, + { + "cell_type": "code", + "execution_count": 12, + "id": "8a9cb3eb-d434-44de-a179-01464ba7bbf8", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "{'id': 34, 'ubigeo': '040101', 'is_depot': True, 'lat': -16.39881421, 'lon': -71.537019649, 'x': 610.847, 'y': -484.02, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n", + "{'id': 122, 'ubigeo': '130101', 'is_depot': True, 'lat': -8.11176389, 'lon': -79.02868652, 'x': -222.189, 'y': 437.458, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n", + "{'id': 134, 'ubigeo': '150101', 'is_depot': True, 'lat': -12.04591952, 'lon': -77.03049615, 'x': 0.0, 'y': 0.0, 'demand': 0.0, 'ready_time': 0, 'due_time': 8000.0, 'service_time': 60}\n" + ] + } + ], + "source": [ + "for node in nodes:\n", + " if node.is_depot:\n", + " print(node.__dict__)" + ] + }, + { + "cell_type": "code", + "execution_count": 15, + "id": "79fcde2d-d0df-4cca-8334-3ffd7a0da997", + "metadata": {}, + "outputs": [], + "source": [ + "node_num = len(nodes)\n", + "\n", + "tramos = []\n", + "with open('../data/inf226.tramos.v.2.0.csv', newline='') as f:\n", + " rows = csv.reader(f)\n", + " count = 1\n", + " for row in rows:\n", + " if count >= 2:\n", + " tramos.append([row[0], row[1]])\n", + " count += 1" + ] + }, + { + "cell_type": "code", + "execution_count": 16, + "id": "945de058-6fc3-44c1-8d59-227064323bae", + "metadata": {}, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "7008\n" + ] + }, + { + "data": { + "text/plain": [ + "[['010201', '010301'],\n", + " ['010301', '010201'],\n", + " ['010201', '010401'],\n", + " ['010401', '010201'],\n", + " ['010201', '010501']]" + ] + }, + "execution_count": 16, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "print(len(tramos))\n", + "tramos[:5]" + ] + }, + { + "cell_type": "code", + "execution_count": 17, + "id": "e6895a35-ff22-48a1-88a8-ceb8344f36cb", + "metadata": {}, + "outputs": [], + "source": [ + "node_dist_mat = np.zeros((node_num, node_num))\n", + "\n", + "nodes_d = dict(zip([n.ubigeo for n in nodes], nodes))\n", + "for ubigeo1, ubigeo2 in tramos:\n", + " #if ubigeo1 in nodes_d.keys() and ubigeo2 in nodes_d.keys():\n", + " id1 = nodes_d[ubigeo1].id\n", + " id2 = nodes_d[ubigeo2].id\n", + " n1 = nodes[id1]\n", + " n2 = nodes[id2]\n", + " node_dist_mat[id1][id2] = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)" + ] + }, + { + "cell_type": "code", + "execution_count": 18, + "id": "b971e3b3-cea5-43b8-9c57-5bbb83180ee6", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "(196, 196)" + ] + }, + "execution_count": 18, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "node_dist_mat.shape" + ] + }, + { + "cell_type": "code", + "execution_count": 19, + "id": "abc75da4-fed7-493e-ae9d-f5daba33c693", + "metadata": {}, + "outputs": [ + { + "data": { + "text/plain": [ + "array([[ 0. , 86.349, 0. , 137.864],\n", + " [ 86.349, 0. , 0. , 146.07 ],\n", + " [ 0. , 0. , 0. , 0. ],\n", + " [137.864, 146.07 , 0. , 0. ]])" + ] + }, + "execution_count": 19, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "node_dist_mat[:4, :4]" + ] + }, + { + "cell_type": "code", + "execution_count": 24, + "id": "e818c9bb-28cb-475d-b8b5-98dfe4d11f91", + "metadata": {}, + "outputs": [], + "source": [ + "# depots are '040101', '130101', '150101'\n", + "\n", + "depots = []\n", + "customers = []\n", + "for n in nodes:\n", + " if n.is_depot:\n", + " depots.append(n)\n", + " else:\n", + " customers.append(n)\n", + "depots_customers = depots + customers\n", + "\n", + "with open('data/VRPTW_python/pedidosperu195.txt', 'w', newline='') as csvfile:\n", + " spamwriter = csv.writer(csvfile, delimiter=' ', quoting=csv.QUOTE_MINIMAL)\n", + " i = 0\n", + " for node in depots_customers:\n", + " spamwriter.writerow([\n", + " #node.id,\n", + " i,\n", + " node.x, node.y,\n", + " node.demand, node.ready_time, node.due_time, node.service_time\n", + " ])\n", + " i += 1" + ] + }, + { + "cell_type": "markdown", + "id": "4cf94976-9003-4b9a-a600-ad9b48d3e60e", + "metadata": {}, + "source": [ + "### Transformar a matriz conexa de nodos \"customer\"" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ac9f4ce7-7f54-4d26-9bbf-75252f083046", + "metadata": {}, + "outputs": [], + "source": [ + "for n in nodes[:5]:\n", + " print(n.__dict__)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b3f18eaf-a962-454f-99d4-67bf71067e39", + "metadata": {}, + "outputs": [], + "source": [ + "count = 0\n", + "for n in nodes:\n", + " if n.demand:\n", + " print(n.__dict__)\n", + " count += 1\n", + "count" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "4308a3df-27ca-4910-bff3-1302c8fb589d", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "14d8d583-7766-421b-96cc-ec95ad9604e6", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "f85c9cab", + "metadata": {}, + "outputs": [], + "source": [ + "#node_dist_mat = np.zeros((node_num, node_num))\n", + "elist = []\n", + "\n", + "nodes_d = dict(zip([n.ubigeo for n in nodes], nodes))\n", + "for ubigeo1, ubigeo2 in tramos:\n", + " #if ubigeo1 in nodes_d.keys() and ubigeo2 in nodes_d.keys():\n", + " id1 = nodes_d[ubigeo1].id\n", + " id2 = nodes_d[ubigeo2].id\n", + " n1 = nodes[id1]\n", + " n2 = nodes[id2]\n", + " #node_dist_mat[id1][id2] = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)\n", + " dist = round(distanceInKmBetweenEarthCoordinates(n1.lat, n1.lon, n2.lat, n2.lon), 3)\n", + " elist.append((ubigeo1, ubigeo2, dist))\n", + " \n", + "G = nx.Graph()\n", + "G.add_weighted_edges_from(elist)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "b3c522d4", + "metadata": { + "scrolled": true + }, + "outputs": [], + "source": [ + "print(len(list(nodes_d)))\n", + "print(len(list(G.nodes)))" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "86771f42", + "metadata": {}, + "outputs": [], + "source": [ + "G['010201']['010301']" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "001a04b8", + "metadata": {}, + "outputs": [], + "source": [ + "node_dist_mat[nodes_d['010201'].id, nodes_d['010301'].id]" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "71e54f4d", + "metadata": {}, + "outputs": [], + "source": [ + "G['010201']['250301']" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "7ebe3cdc", + "metadata": {}, + "outputs": [], + "source": [ + "path1 = nx.shortest_path(G, source='010201', target='250301', weight='weight')\n", + "path1" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "cca62d40", + "metadata": {}, + "outputs": [], + "source": [ + "path2 = nx.shortest_path(G, source='010201', target='250301')\n", + "path2" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "756f1845", + "metadata": {}, + "outputs": [], + "source": [ + "l1, l2 = 0, 0\n", + "for i in range(len(path1)):\n", + " if i == 0:\n", + " continue\n", + " l1 += G[path1[i-1]][path1[i]]['weight']\n", + " l2 += G[path2[i-1]][path2[i]]['weight']\n", + "print(l1, l2)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "9e124757", + "metadata": { + "scrolled": true + }, + "outputs": [], + "source": [ + "# https://stackoverflow.com/a/63169428/7498073\n", + "H = nx.subgraph(G, path1)\n", + "nx.draw(H, with_labels=True, font_weight='bold', node_color='lightblue', node_size=500)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "c5ded33b", + "metadata": {}, + "outputs": [], + "source": [ + "len_path = dict(nx.all_pairs_dijkstra(G, weight='weight'))\n", + "#for node, (dist, path) in len_path:\n", + "# print(f\"{node}: {dist} [{path}]\")" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "3361d460", + "metadata": {}, + "outputs": [], + "source": [ + "print(len_path['010201'][0]['250301'])\n", + "print(len_path['010201'][1]['250301'])" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "ba3d4ae7-c6b5-484a-a1b4-0f6ffe1890b6", + "metadata": {}, + "outputs": [], + "source": [ + "help(G)" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "596bf42a-3600-4446-a904-a4e9080d2f2b", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "132bea6b-c50c-4406-8e2f-2279a87e9cbf", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "bf5cac1d-9ae4-4423-ab96-48728c14fa01", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "00f4cd39-c093-4397-ae96-cb3ae2a433c6", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "markdown", + "id": "ff3f7473-6418-4f4a-828f-172f2996ba54", + "metadata": {}, + "source": [ + "## Pruebitas" + ] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "6956f235-0401-4a67-8ed2-d2b3fd07b3bf", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "0ab3843c-faba-46a0-9f7b-97897430ba67", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "e45dd91b-fc32-4da3-a340-d3dc888b1335", + "metadata": {}, + "outputs": [], + "source": [] + }, + { + "cell_type": "code", + "execution_count": null, + "id": "5fdfcaa8-9000-48d7-b3ab-4d2f2efc2bcc", + "metadata": {}, + "outputs": [], + "source": [] + } + ], + "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.9.2" + } + }, + "nbformat": 4, + "nbformat_minor": 5 +} |