I am trying to solve a routing problem as follows:
- We have many ‘tasks’ and each task contains many items to be collected by workers
- items can appear in multiple tasks (e.g. item 1 can be in both task A and B)
- We already have the distance matrix of the items
- depot is fixed
- in each trip, each worker can ONLY collect items in AT MOST 3 tasks (business domain constraint)
My question is how to use or-tools to implement a solver that:
- allows each worker to “unload” the items collected at the depot and continue to next trip
- set a constraint that limits workers to collect items in at most 3 tasks
So far I have tried:
- treat same items appearing in n tasks as n different nodes (reflected in the distance matrix, and the distance among these n nodes are set to 0)
- uses pickup and deliveries to model each task, so one item in each task will be pointed by other items in within the same task. And create a capacity constraint of 3 and set the demand of that node as 1. (e.g. task A contains [1, 2, 3, 4]. I add pickup and deliveries [1, 4], [2, 4], [3, 4]. Then create a capacity constraint of 3 for each worker, and set node 4 a demand of 1.) But adding this seems to kill the jupyter notebook kernal. (Removing this the code can run.)
Sorry for such a long question, thanks and please help!
Update: I made use of AddDisjunction and AddPickupAndDelivery and the results seem to be what I expected. I am not 100% sure if this is the answer to this problem. I am treating same items appearing in different tasks as different nodes. And add the whole set of items in each task as a disjunction set. For pickup and delivery, I didn’t duplicate the nodes, I simply make each item points to the same 1 item in that task.
The code I wrote (updated):
# "order" is the same as a "task" data = { 'distance_matrix': get_distance_matrix(locations), 'demands': demands, 'num_workers': number_of_order_groups, 'max_num_orders': [num_orders_in_group] * number_of_order_groups, 'disjunctions': disjunctions, 'depot': 0, } manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_workers'], data['depot']) routing = pywrapcp.RoutingModel(manager) def distance_callback(from_index, to_index): from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data['distance_matrix'][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data['demands'][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data['max_num_orders'], # vehicle maximum capacities True, # start cumul to zero 'Capacity') for d in data['disjunctions']: routing.AddDisjunction([manager.NodeToIndex(i) for i in d], 100000000, d.shape[0]) for d in data['disjunctions']: for i in d[:-1]: routing.AddPickupAndDelivery(manager.NodeToIndex(i), manager.NodeToIndex(d[-1])) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC search_parameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) else: print('No solution found !')
The result I got:
Objective: 4329 Route for worker 0: 0 Load(0) -> 49 Load(0.0) -> 64 Load(0.0) -> 48 Load(0.0) -> 50 Load(0.0) -> 62 Load(0.0) -> 46 Load(0.0) -> 47 Load(0.0) -> 63 Load(0.0) -> 67 Load(0.0) -> 51 Load(0.0) -> 52 Load(1.0) -> 66 Load(1.0) -> 65 Load(2.0) -> 68 Load(2.0) -> 69 Load(3.0) -> 0 Load(3.0) Distance of the route: 421m Load of the route: 3.0 Route for worker 1: 0 Load(0) -> 178 Load(0.0) -> 163 Load(0.0) -> 179 Load(0.0) -> 136 Load(0.0) -> 137 Load(0.0) -> 160 Load(0.0) -> 170 Load(0.0) -> 143 Load(0.0) -> 183 Load(0.0) -> 145 Load(0.0) -> 144 Load(0.0) -> 181 Load(0.0) -> 169 Load(0.0) -> 132 Load(0.0) -> 165 Load(0.0) -> 167 Load(0.0) -> 182 Load(0.0) -> 138 Load(0.0) -> 140 Load(0.0) -> 166 Load(0.0) -> 133 Load(0.0) -> 168 Load(0.0) -> 172 Load(0.0) -> 161 Load(0.0) -> 171 Load(0.0) -> 142 Load(0.0) -> 162 Load(0.0) -> 164 Load(0.0) -> 139 Load(0.0) -> 175 Load(0.0) -> 159 Load(0.0) -> 177 Load(0.0) -> 134 Load(0.0) -> 173 Load(1.0) -> 135 Load(1.0) -> 141 Load(1.0) -> 146 Load(2.0) -> 176 Load(2.0) -> 180 Load(2.0) -> 184 Load(3.0) -> 0 Load(3.0) Distance of the route: 752m Load of the route: 3.0 Route for worker 2: 0 Load(0) -> 34 Load(0.0) -> 24 Load(0.0) -> 21 Load(0.0) -> 29 Load(0.0) -> 2 Load(0.0) -> 19 Load(0.0) -> 25 Load(0.0) -> 8 Load(0.0) -> 5 Load(0.0) -> 20 Load(0.0) -> 9 Load(0.0) -> 11 Load(0.0) -> 13 Load(0.0) -> 1 Load(0.0) -> 10 Load(0.0) -> 14 Load(0.0) -> 7 Load(0.0) -> 3 Load(0.0) -> 27 Load(0.0) -> 4 Load(0.0) -> 189 Load(0.0) -> 31 Load(0.0) -> 32 Load(0.0) -> 15 Load(0.0) -> 6 Load(0.0) -> 23 Load(0.0) -> 33 Load(0.0) -> 22 Load(0.0) -> 12 Load(0.0) -> 28 Load(0.0) -> 26 Load(0.0) -> 16 Load(1.0) -> 190 Load(1.0) -> 30 Load(1.0) -> 35 Load(2.0) -> 191 Load(3.0) -> 0 Load(3.0) Distance of the route: 730m Load of the route: 3.0 Route for worker 3: 0 Load(0) -> 109 Load(0.0) -> 110 Load(0.0) -> 148 Load(0.0) -> 111 Load(0.0) -> 112 Load(0.0) -> 147 Load(0.0) -> 149 Load(0.0) -> 150 Load(1.0) -> 113 Load(2.0) -> 157 Load(2.0) -> 158 Load(3.0) -> 0 Load(3.0) Distance of the route: 214m Load of the route: 3.0 Route for worker 4: 0 Load(0) -> 117 Load(0.0) -> 129 Load(0.0) -> 127 Load(0.0) -> 76 Load(0.0) -> 123 Load(0.0) -> 71 Load(0.0) -> 122 Load(0.0) -> 115 Load(0.0) -> 119 Load(0.0) -> 125 Load(0.0) -> 74 Load(0.0) -> 73 Load(0.0) -> 72 Load(0.0) -> 130 Load(0.0) -> 116 Load(0.0) -> 120 Load(0.0) -> 124 Load(0.0) -> 70 Load(0.0) -> 75 Load(0.0) -> 118 Load(0.0) -> 128 Load(0.0) -> 77 Load(1.0) -> 126 Load(1.0) -> 131 Load(2.0) -> 121 Load(3.0) -> 0 Load(3.0) Distance of the route: 521m Load of the route: 3.0 Route for worker 5: 0 Load(0) -> 95 Load(0.0) -> 99 Load(0.0) -> 96 Load(0.0) -> 92 Load(0.0) -> 98 Load(0.0) -> 88 Load(0.0) -> 97 Load(0.0) -> 107 Load(0.0) -> 94 Load(0.0) -> 55 Load(0.0) -> 106 Load(0.0) -> 83 Load(0.0) -> 102 Load(0.0) -> 93 Load(0.0) -> 81 Load(0.0) -> 87 Load(0.0) -> 79 Load(0.0) -> 80 Load(0.0) -> 90 Load(0.0) -> 58 Load(0.0) -> 57 Load(0.0) -> 86 Load(0.0) -> 154 Load(0.0) -> 101 Load(0.0) -> 85 Load(0.0) -> 84 Load(0.0) -> 105 Load(0.0) -> 91 Load(0.0) -> 153 Load(0.0) -> 155 Load(0.0) -> 56 Load(0.0) -> 100 Load(0.0) -> 104 Load(0.0) -> 82 Load(0.0) -> 54 Load(0.0) -> 151 Load(0.0) -> 59 Load(1.0) -> 89 Load(1.0) -> 103 Load(1.0) -> 152 Load(1.0) -> 108 Load(2.0) -> 156 Load(3.0) -> 0 Load(3.0) Distance of the route: 721m Load of the route: 3.0 Route for worker 6: 0 Load(0) -> 41 Load(0.0) -> 114 Load(1.0) -> 39 Load(1.0) -> 40 Load(1.0) -> 43 Load(1.0) -> 38 Load(1.0) -> 42 Load(1.0) -> 44 Load(2.0) -> 185 Load(2.0) -> 186 Load(3.0) -> 0 Load(3.0) Distance of the route: 369m Load of the route: 3.0 Route for worker 7: 0 Load(0) -> 78 Load(1.0) -> 60 Load(1.0) -> 61 Load(2.0) -> 187 Load(2.0) -> 188 Load(3.0) -> 0 Load(3.0) Distance of the route: 231m Load of the route: 3.0 Route for worker 8: 0 Load(0) -> 174 Load(1.0) -> 36 Load(1.0) -> 37 Load(2.0) -> 17 Load(2.0) -> 18 Load(3.0) -> 0 Load(3.0) Distance of the route: 198m Load of the route: 3.0 Route for worker 9: 0 Load(0) -> 192 Load(1.0) -> 53 Load(2.0) -> 45 Load(3.0) -> 0 Load(3.0) Distance of the route: 172m Load of the route: 3.0 Total distance of all routes: 4329m Total load of all routes: 30.0
Advertisement
Answer
Posting my final solution for anybody who is working on a similar setting problem:
- allows each vehicle to “unload” the items collected at the depot and continue to next trip
- set a constraint that limits workers to collect items in at most 3 tasks
For 1, I simply set the number of vehicles to be equal the number of tasks. The solution found should contains a lot of vehicles with no items. Our business use case allows workers to move onto next route once he/she has finished the current route so there’s no need to mimic “loading/unloading” in ortools.
For 2, since each task has multiple items. I used a list to represent items for a particular task, e.g.:
items = [1, 2, 3, 4]
Then all the items are represented by a list of list, and 0 is the depot, e.g.:
items = [[0], [1, 2, 3, 4], [5, 6, 7], [8], [9, 10]] # we have 4 tasks here demands = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # all items have 0 demand for now
The key is to created a dummy node for each task and set its demand to 1:
items = [[0], [1, 2, 3, 4, 11], [5, 6, 7, 12], [8, 13], [9, 10, 14]] # we have 4 tasks here demands = [0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1] # dummy nodes have 1 demand
add capacity constraint:
# define demand callback function (demand is the cost of a node) def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data['demands'][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) # associate demand to max_num_orders routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data['max_num_orders'], # worker maximum capacities, 3 in our case True, # start cumul to zero 'Capacity')
Then create pickup and delivery constraints, where the pickup nodes are the REAL items and the delivery nodes are the DUMMIES:
# [1:] because we don't care about the depot for d in data['items'][1:]: for i in d[:-1]: pickup_index = manager.NodeToIndex(i) delivery_index = manager.NodeToIndex(d[-1]) routing.AddPickupAndDelivery(pickup_index, delivery_index) routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
AddDisjunction is no longer required as my problem always has a feasible solution without dropping any node. You might add disjunctions if your problem might requires dropping nodes to get a solution.
That’s it.
If your solver get stuck finding the solution. Try to change your first solution strategy to PATH_CHEAPEST_ARC as this strategy always (I think) gives you a solution.