I'm trying to solve a VRP problem allowing dropping nodes through penalties and multiple depots.
Code works fine with penalties and vehicles starting and ending at the same depots:
data['num_vehicles'] = 2
data['start'] = [0, 4]
data['end'] = [0, 4]
Code works fine with vehicles starting and ending at different depots, commenting the for loop to AddDisjunction for penalties (without allowing dropping nodes):
data['num_vehicles'] = 2
data['start'] = [0, 4]
data['end'] = [0, 9]
.........................
#for node in range(1, len(data['penalties'])):
# routing.AddDisjunction([manager.NodeToIndex(node)], data['penalties'][node])
But with vehicles starting and ending at different depots and trying to add penalties to allow dropping nodes, python crashes with the error (debugging I can see that fails at adding the penalty of the different end depot):
F00-1 -1:-1:-1.000244 24944 routing.cc:1622] Check failed: kUnassigned != indices[i] (-1 vs. -1)
I cannot find any reference about this error. I looked at routing.cc source code around line 1622, but I cannot see any relation with the error. I need help to fix the problem.
Here is the souce code:
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[0, 2253, 2479, 2792, 4707, 6128, 1567, 5643, 1234, 3345, 1827],
[1731, 0, 2193, 2507, 3624, 5040, 3467, 2921, 5791, 1546, 2345],
[1867, 2112, 0, 676, 4406, 5824, 988, 4567, 2134, 4453, 2123],
[2339, 2585, 893, 0, 4879, 6302, 1543, 1298, 6890, 1456, 5623],
[4464, 3766, 5935, 4957, 0, 1749, 987, 3212, 3451, 5212, 3321],
[6568, 5862, 8023, 7055, 2148, 0, 4567, 2124, 4321, 3212, 1234],
[731, 2193, 2507, 7624, 4040, 4467, 0, 2621, 3791, 1567, 1345],
[1731, 3193, 1507, 3624, 6040, 2467, 4921, 0, 5791, 6723, 1345],
[2731, 3193, 2507, 6204, 5040, 1467, 2210, 6791, 0, 2567, 6421],
[3345, 1543, 4421, 1531, 5213, 3215, 1512, 6213, 2431, 0, 5673],
[1832, 2421, 2144, 5232, 3214, 1234, 1432, 1231, 6321, 5461, 0],
]
data['node_time'] = [0, 7200, 3600, 5400, 0, 5400, 7200, 3600, 7200, 0, 300]
data['num_vehicles'] = 2
data['start'] = [0, 4]
data['end'] = [0, 9]
# Penalizaciones por no visitar nodos (drop nodes) en caso de que no tenga solución:
# MAXINT 0x7FFFFFFFFFFFFFF: Hace obligatoria la visita al nodo, no se puede eliminar de la solución
# 1000000: Se puede no visitar el nodo con penalización. La penalización debe ser grande, mayor que 10x veces el mayor tiempo de visita, para evitar que salga mas rentable dejar caer el nodo que pagar la penalización
# 0: En los nodos "depósito" de vehículos, no son visitas intermedias sino inicio y fin de la ruta.
data['penalties'] = [0, 1000000, 1000000, 1000000, 0, 0x7FFFFFFFFFFFFFF, 0x7FFFFFFFFFFFFFF, 1000000, 1000000, 0, 1000000]
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
# Display dropped nodes.
dropped_nodes = 'Nodos sin visitar:'
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if solution.Value(routing.NextVar(node)) == node:
dropped_nodes += ' {}'.format(manager.IndexToNode(node))
print(dropped_nodes + '\n')
max_route_distance = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Ruta para vehículo {}:\n'.format(vehicle_id)
route_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Tiempo de la ruta: {}sg\n'.format(route_distance)
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print('Maximo tiempo de las rutas: {}sg'.format(max_route_distance))
def main():
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_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)
# Create and register a transit callback.
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
tiempo_desplazamiento = data['distance_matrix'][from_node][to_node]
tiempo_ejecucion = data['node_time'][to_node]
return tiempo_desplazamiento + tiempo_ejecucion
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Distance constraint.
routing.AddDimension(
transit_callback_index,
0, # no slack
27000, # vehicle maximum travel distance (7.5 hours, in seconds)
True, # start cumul to zero
'Time')
distance_dimension = routing.GetDimensionOrDie('Time')
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Allow to drop nodes.
for node in range(1, len(data['penalties'])):
routing.AddDisjunction([manager.NodeToIndex(node)], data['penalties'][node])
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 30
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
else:
print('No solution found!')
if __name__ == '__main__':
main()
I've posted the question in Ortools Google Group, with additional research: [https://groups.google.com/g/or-tools-discuss/c/s3PfgLVZpj0][1]
Code seems to be working excluding start and end nodes from the disjunction as explained on that post, but I asked for more info to understand how it works.
In routing.h there is a comment about AddDisjunction
/// 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.
In the for loop to add nodes to the disjunction, excluding start and end nodes seems to be working:
# Allow to drop nodes.
for node in range(0, len(data['distance_matrix'])):
if(node in data['start'] or node in data['end']):
continue
else:
routing.AddDisjunction([manager.NodeToIndex(node)], data['penalties'][node])