optiwindnet.baselines.lkh¶

Module Contents¶

optiwindnet.baselines.lkh.lkh(A: networkx.Graph, *, capacity: int, time_limit: float, scale: float = 100000.0, vehicles: int | 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) → networkx.Graph[source]¶

Lin-Kernighan-Helsgaun via LKH-3 binary. Open Capacitated Vehicle Routing Problem.

A must be normalized - use as_normalized() before calling this.

http://akira.ruc.dk/~keld/research/LKH-3/

Parameters:

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

  • capacity – maximum vehicle capacity

  • time_limit – [s] solver run time limit

  • scale – factor to scale lengths (should be < 1e6)

  • vehicles – number of vehicles (if None, use the minimum feasible)

  • runs – consult LKH manual

  • per_run_limit – [s] consult LKH manual

  • precision – consult LKH manual

  • complete – make the full graph over A available (links not in A assumed direct)

  • keep_log – save the LKH text output to graph attr ‘method_log’

  • seed – for the pseudo-random number generator (if None: random seed)

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, 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]¶

Iterate until crossing-free solution is found (lkh() wrapper).

See the docstring of lkh() for details on the LKH-3 meta-heuristic.

The vehicle-routing solver LKH-3 may produce routes with crossings, this wrapper ensures the output is crossing-free. Each time a solution with a crossing is produced, a repair attempt is made. Failing that, one of the offending edges is removed from A and the solver is called again. In the same way as lkh(), it is recommended to pass a normalized A.

Parameters:

  • * – see lkh()

  • max_retries – maximum number of additional calls to lkh() to avoid crossings

Returns:

Solution topology S