Problem setup
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)
The problem itself
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 "map" and courier may have bicycle what allows to execute job faster comparing to each of them separately even accounting for order transfer costs.
We have researched algorithms and found that our problem looks like assignment problem and there is an algorithmic solution (Hungarian algorithm), but the problem is that classic problem requires "each job is assigned to one worker and each worker is assigned one job" while in our case it is sometimes efficient to have 2 workers per one job.
What we have tried so far
insert (packer A + universal B) combination into the matrix of costs, but in this case we cannot add universal B into the matrix, because as a result we can get that universal B will be assigned to 2 jobs (as a separate unit and as part of combination with packer A)
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.
The question itself
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.
EDIT: I've added the brute force solution of my question. Hope that helps to understand the problem better
# 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 < 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()
There's an obvious heuristic that you could try:
Certainly not the optimum, but a clear first-order improvement over the Hungarian Algorithm alone.