我正在尝试实施特定的 TSP（只有一辆车的 VRP）。我使用了 Google OR-Tools 页面上的 VRP 示例中提供的标准距离矩阵（该页面共有 16 个位置，其中 17 个位置包括仓库）。 出于我的目的，我删除了图中的许多连接。具体来说，从索引0（对应depot的索引）开始，我只能去节点（9 10 11 12 13 14 15 16）。从节点（1 2 3 4 5 6 7 8），我只能去节点 i + 8 或仓库（索引号 17）。最后，从节点 (9 10 11 12 13 14 15 16)，我无法返回到仓库（删除了这些节点与索引 17 之间的连接），并且我无法前往节点 i - 8（例如，从节点 10，我无法到达节点 2)。这和我之前关于是否需要移除depot的问题有关（如果有兴趣，可以回去阅读）。
我的目标是定义一系列要访问的节点，尊重上面定义的约束，以便尽可能接近作为输入提供的路线的最大距离。这个最大距离小于访问所有节点所需的最小距离，因此其中一些节点无法访问。 为了实现这个目标，我首先想到的是添加一个与车辆在
routing.AddDimensionrouting.AddDisjunction"""Capacited Vehicles Routing Problem (CVRP)."""
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"] = [
# fmt: off
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0],
# fmt: on
]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def print_solution(data, manager, routing, assignment):
"""Prints assignment on console."""
print(f"Objective: {assignment.ObjectiveValue()}")
# Display dropped nodes.
dropped_nodes = "Dropped nodes:"
for node in range(routing.Size()):
if routing.IsStart(node) or routing.IsEnd(node):
continue
if assignment.Value(routing.NextVar(node)) == node:
dropped_nodes += f" {manager.IndexToNode(node)}"
print(dropped_nodes)
# Display routes
total_distance = 0
total_load = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
plan_output += f" {node_index} -> "
previous_index = index
index = assignment.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)}\n"
plan_output += f"Distance of the route: {route_distance}m\n"
print(plan_output)
total_distance += route_distance
print(f"Total Distance of all routes: {total_distance}m")
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)
# 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)
return data["distance_matrix"][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Add Distance constraint.
dimension_name = "Distance"
routing.AddDimension(
transit_callback_index,
0, # no slack
7000, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name,
)
# Allow to drop nodes.
for node in range(1, len(data["distance_matrix"])):
routing.AddDisjunction([manager.NodeToIndex(node)], 100)
N = 8
time_dimension = routing.GetDimensionOrDie(dimension_name)
# Definisco una nuova variabile da minimizzare per l'algoritmo
for vehicle_id in range(data["num_vehicles"]):
duration = 5000 - (time_dimension.CumulVar(routing.End(vehicle_id)) - time_dimension.CumulVar(routing.Start(vehicle_id)))
routing.AddVariableMinimizedByFinalizer(duration)
# elimino gli archi che non possono essere percorsi
connessioni_eliminate = {}
for i in range(0, 2*N + 1 + 2*(data["num_vehicles"]) - 1):
connessioni_eliminate[i] = []
for risorsa in range(data["num_vehicles"]):
nodo_considerato = manager.GetStartIndex(risorsa)
connessioni_eliminate[nodo_considerato] = []
for j in range(1, N + 1):
nodo_da_eliminare = manager.NodeToIndex(j)
routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
for risorsa in range(data["num_vehicles"]):
nodo_considerato = manager.GetEndIndex(risorsa)
for j in range(N + 1,2*N + 1):
nodo_precedente = manager.NodeToIndex(j)
routing.NextVar(nodo_precedente).RemoveValue(nodo_considerato)
connessioni_eliminate[nodo_considerato].append(nodo_precedente)
for i in range(1,2*N + 1):
nodo_considerato = manager.NodeToIndex(i)
if nodo_considerato <= N:
for j in range(1,2*N + 1):
nodo_da_eliminare = manager.NodeToIndex(j)
if nodo_da_eliminare == i + N:
continue
else:
routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
else:
nodo_da_eliminare = manager.NodeToIndex(i - N + 1)
routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
for j in range(N + 1,2*N + 1):
nodo_da_eliminare = manager.NodeToIndex(j)
routing.NextVar(nodo_considerato).RemoveValue(nodo_da_eliminare)
connessioni_eliminate[nodo_considerato].append(nodo_da_eliminare)
# 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.FromSeconds(10)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if assignment:
print_solution(data, manager, routing, assignment)
else:
print("No solution found!")
if __name__ == "__main__":
main()
没有解决方案意味着两件事：
为了减少两者的可能性，建议删除硬约束（对时间窗口使用软约束，或相同的车辆约束）并使节点可选（您所做的）。
由于该图具有严格的结构，因此您可以尝试两件事：