Search code examples
pythonc#or-toolstraveling-salesman

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

Solution

  • 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....