我有10,000个地理位置点(POS),10个销售员和一个起点。目标是避免销售员之间的歧视,每个人应该走相同的路程并访问相同数量的销售点。为了实现这一目标,我认为应该应用以下规则:1.为每个销售员分配一条路径,从起点开始,包含相同数量的地理位置点(POS)。 2.每条路径应具有相同的距离。我的解决方案是通过距离对GPS坐标点数组进行排序,然后将每个点分配到路径,直到循环结束,但我怀疑这种方法是否可行。最容易实现此目标的算法是什么?
你有一个非常好的起点,可以按照距离起点的远近对点进行排序。现在将这10000个点看作是由1000个包含10个点的同心圆环组成。我们只需要按照以下方式为每个销售员分配一个环中的点:- 按照销售员当前点的路径长度对销售员进行排序 - 从路径最长的销售员开始: - 销售员选择当前环中最接近自己的点(从当前环的10个点中选择) - 继续选择下一个销售员(从当前环的9个剩余点中选择) - 以此类推,直到选择完其他8个销售员的点如果按照从外到内的顺序迭代这些环,路径长度的差异会变小(而不是从小环到大环的顺序)。你可以用最外层环中的每个点作为每个销售员的起点。对于“最接近”的步骤,你可以将最后添加的点与当前考虑添加的点连接起来。每个销售员的点集路径可能不是最短的,但每个销售员的效率都相同,总体上路径长度的差异会趋近于零。 如果您想改善每个销售员的路径,在考虑添加一个点时,可以在“内部集合”中找到距离候选点最近的两个点,并将其插入到它们之间,或者将其附加到其中一个“端点”上,如果该距离小于到两个最近点的距离之和。