#python #optimization #or-tools
Вопрос:
Я пытаюсь создать массив расстояний для 27 адресов, но возвращаемый набор пуст. Я ничего не понял. Когда я ставлю только 24 адреса, система собирает матрицу расстояний.
from __future__ import division
from __future__ import print_function
import requests
import json
import urllib.request
def create_data():
"""Creates the data."""
data = {}
data['API_key'] = 'API KEY'
data['addresses'] = ['R Carlos Camara 1454 Benfica Fortaleza CE', # depot
'AV DEP PAULINO ROCHA 105 JABUTI ITAITINGA CE',
'R CABO VERDE 660 CJ PALMEIRAS FORTALEZA CE',
'AV Monsenhor AMARILIO RODRIGUES 604 JANGURUSSU FORTALEZA CE',
'R PEDESTRE IX 349 CANINDEZINHO FORTALEZA CE',
'RUA MARECHAL NAPION 733 BARRA DO CEARA FORTALEZA CE',
'R IRACEMA 880 CJ PALMEIRAS FORTALEZA CE',
'R JOSIAS PAULA DE SOUZA 100 VICENTE PINZON FORTALEZA CE',
'R CJ JOAO PAULO II 108 BARROSO FORTALEZA CE',
'AV XXII 474 SENADOR CARLOS JEREISSATI PACATUBA CE',
'R NUNES FEIJO 1454 JANGURUSSU FORTALEZA CE',
'AV A CJ JEREISSATI III 600 SENADOR CARLOS JEREISSATI PACATUBA CE',
'AV CENTRAL 5452 ICARAI CAUCAIA CE',
'R CJ JD CASTELAO 4651 PASSARE FORTALEZA CE',
'R FRIESIO BARROSO 387 MONDUBIM FORTALEZA CE',
'AV C CJ SIT SAO JOAO 87 JANGURUSSU FORTALEZA CE',
'R BOM JESUS 200 BOM JARDIM FORTALEZA CE',
'R TENENTE ROMA 206 ALTO DA BALANCA FORTALEZA CE',
'R SHIRLEY 280 PAUPINA FORTALEZA CE',
'R TEODORO DE CASTRO 2509 GRAJA LISBOA FORTALEZA CE',
'TV SAO FRANCISCO 332 MESSEJANA FORTALEZA CE',
'RUA PERDIGAO DE OLIVEIRA 361 PARANGABA FORTALEZA CE',
'R ALM SOARES DUTRA 33 CUMBUCO CAUCAIA CE',
'R CORDEIRO DE MIRANDA 1311 CJ METROPOLITANO CAUCAIA CE',
'R JOAQUIM MACHADO 287 PAUPINA FORTALEZA CE',
'AV ENG LEAL LIMA VERDE 306 SAPIRANGA FORTALEZA CE', #Conjunto Vazio
'R VERDE 180 JANGURUSSU FORTALEZA CE', #Conjunto vazio
]
return data
def create_distance_matrix(data):
addresses = data["addresses"]
API_key = data["API_key"]
# Distance Matrix API only accepts 100 elements per request, so get rows in multiple
requests.
max_elements = 100
num_addresses = len(addresses) # 16 in this example.
# Maximum number of rows that can be computed per request (6 in this example).
max_rows = max_elements // num_addresses
# num_addresses = q * max_rows r (q = 2 and r = 4 in this example).
q, r = divmod(num_addresses, max_rows)
dest_addresses = addresses
distance_matrix = []
# Send q requests, returning max_rows rows per request.
for i in range(q):
origin_addresses = addresses[i * max_rows: (i 1) * max_rows]
response = send_request(origin_addresses, dest_addresses, API_key)
distance_matrix = build_distance_matrix(response)
# Get the remaining remaining r rows, if necessary.
if r > 0:
origin_addresses = addresses[q * max_rows: q * max_rows r]
response = send_request(origin_addresses, dest_addresses, API_key)
distance_matrix = build_distance_matrix(response)
return distance_matrix
def send_request(origin_addresses, dest_addresses, API_key):
""" Build and send request for the given origin and destination addresses."""
def build_address_str(addresses):
# Build a pipe-separated string of addresses
address_str = ''
for i in range(len(addresses) - 1):
address_str = addresses[i] '|'
address_str = addresses[-1]
return address_str
request = 'https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial'
origin_address_str = build_address_str(origin_addresses)
dest_address_str = build_address_str(dest_addresses)
request = request 'amp;origins=' origin_address_str 'amp;destinations='
dest_address_str 'amp;key=' API_key
jsonResult = urllib.request.urlopen(request).read()
response = json.loads(jsonResult)
return response
def build_distance_matrix(response):
distance_matrix = []
for row in response['rows']:
row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]
distance_matrix.append(row_list)
return distance_matrix
########
# Main #
########
def main():
"""Entry point of the program"""
# Create the data.
data = create_data()
addresses = data['addresses']
API_key = data['API_key']
distance_matrix = create_distance_matrix(data)
print(distance_matrix)
if __name__ == '__main__':
main()
С помощью приведенного ниже алгоритма я могу оптимизировать маршрут с наименьшей диастенцией, но мне также нужна сумма весов, которые нужно оптимизировать, ни один маршрут не может иметь более 100, самое интересное-оставаться между 60 и 90. Это означает, что он будет использовать от 60% до 90% времени, занятого снабжением супермаркетов, более 100 означает, что обслуживание будет плохим. Но я не знаю, как реализовать это ограничение. В этом примере в транспортном средстве 1 было более 100, я мог бы бросить магазин в транспортное средство 3, которое было слишком низким.
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import pandas as pd
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [[0, 22972, 15918, 14739, 12260, 7874, 16321, 12618, 12136, 20286,
14582, 20989, 19583, 12544, 9415, 14593, 8701, 5595, 18205, 10380, 11606, 5471, 28244, 15180,
19088], [29448, 0, 18885, 19844, 28925, 36734, 19138, 32722, 20508, 27405, 19013, 27135,
48981, 22834, 25845, 16567, 33286, 25147, 13481, 35607, 19994, 32821, 57642, 38376, 14362],
[17133, 10750, 0, 2432, 14259, 26384, 1212, 18107, 3544, 16138, 2754, 16841, 34315, 5275,
8433, 2767, 18620, 12832, 5699, 20941, 7679, 12922, 42976, 23710, 6582], [16900, 14836, 2916,
0, 17169, 24186, 1749, 17227, 2664, 19047, 4152, 19750, 37225, 4395, 8067, 4165, 13139,
10225, 8608, 16334, 7446, 12042, 45886, 26620, 9491], [12150, 22554, 16449, 12233, 0, 16331,
16702, 24381, 11976, 12050, 17359, 12753, 25224, 11029, 7254, 17372, 4735, 17379, 17503,
8396, 16769, 7900, 33884, 14618, 18387], [7851, 31385, 24331, 23152, 15926, 0, 24734, 13912,
20549, 25582, 22996, 26285, 12218, 20957, 17180, 23006, 12639, 16703, 26618, 12502, 20020,
10883, 20879, 14277, 27501], [17332, 11944, 1217, 2742, 15454, 22085, 0, 17972, 3409, 17332,
2953, 18035,
35510, 5140, 7273, 2965, 12344, 13031, 6893, 15539, 7877, 13876, 44170, 24904, 7776], [11522,
26596, 19542, 16377, 24422, 13517, 18156, 0, 15374, 30601, 18206, 31304, 24449, 15783, 17965,
18217, 21085, 8510, 21829, 22975, 15228, 17840, 33110, 24893, 22712], [12495, 13389, 3614,
1654, 17867, 19781, 3433, 15191, 0, 19745, 5000, 20448, 30635, 2359, 7887, 5011, 12958, 8189,
8622, 16153, 6915, 10007, 39295, 27318, 9505], [20521, 24318, 18212, 19171, 13669, 25953,
18465, 31235, 18829, 0, 19122, 500, 33725, 17883, 14108, 19135, 16212, 24232, 19267, 19407,
25783, 17744, 42385, 23119, 20150], [16702, 10424, 2545, 3654, 16657, 23987, 2948, 19976,
4052, 18535, 0, 19239, 36713, 6378, 9654, 971, 14726, 12401, 5657, 17921, 7247, 14025, 45374,
26108, 6540], [20143, 23940, 17834, 18793, 13291, 25575, 18087, 30857, 18452, 500, 18744, 0,
33347, 17505, 13730, 18757, 15834, 23854, 18889, 19029, 25405, 17366, 42007, 22741, 19772],
[24121, 42972, 36866, 37825, 27254, 12622, 37120, 25838, 32475, 33763, 37776, 34466, 0,
32594, 28819, 37789, 24278, 28629, 37921, 19467, 31946, 22522, 8661, 11823, 38804], [13864,
14342,
4478, 2518, 10725, 19678, 4298, 16560, 1516, 17105, 5953, 17808, 31393, 0, 4866, 5963, 9937,
9558, 9575, 13132, 6952, 11469, 40054, 23900, 10458], [9744, 18478, 8018, 6553, 7048, 16000,
6851, 17780, 6295, 13427, 10089, 14130, 27716, 5349, 0, 10099, 6260, 10777, 13711, 9454,
11088, 7792, 36377, 21641, 14594], [16204, 9926, 2568, 3676, 16679, 23490, 2970, 19478, 4787,
18557, 971, 19261, 36735, 6518, 9677, 0, 14748, 11903, 5159, 17943, 6750, 19577, 45396, 26130,
6042], [8518, 26325, 13912, 11952, 5182, 12699, 12157, 21028, 11695, 15374, 15488, 16077,
25786, 10748, 6973, 15499, 0, 14025, 21274, 3922, 17490, 4269, 34446, 15180, 22157], [4705,
20812, 13759, 9495, 17540, 11990, 11275, 8803, 8493, 23720, 12423, 24423, 23986, 8901, 11084,
12434, 14203, 0, 16045, 16094, 9447, 10959, 32646, 19889, 16928], [16517, 7670, 6754, 8533,
16794, 23802, 7007, 19791, 7577, 18672, 6082, 19375, 36850, 9903, 13714, 4436, 21155, 12216,
0, 23476, 7062, 19890, 45511, 26245, 1429], [10174, 26621, 16655, 14695, 8462, 12121, 14900,
22764, 14438, 18117, 18231, 18821, 20668, 13491, 9716, 18242, 3919, 15762, 25091, 0, 19227,
5239, 29329, 6994, 25974], [11406, 15283, 8229, 5816, 25666, 18692, 8632, 14680, 4860, 27545,
6894, 28248, 30687, 6866, 11195, 6904, 16266, 7105, 10513, 19914, 0, 14779, 39348, 35117,
5617], [5409, 25829, 12996, 11036, 7348, 10232, 13028, 17999, 10033, 16523, 17440, 17226,
21949, 10442, 7538, 17450, 3654, 10996, 21062, 5333, 14461, 0, 30610, 13561, 21945], [32109,
50960, 44854, 45813, 35241, 20609, 45107, 33826, 40463, 41750, 45764, 42454, 10043, 40582,
36807, 45777, 32266, 36617, 45909, 27455, 39933, 30510, 0, 19810, 46792], [15615, 31200,
25094, 26053, 15482, 13846, 25347, 23418, 27165, 21990, 26004, 22694, 12069, 24933, 21158,
26017, 9839, 22142, 26149, 6158, 32665, 11230, 20730, 0, 27032], [15780, 11894, 8827, 7797,
19583, 23066, 9576, 19054, 6841, 21461, 5345, 22164, 35061, 9166, 17318, 4847, 23944, 11479,
1605, 24288, 6326, 19153, 43722, 29034, 0]]
data['addresses'] = ['R Carlos Camara 1454 Benfica Fortaleza CE', # depot
'AV DEP PAULINO ROCHA 105 JABUTI ITAITINGA CE',
'R CABO VERDE 660 CJ PALMEIRAS FORTALEZA CE',
'AV Monsenhor AMARILIO RODRIGUES 604 JANGURUSSU FORTALEZA CE',
'R PEDESTRE IX 349 CANINDEZINHO FORTALEZA CE',
'RUA MARECHAL NAPION 733 BARRA DO CEARA FORTALEZA CE',
'R IRACEMA 880 CJ PALMEIRAS FORTALEZA CE',
'R JOSIAS PAULA DE SOUZA 100 VICENTE PINZON FORTALEZA CE',
'R CJ JOAO PAULO II 108 BARROSO FORTALEZA CE',
'AV XXII 474 SENADOR CARLOS JEREISSATI PACATUBA CE',
'R NUNES FEIJO 1454 JANGURUSSU FORTALEZA CE',
'AV A CJ JEREISSATI III 600 SENADOR CARLOS JEREISSATI PACATUBA CE',
'AV CENTRAL 5452 ICARAI CAUCAIA CE',
'R CJ JD CASTELAO 4651 PASSARE FORTALEZA CE',
'R FRIESIO BARROSO 387 MONDUBIM FORTALEZA CE',
'AV C CJ SIT SAO JOAO 87 JANGURUSSU FORTALEZA CE',
'R BOM JESUS 200 BOM JARDIM FORTALEZA CE',
'R TENENTE ROMA 206 ALTO DA BALANCA FORTALEZA CE',
'R SHIRLEY 280 PAUPINA FORTALEZA CE',
'R TEODORO DE CASTRO 2509 GRAJA LISBOA FORTALEZA CE',
'TV SAO FRANCISCO 332 MESSEJANA FORTALEZA CE',
'RUA PERDIGAO DE OLIVEIRA 361 PARANGABA FORTALEZA CE',
'R ALM SOARES DUTRA 33 CUMBUCO CAUCAIA CE',
'R CORDEIRO DE MIRANDA 1311 CJ METROPOLITANO CAUCAIA CE',
'R JOAQUIM MACHADO 287 PAUPINA FORTALEZA CE',
]
data['weights'] = [0,12,15,15,13,7,13,23,10,11,13,9,7,15,8,9,6,11,5,9,5,8,12,13,12]
data['num_vehicles'] = 4
data['depot'] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f'Objective: {solution.ObjectiveValue()}')
max_route_distance = 0
matrix_route = []
matrix_car = []
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}: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)
matrix_route.append(manager.IndexToNode(index)) #Criando a matrix de indices
matrix_car.append(f"Veículo {vehicle_id}") #Craindo a matriz com o nome das rotas
plan_output = '{}n'.format(manager.IndexToNode(index))
plan_output = 'Distance of the route: {}mn'.format(route_distance)
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
#DataFrame with Routes
df = pd.DataFrame(zip(matrix_route,matrix_car), columns = ['Routes', 'Car'])
zero_value = df[df['Routes']<=0]
df = df.drop(zero_value.index)
print(df)
#DataFrame with adresses
df_info = pd.DataFrame(zip(data['addresses'], data['weights']), columns=
["addresses","weights"])
#df_remove_depot = df_info.loc[df_info['addresses']=='3610 Hacks Cross Rd Memphis TN']
df_remove_depot =
df_info.loc[df_info['addresses']=='R Carlos Camara 1454 Benfica Fortaleza CE']
df_info = df_info.drop(df_remove_depot.index)
print(df_info)
## Merge
tabela = pd.merge(df_info, df, left_index=True, right_on="Routes",how="left")
## Save excel
print(tabela)
tabela.to_excel('C:/Users/mateuscarvalho/Documents/Mateus Carvalho - 2021/Otimização de rotas.xlsx', index = False)
#Menor Distância
print('Maximum of the route distances: {}m'.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['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
70000, # vehicle maximum travel distance
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# 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()
Ответ №1:
создайте измерение нагрузки/веса, добавьте cumulVarSoftUpperBound 90 на каждом узле, чтобы побудить решателя не набирать лишний вес ?
сначала проверьте
assert len(data['distance_matrix']) == data['weights']
Затем мы можем создать дополнительный весовой размер, чтобы ограничить нагрузку до 100.
# Add Capacity constraint.
def load_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data['weights'][from_node]
load_callback_index = routing.RegisterUnaryTransitCallback(load_callback)
routing.AddDimension(
load_callback_index,
0, # null capacity slack
100, # vehicle maximum capacity
True, # start cumul to zero
'Load')
ссылка: https://developers.google.com/optimization/routing/cvrp
Комментарии:
1. в данном случае это ограничение. потому что, например, я не могу послать промоутера по продажам в два магазина, которые продают оптом, он не может поставлять. Мне нужно сбалансировать доставку в небольшой магазин и оптовый магазин. Поэтому я оптимизирую расстояние, и в результате у него будет больше времени в запасе, чтобы снабдить их моими продуктами. Я работаю в пищевой промышленности
2. не понимаю, извините, у вас может быть любое количество измерений, которое вы хотите… таким образом, оптимизируя общее пройденное расстояние, вы все равно можете добавить еще одно измерение, чтобы ограничить максимальный вес, который может перевозить транспортное средство…
3. ДА. Я ищу это, чтобы понять, как я могу добавить это ограничение. Я искал это в некоторых статьях, но они не освещают это. Добавление ограничений в инструменты
4. чтобы добавить расширенное ограничение, вы можете получить доступ к решателю подчеркивания CP с помощью
routing.solver()