{
"cells": [
{
"cell_type": "markdown",
"id": "3ce77085-3338-46b2-8784-de1187f43f25",
"metadata": {},
"source": [
"## Lin-Kernighan-Helsgaun meta-heuristic example"
]
},
{
"cell_type": "markdown",
"id": "5003abe0-384b-46d8-87e0-934500cc0496",
"metadata": {},
"source": [
"The meta-heuristic used is K. Helsgaun's [LKH-3](http://akira.ruc.dk/~keld/research/LKH-3/), an extension to [LKH-2](http://akira.ruc.dk/~keld/research/LKH/).\n",
"\n",
"- K. Helsgaun, [An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems](http://akira.ruc.dk/~keld/research/LKH-3/LKH-3_REPORT.pdf). Technical Report, Roskilde University, 2017."
]
},
{
"cell_type": "markdown",
"id": "3a003e11-a625-460f-865b-62a4439c2628",
"metadata": {},
"source": [
"Notes:\n",
"- OptiWindNet interfaces with the LKH solver through temporary files and system calls to the `LKH` executable, which must be in the **PATH** environment variable as seen from the Python code.\n",
"- Keld Helsgaun distributes his implementation (for academic and non-commercial use) as C source code and as a Windows binary at .\n",
"- The wrapper supports multiple substations by clustering terminals and solving one LKH instance per root.\n"
]
},
{
"cell_type": "markdown",
"id": "71a324a5-727c-40a0-b4df-72d522633b16",
"metadata": {},
"source": [
"LKH-3 can produce both **radial** (default Open-CVRP) and **ringed** (`ringed=True` CVRP) topologies. Solutions produced by this method can be used directly or as warm-starts for MILP 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.lkh import lkh3\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 Greater Gabbard Inner"
]
},
{
"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.gabbin\n",
"svgplot(L)"
]
},
{
"cell_type": "markdown",
"id": "c7d1dd72-c13b-4454-8754-9098e2faf9a8",
"metadata": {},
"source": [
"### Optimize Greater Gabbard Inner"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "37c0ec1f-bcc2-4025-92bc-613fdebbf1b1",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0.87\n"
]
},
{
"data": {
"image/svg+xml": [
""
],
"text/plain": [
""
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"P, A = make_planar_embedding(L)\n",
"S = lkh3(as_normalized(A), capacity=7, time_limit=2)\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": "e17c3984",
"metadata": {},
"source": [
"### Current LKH options\n",
"\n",
"`warmstart` supplies initial tours derived from a feasible topology. `complete=True` fills missing candidate links with direct Euclidean links; leave it false to restrict the solve to the allowed graph. `runs` and `per_run_limit` are passed to LKH-3, and `seed` controls its pseudo-random seed. The wrapper repairs crossings iteratively by default; as with HGS, that repair work can make wall time exceed the per-run limit.\n",
"\n",
"LKH returns an electrical topology. Convert it with `G_from_S()` and route it with `PathFinder` when a physical routeset is needed."
]
}
],
"metadata": {
"language_info": {
"name": "python"
}
},
"nbformat": 4,
"nbformat_minor": 5
}