python - OR-Tools 具有多次行程、多次接送和有限容量的车辆路线
问题描述
我正在尝试解决路由问题,如下所示:
- 我们有许多“任务”,每个任务都包含许多要由工人收集的物品
- 项目可以出现在多个任务中(例如项目 1 可以同时出现在任务 A 和 B 中)
- 我们已经有了项目的距离矩阵
- 仓库是固定的
- 每次旅行,每个工人最多只能收集3 个任务中的物品(业务领域约束)
我的问题是如何使用 or-tools 来实现一个求解器:
- 允许每个工人“卸载”在仓库收集的物品并继续下一次旅行
- 设置一个约束,限制工人在最多 3 个任务中收集物品
到目前为止,我已经尝试过:
- 将n个任务中出现的相同项目视为n个不同的节点(反映在距离矩阵中,这n个节点之间的距离设置为0)
- 使用拾取和交付来模拟每个任务,因此每个任务中的一个项目将被同一任务中的其他项目指向。并创建容量约束 3 并将该节点的需求设置为 1。(例如任务 A 包含 [1, 2, 3, 4]。我添加提货和交付 [1, 4], [2, 4], [ 3, 4]。然后为每个工作人员创建 3 的容量约束,并将节点 4 的需求设置为 1。)但是添加这个似乎会杀死 jupyter notebook 内核。(删除这个代码可以运行。)
抱歉问了这么长的问题,谢谢,请帮忙!
更新:我使用了 AddDisjunction 和 AddPickupAndDelivery,结果似乎符合我的预期。我不是 100% 确定这是否是这个问题的答案。我将出现在不同任务中的相同项目视为不同的节点。并将每个任务中的整个项目集添加为析取集。对于取件和交付,我没有复制节点,我只是让每个项目指向该任务中的同一个项目。
我写的代码(更新):
# "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 !')
我得到的结果:
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
解决方案
- Unload/Multitrip 对于卸载,您必须复制 depot 节点并添加负需求以模拟“卸载”(如果卸载过多,则使用 slackvar 重置为零)请参阅:https ://github.com/google/ or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py
或者,您可以增加车队,并将每条车辆路线视为您可以分配给任何工人的“行程”。即每个工人可能被“分配”到几条车辆路线。注意:如果你有时间限制,你可以添加一些限制,比如time_dimension.Cumulvar(End_N) <= time_dimension.CumulVar(Start_N+1)
- 任务限制对于任务限制,我需要考虑一下,我会尝试
- 为每个任务创建一个计数器维度。
- 对于每个项目位置,为相应的任务添加 +1
因此,现在如果您正在查看每个车辆端节点。
您可以通过计算非零任务维度来了解车辆执行的任务数量。因此,添加一个约束以将其限制为最多 3 应该使它成为恕我直言
进行中的伪代码:
# List of tasks
tasks = ("TaskA", "TaskB", "TaskC", ...)
# Task demands 1 if locations index belongs to the task, 0 otherwise
task_demands = {}
task_demands["TaskA"] = (0, 0, 1, 0, ...)
task_demands["TaskB"] = (0, 1, 1, 0, ...)
...
# Creates tasks demand callbacks and register them
# note: this is similar to any capacity dimension example
tasks_demand_evaluator_index = {}
for task in tasks:
def task_demand(index):
node = manager.IndexToNode(index)
return task_demands[task][node]
tasks_demand_evaluator_index[task] =
routing.registerUnaryTransitCallback(task_demand)
# create task dimensions
for task in tasks:
routing.AddDimension(
tasks_demand_evaluator_index[task],
0,
LARGE_ENOUGH,
True, # start at zero
task # dimension name
)
solver = routing.solver()
for vehicle in range(manager.GetNumberOfVehicles()):
end = routing.End(vehicle)
performed_tasks = []
for task in tasks:
dim = routing.GetDimensionOrDie(task)
has_done_this_task = dim.CumulVar(end) > 0 # only true if vehicle visit an item associated to this task
performed_tasks.append(has_done_this_task)
solver.Add(solver.Sum(performed_tasks) <= 3)
推荐阅读
- svn - 如何在 SVN 中隐藏用户的路径
- autohotkey - 使用鼠标位置激活键盘键的代码
- ios - Flutter 应用程序作为从 IOS 上的浏览器接收 pdf 的选项
- python - 如何用变量更新sql表
- amazon-s3 - Cloudwatch 突然上传到 s3 的警报
- ansible - 从 git repo (Ansible for Nsxt) 安装和使用 Ansible 模块
- json - Elasticsearch 查询以获取多个属性的值
- string - 如何在lua中删除多行字符串
- android - Mailchimp 和 Gmail:文本颜色失真
- python - windows上部分导入pyvirtualcam、python 3.8