2-opt local search

jsprit
1

Hi,
I want to implement the 2-opt algorithm and I have no idea how to proceed.
Please, can someone show me a way to do it in Jsprit?
Thank you

2

Hi @anasstaha19,

Jspirit uses Ruin and Recreate heuristic to search the solution space. Which is very different from 2-opt algorithm. You can modify Jsprit to use your own heuristic. But first you need to define your problem. Do you really want to solve VRPTW using 2-opt? I would suggest you to try it on TSP first.
This might help you.

3

HI @Bhoumik_Shah
Thank you for your replay.
Jsprit uses Ruin and Recreate to search for far neighborhoods. During the optimization process, I want to switch between searching for far neighbors and closest one. If I reduce the number of jobs (3% of the total number of jobs) to remove, does it do the trick ?

4

Hi @anasstaha19,

Is you aim searching close neighbors or implementing 2-opt?

If it is searching close neighbors reducing number of jobs to be removed will work.
Also you might want to use Radial Ruin.

5

Interesting. Why not trying to integrate classical local search strategies. I think that you should be able to specify your own SearchStrategy. Implement your 2-opt approach there (e.g. as SearchStrategyModule) and add it to the SearchStrategyManager. Assign a weight and according to the weight, the strategy will be selected in the course of the iterations. It sounds like a nice project.
Additionally, it would be nice to have an overview how these different strategies perform (some nice chart or similar). Actually, I wanted to implementend something like this, but have not had the time yet ;).
EDIT: The future will then be that the weights of the strategies change according to their performance. It would then be an adapted neighborhood search.

6

@Bhoumik_Shah
I think I will use Radial Ruin with low number of removed jobs, it will do the trick.

@stefan
I already implemented a simple adaptative behaviour using StrategySelectedListener , it updates the weights each iteration, not as good as Stefan Ropke did in his work, but it works :slight_smile:.

StrategySelectedListener adaptiveSearch = new StrategySelectedListener() {
    @Override
    public void informSelectedStrategy(DiscoveredSolution discoveredSolution,VehicleRoutingProblem vehicleRoutingProblem, Collection<VehicleRoutingProblemSolution> vehicleRoutingProblemSolutions,VehicleRoutingAlgorithm vra) {
	//if the new solution is accepted after performing ruin and recreate
	if (discoveredSolution.isAccepted()) {
	    // update the weight of the used Strategy by 0.05
            vra.getSearchStrategyManager().informStrategyWeightChanged(discoveredSolution.getStrategyId(),
                    vra.getSearchStrategyManager().getWeight(discoveredSolution.getStrategyId()) + 0.05);
	}
    }
};

Also, Jsprit needs the ruin operator that use historical information in the local search, it has the name of Historical node-pair removal or neighbors graph removal.

7

Hi @anasstaha19,

This sounds interesting.