VRP with arbitrary start and end locations max distance "directly" from end of a route to start.

[ubuntumaroon]

What language and solver does this apply to?
Python

Describe the problem you are trying to solve.
I am solving a pickup and delivery problem with multiple vehicles, and the vehicles can start/end at any arbitrary start and end locations.
But we do not want driver takes long time to drive back from end location to start location. Limit the max distance travel directly from end node of a vehicle to start of a vehicle.
distance_matrix[end_node][start_node] < MAX
There is no limitation on the cumVar of a vehicle.

For example, we have solution:
0 -> 1- > 2 -> 3->4->0, real start node: 1, end node 4, we want the solution meet: distance_matrix[4][1] < MAX

Tried to add constraints using: routing.solver().Add(), but could not get the actual start node and end not. As for all vehicles the start/end node index are the dummy 0.
Is it possible to get second node and the node before the last?

Thank you very much!

[Mizux]

1. To add constraint you must use index not node aka first you should use manager.NodeToIndex() BUT this is not allowed for start/end node since this is not a bijection, like you spot out node 0 is use by several vehicles so you must use
   routing.Start(vehicle_idx) and routing.End(vehicle_idx) respectively.

2. you could use routing.NextVar(routing.Start(vehicle_index)) to get the index of the node after the vehcile start node.

[ubuntumaroon]

Thank you very much @Mizux .

Still could not make it work:

1. not able to get the last node before the dummy depot 0.
2. could not add constraints in following way:
   solver().Add(time_matrix[manager.IndexToNode(end_node), manager.IndexToNode(start_node)] < max_distance)
TypeError: in method 'Solver_AddConstraint', argument 2 of type 'operations_research::Constraint *const'

Do you have suggestion how to apply such constraint?

Thanks

[Mizux]

I'd try channeling...

# eg for vehicle k to do for each vehicle -_-
start = routing.Start(k)
end = routing.End(k)

# Create is_next_of_start[node]
is_next_of_start = dict()
for node in nodes:
  if node == depot:
    continue
  index = manager.NodeToIndex(node)
  # Create a BooleanVar: True if index is the next node of start, false otherwise
  is_next_of_start[node] = routing.NextVar(start) == index

# Create is_previous_of_end[node]
is_previous_of_end = dict()
for node in nodes:
  if node == depot:
    continue
  index = manager.NodeToIndex(node)
  # Create a BooleanVar: True if index is the previous node of end, false otherwise
  is_previous_of_end[node] = routing.NextVar(index) == end

# create expr[(i, j)] : is_next_of_start[i] * is_previous_of_end[j] * distance[j][i]
# only one pair (i, j) will have is_next_of_start[i] * is_previous_of_end[j] = 1 all others will be zero
# only the sum of all expr is equal to distance[j][i]
exprs = []
for from_node in nodes:
  if from_node == depot:
    continue
  for to_node in nodes:
    if to_node == depot or to_node == from_node: # ignore since distance(i,i) == 0
      continue
    exprs.append(is_next_of_start[from_node] * is_previous_of_end[to_node] * distance[to_node][from_node])

# Lastly, add our constraint distance[j][i] < MAX
routing.solver().Add(sum(exprs) <= MAX)

[ubuntumaroon]

Thank you very much! I will try this solution.

[ubuntumaroon]

@Mizux It works, thank you very much!
The speed slows down a lot when number of node more than 100.
100 node with pickup and delivery: 3 seconds before adding the constraints, after more than 20 minutes.

Trying to find a way to improve the speed.