問題設定
現在、フードテック スタートアップ (電子食料品店) の派遣問題に取り組んでいます。私たちには仕事（配達される注文）と労働者（宅配業者/梱包業者/ユニバーサル）があります。問題は、注文を労働者に効率的に割り当てることです。最初のステップでは、CTE (クリックして食べる - 注文してから配達までの時間) を最適化することにしました。
問題そのもの
問題は、単一のエグゼキューターではなく、1 つのジョブにつき 2 人のワーカーを持つことが効率的であるという事実から生じます。なぜなら、パッカーは店舗の「マップ」を知っている可能性があり、宅配業者は自転車を持っている可能性があるため、それぞれを個別に比較した場合でもジョブをより速く実行できるからです。注文転送費用の会計。
アルゴリズムを調査したところ、私たちの問題は割り当て問題のように見え、アルゴリズムによる解決策 (ハンガリーのアルゴリズム) があることがわかりましたが、問題は、古典的な問題では、「各ジョブが 1 つのワーカーに割り当てられ、各ワーカーに 1 つのジョブが割り当てられる」必要があることです。私たちの場合、1 つのジョブに 2 人のワーカーを配置すると効率的な場合があります。
これまでに試したこと
(パッカー A +ユニバーサル B ) の組み合わせをコストのマトリックスに挿入しますが、この場合、ユニバーサル B をマトリックスに追加することは できません。パッカーAとの組み合わせの一部として）
その結果、2 つのハンガリー語アルゴリズムを実装します。最初にパッケージを割り当て、次に配送を割り当てます。これはほとんどの場合に機能しますが、非効率的なソリューションにつながることもあります。必要に応じて、例を追加します。
質問自体
私はたくさんグーグルで検索しましたが、問題の解決策を教えてくれるものは何も見つかりませんでした。解決の手がかりとして使用できるリンクやアイデアがあれば、喜んでチェックさせていただきます。
編集:私の質問のブルート フォース ソリューションを追加しました。問題をよりよく理解するのに役立つことを願っています
# 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()