Can we specify forbidden edge constraints in Google OR Tools?

user_5703903 0
Viewed 146

I'm trying to solve a classic Traveling Salesman Problem (TSP). I'm using Google OR Tools default TSP wrapper code. I want some arcs to be forbidden, in the sense that perhaps there is no path between node 10 and node 12. In this instance, I set the value to a large number, like 10^6, but the solver still uses that arc.

I verified that this particular instance has a feasible solution, in the sense that when I run the same code twice or extend the time limit of the solver from 30s to 60s, the solver found a solution that does not use this arc.

The question I have: is there a way to specify a hard constraint that this can't be used, instead of setting the arc cost to ∞? I imagine that in a classic TSP Linear Program, a constraint can be set on the binary decision variable.

or-tools
1 Answers

You have two options:

  1. Create a routing dimension so you can set a vehicle capacity (i.e. vehicle longest distance allowed). Thus any arc whose transit cost is above this capacity is effectively forbidden (vehicle capacity is an hard constraint).

e.g.

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
  transit_callback_index, # you can reuse the same callback use in SetArcCost
  0,  # no slack
  42_000, # vehicle maximum travel distance
  True,  # start cumul to zero
  dimension_name)

now every arcs above 42_000 is forbidden.

  1. You can remove some arcs by tweaking the routing.NextArc() e.g. to remove arc {I,J}
i_index = manager.NodeToIndex(I)
j_index = manager.NodeToIndex(J)
routing.NextVar(i_index).RemoveValue(j_index)

note: you also have the RemoveValues([....]) to suppress a list of outgoing arcs.

user_57102330
Related