optiwindnet.baselines.lkh¶

Module Contents¶

optiwindnet.baselines.lkh.lkh(*args, **kwargs) → networkx.Graph[source]¶

DEPRECATED: backward-compatible alias of _lkh(). Use lkh3() instead.

Kept for callers that relied on the previous low-level single-root LKH-3 API. New code should use lkh3() (the high-level wrapper that mirrors hgs_cvrp() and supports both single- and multi-root instances).

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, warmstart: networkx.Graph | None = None) → networkx.Graph[source]¶

Solve the OCVRP 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). Normalization of 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 to the minimum feasible value per cluster (a warning is issued if a different value is requested).

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 minimum feasible; 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.

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

DEPRECATED: backward-compatible alias of lkh3(). Use it instead.

Earlier this function pre-pruned bad links and iterated lkh(); this behaviour is now part of lkh3(), which also supports multi-root instances.