2
$\begingroup$

I'm using Google's OR tools in Python to do some optimization in routing in a model where I need to pick just the bare minimum to satisfy a demand.

The situation is, let's say I need 100 units of the product, but there are 300 available in the entire network. My objective is to pick an amount that satisfies that goal, but there is no need to pick up more.

For that, I'm making all nodes optional using the following the following line:

for node in range(1, n_nodes):
    self.routing.AddDisjunction([self.manager.NodeToIndex(node)], 0)

While, on the other hand I'm adding the following restriction to ensure we have the required amount of material at the end, which is essentially that the sum of all capacities is at least the required amount.

capacity = self.routing.GetDimensionOrDie('Capacity')
sum_cargos = capacity.CumulVar(self.routing.End(0))
for vehicle_id in range(1, self.data['num_vehicles']):
   sum_cargos += capacity.CumulVar(self.routing.End(vehicle_id))

solver = self.routing.solver()
solver.AddConstraint(sum_cargos >= self.data['final_cargo'])

In theory with these restrictions the solver should stop visiting nodes after reaching the minimum amount of material, since visiting more nodes would make the objective value worse. However, the algorithm insist in visiting all nodes even with small values of "final_cargo".

Is there some behaviour I might be missing? Or another way to achieve the objective?

$\endgroup$
2
  • $\begingroup$ What happens if you use an equal sign ? solver.AddConstraint(sum_cargos == self.data['final_cargo']) $\endgroup$
    – Kuifje
    Jan 4, 2022 at 17:55
  • $\begingroup$ It becomes infeasible. $\endgroup$ Jan 4, 2022 at 18:08

1 Answer 1

3
$\begingroup$

I found what the problem seemed to be. I had set the first solution strategy to automatic, which generated a first solution using all trucks.

Reading the documentation I found this strategy called "ALL_UNPERFORMED" which does the following.

Make all nodes inactive. Only finds a solution if nodes are optional (are element of a disjunction constraint with a finite penalty cost).

This way it only uses as many nodes as needed.

$\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.