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

Question

我正在使用 OR-Tool 解决 VRP 问题。我对文档中的示例问题进行了一些实验，并设法编写了一个功能正常的程序，但是，我不了解 SetGlobalSpanCostCoefficient 的用途以及如何正确设置它。根据this site，它是全局跨度成本与所有路由中最大和最小维度值之间的差值之间的系数。那么，这个全局成本是所有路线成本的总和吗，它是根据维度的 'capacity' 参数计算出来的，并且像最大容量限制器一样使用。

我的代码中的问题是，除非我在 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)

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

Answer 1

跨度成本是用来衡量空闲时间的。

参见：the SetGlobalSpanCostCoefficient doc entry

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

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

Answer 2

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

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

据我了解，我认为此函数调整（配置）objective 函数（线性程序求解器试图最小化的函数）。在这样的问题中，通常您希望最小化总路线长度（所有车辆路线长度的总和）。

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

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

但我认为在那种情况下 objective 函数更复杂，它只是最小化所有车辆路线长度的总和，我认为它们也会最小化 最长路线 [=83= 的比率]/更短的路线.

由于它是一个二维问题，因此有几个最佳解决方案。每个解属于二维解的一个 Pareto 边界space。解决方案 space 中的每个点都只是一个解决方案，即（路线长度总和，最长路线/较短的路线比率）对。这是它的样子 (ref):

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

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

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

Sets a cost proportional to the global dimension span, that is the difference between the largest value of route end cumul variables and the smallest value of route start cumul variables. In other words: global_span_cost = coefficient * (Max(dimension end value) - Min(dimension start value)).

不太清楚这是否符合我之前描述的内容。因为据我所知 global_span_cost 不是路由长度的总和，而是正如他们所说，它是路由的“全局跨度，在这个例子中是最大值路线的距离”。所以我想这是所有车辆路线中最长路线的长度。我不知道什么是“最终价值”和“开始价值”。同样，所有这些都是基于假设......

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

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（对两个维度“总和”和“最大。”).

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

a) 最大路由长度 = 3，路由总长度 = .7

b) 最大路由长度 = 2.4，路由总长度 = 1

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

同样，我只是写下了我的猜测，因为 none 这似乎已经记录在案（或者可能只是很难找到？）。另外，我仍然不知道如何根据您的 preferences/needs.
选择该系数

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

How to set SetGlobalSpanCostCoefficient and the capacity parameter in AddDimension properly?

python

or-tools