Launch with Binder Edit on Gitlab

🧭 LKH-3

Concepts: LKH-3 · Meta-heuristics

The meta-heuristic used is K. Helsgaun’s LKH-3, an extension to LKH-2 — see LKH-3 for what it does and how it is distributed.

Note: OptiWindNet interfaces with LKH through temporary files and system calls to the LKH executable, which must be in the PATH environment variable as seen from the Python code.

LKH-3 can produce both radial (default Open-CVRP) and ringed (ringed=True CVRP) topologies. Solutions can be used directly or as warm-starts for MILP models — see Warm-start acceptance requirements.

If a routeset is desired, use PathFinder.

[1]:

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

Load Greater Gabbard Inner

[2]:

locations = load_repository()

[3]:

L = locations.gabbin
svgplot(L)

[3]:
../_images/notebooks_lo22_lkh_8_0.svg

Optimize Greater Gabbard Inner

[4]:

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

1.96

[4]:
../_images/notebooks_lo22_lkh_10_1.svg

Route the feeders so as to avoid crossings

[5]:

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

[5]:
../_images/notebooks_lo22_lkh_12_0.svg

Check the LKH-3 log

LKH-3 runs as an external program, so its log is available only after it finishes. With keep_log=True, the log is stored in the solution’s method_log graph attribute.

[6]:

print(S.graph['method_log'])

PARAMETER_FILE = /home/masoda/tmp/tmpwj1xcst5/params.txt
Reading PROBLEM_FILE: "/home/masoda/tmp/tmpwj1xcst5/problem.txt" ... done
ASCENT_CANDIDATES = 50
BACKBONE_TRIALS = 0
BACKTRACKING = NO
# BWTSP =
# CANDIDATE_FILE =
CANDIDATE_SET_TYPE = ALPHA
DISTANCE = 193139.9
DEPOT = 103
# EDGE_FILE =
DRONES = 1
ENDURANCE = 0.0
EXCESS = 0.128205
EXTERNAL_SALESMEN = 0
EXTRA_CANDIDATES = 0
EXTRA_CANDIDATE_SET_TYPE = QUADRANT
GAIN23 = NO
GAIN_CRITERION = YES
INITIAL_PERIOD = 117
INITIAL_STEP_SIZE = 1
INITIAL_TOUR_ALGORITHM = WALK
# INITIAL_TOUR_FILE =
INITIAL_TOUR_FRACTION = 1.000
# INPUT_TOUR_FILE =
# K =
KICK_TYPE = 4
KICKS = 1
# MAX_BREADTH =
MAKESPAN = NO
MAX_CANDIDATES = 5
MAX_SWAPS = 0
MAX_TRIALS = 234
# MERGE_TOUR_FILE =
MOVE_TYPE = 5 SPECIAL
MTSP_MIN_SIZE = 4
MTSP_MAX_SIZE = 7
MTSP_OBJECTIVE = MINSUM
MTSP_SOLUTION_FILE = /home/masoda/tmp/tmpwj1xcst5/solution.out
# NONSEQUENTIAL_MOVE_TYPE = 5
# OPTIMUM =
# OUTPUT_TOUR_FILE =
PATCHING_A = 1
PATCHING_C = 0
# PI_FILE =
POPMUSIC_INITIAL_TOUR = NO
POPMUSIC_MAX_NEIGHBORS = 5
POPMUSIC_SAMPLE_SIZE = 10
POPMUSIC_SOLUTIONS = 50
POPMUSIC_TRIALS = 1
POPULATION_SIZE = 10
PRECISION = 1000
# PROBABILITY =
PROBLEM_FILE = /home/masoda/tmp/tmpwj1xcst5/problem.txt
RECOMBINATION = IPT
RESTRICTED_SEARCH = YES
RUNS = 50
SALESMEN = 15
SCALE = 1
SEED = 1234567
# SINTEF_SOLUTION_FILE =
STOP_AT_OPTIMUM = YES
SUBGRADIENT = YES
# SUBPROBLEM_SIZE =
# SUBPROBLEM_TOUR_FILE =
SUBSEQUENT_MOVE_TYPE = 5 SPECIAL
SUBSEQUENT_PATCHING = YES
TIME_LIMIT = 15.0
TOTAL_TIME_LIMIT = 2.0
TOUR_FILE = /home/masoda/tmp/tmpwj1xcst5/solution.tour
TRACE_LEVEL = 1
VEHICLES = 15

