Reputation: 976
Assignment problem with 2 workers per job
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()
Upvotes: 1
Views: 1227
Answers (3)
Reputation: 16724
I did a quick-and-dirty test with a model that can handle teams. Just for illustration purposes.
I created two types of workers: type A and type B, and also teams consisting of two workers (one of each type). In addition, I created random cost data.
Here is a partial printout of all the data.
---- 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)
My attempt to model this as Mixed-Integer Programming model is as follows:
Obviously, this is no longer a pure assignment problem. The first constraint is more complicated than we are used to. It says for each worker w, we can assign him/herself or any team that has w as member only once.
When I solve this without using teams, I get the following solution:
---- 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
This is a standard assignment problem, but I solved it as an LP (so I could use the same tools).
When I allow teams, I get:
---- 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
The objective is better (just because it could select teams with low "cost"). Also, note that in the solution no worker is selected twice (either individually or part of a team). Here is some additional solution report that confirms this:
---- 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
Note that the model is not very small:
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
However, the MIP model solves quite easily: less than a second.
I did not test the model on large data sets. It is just to show how one could approach a problem like this.
Upvotes: 1
Reputation: 12141
The Hungarian algorithm is an antiquated solution that remains popular for some unexplicable reason I do not understand (perhaps because it is conceptually simple.)
Use Minimum Cost Flow to model your problem. It is far more flexible, and has many efficient algorithms. It can also be proved to solve any problem the Hungarian algorithm can (proof is simple.)
Given the very vague description of your problem, you would want to model the underlying graph G=(V,E) with two layers of nodes V = (O,W), where O are the orders and W are the workers.
Edges can be directed, with each Worker having an edge with capacity 1 to every possible order. Connect the source node to the worker with edge capacity 1 and connect each order node to the sink node with capacity 2 (or higher, allowing for more workers per order).
What I described above is actually a maxflow instance not a MCF as it assigns no weights. You can however, assign weights to any of the edges.
Given your problem formulation, I don't understand how this is even an assignment problem, can you not use a simple first come first assign (queue) type strategy, given you don't seem to have any criteria to have a worker prefer working on a certain order over another.
Upvotes: 1
Reputation: 56725
There's an obvious heuristic that you could try:
- Solve the classical problem using the Hungarian Algorithm,
- Then using the pool of unassigned agents, find the combined assignment for each that gives the biggest improvement.
Certainly not the optimum, but a clear first-order improvement over the Hungarian Algorithm alone.
Upvotes: 0
Related Questions
- Assignment Problem when jobs are available more than once
- How to solve the assignment problem with the hungarian algorithm when there is more than one optimum solution
- Assignment problem with multiple persons needed on each job
- Hungarian algorithm: multiple jobs per worker
- Optimal assignment of jobs that can be solved by one strong worker or multiple weak workers
- Job assignment with NO cost, would Hungarian method work?
- Assigning jobs to workers
- Hungarian algorithm with unequal number of workers and tasks
- Hungarian algorithm: I'm having trouble with assigning as many jobs to workers as possible
- detailed hungarian algorithm(assignment problem) question