#algorithm #linear-programming #hungarian-algorithm #assignment-problem
Вопрос:
Настройка проблемы
В настоящее время мы работаем над решением проблемы отправки для стартапа в области пищевых технологий (электронного магазина). У нас есть рабочие места (заказы должны быть доставлены) и работники (курьеры/упаковщики/универсалы) Проблема заключается в том, чтобы эффективно распределять заказы между работниками. На первом этапе мы решили оптимизировать CTE (время между размещением заказа и доставкой заказа). Нажмите, чтобы съесть.
Сама проблема
Проблема заключается в том, что иногда эффективно иметь 2 работника на одно задание, а не одного исполнителя, потому что упаковщик может знать «карту» магазина, а у курьера может быть велосипед, что позволяет выполнять работу быстрее по сравнению с каждым из них в отдельности, даже с учетом затрат на передачу заказа.
Мы исследовали алгоритмы и обнаружили, что наша проблема выглядит как проблема присвоения и существует алгоритмического решения (венгерский алгоритм), но проблема в том, что классическая проблема требует «каждое задание отводится для одного работника и каждый работник назначается одного задания», а в нашем случае иногда выгоднее иметь 2 рабочих на одну работу.
То, что мы пробовали до сих пор
- вставьте комбинацию (упаковщик A универсальный B) в матрицу затрат, но в этом случае мы не можем добавить универсальный B в матрицу, потому что в результате мы можем получить, что универсальный B будет назначен на 2 задания (как отдельная единица и как часть комбинации с упаковщиком 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()
Комментарии:
1. Почему бы просто не разделить каждое задание на две задачи (задача упаковщика и задача курьера) и не запустить венгерский алгоритм один раз?
2. @kaya3 вы можете объяснить, как запустить один раз? Мы не можем этого сделать, потому что мы можем заставить работника 1 выполнять работу 1, работника 2 выполнять работу 1, работника 1 работника 2 выполнять работу 1, работника 1 работника 3 выполнять работу 2. Поэтому мы получаем, что некоторые задания невозможно будет выполнить в сочетании
3. Вам нужно оптимальное решение или достаточно эвристики?
4. @Rbarryyung Сначала мы были бы довольны эвристикой, но как только наши продажи вырастут, мы захотим найти оптимальное решение и сделать его достаточно быстрым для производства
5. Это больше не проблема с назначением. Я бы начал записывать это как формальную задачу оптимизации (и решать как модель MIP/CP). Это обеспечивает хороший инструмент для экспериментов (работает ли он, оценивает решения, оценивает производительность). При необходимости позже можно разработать эвристику для повышения производительности. С помощью модели оптимизации вы можете, по крайней мере, сравнить оптимальные решения (в противном случае вы полностью в неведении относительно качества решений wrt). Если у вас нет опыта в этом, возможно, наймите студента, который поможет вам в этом.
Ответ №1:
Я провел быстрый и грязный тест с моделью, которая может работать с командами. Просто для иллюстрации.
Я создал два типа работников: тип A и тип B, а также команды, состоящие из двух работников (по одному от каждого типа). Кроме того, я создал случайные данные о затратах.
Вот частичная распечатка всех данных.
---- 13 SET i workers,teams
a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10
b1 , b2 , b3 , b4 , b5 , b6 , b7 , b8 , b9 , b10
team1 , team2 , team3 , team4 , team5 , team6 , team7 , team8 , team9 , team10
team11 , team12 , team13 , team14 , team15 , team16 , team17 , team18 , team19 , team20
team21 , team22 , team23 , team24 , team25 , team26 , team27 , team28 , team29 , team30
team31 , team32 , team33 , team34 , team35 , team36 , team37 , team38 , team39 , team40
team41 , team42 , team43 , team44 , team45 , team46 , team47 , team48 , team49 , team50
team51 , team52 , team53 , team54 , team55 , team56 , team57 , team58 , team59 , team60
team61 , team62 , team63 , team64 , team65 , team66 , team67 , team68 , team69 , team70
team71 , team72 , team73 , team74 , team75 , team76 , team77 , team78 , team79 , team80
team81 , team82 , team83 , team84 , team85 , team86 , team87 , team88 , team89 , team90
team91 , team92 , team93 , team94 , team95 , team96 , team97 , team98 , team99 , team100
---- 13 SET w workers
a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10, b1 , b2 , b3 , b4 , b5
b6 , b7 , b8 , b9 , b10
---- 13 SET a a workers
a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10
---- 13 SET b b workers
b1 , b2 , b3 , b4 , b5 , b6 , b7 , b8 , b9 , b10
---- 13 SET t teams
team1 , team2 , team3 , team4 , team5 , team6 , team7 , team8 , team9 , team10
team11 , team12 , team13 , team14 , team15 , team16 , team17 , team18 , team19 , team20
team21 , team22 , team23 , team24 , team25 , team26 , team27 , team28 , team29 , team30
team31 , team32 , team33 , team34 , team35 , team36 , team37 , team38 , team39 , team40
team41 , team42 , team43 , team44 , team45 , team46 , team47 , team48 , team49 , team50
team51 , team52 , team53 , team54 , team55 , team56 , team57 , team58 , team59 , team60
team61 , team62 , team63 , team64 , team65 , team66 , team67 , team68 , team69 , team70
team71 , team72 , team73 , team74 , team75 , team76 , team77 , team78 , team79 , team80
team81 , team82 , team83 , team84 , team85 , team86 , team87 , team88 , team89 , team90
team91 , team92 , team93 , team94 , team95 , team96 , team97 , team98 , team99 , team100
---- 13 SET j jobs
job1 , job2 , job3 , job4 , job5 , job6 , job7 , job8 , job9 , job10, job11, job12
job13, job14, job15
---- 23 SET team composition of teams
team1 .a1 , team1 .b1 , team2 .a1 , team2 .b2 , team3 .a1 , team3 .b3 , team4 .a1
team4 .b4 , team5 .a1 , team5 .b5 , team6 .a1 , team6 .b6 , team7 .a1 , team7 .b7
team8 .a1 , team8 .b8 , team9 .a1 , team9 .b9 , team10 .a1 , team10 .b10, team11 .a2
team11 .b1 , team12 .a2 , team12 .b2 , team13 .a2 , team13 .b3 , team14 .a2 , team14 .b4
team15 .a2 , team15 .b5 , team16 .a2 , team16 .b6 , team17 .a2 , team17 .b7 , team18 .a2
team18 .b8 , team19 .a2 , team19 .b9 , team20 .a2 , team20 .b10, team21 .a3 , team21 .b1
team22 .a3 , team22 .b2 , team23 .a3 , team23 .b3 , team24 .a3 , team24 .b4 , team25 .a3
team25 .b5 , team26 .a3 , team26 .b6 , team27 .a3 , team27 .b7 , team28 .a3 , team28 .b8
team29 .a3 , team29 .b9 , team30 .a3 , team30 .b10, team31 .a4 , team31 .b1 , team32 .a4
team32 .b2 , team33 .a4 , team33 .b3 , team34 .a4 , team34 .b4 , team35 .a4 , team35 .b5
team36 .a4 , team36 .b6 , team37 .a4 , team37 .b7 , team38 .a4 , team38 .b8 , team39 .a4
team39 .b9 , team40 .a4 , team40 .b10, team41 .a5 , team41 .b1 , team42 .a5 , team42 .b2
team43 .a5 , team43 .b3 , team44 .a5 , team44 .b4 , team45 .a5 , team45 .b5 , team46 .a5
team46 .b6 , team47 .a5 , team47 .b7 , team48 .a5 , team48 .b8 , team49 .a5 , team49 .b9
team50 .a5 , team50 .b10, team51 .a6 , team51 .b1 , team52 .a6 , team52 .b2 , team53 .a6
team53 .b3 , team54 .a6 , team54 .b4 , team55 .a6 , team55 .b5 , team56 .a6 , team56 .b6
team57 .a6 , team57 .b7 , team58 .a6 , team58 .b8 , team59 .a6 , team59 .b9 , team60 .a6
team60 .b10, team61 .a7 , team61 .b1 , team62 .a7 , team62 .b2 , team63 .a7 , team63 .b3
team64 .a7 , team64 .b4 , team65 .a7 , team65 .b5 , team66 .a7 , team66 .b6 , team67 .a7
team67 .b7 , team68 .a7 , team68 .b8 , team69 .a7 , team69 .b9 , team70 .a7 , team70 .b10
team71 .a8 , team71 .b1 , team72 .a8 , team72 .b2 , team73 .a8 , team73 .b3 , team74 .a8
team74 .b4 , team75 .a8 , team75 .b5 , team76 .a8 , team76 .b6 , team77 .a8 , team77 .b7
team78 .a8 , team78 .b8 , team79 .a8 , team79 .b9 , team80 .a8 , team80 .b10, team81 .a9
team81 .b1 , team82 .a9 , team82 .b2 , team83 .a9 , team83 .b3 , team84 .a9 , team84 .b4
team85 .a9 , team85 .b5 , team86 .a9 , team86 .b6 , team87 .a9 , team87 .b7 , team88 .a9
team88 .b8 , team89 .a9 , team89 .b9 , team90 .a9 , team90 .b10, team91 .a10, team91 .b1
team92 .a10, team92 .b2 , team93 .a10, team93 .b3 , team94 .a10, team94 .b4 , team95 .a10
team95 .b5 , team96 .a10, team96 .b6 , team97 .a10, team97 .b7 , team98 .a10, team98 .b8
team99 .a10, team99 .b9 , team100.a10, team100.b10
---- 28 PARAMETER c cost coefficients
job1 job2 job3 job4 job5 job6 job7 job8 job9
a1 17.175 84.327 55.038 30.114 29.221 22.405 34.983 85.627 6.711
a2 63.972 15.952 25.008 66.893 43.536 35.970 35.144 13.149 15.010
a3 11.049 50.238 16.017 87.246 26.511 28.581 59.396 72.272 62.825
a4 18.210 64.573 56.075 76.996 29.781 66.111 75.582 62.745 28.386
a5 7.277 17.566 52.563 75.021 17.812 3.414 58.513 62.123 38.936
a6 78.340 30.003 12.548 74.887 6.923 20.202 0.507 26.961 49.985
a7 99.360 36.990 37.289 77.198 39.668 91.310 11.958 73.548 5.542
a8 22.575 39.612 27.601 15.237 93.632 42.266 13.466 38.606 37.463
a9 10.169 38.389 32.409 19.213 11.237 59.656 51.145 4.507 78.310
a10 50.659 15.925 65.689 52.388 12.440 98.672 22.812 67.565 77.678
b1 73.497 8.544 15.035 43.419 18.694 69.269 76.297 15.481 38.938
b2 8.712 54.040 12.686 73.400 11.323 48.835 79.560 49.205 53.356
b3 2.463 17.782 6.132 1.664 83.565 60.166 2.702 19.609 95.071
b4 39.334 80.546 54.099 39.072 55.782 93.276 34.877 0.829 94.884
b5 58.032 16.642 64.336 34.431 91.233 90.006 1.626 36.863 66.438
b6 49.662 4.493 77.370 53.297 74.677 72.005 63.160 11.492 97.116
b7 79.070 61.022 5.431 48.518 5.255 69.858 19.478 22.603 81.364
b8 81.953 86.041 21.269 45.679 3.836 32.300 43.988 31.533 13.477
b9 6.441 41.460 34.161 46.829 64.267 64.358 33.761 10.082 90.583
b10 40.419 11.167 75.113 80.340 2.366 48.088 27.859 90.161 1.759
team1 50.421 83.126 60.214 8.225 57.776 59.318 68.377 15.877 33.178
team2 57.624 71.983 68.373 1.985 83.980 71.005 15.551 61.071 66.155
team3 1.252 1.017 95.203 97.668 96.632 85.628 14.161 4.973 55.303
team4 34.968 11.734 58.598 44.553 41.232 91.451 21.378 22.417 54.233
team5 31.014 4.020 82.117 23.096 41.003 30.258 44.492 71.600 59.315
team6 68.639 67.463 33.213 75.994 17.678 68.248 67.299 83.121 51.517
team7 8.469 57.216 2.206 74.204 90.510 56.082 47.283 71.756 51.301
team8 96.552 95.789 89.923 32.755 45.710 59.618 87.862 17.067 63.360
team9 33.626 58.864 57.439 54.342 57.816 97.722 32.147 76.297 96.251
. . .
team98 21.277 8.252 28.341 97.284 47.146 22.196 56.537 89.966 15.708
team99 77.385 12.015 78.861 79.375 83.146 11.379 3.413 72.925 88.689
team100 11.050 20.276 21.448 27.928 15.073 76.671 91.574 94.498 7.094
(cost data for other jobs skipped)
Моя попытка смоделировать это как модель смешанного целочисленного программирования выглядит следующим образом:
Очевидно, что это уже не проблема чистого назначения. Первое ограничение сложнее, чем мы привыкли. В нем говорится, что для каждого работника w мы можем назначить его/себя или любую команду, в которой w является членом только один раз.
Когда я решаю эту проблему без использования команд, я получаю следующее решение:
---- 56 VARIABLE x.L assignment
job1 job2 job3 job4 job5 job6 job7 job8 job9
a5 1
a6 1
b1 1
b3 1
b4 1
b6 1
b8 1
b9 1
b10 1
job10 job11 job12 job13 job14 job15
a1 1
a4 1
a7 1
b2 1
b5 1
b7 1
---- 56 VARIABLE z.L = 59.379 total cost
Это стандартная проблема с назначением, но я решил ее как LP (чтобы использовать те же инструменты).
Когда я разрешаю командам, я получаю:
---- 65 VARIABLE x.L assignment
job1 job2 job3 job4 job5 job6 job7 job8 job9
a1 1
a5 1
a6 1
b3 1
b4 1
b9 1
b10 1
team17 1
team28 1
job10 job11 job12 job13 job14 job15
a4 1
a7 1
b2 1
b5 1
team86 1
team91 1
---- 65 VARIABLE z.L = 40.057 total cost
Цель лучше (просто потому, что она может отбирать команды с низкой «стоимостью»). Также обратите внимание, что в решении ни один работник не выбирается дважды (ни индивидуально, ни в составе команды). Вот некоторый дополнительный отчет о решении, который подтверждает это:
---- 70 SET sol alternative solution report
job1 job2 job3 job4 job5 job6 job7 job8 job9
team17.a2 YES
team17.b7 YES
team28.a3 YES
team28.b8 YES
- .a1 YES
- .a5 YES
- .a6 YES
- .b3 YES
- .b4 YES
- .b9 YES
- .b10 YES
job10 job11 job12 job13 job14 job15
team86.a9 YES
team86.b6 YES
team91.a10 YES
team91.b1 YES
- .a4 YES
- .a7 YES
- .b2 YES
- .b5 YES
Обратите внимание, что модель не очень маленькая:
MODEL STATISTICS
BLOCKS OF EQUATIONS 3 SINGLE EQUATIONS 36
BLOCKS OF VARIABLES 2 SINGLE VARIABLES 1,801
NON ZERO ELEMENTS 6,901 DISCRETE VARIABLES 1,800
Однако модель MIP решается довольно легко: менее чем за секунду.
Я не тестировал модель на больших наборах данных. Это просто для того, чтобы показать, как можно подойти к подобной проблеме.
Комментарии:
1. не могли бы вы добавить библиотеки, которые вы используете для решения проблемы модели MIP?
2. Я использовал GAMS/Cplex. Но это универсальная модель MIP, поэтому подойдет любой решатель MIP (по крайней мере, для небольших экземпляров). Большие экземпляры могут потребовать немного больше размышлений.
Ответ №2:
Есть очевидная эвристика, которую вы могли бы попробовать:
- Решите классическую задачу с помощью венгерского алгоритма,
- Затем, используя пул неназначенных агентов, найдите комбинированное назначение для каждого, которое дает наибольшее улучшение.
Конечно, не оптимальный, но явное улучшение первого порядка по сравнению с одним только венгерским алгоритмом.
Комментарии:
1. у нас около 2 агентов на задание, поэтому пул неназначенных агентов может быть большим, так что предлагаемое вами решение становится дорогостоящим с точки зрения вычислений. Спасибо, еще попробую этот подход на симуляциях
2. @ArtyomAkselrod Это действительно не так дорого с точки зрения вычислений, это всего лишь дополнительная
O(n^2)плата, и венгерский алгоритм уже самO(n^3)по себе илиO(n^4)поэтому он не меняет большого О.
Ответ №3:
Венгерский алгоритм-устаревшее решение, которое остается популярным по какой-то необъяснимой причине, которую я не понимаю (возможно, потому, что оно концептуально простое).
Используйте поток минимальных затрат для моделирования вашей проблемы. Он гораздо более гибкий и имеет множество эффективных алгоритмов. Это также может быть доказано для решения любой проблемы, которую может решить венгерский алгоритм (доказательство простое).
Учитывая очень расплывчатое описание вашей проблемы, вы хотели бы смоделировать базовый граф G=(V,E) с двумя слоями узлов V = (O,W), где O-заказы, а W-рабочие.
Ребра могут быть направлены, при этом каждый работник имеет ребро емкостью 1 для каждого возможного заказа. Подключите исходный узел к работнику с пропускной способностью 1 и подключите каждый узел заказа к узлу-приемнику с пропускной способностью 2 (или выше, что позволяет использовать больше работников на заказ).
То, что я описал выше, на самом деле является экземпляром maxflow, а не MCF, поскольку он не присваивает весов. Однако вы можете назначить веса любому из ребер.
Учитывая вашу формулировку проблемы, я не понимаю, как это вообще проблема с назначением, не можете ли вы использовать простую стратегию типа «первый пришел первым» (очередь), учитывая, что у вас, похоже, нет никаких критериев, по которым работник предпочитает работать над определенным заказом, а не над другим.
Комментарии:
1. извините, но у меня, очевидно, есть критерии, мне нужно оптимизировать клик, чтобы поесть, поэтому обычно наиболее предпочтителен ближайший к работе работник. Однако иногда велосипедист, находящийся на большом расстоянии от работы, может быть более эффективным, чем пеший курьер. В моей службе доставки мы получаем X заказов в минуту, и мы должны назначать наших работников на эти заказы, что на самом деле является проблемой назначения, я считаю
2. таким образом, наши расходы-это время полета (время, чтобы добраться до магазина) покупка необходимых товаров для заказов доставка. Иногда у нас есть 2 работника, назначенных для одного заказа, потому что может быть эффективно покупать товары одним работником и доставлять другим
3. Хорошо, вы очень расплывчато объясняете, как устроена ваша проблема. Если я правильно понимаю, работник может быть назначен либо водителем велосипеда, либо покупателем? Можем ли мы сказать, что эффективность (доход минус затраты) равна X с покупателем и X Y с покупателем и водителем велосипеда (т. Е. Эффект линейный)? Если эффект нелинейный, ваша проблема будет намного сложнее.