如何使用OrTools优化路线并装配矩阵距离？

2024-09-30 18:18:25 发布

您现在位置：Python中文网/ 问答频道 /正文
9786 3

我试图为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 + '&origins=' + origin_address_str + '&destinations=' + \
                   dest_address_str + '&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: {}m\n'.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()

Tags： thedfdataindexrequestaddressesroutingmatrix
1条回答
网友
1楼 · 发布于 2024-09-30 18:18:25

创建负载/重量维度，在每个节点上添加90的cumulVarSoftUpperBound，以激励解算器不超重

先核实

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

相关问题 更多 >

    编程相关推荐