Other single-trajectory heuristics

The alns package supports several other single-trajectory heuristics as special cases, in addition to ‘just’ ALNS. This page explains how to implement iterated local search (ILS), variable neighbourhood search (VNS), and the greedy randomised adaptive search procedure (GRASP) using alns.

ILS

ILS is an iterative algorithm that, in each iteration, performs two things:

  1. Perturb the current solution;

  2. Perform local search on the perturbed solution.

ILS is easy to implement in alns by having one destroy operator that is responsible for the perturbation, and one repair operator that performs the local search. Since there is just one destroy and repair operator pair, the operator selection scheme is not relevant. We suggest to use the simplest scheme: RouletteWheel. At a high level, one could thus implement the following:

from alns import ALNS, State


def perturb(sol: State, rnd_state) -> State:
    <perturb sol>
    return <perturbed solution>


def local_search(sol: State, rnd_state) -> State:
    <perform local search around sol>
    return <improved solution>


alns = ALNS()
alns.add_destroy_operator(perturb)
alns.add_repair_operator(local_search)

Where the choice of acceptance and stopping criterion are left to the user.

VNS

VNS is an iterative algorithm that, in each iteration, performs the following steps given a neighbourhood \(\mathcal{N}_k\):

  1. Perturb the current solution (possibly using \(\mathcal{N}_k\));

  2. Perform local search in \(\mathcal{N}_k\) on the perturbed solution;

  3. Change neighbourhoods.

The first two steps look a lot like ILS. For the third, we need a bit more: an object to store \(k\) and a list of neighbourhoods. Assume we have this list of neighbourhoods available. Then, a high-level implementation could look like:

from dataclasses import dataclass

from alns import ALNS, State


@dataclass
class Neighbourhood:
    neighbourhoods: list
    k: int


def perturb(sol: State, rnd_state, neighbourhood: Neighbourhood) -> State:
    <perturb sol, possibly using neighbourhood k>
    return <perturbed solution>


def local_search(
    sol: State,
    rnd_state,
    neighbourhood: Neighbourhood
) -> State:
    <perform local search around sol using neighbourhood k>

    # Set next neighbourhood: if we found an improving solution, the
    # callback will reset the neighbourhood; else we start from the next
    # neighbourhood in the following iteration.
    neighbourhood.k = min(
        neighbourhood.k + 1,
        len(neighbourhood.neighbourhoods)
    )

    return <improved solution>


def on_best(sol: State, rnd_state, neighbourhood: Neighbourhood):
    # New best solution: start again from first neighbourhood.
    neighbourhood.k = 1


neighbourhood = Neighbourhood(<neighbourhoods>, 1)
alns = ALNS()
alns.on_best(on_best)
alns.add_destroy_operator(perturb)
alns.add_repair_operator(local_search)

res = alns.iterate(..., neighbourhood=neighbourhood)

This example uses two somewhat advanced features: first, we use the on_best() callback function to reset the neighbourhoods in case of improvement. Second, we use the flexible **kwargs argument of iterate() to pass the neighbourhood object to the operators.

We again suggest to use RouletteWheel, and leave the choice of acceptance and stopping criterion to the user.

GRASP

GRASP is an iterative algorithm that performs a greedy randomised improvement step in each iteration. This greedy randomised step could start from an empty solution, or from a partial solution. This suggests one destroy operator that is responsible for either generating an empty solution, or a partially broken solution that can be repaired by a greedy randomised repair operator. At a high level, one could thus implement the following:

from alns import ALNS, State


def destroy(sol: State, rnd_state) -> State:
    <destroy sol to some fixed degree of destruction (possibly completely)>
    return <destroyed solution>


def greedy_randomised_repair(sol: State, rnd_state) -> State:
    <do greedy randomised repair around sol>
    return <improved solution>


alns = ALNS()
alns.add_destroy_operator(destroy)
alns.add_repair_operator(greedy_randomised_repair)

We again suggest to use RouletteWheel, and leave the choice of acceptance and stopping criterion to the user.