尝试合并惩罚和不同的起点终点站时 Ortools VRP 错误
Ortools VRP error when trying to merge penalties and different start-end depots
我正在尝试解决一个 VRP 问题，该问题允许通过惩罚和多个 depot 删除节点。
代码适用于处罚和车辆在同一个站点开始和结束：
data['num_vehicles'] = 2
data['start'] = [0, 4]
data['end'] = [0, 4]
代码适用于在不同站点开始和结束的车辆，将 for 循环注释为 AddDisjunction 以进行惩罚（不允许删除节点）：
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])
但是车辆在不同的站点开始和结束并试图增加惩罚以允许丢弃节点，python 崩溃并出现错误（调试我可以看到添加不同末端站点的惩罚失败） :
F00-1 -1:-1:-1.000244 24944 routing.cc:1622] 检查失败：kUnassigned != indices[i] (-1 vs. -1)
我找不到关于此错误的任何参考资料。我查看了第 1622 行附近的 routing.cc 源代码，但我看不出与该错误有任何关系。我需要帮助来解决这个问题。
源代码如下：
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()
我已经 post在 Ortools Google 组中编辑了这个问题，并进行了额外的研究：
[https://groups.google.com/g/or-tools-discuss/c/s3PfgLVZpj0][1]
代码似乎可以正常工作，如 post 中所述，从析取中排除开始和结束节点，但我要求提供更多信息以了解其工作原理。
对于自定义开始和结束，您应该使用 Routing.Start(vehicle_index) 和 Routing.End(vehicle_index) 来获取这些节点的索引。
在 routing.h 中有一条关于 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.
在 for 循环中将节点添加到析取中，排除开始和结束节点似乎有效：
# 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])
我正在尝试解决一个 VRP 问题，该问题允许通过惩罚和多个 depot 删除节点。
代码适用于处罚和车辆在同一个站点开始和结束：
data['num_vehicles'] = 2
data['start'] = [0, 4]
data['end'] = [0, 4]
代码适用于在不同站点开始和结束的车辆，将 for 循环注释为 AddDisjunction 以进行惩罚（不允许删除节点）：
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])
但是车辆在不同的站点开始和结束并试图增加惩罚以允许丢弃节点，python 崩溃并出现错误（调试我可以看到添加不同末端站点的惩罚失败） :
F00-1 -1:-1:-1.000244 24944 routing.cc:1622] 检查失败：kUnassigned != indices[i] (-1 vs. -1)
我找不到关于此错误的任何参考资料。我查看了第 1622 行附近的 routing.cc 源代码，但我看不出与该错误有任何关系。我需要帮助来解决这个问题。
源代码如下：
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()
我已经 post在 Ortools Google 组中编辑了这个问题，并进行了额外的研究： [https://groups.google.com/g/or-tools-discuss/c/s3PfgLVZpj0][1]
代码似乎可以正常工作，如 post 中所述，从析取中排除开始和结束节点，但我要求提供更多信息以了解其工作原理。
对于自定义开始和结束，您应该使用 Routing.Start(vehicle_index) 和 Routing.End(vehicle_index) 来获取这些节点的索引。
在 routing.h 中有一条关于 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.
在 for 循环中将节点添加到析取中，排除开始和结束节点似乎有效：
# 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])