Lower bound = 984838.7, Ascent time = 0.04 sec.
Cand.min = 5, Cand.avg = 5.0, Cand.max = 5
Edges.fixed = 117 [Cost = 0]
Preprocessing time = 0.04 sec.
* 1: Cost = 6_1260799, Time = 0.04 sec.
* 2: Cost = 5_1260019, Time = 0.05 sec.
* 3: Cost = 1_1280401, Time = 0.07 sec.
* 4: Cost = 1_1280163, Time = 0.07 sec.
* 5: Cost = 1_1264370, Time = 0.07 sec.
* 6: Cost = 1_1247307, Time = 0.08 sec.
* 12: Cost = 0_1266447, Time = 0.10 sec.
* 15: Cost = 0_1259256, Time = 0.11 sec.
* 20: Cost = 0_1256792, Time = 0.13 sec.
* 21: Cost = 0_1254885, Time = 0.13 sec.
* 30: Cost = 0_1250125, Time = 0.16 sec.
* 31: Cost = 0_1248075, Time = 0.16 sec.
* 37: Cost = 0_1246677, Time = 0.18 sec.
* 45: Cost = 0_1236853, Time = 0.20 sec.
* 48: Cost = 0_1236402, Time = 0.21 sec.
* 60: Cost = 0_1231664, Time = 0.23 sec.
* 68: Cost = 0_1230076, Time = 0.25 sec.
* 69: Cost = 0_1228782, Time = 0.25 sec.
* 73: Cost = 0_1225435, Time = 0.27 sec.
* 105: Cost = 0_1223432, Time = 0.37 sec.
* 126: Cost = 0_1222084, Time = 0.43 sec.
* 131: Cost = 0_1215245, Time = 0.44 sec.
* 150: Cost = 0_1214265, Time = 0.49 sec.
* 151: Cost = 0_1211955, Time = 0.49 sec.
* 155: Cost = 0_1204938, Time = 0.50 sec.
* 164: Cost = 0_1198671, Time = 0.53 sec.
* 217: Cost = 0_1198113, Time = 0.71 sec.
Population:
  1: 0_1198113
Writing TOUR_FILE: "/home/masoda/tmp/tmpwj1xcst5/solution.tour" ... done
Run 1: Cost = 0_1198113, Time = 0.76 sec.

* 1: Cost = 0_1278912, Time = 0.01 sec.
* 2: Cost = 0_1277881, Time = 0.02 sec.
* 3: Cost = 0_1274887, Time = 0.02 sec.
* 4: Cost = 0_1273734, Time = 0.02 sec.
* 5: Cost = 0_1270536, Time = 0.02 sec.
* 9: Cost = 0_1267243, Time = 0.03 sec.
* 12: Cost = 0_1258259, Time = 0.04 sec.
* 14: Cost = 0_1246878, Time = 0.05 sec.
* 20: Cost = 0_1238884, Time = 0.06 sec.
* 55: Cost = 0_1228743, Time = 0.14 sec.
* 87: Cost = 0_1223856, Time = 0.23 sec.
* 122: Cost = 0_1216793, Time = 0.33 sec.
* 179: Cost = 0_1216744, Time = 0.43 sec.
* 188: Cost = 0_1215077, Time = 0.46 sec.
Population:
  1: 0_1198113
  2: 0_1215077
Run 2: Cost = 0_1215077, Time = 0.58 sec.

* 1: Cost = 1_1278131, Time = 0.03 sec.
* 3: Cost = 1_1274338, Time = 0.06 sec.
* 5: Cost = 1_1260162, Time = 0.07 sec.
* 6: Cost = 0_1272382, Time = 0.08 sec.
* 8: Cost = 0_1262551, Time = 0.09 sec.
* 9: Cost = 0_1242968, Time = 0.10 sec.
* 11: Cost = 0_1239492, Time = 0.10 sec.
* 15: Cost = 0_1229675, Time = 0.11 sec.
* 31: Cost = 0_1218271, Time = 0.17 sec.
* 34: Cost = 0_1212891, Time = 0.18 sec.
* 42: Cost = 0_1206971, Time = 0.20 sec.
* 45: Cost = 0_1206571, Time = 0.22 sec.
* 47: Cost = 0_1202822, Time = 0.22 sec.
* 67: Cost = 0_1198125, Time = 0.26 sec.
* 127: Cost = 0_1195274, Time = 0.41 sec.
* 129: Cost = 0_1189937, Time = 0.41 sec.
* 141: Cost = 0_1189687, Time = 0.46 sec.
* 144: Cost = 0_1185256, Time = 0.47 sec.
* 159: Cost = 0_1184501, Time = 0.51 sec.
*** Time limit exceeded*** Time limit exceeded ***
Population:
  1: 0_1184501
  2: 0_1198113
  3: 0_1215077
Writing TOUR_FILE: "/home/masoda/tmp/tmpwj1xcst5/solution.tour" ... done
Run 3: Cost = 0_1184501, Time = 0.62 sec.

*** Time limit exceeded ***
Successes/Runs = 0/50
Cost.min = 1184501, Cost.avg = 1199230.33, Cost.max = 1215077
Gap.min = 0.0000%, Gap.avg = 1.2435%, Gap.max = 2.5813%
Penalty.min = 0, Penalty.avg = 0.00, Penalty.max = 0
Trials.min = 197, Trials.avg = 221.7, Trials.max = 234
Time.min = 0.58 sec., Time.avg = 0.65 sec., Time.max = 0.76 sec.
Time.total = 2.00 sec.
  Size.min = 5, Size.max = 7, Penalty = 0
  Cost.min = 44504, Cost.max = 106927, Cost.sum = 1184501
Writing MTSP_SOLUTION_FILE: "/home/masoda/tmp/tmpwj1xcst5/solution.out" ... done
Best OVRP solution:
  Cost = 0_1184501

Current LKH options

warmstart supplies initial tours from a feasible topology. Use complete=True to compare solution quality when all terminal pairs are available: links absent from A receive their Euclidean lengths, while existing links retain their stored lengths. This requires repair=False because crossing repair relies on A’s planar mesh. With complete=False, missing links receive a large edge-weight penalty but can still be selected. seed sets the pseudo-random seed.

Within each invocation, runs limits the number of search runs, per_run_limit limits each run, and time_limit limits their combined search time. Repair can trigger further invocations, up to max_retries, with the same budget per cluster. Other processing usually adds only a small overhead.

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