Keep n unique and most effective alternatives

[frinux]

This is either a question or a feature request.

It would be handy to keep not only the best solution, but also n other feasible and unique alternatives (sorted by cost).

As pointed by Hung_Do_Xuan in the forum, a solution exist by writing an IterationEndsListener and keep these alternatives in memory:

algorithm.addListener(new IterationEndsListener() {
        @Override
        public void informIterationEnds(int i, VehicleRoutingProblem problem, Collection<VehicleRoutingProblemSolution> iterationSolutions) {
            VehicleRoutingProblemSolution iterationSolution = Solutions.bestOf(iterationSolutions);
            if(iterationSolution != null && !alternativeExists(iterationSolution))
                    if(MAX_ALTERNATIVES > alternatives.size()) {
                        alternatives.add(iterationSolution);
                    } else {
                        alternatives.add(iterationSolution);
                        alternatives.sort(solutionComparator);
                        alternatives.remove(alternatives.size() - 1);
                    }
        }
    });

However, I'm not sure about the consequences of this code in jSprit in terms of accuracy and performance.

Could it be possible, through a native feature, to keep safely all these alternatives and retrieve theme (for example with a Solutions.alternatives() method)?

Thanks for considering this proposal.

[oblonski]

I doubt that these solutions are "good" alternatives. A more promising approach might be to solve your problem with different random numbers, i.e. different roots for the random number generator. This way, the algorithm walks different paths through the solution space and might provide you with "good" alternatives, but still it does not guarantee alternatives at all.

[frinux]

I'm not sure I understood the Ruin and Recreate then.

I thought the idea was to iterate over feasible solutions, alter (ruin) them to find new and better solution. Thus, storing the 10 best (as best score) iteration solutions should return what I'm looking for.

In parallel, I tried to follow your advice (and your implementation there):

package com.fiftytruck.solver.jsprit.util;

import java.util.Random;

public class RandomNumberGeneration {

    private static Random random = new Random(generateRandomSeed());

    public static Random newInstance() {
        return new Random(generateRandomSeed());
    }

    public static Random getRandom() {
        return random;
    }

    public static void setSeed(long seed) {
        random.setSeed(seed);
    }

    public static void reset() {
        reset(random);
    }

    public static void reset(Random random) {
        random.setSeed(generateRandomSeed());
    }

    private static long generateRandomSeed() {
        return new Random().nextLong();
    }

}

And in my main():

    Random randomNumberGenerator = RandomNumberGeneration.getRandom();

    VehicleRoutingAlgorithm algorithm = Jsprit.Builder.newInstance(problem)
        .setStateAndConstraintManager(stateManager, constraintManager)
        .setProperty(Jsprit.Parameter.FIXED_COST_PARAM.toString(), "0.")
        .setRandom(randomNumberGenerator)
        .buildAlgorithm();

Run on a simple case (1 truck, 3 shipments), tried with small (10) or standard (2000) iterations, the solution is always the same (even if other solutions are feasible, but cost more).

[oblonski]

It depends on what you expect from alternatives. If you just want to know which tentative solutions are used by the algorithm to find the final solution, you can implement https://github.com/graphhopper/jsprit/blob/master/jsprit-core/src/main/java/com/graphhopper/jsprit/core/algorithm/listener/StrategySelectedListener.java and add it with .addListener(...) to your algorithm. This way you can store all accepted solutions for your own.

[frinux]

The idea is to fetch the n best solutions found during the solving process (I call them "alternatives"). I'm aware that depending on the initial solution found, we may be already near the optimum, so it would generate few alternatives.

For instance, given this problem:

I would expect a list of n solutions, sorted by cost:

Solution1

Solution2

For now, with IterationEndsListener, I'm able to store these only 2 solutions. It seems however that all feasible solutions (for instance start -> pickup(5) => delivery (5) -> end) are not evaluated. Maybe is it related to the way solutions are ruined?

[oblonski]

It does not evaluate all feasible solution. It is actually the purpose the meta-heuristic to avoid that, but to search for promising solutions in the search space.