从同一地理点绘制等长路径

Question

3

我有10,000个地理位置点（POS），10个销售员和一个起点。目标是避免销售员之间的歧视，每个人应该走相同的路程并访问相同数量的销售点。

为了实现这一目标，我认为应该应用以下规则：

1.为每个销售员分配一条路径，从起点开始，包含相同数量的地理位置点（POS）。 2.每条路径应具有相同的距离。

我的解决方案是通过距离对GPS坐标点数组进行排序，然后将每个点分配到路径，直到循环结束，但我怀疑这种方法是否可行。

最容易实现此目标的算法是什么？

- Nizar

请注意，可能无法获得具有相同顶点/点数的10条不同长度的路径。 - Thomas

@second 感谢您的评论！是的，每条路径应该有独特的位置，尽可能相同，但每个销售员要访问的位置数量应该相同。每个销售员在一个月内应该访问1000个位置，大约是每天38个位置（1000个位置/26天）。 - Nizar

我找到了这个，它非常接近我需要的 https://developers.google.com/optimization/routing/vrp - Nizar

它们都从同一点开始吗？ - Edward Aung

尝试一些分区算法（网络分区算法）。如果您可以稍微放松不去相同节点的限制，那么您将有更好的机会。 - Edward Aung

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- karmakaze · Answer 1

你有一个非常好的起点，可以按照距离起点的远近对点进行排序。现在将这10000个点看作是由1000个包含10个点的同心圆环组成。我们只需要按照以下方式为每个销售员分配一个环中的点：

- 按照销售员当前点的路径长度对销售员进行排序 - 从路径最长的销售员开始： - 销售员选择当前环中最接近自己的点（从当前环的10个点中选择） - 继续选择下一个销售员（从当前环的9个剩余点中选择） - 以此类推，直到选择完其他8个销售员的点

如果按照从外到内的顺序迭代这些环，路径长度的差异会变小（而不是从小环到大环的顺序）。

你可以用最外层环中的每个点作为每个销售员的起点。

对于“最接近”的步骤，你可以将最后添加的点与当前考虑添加的点连接起来。每个销售员的点集路径可能不是最短的，但每个销售员的效率都相同，总体上路径长度的差异会趋近于零。

如果您想改善每个销售员的路径，在考虑添加一个点时，可以在“内部集合”中找到距离候选点最近的两个点，并将其插入到它们之间，或者将其附加到其中一个“端点”上，如果该距离小于到两个最近点的距离之和。