如何使用 or-tools 和 google-distance 矩阵创建车辆路线优化问题，同时仅取消终点位置？
How to create a vehicle route optimization problem using or-tools and google-distance matrix while nullifying the end location only?
我正在尝试为 multi-drivers 创建车辆路径问题，其中包含取件和 drop-off 位置。每个 driver 的起点是它们的当前位置，终点是它们结束的任何地方。
我的算法的输入是一系列 lot/long 个位置。最终输出将是为 driver 决定的最佳（最短）路线，从他的位置开始并在任何位置结束。我的实际最终输出是一条从 driver 位置开始并在 driver 位置结束的路线。
我的问题是如何在取消结束位置的同时创建距离矩阵（从结束节点到任何其他节点的距离将为零）。
这些是将 lat/long 位置转换为距离矩阵的函数 >>
def create_data():
"""Creates the data."""
data = {}
data['API_key'] = xxxxxxxxxxxxx
data['addresses'] = ["30.588306869629527%2C31.47918156839698", #driver #12 current loca
"30.073040504782547%2C31.345765282277267", #order 13 pickup loc
"30.068329781020058%2C31.323759091237868", #order 13 dropoff loc
"30.073040504782547%2C31.345765282277267", #order 14 pickup loc
"30.062493604295614%2C31.34477108388055", #order 14 dropoff loc
"30.073040504782547%2C31.345765282277267", #order 15 pickup loc
"30.09912973586751%2C31.315054495649424", #order 15 dropoff loc
"30.584087371098757%2C31.50439621285545", #order 16 pickup loc
"30.596311789481327%2C31.488618697512486", #order 16 dropoff loc
"30.584087371098757%2C31.50439621285545", #order 17 pickup loc
"30.548610813018943%2C31.834700566824836"] #order 17 dropoff loc
return data
def create_distance_matrix():
data = create_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)
# Maximum number of rows that can be computed per request.
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 #the outut is down below
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 = str(request) + '&origins=' + str(origin_address_str) + '&destinations=' + str(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
然后距离矩阵看起来像这样>>
[[0, 77825, 77826, 77825, 79238, 77825, 74846, 5548, 2112, 5548, 45588],
[85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[82238, 4300, 0, 4300, 3791, 4300, 7753, 81180, 84267, 81180, 101818],
[85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[85128, 3702, 6139, 3702, 0, 3702, 12171, 84069, 87157, 84069, 103947],
[85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[82508, 7453, 7172, 7453, 10358, 7453, 0, 76139, 84537, 76139, 101220],
[3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[2959, 79693, 79694, 79693, 81107, 79693, 76715, 3303, 0, 3303, 42743],
[3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[37626, 89250, 89251, 89250, 90663, 89250, 86271, 35225, 36644, 35225, 0]]
在 Google OR-tools it mentions if I wanted to have arbitrary start and end locations I should add a row and column of zeros to my distance matrix. But for me that would create a problem because I wouldnt be able to map back the indices to lat/long locations. Also same 中，我在 post 此处找到，但仍然是同样的问题，因为我使用索引映射回 lat/long 位置。
这是我的确切算法 >> https://developers.google.com/optimization/routing/routing_tasks#setting-start-and-end-locations-for-routes
只有开始和结束位置是交付者的当前位置，这是将路线映射回实际位置的额外部分，这导致将索引映射回 lat/long loc
的问题
"Final Output"
# mapping back to order_id and pickup and delivery location
# routes >> [[0, 9, 10, 1, 5, 3, 4, 2, 6, 7, 8]]
def get_deliverer_route(routes):
addresses = [{'deliverer_12': '30.588306869629527%2C31.47918156839698'},
{'13_pickup': '30.073040504782547%2C31.345765282277267'},
{'13_dropoff': '30.068329781020058%2C31.323759091237868'},
{'14_pickup': '30.073040504782547%2C31.345765282277267'},
{'14_dropoff': '30.062493604295614%2C31.34477108388055'},
{'15_pickup': '30.073040504782547%2C31.345765282277267'},
{'15_dropoff': '30.09912973586751%2C31.315054495649424'},
{'16_pickup': '30.584087371098757%2C31.50439621285545'},
{'16_dropoff': '30.596311789481327%2C31.488618697512486'},
{'17_pickup': '30.584087371098757%2C31.50439621285545'},
{'17_dropoff': '30.548610813018943%2C31.834700566824836'}]
route_table = []
deliverer_request = []
for idx in range(len(routes)):
# create delivere location id
address = addresses[idx]
for key, value in address.items():
single_loc = {}
k = key.split('_')
single_loc['deliverer_id'] = k[1]
single_loc['coordinates'] = value.replace('%2C', ',')
deliverer_request = [single_loc]
route_table.append(deliverer_request)
# create orders addresses
route = routes[idx]
route.pop(0)
for n in route:
order_address = addresses[n]
for key, value in order_address.items():
single_loc = {}
k = key.split("_")
single_loc["order_id"] = k[0]
single_loc["coordinates"] = value.replace('%2C', ',')
single_loc["type"] = k[1]
route_table[idx].append(single_loc)
return route_table
显然，它和另一个中的回答一样简单。在创建距离矩阵后，我在每一行的开头添加了一行零和一个额外的零 > 这将告诉算法索引零处的点与任何其他点之间的距离为 0。然后我设置终点 data["ends"] = 0。
所以在我的例子中，距离矩阵看起来像这样 >>
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 77825, 77826, 77825, 79238, 77825, 74846, 5548, 2112, 5548, 45588],
[0, 85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[0, 82238, 4300, 0, 4300, 3791, 4300, 7753, 81180, 84267, 81180, 101818],
[0, 85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[0, 85128, 3702, 6139, 3702, 0, 3702, 12171, 84069, 87157, 84069, 103947],
[0, 85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[0, 82508, 7453, 7172, 7453, 10358, 7453, 0, 76139, 84537, 76139, 101220],
[0, 3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[0, 2959, 79693, 79694, 79693, 81107, 79693, 76715, 3303, 0, 3303, 42743],
[0, 3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[0, 37626, 89250, 89251, 89250, 90663, 89250, 86271, 35225, 36644, 35225, 0]]
这样做的代码如下>>
def create_distance_matrix(deliverers_location, orders):
data = create_data(deliverers_location, orders)
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)
# Maximum number of rows that can be computed per request.
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 = []
# add the zeros row at the beginning of the matrix >> end node distance
end_node = []
for i in range(len(addresses)+1):
end_node.append(0)
distance_matrix.append(end_node)
# 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)
# Add a row of zeros and a zero at the start of each row
dist_matrix = []
for row in distance_matrix:
if len(row) == len(addresses)+1: # check if the zero is already added to the beginning of the row
dist_matrix.append(row) # just add row to the new list
elif len(row) == len(addresses):
row.insert(0,0) # insert zero at the beginning and append row
dist_matrix.append(row)
distance_matrix = dist_matrix
return distance_matrix
p.s。如果有人需要澄清，请随时联系 :)
我正在尝试为 multi-drivers 创建车辆路径问题，其中包含取件和 drop-off 位置。每个 driver 的起点是它们的当前位置，终点是它们结束的任何地方。
我的算法的输入是一系列 lot/long 个位置。最终输出将是为 driver 决定的最佳（最短）路线，从他的位置开始并在任何位置结束。我的实际最终输出是一条从 driver 位置开始并在 driver 位置结束的路线。
我的问题是如何在取消结束位置的同时创建距离矩阵（从结束节点到任何其他节点的距离将为零）。
这些是将 lat/long 位置转换为距离矩阵的函数 >>
def create_data():
"""Creates the data."""
data = {}
data['API_key'] = xxxxxxxxxxxxx
data['addresses'] = ["30.588306869629527%2C31.47918156839698", #driver #12 current loca
"30.073040504782547%2C31.345765282277267", #order 13 pickup loc
"30.068329781020058%2C31.323759091237868", #order 13 dropoff loc
"30.073040504782547%2C31.345765282277267", #order 14 pickup loc
"30.062493604295614%2C31.34477108388055", #order 14 dropoff loc
"30.073040504782547%2C31.345765282277267", #order 15 pickup loc
"30.09912973586751%2C31.315054495649424", #order 15 dropoff loc
"30.584087371098757%2C31.50439621285545", #order 16 pickup loc
"30.596311789481327%2C31.488618697512486", #order 16 dropoff loc
"30.584087371098757%2C31.50439621285545", #order 17 pickup loc
"30.548610813018943%2C31.834700566824836"] #order 17 dropoff loc
return data
def create_distance_matrix():
data = create_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)
# Maximum number of rows that can be computed per request.
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 #the outut is down below
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 = str(request) + '&origins=' + str(origin_address_str) + '&destinations=' + str(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
然后距离矩阵看起来像这样>>
[[0, 77825, 77826, 77825, 79238, 77825, 74846, 5548, 2112, 5548, 45588],
[85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[82238, 4300, 0, 4300, 3791, 4300, 7753, 81180, 84267, 81180, 101818],
[85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[85128, 3702, 6139, 3702, 0, 3702, 12171, 84069, 87157, 84069, 103947],
[85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[82508, 7453, 7172, 7453, 10358, 7453, 0, 76139, 84537, 76139, 101220],
[3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[2959, 79693, 79694, 79693, 81107, 79693, 76715, 3303, 0, 3303, 42743],
[3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[37626, 89250, 89251, 89250, 90663, 89250, 86271, 35225, 36644, 35225, 0]]
在 Google OR-tools it mentions if I wanted to have arbitrary start and end locations I should add a row and column of zeros to my distance matrix. But for me that would create a problem because I wouldnt be able to map back the indices to lat/long locations. Also same
这是我的确切算法 >> https://developers.google.com/optimization/routing/routing_tasks#setting-start-and-end-locations-for-routes 只有开始和结束位置是交付者的当前位置，这是将路线映射回实际位置的额外部分，这导致将索引映射回 lat/long loc
的问题"Final Output"
# mapping back to order_id and pickup and delivery location
# routes >> [[0, 9, 10, 1, 5, 3, 4, 2, 6, 7, 8]]
def get_deliverer_route(routes):
addresses = [{'deliverer_12': '30.588306869629527%2C31.47918156839698'},
{'13_pickup': '30.073040504782547%2C31.345765282277267'},
{'13_dropoff': '30.068329781020058%2C31.323759091237868'},
{'14_pickup': '30.073040504782547%2C31.345765282277267'},
{'14_dropoff': '30.062493604295614%2C31.34477108388055'},
{'15_pickup': '30.073040504782547%2C31.345765282277267'},
{'15_dropoff': '30.09912973586751%2C31.315054495649424'},
{'16_pickup': '30.584087371098757%2C31.50439621285545'},
{'16_dropoff': '30.596311789481327%2C31.488618697512486'},
{'17_pickup': '30.584087371098757%2C31.50439621285545'},
{'17_dropoff': '30.548610813018943%2C31.834700566824836'}]
route_table = []
deliverer_request = []
for idx in range(len(routes)):
# create delivere location id
address = addresses[idx]
for key, value in address.items():
single_loc = {}
k = key.split('_')
single_loc['deliverer_id'] = k[1]
single_loc['coordinates'] = value.replace('%2C', ',')
deliverer_request = [single_loc]
route_table.append(deliverer_request)
# create orders addresses
route = routes[idx]
route.pop(0)
for n in route:
order_address = addresses[n]
for key, value in order_address.items():
single_loc = {}
k = key.split("_")
single_loc["order_id"] = k[0]
single_loc["coordinates"] = value.replace('%2C', ',')
single_loc["type"] = k[1]
route_table[idx].append(single_loc)
return route_table
显然，它和另一个data["ends"] = 0。
所以在我的例子中，距离矩阵看起来像这样 >>
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 77825, 77826, 77825, 79238, 77825, 74846, 5548, 2112, 5548, 45588],
[0, 85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[0, 82238, 4300, 0, 4300, 3791, 4300, 7753, 81180, 84267, 81180, 101818],
[0, 85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[0, 85128, 3702, 6139, 3702, 0, 3702, 12171, 84069, 87157, 84069, 103947],
[0, 85342, 0, 5147, 0, 2770, 0, 8420, 79286, 87371, 79286, 102144],
[0, 82508, 7453, 7172, 7453, 10358, 7453, 0, 76139, 84537, 76139, 101220],
[0, 3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[0, 2959, 79693, 79694, 79693, 81107, 79693, 76715, 3303, 0, 3303, 42743],
[0, 3783, 77535, 77536, 77535, 78948, 77535, 74556, 0, 3560, 0, 40769],
[0, 37626, 89250, 89251, 89250, 90663, 89250, 86271, 35225, 36644, 35225, 0]]
这样做的代码如下>>
def create_distance_matrix(deliverers_location, orders):
data = create_data(deliverers_location, orders)
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)
# Maximum number of rows that can be computed per request.
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 = []
# add the zeros row at the beginning of the matrix >> end node distance
end_node = []
for i in range(len(addresses)+1):
end_node.append(0)
distance_matrix.append(end_node)
# 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)
# Add a row of zeros and a zero at the start of each row
dist_matrix = []
for row in distance_matrix:
if len(row) == len(addresses)+1: # check if the zero is already added to the beginning of the row
dist_matrix.append(row) # just add row to the new list
elif len(row) == len(addresses):
row.insert(0,0) # insert zero at the beginning and append row
dist_matrix.append(row)
distance_matrix = dist_matrix
return distance_matrix
p.s。如果有人需要澄清，请随时联系 :)