如何在 AddDimension 中正确设置 SetGlobalSpanCostCoefficient 和容量参数？

Question

我正在使用 OR-Tool 来解决 VRP 问题。我已经对文档中的示例问题进行了一些实验，并设法编写了一个正常运行的程序，但是，我不明白 SetGlobalSpanCostCoefficient 的目的以及如何正确设置它。根据该站点，它是全局跨度成本与所有路线中最大和最小尺寸值之间的差异之间的系数。那么，这个全局成本是所有路线成本的总和吗，它是从维度的“容量”参数计算出来的，并像最大容量限制器一样使用。

我的代码中的问题是，除非我手动调整 AddDimension 函数中的容量（最大路线距离）和 globalSpanCostcoefficient，否则不会使用 somme vihecles。我有 1000 个节点： 距离分布（以米为单位）如下所示：

    # Add Distance constraint.
    distance_dimension_name = 'Distance'
    routing.AddDimension(
        transit_callback_index,
        0,  # no slack
        25000,  # vehicle maximum travel distance
        True,  # start cumul to zero
        distance_dimension_name)
    distance_dimension = routing.GetDimensionOrDie(distance_dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

在这里，我得到了 2610m 的最大路线距离，有 5 辆和 6 辆汽车，它聚集在两条路线上。我试图添加一个像这里描述的计数维度，但即使对于 100 个节点它也变得太慢，并且结果与 5 辆车相同。

Answer 1

跨度成本旨在衡量空闲时间。

请参阅：SetGlobalSpanCostCoefficient 文档条目

它与维度弧成本不同，因为 (1) 它包含节点处的松弛，以及 (2) 它不计算仓库的初始等待时间。

在您的示例中，您都禁止松弛，并强制第一个 cumul 为 0。因此 SpanCost 是无用的。

Answer 2

文档非常神秘，很难真正理解发生了什么。有很多行话，但从来没有明确定义（正式）。但这是我根据我想象它所做的猜测（基于纯粹的猜测和实验）。

首先我认为这个工具使用线性规划（求解器）。这可能有助于了解正在发生的事情。

据我所知，我认为这个函数会调整（配置）目标函数（线性规划求解器试图最小化的函数）。在像这样的问题中，通常您希望最小化总路线长度（所有车辆路线长度的总和）。

如果您只尝试将其最小化，那么在没有任何进一步约束的情况下，该问题的最佳解决方案是单次游览（一辆车访问每个节点一次）。

添加到此类问题中的一个典型约束是限制最大路线长度（此约束使得单个车辆不可能在一次旅行中访问所有节点）。我认为，您有几种解决方案，例如：1）增加车辆数量，2）允许车辆加油（能量受限），……

但我认为在那种情况下，目标函数更复杂，只是最小化所有车辆路线长度的总和，我认为他们也最小化了最长路线/较短路线的比率。

由于它是一个二维问题，因此有几个最佳解决方案。每个解都属于二维解空间的一个帕累托边界。解决方案空间中的每个点只是一个解决方案，即（路线长度总和，最长路线/较短路线比率）对。这是它的样子（参考）：

我认为这个工具不会寻找所有这些解决方案（因为解决多标准问题非常困难，当找到一个解决方案点已经很困难时更是如此）。相反，我认为他们试图找到最接近给定仿射函数的解决方案，如下所示：

该函数的斜率表示“您对一个标准的重视程度高于另一个标准”。在那种情况下，由于我们想要最小化最大路由长度和总路由长度，我猜这就是这个配置函数的作用。它设置斜率。

另一方面，给出文档中的描述：

设置与全局维度跨度成比例的成本，即路径结束累积变量的最大值与路径起始累积变量的最小值之间的差值。换句话说：global_span_cost = coefficient * (Max(dimension end value) - Min(dimension start value))。

目前还不清楚这是否与我之前描述的相符。因为据我所知global_span_cost不是路线长度的总和，正如他们所说，它是“路线的全局跨度，在本例中是路线距离的最大值”。所以我猜这是所有车辆路线中最长路线的长度。我无法弄清楚“最终价值”和“起始价值”是什么。再说一次，这一切都是基于假设……

因此，斜率系数可能是固定的（某个常数，1？），而该系数会影响两个轴之一（其在 2D 解空间中的坐标）上的解点映射。例如，如果您有两个解决方案：

• a) 最大路由长度 = 10，路由长度总和 = 63
• b) 最大路由长度 = 8，路由长度总和 = 90

（请注意，两者都无法比较，在一个标准上，每个都比另一个更好，它们都是“最佳”）。

他们可能会标准化每个维度：

• a) 最大路由长度 = 20 / 20，路由长度总和 = 63 / 90
• b) 最大路由长度 = 16 / 20，路由长度总和 = 90 / 90

这使：

• a) 最大路由长度 = 1，路由长度总和 = .7
• b) 最大路由长度 = .8，路由长度总和 = 1

使用这两种解，如果用于区分不可y = x比解的仿射函数为，则解a)略好于解b)。由于x = y两个标准在选择中具有相同的重要性，因此solution 1 = 1.7和solution 2 = 1.8（两个维度“sum.”和“max.”的简单总和）。

通过改变斜率，我们基本上让第一个标准比第二个更重要，这相当于将第一个标准乘以给定的因子，例如，3：

• a) 最大路由长度 = 3，路由长度总和 = .7
• b) 最大路由长度 = 2.4，路由长度总和 = 1

给出solution a = 3.7和solution b = 3.4，解决方案 b) 现在比解决方案 a) 更好。

同样，我只是写下我的猜测，因为这些似乎都没有记录（或者可能很难找到？）。此外，我仍然不知道如何根据您的喜好/需要选择该系数。