问题：

或具有多次出行、多次取货和有限容量的工具车辆路线

欧阳睿范

2023-03-14

我正在尝试解决一个路由问题，如下所示：

我们有许多“任务”，每个任务都包含许多需要工人收集的项目

我的问题是如何使用或工具实现以下解算器：

允许每个工人“卸载”在仓库收集的物品并继续下一次行程

到目前为止，我已经尝试：

将n个任务中出现的相同项目视为n个不同的节点（反映在距离矩阵中，这些n个节点之间的距离设置为0）

很抱歉问了这么长的问题，谢谢，请帮忙！

更新：我使用了AddDisconction和AddPickupAndDelivery，结果似乎是我所期望的。我不能百分之百确定这是否是这个问题的答案。我将不同任务中出现的相同项目视为不同的节点。并将每个任务中的整个项目集添加为析取集。对于收货和发货，我没有复制节点，我只是让每个项目指向该任务中的同一个1项目。

我编写的代码（已更新）：

    # "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

共有2个答案

雷晋

2023-03-14

为正在处理类似设置问题的任何人发布我的最终解决方案：

允许每辆车“卸载”在车辆段收集的物品并继续下一次行程
设置限制工作人员最多在3个任务中收集项目的约束

对于1，我只需将车辆数量设置为与任务数量相等。找到的解决方案应该包含许多没有项目的车辆。我们的业务用例允许工人在完成当前路线后进入下一条路线，因此无需在ortools中模拟“加载/卸载”。

对于2，因为每个任务都有多个项目。我使用列表来表示特定任务的项目，例如：

items = [1, 2, 3, 4]

然后，所有项目都由列表列表表示，0表示仓库，例如：

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

关键是为每个任务创建一个虚拟节点，并将其需求设置为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

添加容量约束：

# 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')

然后创建拾取和交付约束，其中拾取节点是REAL项目，交付节点是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))

不再需要AddDisconction，因为我的问题总是有一个可行的解决方案，而不会删除任何节点。如果您的问题可能需要删除节点才能获得解决方案，则可以添加析取。

就是这样。

如果您的解算器无法找到解决方案。尝试将您的第一个解决方案策略更改为PATH\u CHEAPEST\u ARC，因为这个策略（我认为）总是为您提供解决方案。

房冥夜

2023-03-14

卸载/多程对于卸载，您必须复制仓库节点并添加负需求来模拟“卸载”（如果卸载太多，使用slackvar重置为零），请参阅：https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/samples/cvrp_reload.py

或者，您可以增加车队，并将每条车辆路线视为可以分配给任何工人的“行程”。i、 e.每个工人可“分配”到多条车辆路线。注意：如果您有时间约束，您可以添加一些约束，如时间维度。积云（End\N）

为每个任务创建计数器维度

现在，如果您查看每个车辆末端节点
通过计算非零任务维度，您可以知道车辆执行的任务数。因此，添加一个约束以将其限制为最多3应该使其IMHO

正在进行的伪代码：

# 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)

类似资料：

具有多次跳闸的OR-Tools CVRP

我正在尝试使用OR Tools的路由解算器来解决多行程容量VRP。我需要的是一个停车场，路线从这里开始和结束因此，车辆应该从每个节点提取货物，直到装满货物。然后转到“卸载位置”，卸载所有节点的重量，并继续从节点收集需求，直到达到时间限制或收集所有货物。然后返回仓库。 CVRP重新装载的例子似乎非常接近，但在我的情况下，在路线的末尾，车辆应该在车辆段之前到达卸载位置。换言之，车辆不能满载前往车辆
错误-多次出现具有不同值的“内容类型”是非法的

我在Eclipse中有一个动态web项目，我在GlassFish4上运行。在项目中，下面给出了一个index.jsp文件。当我在服务器上运行这个jsp时，我得到错误：
具有多个角色并具有多个权限的laravel用户

我想在laravel中创建一个RBAC系统，其中一个用户可以属于多个角色，每个角色可以有多个权限。中间件应在继续请求之前检查用户是否具有特定权限（在其任何角色内）。我能够实施一个案例，其中用户属于一个具有多个权限的角色我需要实现具有多个权限的多个角色的用户。有什么指点吗？
Sass @each具有多个变量

问题内容：我刚刚开始使用Sass和Compass，我喜欢它。我想做的就是利用该功能简化重复性任务。但是，我仅看到了插入一个变量的示例，并且我希望能够使用多个变量。标准方式（来自[Sass参考）：很棒，但是我希望能够执行以下操作：这可能吗？问题答案：我在同一条船上（Sass / Compass的初学者），不得不做类似的事情。这是我使用嵌套列表想到的：这不是最优雅的解决方案，但是如果您找
Python抓取具有多个和嵌套的站点（具有多个声明的网站）

我很难从一些网站上删除多个
具有文本限制的多行编辑文本

如何创建具有文本限制的多行edittext？我设置了edittext的maxLength，但它使edittext成为单行，如果我将inputType添加到textMultiLine，则设置为actionDone的imeOptions将不会显示。我不想为maxLines属性设置静态值。而且，当编辑文本达到其极限时，键盘仍然允许文本，这使得删除文本变得困难。如何解决这个问题？

或具有多次出行、多次取货和有限容量的工具车辆路线

共有2个答案

相关问答

相关文章

相关阅读

相关工具

相关文档