{
"cells": [
{
"cell_type": "markdown",
"id": "3ce77085-3338-46b2-8784-de1187f43f25",
"metadata": {},
"source": [
"## Hybrid Genetic Search meta-heuristic example"
]
},
{
"cell_type": "markdown",
"id": "5003abe0-384b-46d8-87e0-934500cc0496",
"metadata": {},
"source": [
"The meta-heuristic used is [vidalt/HGS-CVRP: Modern implementation of the hybrid genetic search (HGS) algorithm specialized to the capacitated vehicle routing problem (CVRP). This code also includes an additional neighborhood called SWAP\\*.](https://github.com/vidalt/HGS-CVRP)"
]
},
{
"cell_type": "markdown",
"id": "71a324a5-727c-40a0-b4df-72d522633b16",
"metadata": {},
"source": [
"HGS-CVRP can only produce *radial* topologies. Since a *radial* topology is a special case of the *branched* topology, solutions produced by this method can be used to warm-start both *branched*- and *radial*-topology models.\n",
"\n",
"If a routeset is desired, use *PathFinder*."
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "672c7061-abbf-4da0-9236-232dde141ac9",
"metadata": {},
"outputs": [],
"source": [
"from optiwindnet.importer import load_repository\n",
"from optiwindnet.svg import svgplot\n",
"from optiwindnet.baselines.hgs import hgs_cvrp\n",
"from optiwindnet.mesh import make_planar_embedding\n",
"from optiwindnet.pathfinding import PathFinder\n",
"from optiwindnet.interarraylib import G_from_S, as_normalized"
]
},
{
"cell_type": "markdown",
"id": "92bfd6df-c545-48d2-b4d0-e69a1a6c473b",
"metadata": {},
"source": [
"### Load Hornsea"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "51e1e821-a0ea-47c3-a197-4b625bbf3a3b",
"metadata": {},
"outputs": [],
"source": [
"locations = load_repository()"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "36ac83fb-02db-4640-b7a5-891715f70b83",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"L = locations.hornsea\n",
"svgplot(L)"
]
},
{
"cell_type": "markdown",
"id": "c7d1dd72-c13b-4454-8754-9098e2faf9a8",
"metadata": {},
"source": [
"### Optimize Hornsea"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "37c0ec1f-bcc2-4025-92bc-613fdebbf1b1",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(0.13, 0.11, 0.29)\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P, A = make_planar_embedding(L)\n",
"S = hgs_cvrp(as_normalized(A), capacity=7, time_limit=0.5)\n",
"print(S.graph['solution_time'])\n",
"G = G_from_S(S, A)\n",
"svgplot(G)"
]
},
{
"cell_type": "markdown",
"id": "e8aa52ec-ba4f-41bd-9bb0-f6655fcc6aab",
"metadata": {},
"source": [
"### Route the feeders so as to avoid crossings"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "cf958a39-99fe-48d6-891c-8ccb1688b261",
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"H = PathFinder(G, P, A).create_detours()\n",
"svgplot(H)"
]
},
{
"cell_type": "markdown",
"id": "0c53998a-170a-4091-a116-2c8c73a56646",
"metadata": {},
"source": [
"### Check the HGS-CVRP log"
]
},
{
"cell_type": "markdown",
"id": "e52c6a41-51f4-4264-ae77-c7abc3b7bd28",
"metadata": {},
"source": [
"There are two alternatives to see the HGS log:\n",
"1. Store it in the solution object (must wait until HGS has finished)\n",
"2. Stream it using a callback function that gets one line per call"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "920596e7-51d0-4d16-85a7-e0489a14ff77",
"metadata": {},
"outputs": [],
"source": [
"L = locations.meerwind\n",
"P, A = make_planar_embedding(L)"
]
},