OR-Tools: how to define node that not possible to visit in VRP/CVRP/VRPTW?

user_3462243 0
Viewed 174

im trying this vrp example
From my understanding, we must have 2d array to define distance matrix between all nodes
But for my demand, there is few nodes wont have distance matrix between, like this graph

enter image description here

The distance matrix array will be:

public final long[][] distanceMatrix = {
         {0, 2, 1, 0, 0},
         {0, 0, 0, 2, 1},
         {0, 1, 0, 0, 0},
         {0, 0, 0, 0, 3},
         {0, 0, 0, 0, 0},
  };

The issue is that for the distance matrix array, we must have int number between all nodes, so for two nodes that dont have direct path between (like A->D) i use 0, but OrTool will understand the cost to travel between those two nodes is zero. and the solver always choose that path to go.
So is there any support from ortool library to declare this kind on directional graph?
Thanks

or-tools
2 Answers

To forbid an arc you have basically two ways:

  1. Using a Distance Dimension and a value above the vehicle max capacity. e.g. suppose you have a distance dimension:
transit_callback_index = routing.RegisterTransitCallback(distance_callback)

routing.AddDimension(
  transit_callback_index,
  0, # no slack for distance, can be use as waiting time for Time dimension
  42,  # maximum distance a vehicle can travel
  True,  # force start cumul to zero, i.e. vehicle start a km 0
  "Distance"
)
...

As you can see, here 42 is the limit for vehicles SO if in your distance matrix you use 43 no vehicle could take this arc since it is above the vehicle capacity (ed above the upper bound of the CumulVar domain). Thus you could write your distance matrix as:

public final long[][] distanceMatrix = {
         {43, 2, 1,43,43},
         {43,43,43, 2, 1},
         {43, 1,43,43,43},
         {43,43,43,43, 3},
         {43, 3,43,43,43},
  };

note: your SetArcCost() and AddDimension() can use the same registered evaluator.

  1. You can set the list of allowed next nodes. For each node you can define a list a allowed nodes (by default all nodes) e.g. here you have:
next = {
  [A, [B, C]],
  [B, [E, D]],
  [C, [B]],
  [D, [E]],
  [E, []]}

note(instead of A-E you must use 0-4)

Then you can use:

for node, l in next:
  node_index = manager.NodeToIndex(node)
  next_indices = [node_index] # need itself in case node is dropped
  for next_node in l:
    next_indices.append(manager.NodeToIndex(next_node))
  routing.NextVar(node_index).SetValues(next_indices)
user_57102330

Instead of 0, I would try to initialize those nodes with an unaffordable cost, eg int64.Maxvalue

user_41301610
Related