CODEWITHSUNDEEP
pythonor-toolsvehicle-routing
Cakra1337
Cakra1337

Reputation: 23

Google OR Tools does not return solution if First solution strategy = SAVINGS

I'm currently learning on how to use Google OR-Tools, specifically on the routing problem. I want to try to use Clarke and Wright Savings Algorithm by setting the first solution strategy equals SAVINGS as we can see below

search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.SAVINGS)

but when i try executing the program, it returns nothing. what did i do wrong?

my code is exactly like the code here https://developers.google.com/optimization/routing/cvrp

Thanks!

Upvotes: 0

Views: 747

Answers (2)

watchdogs132
watchdogs132

Reputation: 331

Sometimes Parallel Savings can find the solution. The default is the Sequential version.

search_parameters.savings_parallel_routes = True

Upvotes: 0

Laurent Perron
Laurent Perron

Reputation: 11014

First solutions heuristics are exactly that, heuristics. They cannot fail on a pure problem.

When adding constraints, they all have blind spots and can fail to find a solution, especially if constraints are tight.

The best solution is to:

  • relax time windows with soft constraints
  • allow node yo be optional

This way, the solver usually find a first solution, albeit a bad one, and then can use LS to improve it.

Upvotes: 1

Related Questions