{
"cells": [
{
"cell_type": "markdown",
"id": "833ef04c-0db6-4592-bcd1-c05ee0290184",
"metadata": {},
"source": [
"This is used in the paper **Flexible cable routing framework for wind farm collection system optimization**."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "62acfbb5-c974-4aad-8f5a-1ea75d8016b5",
"metadata": {},
"outputs": [],
"source": [
"from itertools import chain, pairwise, accumulate\n",
"import networkx as nx\n",
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "8d9d606d-ac9b-4352-84a4-f046c8c7b2c5",
"metadata": {},
"outputs": [],
"source": [
"from optiwindnet.svg import svgplot\n",
"from optiwindnet.interarraylib import G_from_S, L_from_site\n",
"from optiwindnet.mesh import make_planar_embedding"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "4caf3f04-bcca-43a1-8803-8fba37473e25",
"metadata": {},
"outputs": [],
"source": [
"import vrplib"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "9e483edd-a28b-4985-b26f-2b13a4b40f9b",
"metadata": {},
"outputs": [],
"source": [
"import urllib.request\n",
"import zipfile\n",
"import fnmatch\n",
"import os"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "b62967e0-5f3e-4eb4-bf64-cf00f6a72dd6",
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"plt.style.use('jupyter_dark')"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "e6720c76-16e7-4286-99a1-a09e7685dc07",
"metadata": {},
"outputs": [],
"source": [
"%config InlineBackend.figure_formats = ['svg']\n",
"plt.rcParams['svg.fonttype'] = 'none'"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "389ad434-e702-4aaa-8f34-97aa82c211c8",
"metadata": {},
"outputs": [],
"source": [
"dir_instances = 'Vrp-Set-XML100/instances/'\n",
"dir_solutions = 'Vrp-Set-XML100/solutions/'"
]
},
{
"cell_type": "markdown",
"id": "6de2a586-04d9-42cf-b2d3-f178b36045b8",
"metadata": {},
"source": [
"## Data download"
]
},
{
"cell_type": "markdown",
"id": "c783317b-0eae-45eb-a6e6-6900c401872a",
"metadata": {},
"source": [
"Queiroga, E., Sadykov, R., Uchoa, E., & Vidal, T. (2021, November 24). 10,000 optimal CVRP solutions for testing machine learning based heuristics. AAAI-22 Workshop on Machine Learning for Operations Research (ML4OR). https://openreview.net/forum?id=yHiMXKN6nTl"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5a2e1dbe-d952-4e91-9e63-e330ce25e0c7",
"metadata": {},
"outputs": [],
"source": [
"url = 'http://vrp.galgos.inf.puc-rio.br/media/com_vrp/instances/Vrp-Set-XML100.zip'\n",
"filehandle, _ = urllib.request.urlretrieve(url)\n",
"zip_file_object = zipfile.ZipFile(filehandle, 'r')"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fd43603a-6392-42f7-abde-fde4f10ffadc",
"metadata": {},
"outputs": [],
"source": [
"instances = fnmatch.filter(zip_file_object.namelist(),\n",
" dir_instances + 'XML100_?11?_??.vrp')\n",
"solutions = fnmatch.filter(zip_file_object.namelist(),\n",
" dir_solutions + 'XML100_?11?_??.sol')\n",
"len(instances), len(solutions)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "af11882f-92fc-4d6b-83d2-a78216f88cc0",
"metadata": {},
"outputs": [],
"source": [
"for filename in instances + solutions:\n",
" zip_file_object.extract(filename)"
]
},
{
"cell_type": "markdown",
"id": "148daecc-c508-458b-afd6-f69a140ae68e",
"metadata": {},
"source": [
"## If already downloaded skip to this cell"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "27e8fb14-0d2d-442e-bc3d-dae269249920",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(480, 480)"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# now the lists do not include the full path\n",
"instances = os.listdir(dir_instances)\n",
"solutions = [instance.replace('/instances/', '/solutions/').replace('.vrp', '.sol')\n",
" for instance in instances]\n",
"len(instances), len(solutions)"
]
},