我正在使用这个 python 库或工具：https ://developers.google.com/optimization/routing/tsp/vehicle_routing （代码可以在这里找到）。
问题是，当您运行解决方案时，它会为您提供一条覆盖所有节点的路径。但是我的项目需要对节点之间的路径进行限制。例如，如果您在节点 {3} 上，您可能无法前往节点 {18}。或者以另一种方式，如果您在节点 {5}，您只能前往节点 {1、12、14}。我不确定如何将此约束添加到当前代码示例中。
请允许我进一步解释...
如果我们看这张图：
您可以在此处看到此图的表示形式： https ://www.datacamp.com/community/tutorials/networkx-python-graph-tutorial
显然，在这个问题中，您不能从其他节点前往某些节点。我在 google or-tools 示例中使用此图表中的数据来获得车辆路线问题的解决方案。
这是我的代码：
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
import pandas as pd
from sklearn import preprocessing
def distance(x1, y1, x2, y2):
dist = ((x1 - x2)**2 + (y1 - y2)**2)**(1/2)
return dist
class CreateDistanceCallback(object):
"""Create callback to calculate distances between points."""
def __init__(self, locations):
"""Initialize distance array."""
size = len(locations)
self.matrix = {}
for from_node in range(size):
self.matrix[from_node] = {}
for to_node in range(size):
x1 = locations[from_node][0]
y1 = locations[from_node][1]
x2 = locations[to_node][0]
y2 = locations[to_node][1]
self.matrix[from_node][to_node] = distance(x1, y1, x2, y2)
def Distance(self, from_node, to_node):
return int(self.matrix[from_node][to_node])
# Demand callback
class CreateDemandCallback(object):
"""Create callback to get demands at each location."""
def __init__(self, demands):
self.matrix = demands
def Demand(self, from_node, to_node):
return self.matrix[from_node]
def main():
# Create the data.
data = create_data_array()
locations = data[0]
demands = data[1]
num_locations = len(locations)
depot = 0 # The depot is the start and end point of each route.
num_vehicles = 1
# Create routing model.
if num_locations > 0:
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
# Callback to the distance function.
dist_between_locations = CreateDistanceCallback(locations)
dist_callback = dist_between_locations.Distance
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
# Put a callback to the demands.
demands_at_locations = CreateDemandCallback(demands)
demands_callback = demands_at_locations.Demand
# Add a dimension for demand.
slack_max = 0
vehicle_capacity = 1500
fix_start_cumul_to_zero = True
demand = "Demand"
routing.AddDimension(demands_callback, slack_max, vehicle_capacity,
fix_start_cumul_to_zero, demand)
# Solve, displays a solution if any.
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
# Display solution.
# Solution cost.
print("Total distance of all routes: " + str(assignment.ObjectiveValue()) + "\n")
for vehicle_nbr in range(num_vehicles):
index = routing.Start(vehicle_nbr)
index_next = assignment.Value(routing.NextVar(index))
route = ''
route_dist = 0
route_demand = 0
while not routing.IsEnd(index_next):
node_index = routing.IndexToNode(index)
node_index_next = routing.IndexToNode(index_next)
route += str(node_index) + " -> "
# Add the distance to the next node.
route_dist += dist_callback(node_index, node_index_next)
# Add demand.
route_demand += demands[node_index_next]
index = index_next
index_next = assignment.Value(routing.NextVar(index))
node_index = routing.IndexToNode(index)
node_index_next = routing.IndexToNode(index_next)
route += str(node_index) + " -> " + str(node_index_next)
route_dist += dist_callback(node_index, node_index_next)
print("Route for vehicle " + str(vehicle_nbr) + ":\n\n" + route + "\n")
print("Distance of route " + str(vehicle_nbr) + ": " + str(route_dist))
print("Demand met by vehicle " + str(vehicle_nbr) + ": " + str(route_demand) + "\n")
else:
print('No solution found.')
else:
print('Specify an instance greater than 0.')
def create_data_array():
nodelist = pd.read_csv('https://gist.githubusercontent.com/brooksandrew/f989e10af17fb4c85b11409fea47895b/raw/a3a8da0fa5b094f1ca9d82e1642b384889ae16e8/nodelist_sleeping_giant.csv')
locations = [[e.X, e.Y] for e in nodelist.itertuples()]
demands = [1] + [1] + [1] * 75
data = [locations, demands]
return data
if __name__ == '__main__':
main()
这输出了一个解决方案：
Total distance of all routes: 12900
Route for vehicle 0:
0 -> 56 -> 40 -> 53 -> 63 -> 55 -> 14 -> 15 -> 12 -> 26 -> 34 -> 69 -> 36 -> 1 -> 64 -> 27 -> 48 -> 70 -> 47 -> 13 -> 10 -> 61 -> 45 -> 42 -> 60 -> 9 -> 8 -> 21 -> 43 -> 44 -> 3 -> 18 -> 58 -> 38 -> 28 -> 49 -> 32 -> 35 -> 50 -> 74 -> 46 -> 54 -> 76 -> 71 -> 65 -> 29 -> 16 -> 17 -> 22 -> 59 -> 7 -> 24 -> 31 -> 37 -> 67 -> 73 -> 41 -> 52 -> 75 -> 72 -> 20 -> 2 -> 39 -> 57 -> 23 -> 66 -> 5 -> 6 -> 30 -> 33 -> 68 -> 19 -> 25 -> 4 -> 11 -> 62 -> 51 -> 0
Distance of route 0: 12900
Demand met by vehicle 0: 76
如您所见，我们正在无法在其间旅行的节点之间旅行。