I am trying to create a vehicle routing problem for multi-drivers with pickup and drop-off locations. The starting point for each driver is their current location and the ending point would be anywhere they end.
The input to my algorithm is a series of lot/long locations. The final output would be the best(shortest) route decided for the driver starting from his location and ending at any location. My actual final output is a route that starts at the driver location and ends at the driver location.
My problem is how can I create the distance matrix while nullifying the end location (the distance from the end node to any other node would be zero).
These are the functions that convert the lat/long locations to distance matrix >>
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
Then the distance matrix would look like this >>
[[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]]
In the 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 solution I found in a post here but still the same problem because I use the indices to map back to the lat/long locations.
This is my exact algorithm >> https://developers.google.com/optimization/routing/routing_tasks#setting-start-and-end-locations-for-routes only start and end locations are the deliverer current location and this is the extra part of mapping back the routes to the actual locations which is causing the problem of mapping back indices to 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
Advertisement
Answer
Apparently, it is as simple as it is answered in the other question. I added a row of zeros and an additional zero at the start of every row after creating the distance matrix > this will tell the algorithm that the distance between the point at index zero and any other point is 0. And I set my end point data["ends"] = 0
.
So in my case the distance matrix would look like this >>
[[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]]
This code for doing so is as follows >>
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. if anyone needs clarifying feel free to reach out :)