维度

路线求解器使用名为“维度”的对象来跟踪沿车辆路线累计的数量（例如行程时间），或者，如果车辆正在自提和交货，则跟踪其携带的总重量。如果路由问题涉及此类数量（无论是约束还是目标函数），您需要定义一个维度来指定限制。

本部分介绍了如何定义和使用维度。

维度示例

以下是前几部分中的维度示例。

  • VRPTW 示例会创建一个维度来跟踪每辆车的累计行程时间。求解器使用该维度强制规定车辆只能访问该时间范围内的营业地点。

  • CVRP 示例为需求（例如，要提取的权重或包裹数量）创建维度，用于跟踪车辆沿其路线承载的累计负载。该求解器使用该维度强制执行车辆负载不会超过其容量的限制。

以下示例使用 AddDimension 方法定义了 VRPTW 的维度。

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

AddDimension 方法具有以下输入：

  • callback_index：返回数量的回调的索引。索引是求解器的内部对回调的引用，通过 RegisterTransitCallback 或 RegisterUnitaryTransitCallback 等方法创建。
  • slack_max：slack（用于表示营业地点的等待时间）的最大值。如需了解详情，请参阅下文的 Slack 变量。如果此问题不涉及等待时间，通常可以将 slack_max 设置为 0。
  • capacity：沿每条路线累积的总数上限。使用 capacity 创建类似于 CVRP 中的限制条件。如果您的问题没有此类限制，您可以将 capacity 设置为足够大的值，不对路线施加限制，例如，用于定义回调的矩阵或数组的所有条目的总和。
  • fix_start_cumulative_to_zero：布尔值。如果为 true，则数量的累积值从 0 开始。在大多数情况下，应将其设置为 True。不过，对于 VRPTW 或资源限制问题，由于时间限制，某些车辆可能需要在时间 0 之后启动，因此对于这些问题，您应将 fix_start_cumulative_to_zero 设置为 False。
  • dimension_name：维度名称字符串，例如 'Distance'，可用于访问程序中其他位置的变量。

CVRP 程序使用 AddDimensionWithVehicleCapacity 方法创建略有不同的维度类型。此方法需要一个容量数组，每个车辆对应一个条目。（AddDimension 与之不同的是，capacity 采用单个值，因此假定所有车辆都具有相同的容量。）

如需了解创建维度的其他方法，请参阅 RoutingModel 参考页面。

将解决方案时间窗口保存到列表或数组部分介绍了将累积数据保存到列表或数组中的维度的函数。

Slack 变量

以下示例说明了涉及行程时间的问题的 Slack 变量。假设车辆在其路线的一个步骤中从位置 i 到达位置 j，并且：

  • 车辆在 i 的累计行驶时间为 100 分钟。
  • 车辆在 j 的累计行程时间为 200 分钟。
  • 从 i 到 j 需要 75 分钟。

车辆在到达时不能立即离开地点 i，否则其在地点 j 的累计时间将为 175。相反，车辆必须在位置 i 等待 25 分钟才能离开；换言之，位置 i 为 25 分钟。

在 VRPTW 中需要留出时间，因为受时间限制，车辆可能需要等待一段时间才能前往某个地点。在此类问题中，请将 slack_max 设为您希望车辆在到达下一个位置之前等待的最长时间。无论用户等待多久，都可以将 slack_max 设置为非常大的数字。

另一方面，对于 CVRP，累计负载从 i 更改为 j 时始终等于 i 的需求，因此不会有任何空缺。对于此类问题，您可以将 slack_max 设置为 0。

接下来，我们将介绍 Slack 的正式定义。在内部，维度会存储两类与沿路线累积的数量相关的变量：

  • 公交变量：路由的每个步骤中的数量的增加或减少。如果 i -> j 是路线中的路段之一，则公交变量要么是公交矩阵的 i、j 条目（公交公交），要么就是位置 i 的回调值（如果回调函数仅靠一个地点）。
  • 累计变量：每个地理位置的累计数量。您可以通过 dimension_name.CumulVar(i) 在位置 i 访问累积变量。如需查看示例，请参阅 VRPTW 示例中的时间范围限制。

假设车辆一步完成从位置 i 到位置 j 的操作，该 Slack 与这些变量相关，如下所示： 

slack(i) = cumul(j) - cumul(i) - transit(i, j)

如需详细了解维度，请参阅参考部分中的 RoutingDimension。