ALNS

The top-level alns module exposes the ALNS class, which is used to run the ALNS algorithm.

Finally, the iterate() method on ALNS instances returns a Result object. Its properties and methods can be used to access the final solution and runtime statistics. The Statistics object is also presented below, but it is typically not necessary to interact with it: most things are already available via the Result object.

class alns.ALNS.ALNS(rng: ~numpy.random._generator.Generator = Generator(PCG64) at 0x7FC4D8A2D000)

Implements the adaptive large neighbourhood search (ALNS) algorithm. The implementation optimises for a minimisation problem, as explained in the text by Pisinger and Røpke (2010).

Note

Like the operators passed into the ALNS instance, any registered callback functions (registered via on_best(), on_better(), on_accept(), or on_reject()) should take a candidate State and Generator as arguments. Unlike the operators, no solution should be returned: if desired, the given candidate solution should be modified in-place instead. Note that this solution is not evaluated again (so a rejected candidate solution will stay rejected!).

Parameters

rng: Optional random number generator (RNG). When passed, this generator is used for operator selection and general computations requiring random numbers. It is also passed to the destroy and repair operators, as a second argument.

References

1: Pisinger, D., and Røpke, S. (2010). Large Neighborhood Search. In M. Gendreau (Ed.), Handbook of Metaheuristics (2 ed., pp. 399 - 420). Springer.

Attributes

destroy_operators: Returns the destroy operators set for the ALNS algorithm.
repair_operators: Returns the repair operators set for the ALNS algorithm.

Methods

`add_destroy_operator`(op[, name])	Adds a destroy operator to the heuristic instance.
`add_repair_operator`(op[, name])	Adds a repair operator to the heuristic instance.
`iterate`(initial_solution, op_select, accept, ...)	Runs the adaptive large neighbourhood search heuristic [1], using the previously set destroy and repair operators.
`on_accept`(func)	Sets a callback function to be called when ALNS accepts a new solution as the current incumbent (that is not a new global best, or otherwise improving).
`on_best`(func)	Sets a callback function to be called when ALNS finds a new global best solution state.
`on_better`(func)	Sets a callback function to be called when ALNS finds a better solution than the current incumbent.
`on_reject`(func)	Sets a callback function to be called when ALNS rejects a new solution.

property destroy_operators: List[Tuple[str, _OperatorType]]

Returns the destroy operators set for the ALNS algorithm.

Returns

list: A list of (name, operator) tuples. Their order is the same as the one in which they were passed to the ALNS instance.

property repair_operators: List[Tuple[str, _OperatorType]]

Returns the repair operators set for the ALNS algorithm.

Returns

list: A list of (name, operator) tuples. Their order is the same as the one in which they were passed to the ALNS instance.

add_destroy_operator(op: _OperatorType, name: Optional[str] = None)

Adds a destroy operator to the heuristic instance.

Warning

A destroy operator will receive the current solution state maintained by the ALNS instance, not a copy. Make sure to modify a copy of this state in the destroy operator, created using, for example, copy.copy() or copy.deepcopy().

Parameters

op: An operator that, when applied to the current state, returns a new state reflecting its implemented destroy action. Its second argument is the RNG passed to the ALNS instance.
name: Optional name argument, naming the operator. When not passed, the function name is used instead.

add_repair_operator(op: _OperatorType, name: Optional[str] = None)

Adds a repair operator to the heuristic instance.

Parameters

op: An operator that, when applied to the destroyed state, returns a new state reflecting its implemented repair action. Its second argument is the RNG passed to the ALNS instance.
name: Optional name argument, naming the operator. When not passed, the function name is used instead.

iterate(initial_solution: State, op_select: OperatorSelectionScheme, accept: AcceptanceCriterion, stop: StoppingCriterion, **kwargs) → Result

Runs the adaptive large neighbourhood search heuristic [1], using the previously set destroy and repair operators. The first solution is set to the passed-in initial solution, and then subsequent solutions are computed by iteratively applying the operators.

Parameters

initial_solution: The initial solution, as a State object.
op_select: The operator selection scheme to use for selecting operators. See also the alns.select module for an overview.
accept: The acceptance criterion to use for candidate states. See also the alns.accept module for an overview.
stop: The stopping criterion to use for stopping the iterations. See also the alns.stop module for an overview.
**kwargs: Optional keyword arguments. These are passed to the operators and any registered callbacks.

Returns

Result: A result object, containing the best solution and some additional statistics.

Raises

ValueError: When the parameters do not meet requirements.

References

