1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
| from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp import matplotlib.pyplot as plt import networkx as nx
locations = [(35, 10), (15, 15), (25, 25), (30, 40), (45, 35), (10, 20), (50, 25)]
depot = (0, 0)
def create_data_model(): data = {} data['distance_matrix'] = [ [0, 10, 15, 20, 25, 30, 35], [10, 0, 10, 15, 20, 25, 30], [15, 10, 0, 10, 15, 20, 25], [20, 15, 10, 0, 10, 15, 20], [25, 20, 15, 10, 0, 10, 15], [30, 25, 20, 15, 10, 0, 10], [35, 30, 25, 20, 15, 10, 0] ] data['num_vehicles'] = 1 data['depot'] = 0 return data
def plot_solution(manager, routing, solution): index = routing.Start(0) plan_output = 'Route for vehicle 0:\n' route_distance = 0 while not routing.IsEnd(index): plan_output += f'{manager.IndexToNode(index)} -> ' previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle(previous_index, index, 0) plan_output += f'{manager.IndexToNode(index)}\n' route_distance += routing.GetArcCostForVehicle(previous_index, index, 0) print(plan_output) print(f'Distance of the route: {route_distance} units')
G = nx.Graph() for i in range(len(locations)): G.add_node(i, pos=locations[i]) for i in range(manager.GetNumberOfVehicles()): index = routing.Start(i) while not routing.IsEnd(index): next_index = solution.Value(routing.NextVar(index)) G.add_edge(manager.IndexToNode(index), manager.IndexToNode(next_index)) index = next_index
pos = nx.get_node_attributes(G, 'pos') nx.draw(G, pos, with_labels=True, font_weight='bold', node_size=700, node_color='skyblue', font_size=8, font_color='black') plt.show()
def main(): data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot'])
routing = pywrapcp.RoutingModel(manager)
def distance_callback(from_index, to_index): 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)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.local_search_metaheuristic = (routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) search_parameters.time_limit.seconds = 30
solution = routing.SolveWithParameters(search_parameters)
if solution: plot_solution(manager, routing, solution)
if __name__ == '__main__': main()
|