Setting precedence on jobs

[supriya-clutter]

We are trying to model our dispatching problem to use the vehicle routing paradigm. We have two kinds of jobs: pickups and returns. Returns are orders where we return objects to customers. Pickups are orders where we pickup objects from customers.
On a given day, we want to dispatch orders that are mix of these two types. Ideally, we want service the returns first and only get do the pickups. Most of the time, the time window constraints are specified in this manner, i.e Returns can be scheduled between 7am to 9am. Pickups can be scheduled from 9am to 11am. Only rare occasions to meet supply, we do returns at 11am as well.

I want to the following constraint: for every route, return orders should performed before the pickup orders. I tried adding a PickupAndDelivery constraint, to each of the return and pickup order pairs, but that seems wrong, and expectedly the solver isn't able to solve.

Is there a way to specify the above constraint ?

Here is a snippet of our code:

def get_google_distance(locations):
  distance_matrix = {}
  drive_times_matrix = {}
  num_locations = len(locations)

  google_key = os.environ['GOOGLE_DISTANCE_MATRIX_API_KEY']
  client = googlemaps.Client(google_key)
  for from_node in xrange(num_locations):
    distance_matrix[from_node] = {}
    drive_times_matrix[from_node] = {}
    for to_node in xrange(num_locations):
      result = client.distance_matrix(locations[from_node], locations[to_node])
      distance_matrix[from_node][to_node] = result['rows'][0]['elements'][0]['distance']['value']
      drive_times_matrix[from_node][to_node] = result['rows'][0]['elements'][0]['duration']['value']
  return [distance_matrix, drive_times_matrix]

class CreateDistanceCallback(object):
  """Create callback to calculate distances and travel times between points."""
  def __init__(self, distance_matrix):
    self.matrix = distance_matrix

  def Distance(self, from_node, to_node):
    return int(self.matrix[from_node][to_node])

# Service time (proportional to demand) callback.
class CreateServiceTimeCallback(object):
  """Create callback to get time windows at each location."""

  def __init__(self, demands, time_per_demand_unit):
    self.matrix = demands
    self.time_per_demand_unit = time_per_demand_unit

  def ServiceTime(self, from_node, to_node):
    # print self.matrix[from_node] * self.time_per_demand_unit
    return self.matrix[from_node] * self.time_per_demand_unit

class CreateTravelTimeCallback(object):
  """Create callback to get travel times."""

  def __init__(self, travel_times_matrix):
    self.matrix = travel_times_matrix

  def TravelTime(self, from_node, to_node):
    return (self.matrix[from_node][to_node] * 1.3)


# Create total_time callback (equals service time plus travel time).
class CreateTotalTimeCallback(object):
  def __init__(self, service_time_callback, travel_time_callback, parking_overhead):
    self.service_time_callback = service_time_callback
    self.travel_time_callback = travel_time_callback
    self.parking_overhead = parking_overhead

  def TotalTime(self, from_node, to_node):
    service_time = self.service_time_callback(from_node, to_node)
    travel_time = self.travel_time_callback(from_node, to_node)
    return float(service_time) + float(travel_time) + self.parking_overhead

def get_solution(data, date, region_name):
  begin = datetime.datetime.now()
  order_ids = data[0]
  demands = data[1]
  start_times = data[2]
  complete_locations = data[3]
  num_locations = len(order_ids)

  # Assume number of vehicles is not a problem
  depot_locations = data[8]
  num_vehicles_per_depot = 10
  num_vehicles = num_vehicles_per_depot * len(depot_locations)
  depot = []
  for i in xrange(len(depot_locations)):
    for j in xrange(num_vehicles_per_depot):
      depot.append(i)

  parking_duration = 15 * 60
  if (region_name == "New York"):
    parking_duration = 20 * 60
  wrap_up_duration = 10 * 60
  parking_overhead = parking_duration + wrap_up_duration

  # Subtract the parking duration time from an order's start time
  for order_start_time in start_times:
    order_start_time = order_start_time - parking_duration

  print "Number of orders", num_locations

  [distance_matrix, drive_times_matrix] = get_google_distance(complete_locations)

  # Create routing model.
  if num_locations > 0:

    # The number of nodes of the VRP is num_locations.
    # Nodes are indexed from 0 to num_locations - 1. By default the start of
    # a route is node 0.
    routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot, depot)

    # Setting first solution heuristic: the
    # method for finding a first solution to the problem.
    # The 'PATH_CHEAPEST_ARC' method does the following:
    # Starting from a route "start" node, connect it to the node which produces the
    # cheapest route segment, then extend the route by iterating on the last
    # node added to the route.
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
    search_parameters.first_solution_strategy = (
      routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # Put callbacks to the distance function and travel time functions here.

    # Callback to the distance function.
    dist_between_locations = CreateDistanceCallback(distance_matrix)
    dist_callback = dist_between_locations.Distance
    routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)

    time_per_demand_unit = 1
    service_times = CreateServiceTimeCallback(demands, time_per_demand_unit)
    service_time_callback = service_times.ServiceTime

    travel_times = CreateTravelTimeCallback(drive_times_matrix)
    travel_time_callback = travel_times.TravelTime

    total_times = CreateTotalTimeCallback(service_time_callback, travel_time_callback, parking_overhead)
    total_time_callback = total_times.TotalTime

    # Adding capacity dimension constraints.
    capacities = []
    for i in xrange(num_vehicles):
      capacities.append(10*3600)

    capacity_string = "Capacity"
    routing.AddDimensionWithVehicleCapacity(
      total_time_callback,
      0, # null capacity slack
      capacities, # vehicle maximum capacities
      True, # start cumul to zero
      capacity_string)

    # Adding time dimension constraints.
    horizon = 17 * 3600
    time_string = "Time"

    # SLA window
    tw_duration = 3 * 3600

    # Add a dimension for time-window constraints and limits on the start times and end times.
    fix_start_cumul_to_zero = False
    routing.AddDimension(total_time_callback,  # total time function callback
                         horizon,
                         horizon,
                         fix_start_cumul_to_zero,
                         time_string)

    # Add limit on size of the time windows.
    time_dimension = routing.GetDimensionOrDie(time_string)

    for order_idx in xrange(1, num_locations):
      start = start_times[order_idx]
      time_dimension.CumulVar(routing.NodeToIndex(order_idx)).SetRange(start, start + tw_duration)

    # Solve displays a solution if any.
    assignment = routing.SolveWithParameters(search_parameters)
   print(assignment, routing, data)

Thanks!

[morruth]

try to add

something like

solver=routing.solver()
for returnnodeindex in returnIndexes:
  for pickupnodeindex in pickupIndexes:
     solver.Add(time_dimension.CumulVar(returnnodeindex) <= time_dimension.CumulVar(pickupnodeindex))

also capacity dimension can be helpful

[supriya-clutter]

Thanks for the help. I added that exactly but the solver wasn't able to find a solution.

Is there a way to add a constraint to indicate that we need the returns before pickups only when they are in a route together ?

[Mizux]

please look at #847 (comment)