1: Pisinger, D., & Røpke, S. (2010). Large Neighborhood Search. In M. Gendreau (Ed.), Handbook of Metaheuristics (2 ed., pp. 399 - 420). Springer.
2: S. Røpke and D. Pisinger (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171: 750-775.

on_best(func: _CallbackType): Sets a callback function to be called when ALNS finds a new global best solution state.

on_better(func: _CallbackType): Sets a callback function to be called when ALNS finds a better solution than the current incumbent.

on_accept(func: _CallbackType): Sets a callback function to be called when ALNS accepts a new solution as the current incumbent (that is not a new global best, or otherwise improving).

on_reject(func: _CallbackType): Sets a callback function to be called when ALNS rejects a new solution.

class alns.State.State(*args, **kwargs)

Protocol for a solution state. Solutions should define an objective() member function for evaluation.

Methods

objective()

Computes the state's associated objective value.

objective() → float: Computes the state’s associated objective value.

class alns.State.ContextualState(*args, **kwargs)

Protocol for a solution state that also provides context. Solutions should define objective() and get_context() methods.

Methods

`get_context`()	Computes a context vector for the current state.
`objective`()	Computes the state's associated objective value.

get_context() → ndarray: Computes a context vector for the current state.

class alns.Result.Result(best: State, statistics: Statistics)

Stores ALNS results. An instance of this class is returned once the algorithm completes.

Parameters

best: The best state observed during the entire iteration.
statistics: Statistics collected during iteration.

Attributes

best_state: The best state observed during the entire iteration.
statistics: The statistics object populated during iteration.

Methods

`plot_objectives`([ax, title])	Plots the collected objective values at each iteration.
`plot_operator_counts`([fig, title, legend])	Plots an overview of the destroy and repair operators' performance.

property best_state: State: The best state observed during the entire iteration.

property statistics: Statistics: The statistics object populated during iteration.

plot_objectives(ax: Optional[Axes] = None, title: Optional[str] = None, **kwargs: Dict[str, Any])

Plots the collected objective values at each iteration.

Parameters

ax: Optional axes argument. If not passed, a new figure and axes are constructed.
title: Optional title argument. When not passed, a default is set.
kwargs: Optional arguments passed to ax.plot.

plot_operator_counts(fig: Optional[Figure] = None, title: Optional[str] = None, legend: Optional[List[str]] = None, **kwargs: Dict[str, Any])

Plots an overview of the destroy and repair operators’ performance.

Parameters

fig: Optional figure. If not passed, a new figure is constructed, and some default margins are set.
title: Optional figure title. When not passed, no title is set.
legend: Optional legend entries. When passed, this should be a list of at most four strings. The first string describes the number of times a best solution was found, the second a better, the third a solution was accepted but did not improve upon the current or global best, and the fourth the number of times a solution was rejected. If less than four strings are passed, only the first len(legend) count types are plotted. When not passed, a sensible default is set and all counts are shown.
kwargs: Optional arguments passed to each call of ax.barh.

class alns.Outcome.Outcome(value, names=None, *, module=None, qualname=None, type=None, start=1, boundary=None)

Enum of evaluation outcomes. A candidate solution can be a new global best, a better solution than the current incumbent, just accepted (but not improving anything), or rejected.

Attributes

denominator: the denominator of a rational number in lowest terms
imag: the imaginary part of a complex number
numerator: the numerator of a rational number in lowest terms
real: the real part of a complex number

Methods

`as_integer_ratio`(/)	Return integer ratio.
`bit_count`(/)	Number of ones in the binary representation of the absolute value of self.
`bit_length`(/)	Number of bits necessary to represent self in binary.
`conjugate`	Returns self, the complex conjugate of any int.
`from_bytes`(/, bytes[, byteorder, signed])	Return the integer represented by the given array of bytes.
`to_bytes`(/[, length, byteorder, signed])	Return an array of bytes representing an integer.

BEST = 0: Candidate solution is a new global best.

BETTER = 1: Candidate solution is better than the current incumbent.

ACCEPT = 2: Candidate solution is accepted.

REJECT = 3: Candidate solution is rejected.

class alns.Statistics.Statistics

Statistics object that stores some iteration results. Populated by the ALNS algorithm.

Attributes

destroy_operator_counts: Returns the destroy operator counts, as a dictionary of operator names to lists of counts.
objectives: Returns an array of previous objective values, tracking progress.
repair_operator_counts: Returns the repair operator counts, as a dictionary of operator names to lists of counts.
runtimes: Returns an array of iteration run times (in seconds).
start_time: Return the reference start time to compute the runtimes.
total_runtime: Return the total runtime (in seconds).

Methods

`collect_destroy_operator`(operator_name, outcome)	Collects a score (index) for a used destroy operator.
`collect_objective`(objective)	Collects an objective value.
`collect_repair_operator`(operator_name, outcome)	Collects a score (index) for a used repair operator.
`collect_runtime`(time)	Collects the time one iteration took.

property objectives: ndarray: Returns an array of previous objective values, tracking progress.

property start_time: float: Return the reference start time to compute the runtimes.

property total_runtime: float: Return the total runtime (in seconds).

property runtimes: ndarray: Returns an array of iteration run times (in seconds).

property destroy_operator_counts: DefaultDict[str, List[float]]

Returns the destroy operator counts, as a dictionary of operator names to lists of counts. Such a list consists of four elements, one for each possible outcome, and counts the number of times that the application of that operator resulted in such an outcome.

Returns

defaultdict: Destroy operator counts.

property repair_operator_counts: DefaultDict[str, List[float]]

Returns the repair operator counts, as a dictionary of operator names to lists of counts. Such a list consists of four elements, one for each possible outcome, and counts the number of times that the application of that operator resulted in such an outcome.

Returns

defaultdict: Repair operator counts.

collect_objective(objective: float)

Collects an objective value.

Parameters

objective: The objective value to be collected.

collect_runtime(time: float)

Collects the time one iteration took.

Parameters

time: Time in seconds.

collect_destroy_operator(operator_name: str, outcome: Outcome)

Collects a score (index) for a used destroy operator. This maintains count of the number of times this operator was used, and what result came from its use.

Parameters

operator_name: Operator name. This was set when the operator was passed to the ALNS instance.
outcome: Score enum value used for the various iteration outcomes.

collect_repair_operator(operator_name: str, outcome: Outcome)

Collects a score (index) for a used repair operator. This maintains count of the number of times this operator was used, and what result came from its use.

Parameters

operator_name: Operator name. This was set when the operator was passed to the ALNS instance.
outcome: Score enum value used for the various iteration outcomes.

alns.show_versions.show_versions()

This function prints version information that is useful when filing bug reports.

Examples

Calling this function should print information like the following (dependency versions in your local installation will likely differ):

>>> import alns
>>> alns.show_versions()
INSTALLED VERSIONS
------------------
      alns: 5.0.1
     numpy: 1.23.4
matplotlib: 3.5.1
    Python: 3.9.9