optiwindnet.baselines.lkh

Module Contents

optiwindnet.baselines.lkh.lkh3(A: networkx.Graph, *, capacity: int, time_limit: float, vehicles: int | None = None, seed: int | None = None, keep_log: bool = False, repair: bool = True, max_retries: int = 10, balanced: bool = False, scale: float = 100000.0, runs: int = 50, per_run_limit: float = 15.0, precision: int = 1000, complete: bool = False, ringed: bool = False, warmstart: networkx.Graph | None = None) → networkx.Graph[source]

Solve the O/CVRP using LKH-3 with links from A.

Wraps the LKH-3 executable, which is not distributed with OptiWindNet. Get it from http://akira.ruc.dk/~keld/research/LKH-3/ and make sure the LKH executable is in the environment’s PATH.

Uses the Lin-Kernighan-Helsgaun meta-heuristic to solve an Open-CVRP (i.e., vehicles do not return to the depot), yielding radial layouts. With ringed=True it solves the closed CVRP instead (TYPE=CVRP): every route returns to the depot, forming a ring whose capacity is doubled internally (2 * capacity) so each of the two arms holds at most capacity terminals. Normalization of the input graph is recommended before calling this function (use as_normalized()).

For single-root problems, the solver runs on the full graph. For multi-root problems, the graph is clustered (one cluster per root) and each cluster is solved concurrently.

For multi-root instances, the vehicles (feeders) parameter is forced per cluster (a warning is issued if a different value is requested): to the minimum feasible value, except for a cluster that fits within capacity, which is offered enough feeders to use as many as lower the cable length.

If repair=True (the default), the solution is iteratively repaired until no crossings remain (or max_retries is reached). This may cause the actual runtime to be up to (max_retries + 1) times the given time_limit.

Parameters:

  • A – graph with allowed edges (if it has 0 edges, use complete=True).

  • capacity – maximum vehicle capacity.

  • time_limit – [s] solver run time limit (per cluster).

  • vehicles – number of vehicles (if None or at the minimum, use the per-cluster default described above; ignored for multi-root problems).

  • seed – random seed for reproducibility (if None, picks a random one).

  • keep_log – attach solver log to the solution graph.

  • repair – iteratively fix crossings (default True).

  • max_retries – maximum repair iterations.

  • balanced – currently not implemented for this solver.

  • scale – factor to scale lengths (LKH manual).

  • runs – number of LKH runs (LKH manual).

  • per_run_limit – [s] LKH per-run time limit.

  • precision – LKH precision parameter.

  • complete – make the full graph over A available (missing edges assumed direct).

  • warmstart – optional previous solution graph used to seed the initial tour. For multi-root instances each cluster receives the portion of the warmstart attached to its root.

Returns:

Solution topology S.