Optaplanner中CVRP的首次拟合递减算法
First Fit Decreasing Algorithm on CVRP in Optaplanner
我在 Optaplanner 中使用 FFD 算法作为我的 CVRP 问题的构造启发式算法。我以为我从 bin picking 中理解了 FFD-Alg，但是当我在 CVRP 上的 OP 中应用时，我不理解它背后的逻辑。所以我的想法是，它侧重于需求（按降序排列城市，从最高需求开始）。为了证明我的假设，我将城市坐标固定到一个位置，所以到所有城市的站点的距离是相同的。然后我把需求由大改小。但它不会在结果文件中按降序排列城市。
输入为：城市 1：需求 16，城市 2：需求 12，城市 3：需求 8，城市 4：需求 4，
城市 5：需求 2.
3 辆车，每辆车可容纳 40 人。
我想的是：V1<-[C1,C2,C3,C4], V2<-[C5]
发生了什么：V1<-[C5,C4,C3,C2], V2<-[C1]
任何人都可以向我解释一下这个理论吗？另外，我想知道反过来会发生什么，相同的容量，但每个客户的位置不同。我也试过了，但它也没有从最远的城市开始对城市进行排序。
谢谢！
（头脑风暴）
与非 VRP 问题不同，选择 "difficulty comparison" 来确定 "First Fit Decreasing" 的 "Decreasing Difficulty" 并不总是很清楚。我已经用多种形式进行了实验 - 例如基于到站点的距离、到站点的角度、纬度等。您可以在示例中找到所有这些形式的难度比较器，通常是 TSP。
一个常见的陷阱是在启用附近选择之前调整计算器：首先调整附近选择。如果您正在处理大型数据集，"angle to depo" 比较器会表现得更好，只是因为 Nearby Selection and/or Paritioned Search 尚未激活。在任何情况下，一如既往：您需要使用 optaplanner-benchmark 进行此类工作。
这就是说，在纯 TSP用例中，首次拟合递减算法的结果比最近邻算法差（这是我们有限支持 atm 的另一种构造启发式方法。当然，两者都需要本地搜索进一步改进。然而，将最近邻算法转换为 VRP 是 difficult/ambiguous（至少可以这么说）：我 was/am 致力于这样的转换，我称之为 Bouy算法（在以 Bouy 开头的 vrp 示例中寻找 class）。它有效，但它与 IIRC 的 Nearby Selection 结合得不好。
哦，还有 Clarke 和 Wright 储蓄 算法，它非常适合小型纯 CVRP 案例。但是在更大的数据集上遇到 BigO（= 缩放）问题，并且当添加其他约束（例如时间 windows、技能要求、午休时间……）时它也会变成 difficult/ambiguous。
长话短说：对于什么是真实世界的高级 VRP 案例的最佳构建启发式还没有定论。optaplanner-benchmark 将帮助我们实现这一点。尽管所有学术论文都在谈论他们在小型数据集上使用简单形式的 VRP 的完美 CH...
我在 Optaplanner 中使用 FFD 算法作为我的 CVRP 问题的构造启发式算法。我以为我从 bin picking 中理解了 FFD-Alg，但是当我在 CVRP 上的 OP 中应用时，我不理解它背后的逻辑。所以我的想法是，它侧重于需求（按降序排列城市，从最高需求开始）。为了证明我的假设，我将城市坐标固定到一个位置，所以到所有城市的站点的距离是相同的。然后我把需求由大改小。但它不会在结果文件中按降序排列城市。
输入为：城市 1：需求 16，城市 2：需求 12，城市 3：需求 8，城市 4：需求 4， 城市 5：需求 2.
3 辆车，每辆车可容纳 40 人。
我想的是：V1<-[C1,C2,C3,C4], V2<-[C5] 发生了什么：V1<-[C5,C4,C3,C2], V2<-[C1]
任何人都可以向我解释一下这个理论吗？另外，我想知道反过来会发生什么，相同的容量，但每个客户的位置不同。我也试过了，但它也没有从最远的城市开始对城市进行排序。
谢谢！
（头脑风暴）
与非 VRP 问题不同，选择 "difficulty comparison" 来确定 "First Fit Decreasing" 的 "Decreasing Difficulty" 并不总是很清楚。我已经用多种形式进行了实验 - 例如基于到站点的距离、到站点的角度、纬度等。您可以在示例中找到所有这些形式的难度比较器，通常是 TSP。
一个常见的陷阱是在启用附近选择之前调整计算器：首先调整附近选择。如果您正在处理大型数据集，"angle to depo" 比较器会表现得更好，只是因为 Nearby Selection and/or Paritioned Search 尚未激活。在任何情况下，一如既往：您需要使用 optaplanner-benchmark 进行此类工作。
这就是说，在纯 TSP用例中，首次拟合递减算法的结果比最近邻算法差（这是我们有限支持 atm 的另一种构造启发式方法。当然，两者都需要本地搜索进一步改进。然而，将最近邻算法转换为 VRP 是 difficult/ambiguous（至少可以这么说）：我 was/am 致力于这样的转换，我称之为 Bouy算法（在以 Bouy 开头的 vrp 示例中寻找 class）。它有效，但它与 IIRC 的 Nearby Selection 结合得不好。
哦，还有 Clarke 和 Wright 储蓄 算法，它非常适合小型纯 CVRP 案例。但是在更大的数据集上遇到 BigO（= 缩放）问题，并且当添加其他约束（例如时间 windows、技能要求、午休时间……）时它也会变成 difficult/ambiguous。
长话短说：对于什么是真实世界的高级 VRP 案例的最佳构建启发式还没有定论。optaplanner-benchmark 将帮助我们实现这一点。尽管所有学术论文都在谈论他们在小型数据集上使用简单形式的 VRP 的完美 CH...