基于 latitude/longitude 的物流路由和隔离算法
Algorithm for logistical routing and segregation based on latitude/longitude
所以，我正在尝试解决这个 sku 隔离和路由问题以进行交付。
情况如下：
有单区枢纽或起点发货，
输入：
- 客户的地理地址 - 一对（纬度、经度）。
- 输入每个客户的订单数量。
问题：
- 我想为一个人制作不超过 50 个位置的路线（loc1 --> loc2 --> loc7 -->... --> loc n）。
- 我想对这些路线进行聚类，以便我知道要派送到某个区域的 SKU 数量。
我尝试使用 kmeans 和 hdbscan，但它不支持最大簇大小。
我可以推断 this smart solution 以某种方式适用于我的情况吗，我的情况对我来说似乎更具层次性。
声明：在二维space中，一组点属于同一个簇，如果（且仅当）BOTH
他们对 OX 的预测是聚类的，他们对 OY 的预测也是聚类的。
在OX上，A,B,C,D的投影是聚类的；在 OY 上，A、B、C、E 的投影是聚类的；
总体而言，A、B 和 C 聚集在一起。
确定哪些点是聚类的，在 1D space:
让我们在实轴上散布一些点。直觉上，两点属于
如果它们被 'small distance' 分隔，则为同一集群；如果他们分开
通过'large distance'，它们属于不同的集群。现在我们必须确定什么是
'large distance' 什么是 'small distance'。
让我们对所有距离进行排序，并寻找一个阈值。
对于 OX 坐标为 [0,1,3,4,14,15,16,19,29,30,31] 的点集，距离
连续点之间将是 [1,2,1,10,1,1,3,10,1,1]。相同的一组距离，排序时，
看起来像 [1,1,1,1,1,1,2,3,10,10]。在 3 到 10 之间有一个阈值，所以我们将表示所有
距离 <=3 为 'small distances'，所有其他距离为 'large distances'.
我们如何选择阈值？ 通过计算两个相邻元素之间的差异。在我们的
例如，10-3=7 是最大的差异。
如果有多个相等值的阈值，选择
最右边；选择最正确的阈值会导致 'large distances' 很少，否则，
许多距离会被认为很大，因此会有很多簇。
但这取决于您的业务需求。您可以将 30 个位置分组为 3 个集群，每个 10 个位置，
或 10 个集群，每个集群 3 个位置。
如果排序后的距离类似于 [2,4,6,8,10]（没有候选阈值），则选择一些百分位数
就像 75 个百分点：最高四分之一将是 'large distance'，所有其他 - 'small distances'
根据它们在 OX 上的投影将点分组到集群中：
既然我们知道如何对实数进行聚类，让我们采用点的 OX 投影，并对它们进行聚类。
让我们有以下几点，以及它们的 OX 坐标：
P1(101), P2(12), P3(201), P4(13), P5(202), P6(11), P7(102);
相同的点，按它们的 OX 坐标排序：
P6(11), P2(12), P4(13), P1(101), P7(102), P3(201), P5(202);
接下来，我们将根据 OY 预测进行另一个分组。
观察 1：当点的索引排序时，OX 投影没有；当我们对 OX 投影进行排序时，
现在索引不会被排序。
观察 2：当使用 OX 投影进行聚类时，我们不应该期望获得相同的结果
聚类就像我们使用 OY 预测聚类一样。实际上，我们将得到的结果相交。
聚类结果不同是因为一个点的 OY 坐标完全独立于它的 OX 坐标。
因此，OY 轴上的一组值完全不同。
确定实际集群：
我们之前对 OX 和 OY 投影都做了一些聚类，得到
相同点的不同分组。现在我们将交叉这些集群，寻找共同点。
回到我们的第一张图，在OX之后聚类得到(A,B,C,D)簇，在OY之后我们得到(A,B,C,E)，
这些集合的交集将是 (A,B,C) - 最后的集群。但这是一个简单的例子。
一般策略是对 OX 上的簇进行笛卡尔积，并在 OY 上获得簇。
对于笛卡尔乘积的每个这样的元素，我们将 OX 集群中的元素与 OY 集群中的元素相交。
如果我们在 OX 上有 3 个簇，在 OY 上有 4 个簇，笛卡尔积将有 12 个元素。让我们选择其中之一。
它是一对两个簇A和B：A是OX上的一个簇，B是OY上的一个簇。如果A和B有一些共同点，
那么这些点确实是一个簇。
在上面的例子中，从7个点中，我们只得到了一个单独的簇。不令人印象深刻。但是我们
可以进一步加入邻居集群。我们不要忘记橙色部分代表 'small distances'，
而黑色部分代表 'large distances'。上图中，从'cluster'P1到clusters
P5或P3+P7，只有一个'large distance'。从聚类P3+P7，到聚类P4，有两个大距离加上
一小段距离。
免责声明：此程序将世界地图视为矩形（子午线是永不相交的平行线）。
此外，1 度和 179 度的子午线不会看起来彼此很近，而是看起来相距很远。
（它们之间的距离将是 178 度，而不是 2 度）
然而，这不是问题，因为大多数时候，交付行为具有区域性，或者至多是国家级的。
只要你的国家不被 180 度经线穿过，你就没事。
所以，我正在尝试解决这个 sku 隔离和路由问题以进行交付。 情况如下：
有单区枢纽或起点发货，
输入：
- 客户的地理地址 - 一对（纬度、经度）。
- 输入每个客户的订单数量。
问题：
- 我想为一个人制作不超过 50 个位置的路线（loc1 --> loc2 --> loc7 -->... --> loc n）。
- 我想对这些路线进行聚类，以便我知道要派送到某个区域的 SKU 数量。
我尝试使用 kmeans 和 hdbscan，但它不支持最大簇大小。
我可以推断 this smart solution 以某种方式适用于我的情况吗，我的情况对我来说似乎更具层次性。
声明：在二维space中，一组点属于同一个簇，如果（且仅当）BOTH
他们对 OX 的预测是聚类的，他们对 OY 的预测也是聚类的。
在OX上，A,B,C,D的投影是聚类的；在 OY 上，A、B、C、E 的投影是聚类的； 总体而言，A、B 和 C 聚集在一起。
确定哪些点是聚类的，在 1D space:
让我们在实轴上散布一些点。直觉上，两点属于
如果它们被 'small distance' 分隔，则为同一集群；如果他们分开
通过'large distance'，它们属于不同的集群。现在我们必须确定什么是
'large distance' 什么是 'small distance'。
让我们对所有距离进行排序，并寻找一个阈值。 对于 OX 坐标为 [0,1,3,4,14,15,16,19,29,30,31] 的点集，距离 连续点之间将是 [1,2,1,10,1,1,3,10,1,1]。相同的一组距离，排序时， 看起来像 [1,1,1,1,1,1,2,3,10,10]。在 3 到 10 之间有一个阈值，所以我们将表示所有 距离 <=3 为 'small distances'，所有其他距离为 'large distances'.
我们如何选择阈值？ 通过计算两个相邻元素之间的差异。在我们的 例如，10-3=7 是最大的差异。
如果有多个相等值的阈值，选择 最右边；选择最正确的阈值会导致 'large distances' 很少，否则， 许多距离会被认为很大，因此会有很多簇。 但这取决于您的业务需求。您可以将 30 个位置分组为 3 个集群，每个 10 个位置， 或 10 个集群，每个集群 3 个位置。
如果排序后的距离类似于 [2,4,6,8,10]（没有候选阈值），则选择一些百分位数 就像 75 个百分点：最高四分之一将是 'large distance'，所有其他 - 'small distances'
根据它们在 OX 上的投影将点分组到集群中：
既然我们知道如何对实数进行聚类，让我们采用点的 OX 投影，并对它们进行聚类。
让我们有以下几点，以及它们的 OX 坐标： P1(101), P2(12), P3(201), P4(13), P5(202), P6(11), P7(102);
相同的点，按它们的 OX 坐标排序： P6(11), P2(12), P4(13), P1(101), P7(102), P3(201), P5(202);
接下来，我们将根据 OY 预测进行另一个分组。
观察 1：当点的索引排序时，OX 投影没有；当我们对 OX 投影进行排序时， 现在索引不会被排序。
观察 2：当使用 OX 投影进行聚类时，我们不应该期望获得相同的结果 聚类就像我们使用 OY 预测聚类一样。实际上，我们将得到的结果相交。 聚类结果不同是因为一个点的 OY 坐标完全独立于它的 OX 坐标。 因此，OY 轴上的一组值完全不同。
确定实际集群：
我们之前对 OX 和 OY 投影都做了一些聚类，得到 相同点的不同分组。现在我们将交叉这些集群，寻找共同点。
回到我们的第一张图，在OX之后聚类得到(A,B,C,D)簇，在OY之后我们得到(A,B,C,E)， 这些集合的交集将是 (A,B,C) - 最后的集群。但这是一个简单的例子。
一般策略是对 OX 上的簇进行笛卡尔积，并在 OY 上获得簇。
对于笛卡尔乘积的每个这样的元素，我们将 OX 集群中的元素与 OY 集群中的元素相交。
如果我们在 OX 上有 3 个簇，在 OY 上有 4 个簇，笛卡尔积将有 12 个元素。让我们选择其中之一。
它是一对两个簇A和B：A是OX上的一个簇，B是OY上的一个簇。如果A和B有一些共同点，
那么这些点确实是一个簇。
在上面的例子中，从7个点中，我们只得到了一个单独的簇。不令人印象深刻。但是我们 可以进一步加入邻居集群。我们不要忘记橙色部分代表 'small distances'， 而黑色部分代表 'large distances'。上图中，从'cluster'P1到clusters P5或P3+P7，只有一个'large distance'。从聚类P3+P7，到聚类P4，有两个大距离加上 一小段距离。
免责声明：此程序将世界地图视为矩形（子午线是永不相交的平行线）。 此外，1 度和 179 度的子午线不会看起来彼此很近，而是看起来相距很远。 （它们之间的距离将是 178 度，而不是 2 度） 然而，这不是问题，因为大多数时候，交付行为具有区域性，或者至多是国家级的。 只要你的国家不被 180 度经线穿过，你就没事。