
{
"cell_type": "markdown",
"id": "205f5b2d-bbe3-464b-b5d3-ff8fe9168e5b",
"metadata": {},
"source": [
"## Definitions"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "3b1621e6-b4e6-40ac-99a1-4a2b1654de5d",
"metadata": {},
"outputs": [],
"source": [
"def check_rogues(solution, A):\n",
" rogues = []\n",
" branches = ([n - 1 for n in branch] for branch in solution['routes'])\n",
" for branch in branches:\n",
" for edge in pairwise(branch):\n",
" if edge not in A.edges:\n",
" rogues.append(edge)\n",
" return rogues"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "dc8c242e-e87a-48a1-95f0-ecd2bbb884cf",
"metadata": {},
"outputs": [],
"source": [
"def S_from_vrplib(solution, Sʹ):\n",
" '''\n",
" Beware: assumes a single depot!\n",
" '''\n",
" # create a topology graph S from the solution\n",
" S = nx.Graph(\n",
" T=Sʹ.graph['T'], R=Sʹ.graph['R'],\n",
" capacity=Sʹ.graph['capacity'],\n",
" has_loads=True,\n",
" objective=solution['cost'],\n",
" creator='vrplib',\n",
" )\n",
"\n",
" branches = ([n - 1 for n in branch] for branch in solution['routes'])\n",
" for subtree_id, branch in enumerate(branches):\n",
" loads = range(len(branch), 0, -1)\n",
" S.add_nodes_from(((n, {'load': load})\n",
" for n, load in zip(branch, loads)),\n",
" subtree=subtree_id)\n",
" branch_roll = [-1] + branch[:-1]\n",
" reverses = tuple(u < v for u, v in zip(branch, branch_roll))\n",
" edgeD = ({'load': load, 'reverse': reverse}\n",
" for load, reverse in zip(loads, reverses))\n",
" S.add_edges_from(zip(branch_roll, branch, edgeD))\n",
" root_load = sum(S.nodes[n]['load'] for n in S.neighbors(-1))\n",
" S.nodes[-1]['load'] = root_load\n",
" return S"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "6b591101-512d-417f-8cc2-e0aa96157691",
"metadata": {},
"outputs": [],
"source": [
"def L_from_vrplib(instance):\n",
" R = len(instance['depot'])\n",
" T = instance['dimension'] - R\n",
" # make sure depots are numbered 0..M-1\n",
" assert all(depot == i for i, depot in enumerate(instance['depot']))\n",
" L = L_from_site(\n",
" B=4, border=np.arange(T, T + 4),\n",
" R=R, T=T, name=instance['name'], capacity=instance['capacity'],\n",
" VertexC=np.vstack((instance['node_coord'][R:],\n",
" [[0,0], [1000, 0], [1000, 1000], [0, 1000]],\n",
" instance['node_coord'][:R])),\n",
" )\n",
" return L"
]
},
{
"cell_type": "markdown",
"id": "a5b1bdb1-6157-433c-b1f2-f2a9dc6168a6",
"metadata": {},
"source": [
"## Examine XML100 \\_11\\_\n",
"\n",
"(i.e. random client positions, 1-demand)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "7cf8bd99-e3cd-4c0b-96f3-7b2953f5b4cc",
"metadata": {},
"outputs": [],
"source": [
"inst_id = '2115_07'\n",
"instance = vrplib.read_instance(dir_instances + f'XML100_{inst_id}.vrp')\n",
"solution = vrplib.read_solution(dir_solutions + f'XML100_{inst_id}.sol')"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "03ebcb82-bcf7-4a9e-861b-868463bc6ac5",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"dict_keys(['name', 'comment', 'type', 'dimension', 'edge_weight_type', 'capacity', 'node_coord', 'demand', 'depot', 'edge_weight'])"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"instance.keys()"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "093488d6-9484-4af6-83ee-673e4876843a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"dict_keys(['routes', 'cost'])"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solution.keys()"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "9454307a-5a0a-4525-8ef6-c2d99b3e1682",
"metadata": {},
"outputs": [],
"source": [
"L = L_from_vrplib(instance)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "bb0abae0-fde3-4506-aa9b-5ef312249084",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"svgplot(L)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "7b74b839-2ec5-4243-a16b-df2edccf1f72",
"metadata": {},
"outputs": [],
"source": [
"P, A = make_planar_embedding(L)"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "cbf57590-b17a-4f61-b738-f1f695a4d962",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"