Skip to content
Advertisement

How to create a vehicle route optimization problem using or-tools and google-distance matrix while nullifying the end location only?

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 :)

User contributions licensed under: CC BY-SA
8 People found this is helpful
Advertisement