title: Assignment problem with 2 workers per job
body: <p><strong>Problem setup</strong></p>
  <p>Currently we are working at dispatching problem for a food-tech startup (e-grocery). We have jobs (orders to be delivered) and workers (couriers/packers/universal) The problem is to to assign orders to workers efficiently. At first step we've decided to optimise CTE (click-to-eat - time between order placement and order delivery)</p>
  <p><strong>The problem itself</strong></p>
  <p>The problem comes from the fact that sometimes it is efficient to have 2 worker per one job and not a single executor, because packer may know store &quot;map&quot; and courier may have bicycle what allows to execute job faster comparing to each of them separately even accounting for order transfer costs.</p>
  <p>We have researched algorithms and found that our problem looks like <a href="https://en.wikipedia.org/wiki/Assignment_problem" rel="nofollow noreferrer">assignment problem</a> and there is an algorithmic solution (<a href="https://en.wikipedia.org/wiki/Hungarian_algorithm" rel="nofollow noreferrer">Hungarian algorithm</a>), but the problem is that classic problem requires &quot;each job is assigned to one worker and each worker is assigned one job&quot; while in our case it is sometimes efficient to have 2 workers per one job.</p>
  <p><strong>What we have tried so far</strong></p>
  <ol>
  <li><p>insert (<em>packer A</em> + <em>universal B</em>) combination into the matrix of costs, but in this case we cannot add  <em>universal B</em> into the matrix, because as a result we can get that <em>universal B</em> will be assigned to 2 jobs (as a separate unit and as part of combination with <em>packer A</em>)</p>
  </li>
  <li><p>Implement 2 Hungarian algorithms consequently: at first assign packaging, after that assign delivery. It works in vast majority of cases, but sometimes leads to inefficient solutions. If needed, I will add an example.</p>
  </li>
  </ol>
  <p><strong>The question itself</strong></p>
  <p>I've googled a lot, but could not find anything that could direct me to the solution of the problem. If you have any links or ideas that we can use as a clue to solution, I will be happy to check them.</p>
  <p><strong>EDIT:</strong> I've added the brute force solution of my question. Hope that helps to understand the problem better</p>
  <pre class="lang-py prettyprint-override"><code># constants
  delivery_speed = np.array([5, 13]) # km per hour
  delivery_distance = np.array([300, 2700])  # meters
  flight_distance = np.array([500, 1900]) # meters время подлета
  positions_amount = np.array([4, 8]) # number of positions in one order
  assembly_speed = np.array([2, 3]) # minutes per position
  transit_time = 5 * 60 # sec to transfer order
  number_of_orders = 3 # number of orders in a batch
  number_of_workers = 3 
  
  # size of optimization matrix
  matrix_size = max(number_of_workers, number_of_orders)
  
  
  # maximum diagonal length for delivery and flight
  max_length = np.sqrt(max(delivery_distance)**2/2)
  max_flight_length = np.sqrt(max(flight_distance)**2/2)
  
  
  # store positions
  A = np.array([delivery_distance[1], delivery_distance[1]])
  B = np.array([A[0] + max_length / 2, A[1]])
  
  possible_order_position_x = np.array([-max_length/2, max_length]) + A[0]
  possible_order_position_y = np.array([-max_length, max_length]) + A[1]
  possible_courier_position_x = np.array([-max_flight_length/2, max_flight_length]) + A[0]
  possible_courier_position_y = np.array([-max_flight_length, max_flight_length]) + A[1]
  
  
  # generate random data 
  def random_speed(speed_array):
      return np.random.randint(speed_array[0], speed_array[1]+1)
  
  def location(possible_x, possible_y):
      return np.random.randint([possible_x[0], possible_y[0]],
                               [possible_x[1], possible_y[1]],
                               size=2)
  
  
  def generate_couriers():
      # generate couriers 
      couriers = {}
      for courier in range(number_of_workers):
          couriers[courier] = {
              'position': location(possible_courier_position_x, possible_courier_position_y),
              'delivery_speed': random_speed(delivery_speed),
              'assembly_speed': random_speed(assembly_speed),
          }
      return couriers
      
  couriers = generate_couriers()
  
  store_location = {0: A, 1:B}
  
  def generate_orders():
      # generate orders
      orders = {}
      for order in range(number_of_orders):
          orders[order] = {
              'number_of_positions': random_speed(positions_amount),
              'store_position': store_location[np.random.randint(2)],
              'customer_position': location(possible_order_position_x, possible_order_position_y)
          }
      return orders
  
  orders = generate_orders()
  orders
  
  
  # functions to calculate assembly and delivery speed 
  def travel_time(location_1, location_2, speed):
      # time to get from current location to store
      flight_distance = np.linalg.norm(location_1 - location_2)
      delivery_speed = 1000 / (60 * 60) * speed # meters per second
      return flight_distance / delivery_speed # seconds
  
  
  def assembly_time(courier, order):
      flight_time = travel_time(courier['position'], order['store_position'], courier['delivery_speed'])
      assembly_time = courier['assembly_speed'] * order['number_of_positions'] * 60
  
      
      return int(flight_time + assembly_time)
  assembly_time(couriers[0], orders[0])
  
  def brute_force_solution():
      best_cte = np.inf
      best_combination = [[],[]]
  
      for first_phase in itertools.permutations(range(number_of_workers), number_of_orders):
          assembly_time_s = pd.Series(index = range(number_of_orders), dtype=float)
          for order, courier in enumerate(first_phase):
              assembly_time_s[order] = assembly_time(couriers[courier], orders[order]) 
  
  
          # start to work with delivery
          for second_phase in itertools.permutations(range(number_of_workers), number_of_orders):
              delivery_time_s = pd.Series(index = range(number_of_orders), dtype=float)
              for order, courier in enumerate(second_phase):
                  delivery_time = travel_time(orders[order]['store_position'],
                                              orders[order]['customer_position'],
                                              couriers[courier]['delivery_speed'])
                  # different cases for different deliveries
                  if courier == first_phase[order]:
                      # if courier assemblied order, then deliver immidietely 
                      delivery_time_s[order] = delivery_time
                  elif courier not in first_phase:
                      # flight during assembly, wait if needed, transfer time, delivery
                      flight_time = travel_time(orders[order]['store_position'],
                                                couriers[courier]['position'],
                                                couriers[courier]['delivery_speed'])
                      wait_time = max(flight_time - assembly_time_s[order], 0)
                      delivery_time_s[order] = transit_time + wait_time + delivery_time
                  else: 
                      # case when shopper transfers her order and moves deliver other 
                      # check if second order is in the same store
                      first_phase_order = first_phase.index(courier)
                      if (orders[first_phase_order]['store_position'] == orders[order]['store_position']).all():
                          # transit time - fixed and happens only once! 
                          # wait, if second order has not been assemblied yet
                          # time to assembly assigned order
                          assembly_own = assembly_time_s[first_phase_order]
                          # time to wait, if order to deliver is assemblied slower
                          wait_time = max(assembly_time_s[order] - assembly_own, 0)
                          # delivery time is calculated as loop start
                          delivery_time_s[order] = transit_time + wait_time + delivery_time
                      else:
                          # transit own order - flight to the other store - wait if needed - tansit order - delivery_time
                          flight_time = travel_time(orders[first_phase_order]['store_position'],
                                                    orders[order]['store_position'],
                                                    couriers[courier]['delivery_speed'])
                          arrival_own = (assembly_time_s[first_phase_order] + transit_time + flight_time)
                          wait_time = max(assembly_time_s[order] - arrival_own, 0)
                          delivery_time_s[order] = ((transit_time * 2) + flight_time + wait_time + delivery_time)
              
              delivery_time_s = delivery_time_s.astype(int)
  
              # calculate and update best result, if needed
              cte = (assembly_time_s + delivery_time_s).sum()
              if cte &lt; best_cte:
                  best_cte = cte
                  best_combination = [list(first_phase), list(second_phase)]
                  
      return best_cte, best_combination
  
  
  best_cte, best_combination = brute_force_solution()
  </code></pre>