Routing distance and time

[Lahiru Supun]

We have a business requirement for a laundry company.

1. It has only one depot.

2. It has multiple delivery vehicles.

3. Vehicles have maximum load capacity.

4. Needs to drop, pickup clothes on the same route.

   1. While the vehicle dropping washed clothes needs to pick the clothes to wash.

5. Some drops, picks need to reach at a specific time. 

   1. Drop from customer x, needs to come between 10.00 am and 11.00 am

We started working with OR tools and so far have been able to solve 1,2,3,4 parts. Only thing we couldn't accomplish was the 5th one. Here is the code for that.

 

<code>

def route_api1():
    '''
    For direct API calls trought request
    '''
    data = request.get_json(force=True)
    print(type(data))
    print(data)
    print(data["vehicles"])
    print(data["demands"])
    print(data["weight"])
    x = data["vehicles"]
    y = data["demands"]
    z = data["weight"]
    k = data["addresses"]

    def create_data():
      """Creates the data."""
      data = {}
      data['API_key'] = 'Super-Secret-Key'
      data['addresses'] = k
      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

    data = create_data()
    addresses = data['addresses']
    API_key = data['API_key']
    distance_matrix = create_distance_matrix(data)
    print(distance_matrix)

    def create_data_model():
        """Stores the data for the problem."""
        data = {}
        data['distance_matrix'] = distance_matrix
        # [START demands_capacities]
        data['demands'] = y
        data['vehicle_capacities'] = z
        # [END demands_capacities]
        data['num_vehicles'] = x
        data['depot'] = 0
        return data
        # [END data_model]

    def get_routes(solution, routing, manager):
        """Get vehicle routes from a solution and store them in an array."""
        # Get vehicle routes and store them in a two dimensional array whose
        # i,j entry is the jth location visited by vehicle i along its route.
        routes = []
        for route_nbr in range(routing.vehicles()):
            index = routing.Start(route_nbr)
            route = [manager.IndexToNode(index)]
            while not routing.IsEnd(index):
                index = solution.Value(routing.NextVar(index))
                route.append(manager.IndexToNode(index))
            routes.append(route)
        return routes

</code>

 

We can see a time frame option in OR tools. We are unable to combine it with the current solution. Is there a way to combine this time frame window with our current code? 

[Vincent Furnon]

For 5, create a time dimension and constrain the cumul variables of the pickups or drops. Look at the various CVRPTW examples such as https://developers.google.com/optimization/routing/vrptw?hl=id.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/e7fa71c2-3a38-462b-9bde-0961fad07c95n%40googlegroups.com.