Dimensions

路线求解器使用一个称为维度的对象来跟踪 车辆沿途累积的数量，例如行程时间或 如果车辆在取车和送货，其总重量是多少 ，了解所有最新动态。如果路由问题涉及这样的数量，无论是在约束条件中，还是在约束条件中， 您需要定义一个维度来指定它们。

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

维度示例

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

  • VRPTW 示例创建了一个用于跟踪的维度 每辆车的累计行程时间求解器使用维度强制 对车辆只能访问位置范围内某个位置的限制 。

  • CVRP 示例为 需求（例如要自提的包裹的重量或体积），用于跟踪 车辆沿其行驶路线的累计负载。 求解器使用该维度来强制实施车辆负载约束条件 不能超过其容量

以下示例使用 AddDimension 方法。

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 变量

下面的示例展示了涉及 路途时间。假设 某辆车在其路线的一个路段中从位置 i 到位置 j，并且：

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

车辆无法在到达后立即离开位置 i 或其累计值 地点 j 的时间为 175。车辆必须在 出发前的地点 i；也就是说，位置 i 的松厚度为 25。

您需要允许 VRPTW 使用 Slack，因为车辆可能需要等待 访问某个地理位置（由于时间范围限制）。在这类问题中， slack_max到您希望允许车辆等待的最长时间 然后才能前往下一个位置。这无关紧要 只需将 slack_max 设置为一个非常大的数字即可。

另一方面，对于 CVRP，累积负载从 i 变为 j 始终等于 i 的需求，因此没有空余。对于诸如 可以将 slack_max 设置为 0。

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

  • 公交变量： 路径。 如果 i -> j 是路线中的一个路段，则公交变量为 i、 公交矩阵的 j 条目（适用于公交回调），或者干脆是 位置 i 处的回调值（如果回调仅依赖于一个位置）。
  • 累积变量：每个营业地点的累计数量。您 可以通过以下方式访问位置 i 的累积变量： dimension_name.CumulVar(i)。有关示例，请参见 时间范围限制 。

假设车辆从位置 i 前往位置 j 一步， Slack 与这些变量的关系如下： 

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

有关维度的详细信息，请参阅 RoutingDimension 部分。