5
$\begingroup$

I have an initial solution to a CVRP instance which I am setting as input to the solver. The solver as expected returns an improved solution. I have a few questions regarding the solver.

  • How does the solver improve upon the solution when I am not using any particular metaheuristic?. Does it use a mixture of meta-heuristics or just automatically select one?

  • This particular one is very baffling to me. When I set multiple metaheuristics (Tabu, SA, etc.) and even the time limits, the solver always returns the same solution for every one of them, and that too instantly. The solutions returned in the first case and this one is the same for every instance. Is this expected behavior?

    It seems that the metaheuristics and the time limits have no effect on the solver. The solver seems to converge on some particular solution very quickly and stops there.

Relevant Code :

const Assignment* initial_solution =
        routing.ReadAssignmentFromRoutes(data.initial_routes, true);

RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();

// Uncommenting the following has no effect on the final solution

/*
searchParameters.set_local_search_metaheuristic(
        LocalSearchMetaheuristic::TABU_SEARCH);
    searchParameters.mutable_time_limit()->set_seconds(30);
*/

const Assignment* solution = routing.SolveFromAssignmentWithParameters(
        initial_solution, searchParameters);

Edit : Thanks to @Pedrinho's answer, this is how the problem should be tackled.

RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();

searchParameters.set_local_search_metaheuristic(
        LocalSearchMetaheuristic::TABU_SEARCH);
    searchParameters.mutable_time_limit()->set_seconds(30);

routing.CloseModelWithParameters(searchParameters);

const Assignment* initial_solution =
        routing.ReadAssignmentFromRoutes(data.initial_routes, true);

const Assignment* solution = routing.SolveFromAssignmentWithParameters(
        initial_solution, searchParameters);
$\endgroup$

1 Answer 1

2
$\begingroup$
  1. I believe the default is a greedy descent which would be in line with your observations of very fast convergence. In general, the heuristics are a combination of local search and constraint programming. You might find more information here and here.

  2. If you provide an initial solution, you first need to close your model before solving. See a similar question here and a github issue here.

    routing.CloseModelWithParameters(searchParameters);

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.