CODEWITHSUNDEEP
pythonc#or-toolstraveling-salesman
ZantAgg
ZantAgg

Reputation: 97

OR Tools limit visits between two nodes

For example lets say I have something like this:

solver().Add(this.solver.ActiveVar(start) == this.solver.ActiveVar(end));

for a specific route. this means that start index must end on end index. What if I want to limit the number of visits that can happen in between this?

Example if the limit is 2 then only solutions that have something like so will be valid

start-> n1 -> n2 -> end
start -> n1 -> end
start -> end

Normally I would try something involving vehicle constraints, but in this case one vehicle can have multiple starts and ends

Upvotes: 0

Views: 475

Answers (1)

Mizux
Mizux

Reputation: 9301

Few things:

1.

solver().Add(this.solver.ActiveVar(start) == this.solver.ActiveVar(end));

just mean that both locations must be active (i.e. visited) or unvisited (aka 0) (i.e. are part of a disjunction).

  1. What about creating a counter dimension then restrict the difference between both nodes ? In Python should be more or less:
routing.AddConstantDimension(
1, # increase by one at each visit
42, # max count
True, # Force Start at zero
'Counter')
counter_dim = routing.GetDimensionOrDie('Counter')

start = manager.NodeToIndex(start_node)
end = manager.NodeToIndex(end_node)

solver = routing.solver()

# start must be visited at most two nodes before end node
solver.Add(count_dim.CumulVar(start) + 3 >= count_dim.CumulVar(end))

# start must be visited before end
solver.Add(count_dim.CumulVar(start) <= count_dim.CumulVar(end))
  1. Don't get your "vehicle multiple start", each vehicle has only one start. node....

Upvotes: 1

Related Questions