VRP ortools how to exclude certain routing set from a specific vehicle

user_4324307 0
Viewed 45

Each vehicle has specific "distaste" of certain delivery routes. We would like to exclude these specific nodes combinations from specific vehicles.

Let's say we have vehicles A and nodes to visit X, Y, Z And if vehicle A does not want [X, Y] and [X] routes we don't want to have these solutions:

Not OK:

  • Vehicle A: [X, Y]
  • Vehicle A: [Y, X] (any order)
  • Vehicle A: [X]

These are OK:

  • Vehicle A: [Y] ie. subset is fine
  • Vehicle A: [X, Y, Z] ie. addition of another node is fine
  • Vehicle A: [Z, Y, X]
  • Vehicle A: [Z, A] and so on.

I understand there are

if nodes[node_index] according to criteria:
    routing.SetAllowedVehiclesForIndex(list(allowed_vehicle_list)), node_index)

Or

routing.VehicleVar(index).SetValues([-1, 2,3,4])

But these completely exclude that vehicle visiting the node. Any idea how to exclude only certain "solution" for a number of vehicles?

or-tools
1 Answers

You can theoretically achieve that using an extra dimension, similar to how a capacity dimension works.

If we take the example of the [X, Y] constraint, You can create a dimension with UnaryTransitCallback in which nodes X, Y, and the end nodes of all vehicles have a value of 1, start nodes have a value of 0, and the rest have a value of -1. All vehicles but the constrained vehicle have a capacity of 4, while the latter has a capacity of 3. In addition to that, all vehicles start already "loaded" with a value of 1. This way a route Start->X->Y->End yields a total value of 4, which is above the constrained vehicle's capacity. adding any additional node at any point of the route or abandoning either X or Y yields a total capacity of 3 or less. It is important to set allow_slack=true for the dimension in this case to prevent the values from going below zero. (making the vehicles start with a value of 1 is for the edge case of a route Start->some_random_node->X->Y->End, the -1 of the random node won't have any effect if the vehicles start with a value of 0)

user_64795060
Related