Some quetions for using ALNS

[rlacjfjin]

First of all, thanks a lot for your sharing ALNS solver framework.
I have some questions:

1. In addition to customizing the structure of the solution, destroy and repair operators, Isn't there a need to consider other modules(select, accept and stop conditions)?
2. For the stop criterion, can it be mixed to use(for example, under the time limit condition, because the solution for the improvement is not found for a long time, it is terminated early)? If so, are there any examples to refer to?
3. Are there any articles on similar trade-offs in terms of choosing weights? (Similar to stop criterion)
4. If I want to improve the solver, in addition to the custom module, is it focus on how to choose the weight(such as learn select weights)?

Looking forward to your reply, thank you.

Zhe.

[leonlan]

Hi Zhe,

In addition to customizing the structure of the solution, destroy and repair operators, Isn't there a need to consider other modules(select, accept and stop conditions)?

The most important ingredients for your ALNS heuristic are the solution states and the destroy/repair operators. You don't have to implement your own operator selection scheme, acceptance criterion or stopping criteria, because we have already implemented the most common ones from the literature (RouletteWheel, SimulatedAnnealing, etc.). You could customize your own selection scheme or acceptance criterion, but that is generally less impactful than implementing good destroy/repair operators.

For the stop criterion, can it be mixed to use(for example, under the time limit condition, because the solution for the improvement is not found for a long time, it is terminated early)? If so, are there any examples to refer to?

We have not provided any interface yet to mix stopping criteria, but this should do the trick:

from typing import List

from numpy.random import RandomState

from alns.State import State
from alns.stop.StoppingCriterion import StoppingCriterion


class MixedStop(StoppingCriterion):
    """
    Criterion that stops after a specified maximum runtime.
    """

    def __init__(self, stopping_criteria: List[StoppingCriterion]):
        self.stopping_criteria = stopping_criteria

    def __call__(self, rnd: RandomState, best: State, current: State) -> bool:
        """
        Returns true if at least one of the initialized stopping criteria is satisfied.
        """
        return any(stop(rnd, best, current) for stop in self.stopping_criteria)


from als.stop import NoImprovement, MaxRuntime

stop1 = NoImprovement(10000)
stop2 = MaxRuntime(100)

# This criterion stops when the best solution has not been improved for 10K
# or after 100 seconds of runtime.
stop = MixedStop([stop1, stop2])

Are there any articles on similar trade-offs in terms of choosing weights? (Similar to stop criterion)

I don't know of any articles specifically analyzing the choice of weights, but you might be interested in this paper

If I want to improve the solver, in addition to the custom module, is it focus on how to choose the weight(such as learn select weights)?

That is one possible direction, yes. You could also implement your own custom operator selection scheme (see paper above).

Let me know if you have any other questions!

[rlacjfjin]

Thanks,
But I still have a question:
there are several select strategies and accept criterions. The first idea is to make a combination with these strategy, but it will
take a lot of time. Is there a priority for these policies( select and accept strategy)?

[leonlan]

Thanks, But I still have a question: there are several select strategies and accept criterions. The first idea is to make a combination with these strategy, but it will take a lot of time. Is there a priority for these policies( select and accept strategy)?

I'm not sure if I understand you correctly here. Do you mean if there is any recommended selection scheme and acceptance criterion combination? If so, then yes: the vehicle routing literature generally uses the RouletteWheel selection scheme combined with the SimulatedAnnealing acceptance criterion. But if you are trying to solve a different problem, then it may be that there are other combinations that work better. This is indeed time consuming to figure out, but there is no general answer to which combination works best besides running numerical experiments.

[N-Wouda]

If so, then yes: the vehicle routing literature generally uses the RouletteWheel selection scheme combined with the SimulatedAnnealing acceptance criterion.

[To be fair, particularly the (segmented) roulette wheel is used a lot largely due to inertia/lack of interest in experimenting with alternatives. I doubt it's actually the best method for operator selection - it's just the first thing that's been suggested in the literature.]

[rlacjfjin]

Thanks.
I have no other questions.