Google OR-tools Pickups and deliveries 多次访问同一节点

Question

我目前正在使用 C# 和 Google-Or-Tools 来解决 VRP 问题

问题陈述：

我有一个 Depot 节点 0 和 3 个位置节点 (1,2) (1',3) (4,5)。 位置 1 和 1' 是相同的位置（2 个订单）。

车辆容量：10

在位置 1 我需要取 10 个单位

在位置 2 我需要下车 10 个单位

在位置 1' 我需要取 5 个单位

在位置 3 我需要下车 5 个单位

运行程序，它显示以下路由

 Route 1: 0 Load(0) -> 1 Load(10) -> 2 Load(0) -> 1' Load(5) -> 3 Load(0) -> 4 Load(10) -> 5 Load(0)

https://ibb.co/3sYxQYH（抱歉，我无法上传图片）

我的问题是如何使用 or-tools 实现求解器：

每个地点只允许访问一次

例子

路线 1：0 负载(0) -> 1 负载(10) -> 2 负载(0) -> 4 负载(10) -> 5 负载(0)

路线 2：0 负载(0) -> 1' 负载(5) -> 3 负载(0)
位置连续时可以访问多个（1需要取5个单位，1'需要取5个单位）

示例：0 负载(0) -> 1 负载(5) -> 1' 负载(10) -> 2 负载(5) -> 3 负载(0) -> 4 负载(10) -> 5 加载(0)

Answer 1

限制路由只访问一个列表中的一个节点（这里[1, 1']）。
我会：

创建一个“location_token”RoutingDimension：

强制所有松弛度为 0
将容量车辆设置为至少 1
强制开始累积为零
访问时加一 1, 1'
注意：使用容量示例中的一元回调 (https://developers.google.com/optimization/routing/cvrp#demand)

token_transit_callback(from_index):
  from_node = manager.IndexToNode(from_index)
  # return one upon visiting 1 or 1'
  if from_node in (one_node, one_prime_node):
      return 1
  return 0

token_transit_callback_index = routing.RegisterUnaryTransitCallback(
      token_transit_callback)
routing.AddDimension(
  token_transit_callback_index,
  0, # no slack
  1, # vehicle capacity
  True, # force start cumul to zero
  'location_token')

添加约束以访问 1 或 1' 您需要“location_one_token”维度为零（即您尚未访问某些节点在列表中）。

node_list = [one_node, one_prime_node] # 1, 1'
location_token_dim = routing.GetDimensionOrDie('location_token')
for node in node_list:
    index = manager.NodeToIndex(node)
    routing.Solver().Add(location_token_dim.CumulVar(index) < 1)

如果你想允许 1 -> 1' 或 1' -> 1，那么我会使用常规回调和通常的两个参数 from_index 和 to_index .
如果对于 transit(1, 1') 和 transit(1, 1`)，诀窍是不增加令牌数像这样：

token_transit_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    out = 0
    # return one upon visiting 1 or 1'
    if from_node in (one_node, one_prime_node):
        out = 1
    # except if next node is 1 or 1'
    if to_node in (one_node, one_prime_node):
        out = 0
    return out

Google OR-tools Pickups and deliveries 多次访问同一节点

Google OR-tools Pickups and deliverys Multiple Visits of same node

or-tools