Minimize capacity of vehicles in VRP with OR Tools

Question

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?

Answer 1

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.