Lin-Kernighan-Helsgaun meta-heuristic example

The meta-heuristic used is K. Helsgaun’s LKH-3, an extension to LKH-2.

• 11. Helsgaun, An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. Technical Report, Roskilde University, 2017.

Notes:

• 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.

• Keld Helsgaun distributes his implementation (for academic and non-commercial use) as C source code and as a Windows binary at http://akira.ruc.dk/~keld/research/LKH-3/.

• The wrapper supports multiple substations by clustering terminals and solving one LKH instance per root.

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.

If a routeset is desired, use PathFinder.

from optiwindnet.importer import load_repository
from optiwindnet.svg import svgplot
from optiwindnet.baselines.lkh import lkh3
from optiwindnet.mesh import make_planar_embedding
from optiwindnet.pathfinding import PathFinder
from optiwindnet.interarraylib import G_from_S, as_normalized

Load Greater Gabbard Inner

locations = load_repository()

L = locations.gabbin
svgplot(L)

Optimize Greater Gabbard Inner

P, A = make_planar_embedding(L)
S = lkh3(as_normalized(A), capacity=7, time_limit=2)
print(S.graph['solution_time'])
G = G_from_S(S, A)
svgplot(G)

0.87

Route the feeders so as to avoid crossings

H = PathFinder(G, P, A).create_detours()
svgplot(H)

Current LKH options

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.

LKH returns an electrical topology. Convert it with G_from_S() and route it with PathFinder when a physical routeset is needed.