
{
"cell_type": "markdown",
"id": "b807d169-8be0-476f-9cd5-de5ed2899145",
"metadata": {},
"source": [
"#### Store the log"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "3cf7bc01-f4cf-4303-a3df-1160dda45752",
"metadata": {},
"outputs": [],
"source": [
"S = hgs_cvrp(\n",
" as_normalized(A),\n",
" capacity=7,\n",
" time_limit=0.5,\n",
" keep_log=True,\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "db7a7041-c5fe-4130-bcc6-a937023558ea",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"----- FLEET SIZE WAS NOT SPECIFIED: DEFAULT INITIALIZATION TO 18 VEHICLES\n",
"----- INSTANCE SUCCESSFULLY LOADED WITH 80 CLIENTS AND 18 VEHICLES\n",
"----- BUILDING INITIAL POPULATION\n",
"----- STARTING GENETIC ALGORITHM\n",
"It 0 2 | T(s) 0.05 | Feas 60 11.12 11.35 | NO-INFEASIBLE | Div 0.45 -1.00 | Feas 1.00 1.00 | Pen 5.81 0.85\n",
"It 500 225 | T(s) 0.18 | Feas 27 11.02 11.10 | NO-INFEASIBLE | Div 0.36 -1.00 | Feas 1.00 1.00 | Pen 2.58 0.38\n",
"It 1000 725 | T(s) 0.31 | Feas 35 11.02 11.11 | NO-INFEASIBLE | Div 0.38 -1.00 | Feas 1.00 1.00 | Pen 1.14 0.17\n",
"It 1500 1225 | T(s) 0.46 | Feas 40 11.02 11.10 | Inf 4 11.61 11.79 | Div 0.38 0.40 | Feas 0.97 1.00 | Pen 0.51 0.10\n",
"----- GENETIC ALGORITHM FINISHED AFTER 1625 ITERATIONS. TIME SPENT: 0.50001\n",
"\n"
]
}
],
"source": [
"print(S.graph['method_log'])"
]
},
{
"cell_type": "markdown",
"id": "73dd155c-b447-48c7-9c38-ca1a33e7a73d",
"metadata": {},
"source": [
"#### Stream the log"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "b20627a2-08ea-4a32-a7de-6a60ff11ff88",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"----- FLEET SIZE WAS NOT SPECIFIED: DEFAULT INITIALIZATION TO 18 VEHICLES\n",
"----- INSTANCE SUCCESSFULLY LOADED WITH 80 CLIENTS AND 18 VEHICLES\n",
"----- BUILDING INITIAL POPULATION\n",
"----- STARTING GENETIC ALGORITHM\n",
"It 0 2 | T(s) 0.05 | Feas 60 11.19 11.33 | NO-INFEASIBLE | Div 0.44 -1.00 | Feas 1.00 1.00 | Pen 5.81 0.85\n",
"It 500 43 | T(s) 0.18 | Feas 27 11.02 11.12 | NO-INFEASIBLE | Div 0.38 -1.00 | Feas 1.00 1.00 | Pen 2.58 0.38\n",
"It 1000 543 | T(s) 0.31 | Feas 35 11.02 11.09 | NO-INFEASIBLE | Div 0.35 -1.00 | Feas 1.00 1.00 | Pen 1.14 0.17\n",
"It 1500 1043 | T(s) 0.47 | Feas 43 11.02 11.10 | Inf 2 11.70 11.80 | Div 0.36 0.59 | Feas 0.98 1.00 | Pen 0.51 0.10\n",
"----- GENETIC ALGORITHM FINISHED AFTER 1602 ITERATIONS. TIME SPENT: 0.500113\n"
]
}
],
"source": [
"S = hgs_cvrp(\n",
" as_normalized(A),\n",
" capacity=7,\n",
" time_limit=0.5,\n",
" log_callback=(lambda line: print(line, end='')),\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "9328e5e5-022c-4926-81de-a5b23a1ece46",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.18\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"print(S.graph['solution_time'])\n",
"G = G_from_S(S, A)\n",
"svgplot(G)"
]
}
],
"metadata": {
"language_info": {
"name": "python"
}
},
"nbformat": 4,
"nbformat_minor": 5
}