1
私はこのpythonライブラリまたはツールを使用しています：https://developers.google.com/optimization/routing/tsp/vehicle_routing （コードはここにあります）。車両に接続されていないグラフやツールを使ったProbの接続Python
解決策を実行すると、すべてのノードを一度にカバーするパスが得られます。しかし、私のプロジェクトでは、ノード間のパスに制約があります。たとえば、ノード{3}にいる場合、ノード{18}に移動することはできません。または、ノード{5}にいる場合、ノード{1,12,14}にしか移動できません。私はこの制約を現在のコード例に追加する方法が不明です。この中に明らかに https://www.datacamp.com/community/tutorials/networkx-python-graph-tutorial
：あなたがここにこのグラフの表現を見ることが 
：私たちは、このグラフを見ていた場合は
私はさらに説明することができます...
他のノードから特定のノードに移動することはできません。私はgoogleまたはツールの例でこのグラフのデータを使用して、車両ルーティング問題の解決策を得ています。ここで
は私のコードです：あなたは、私たちの間旅することができないノード間を移動している見ることができるように
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
：
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()
これは解決策を出力します。
を参照してください。したがって、2つのノード間の最短経路は距離です。それは実際には素晴らしい解決策です。 ~~私はまだここでエラーを起こしています~~心配しないで、私はそれを理解しました。一つの最後のことは、2つのノード間の最短経路の解を保持することです。したがって、実際の経路を視覚化したい場合は、戻ってそこを通過する各ノードを見ることができます。 – jchaykow
私はこのコメントが理にかなっていることを願っています。だから、私が言っていることは、 '3 - > 22 'から行くなら、最短の道は実際に' 3 - > 5 - > 14 - > 16 - > 22'に行き、何とかその最短経路と場所それを最終的な解に変換します。 – jchaykow
私は私の答えに追加のロジックを追加しました。 graphvizやnetworkxでグラフィカルなソリューションを生成するのは難しくありません。 –