Or-Tools version 9.0.9048. Python 3.8.8
Complete code posted at StackOverflow:
https://stackoverflow.com/questions/71017337/ortools-vrp-error-when-trying-to-merge-penalties-and-different-start-end-depotsHello
I'm trying to solve a VRP problem with different start and end nodes and allowing dropping nodes through penalties.
Code works fine with the same start/end nodes (for one o more vehicles, no difference) and penalties to allow dropping nodes.
Code works fine with vehicles starting and finishing route at teh same node, without allowing dropping nodes.
But code crashes joining both conditions in the foor loop when "node" value is equal to the end node (in the example, where node is 3) with the error:
F00-1 -1:-1:-1.000244 24944 routing.cc:1622] Check failed: kUnassigned != indices[i] (-1 vs. -1)
Code sample:
data['num_vehicles'] = 1
data['start'] = [0]
data['end'] = [3]
..................
#Allow to drop nodes (from google tutorial about VRP)
for node in range(1, len(data['distance_matrix'])):
routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
At StackOverflow post, Laurent answered me to use routing.Start(vehicle_id) and routing.End(vehicle_id) to get start and end node values. Without a clear understanding of this answer, I tried to show these values after creating the routing model:
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['start'], data['end'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
print('{}'.format(routing.Start(0)) + '-> ' + '{}'.format(routing.End(0)))Result: 0-> 10
So, it seems that start node is the value of the data provided, but end node is "moved" to he last position of the array (distance matrix has 11 values, so 10 is the last index).
Where start and end nodes are the same, apparently a new node is added for the end. If start=end=0, then the result of routing.Start(0) is 0 and routing.End(0) is 11 (a node after the last one).
In file routing.h I've seen the following comment:
/// Adds a disjunction constraint on the indices: exactly 'max_cardinality' of
/// the indices are active. Start and end indices of any vehicle cannot be
/// part of a disjunction.
So I've tried to avoid adding start and end nodes to the disjunction, but program crashes as before:
for node in range(1, len(data['distance_matrix'])):
if(node==routing.Start(0) or node==routing.End(0):
continue
else:
routing.AddDisjunction([manager.NodeToIndex(node)], data['penalty'][node])
But using the original data values for start and end nodes, it works (apparently):
for node in range(0, len(data['distance_matrix'])):
if(node==data['start'][0] or node==data['end'][0]):
continue
else:
routing.AddDisjunction([manager.NodeToIndex(node)], data['penalty'][node])
I would like to understand how this works, to figure out how to solve the error:
1- In the Ortools official samples, does for loop to AddDisjunction begin at 1 to avoid add starting node 0 to the disjunction?. If starting node is not 0, the for loop should be from 0 to len(data['distance_matrix'])-1.
2- Does Python crash when trying to add an end node to a disjunction?
3- Is there a new structure in the model moving end nodes to the last positions, keeping the order of the rest nodes?
4- Original node order must be passed to AddDisjunction, avoiding starting and end nodes?
5- Does AddDisjunction work as I explained here, or am I wrong?
Thanks in advance!!!!