集群算法用于纸张的男孩

StackOverflow https://stackoverflow.com/questions/562904

题

我需要帮助选择或创造一个聚类分析算法根据某些标准。

想象一下，你是管理送报的人员。

  • 你有一套的街道地址、每一个地理编码.
  • 你想要群集的地址使每一个集群是分配给运送人。
  • 数量的货人或集群，不是固定的。如果需要的话，我总是可以聘请更多的交付人，或把它们关掉。
  • 每个集群应具有约同样数量的地址。但是，一个集群可能有较少的地址如果一个群集的地址有更多的扩散。(措辞的另一种方法：最低数量的群集在那里的每个集群都包含一个最大数量的地址，以及任何地址内的集群必须分开的一个最大的距离。)
  • 奖励点，当数据集是改变的(地址添加或删除)，算法是重新运行，这将是好的，如果集群保持不变为可能的(ie。这一规则简单的k-装置的集群，这是随机的性质)。否则输送人会发疯。

所以...想法？

更新

街道网络图表，如蜘蛛的回答，是不可能的。

有帮助吗？

解决方案

我认为你想要一个 层次团聚 技术而不是k-装置。如果你得到你的算法正确，您可以停止它的时候你有正确数量的集群。正如其他人所提到的，你可以种后续clusterings与先前的解决方案，这可能会给你一个重点业绩的改善。

你可能想看看密切的距离函数中使用，尤其是如果你的问题具有较高的层面。欧几里德的距离，是最简单的理解，但可能不是最好的，看看替代品，例如马哈拉诺比斯.

我假定你真正的问题没有任何与提供报纸...

其他提示

我已经写了一个效率低下，但简单的算法在爪哇看看如何接近我可以去做一些基本聚集在一组的要点，或多或少所描述的问题。

算法工作上的一个列表，如果(x,y)coords ps 被指定为 ints.它需要三其他参数，以及：

  1. 半径为(r):给点，什么是半径为扫描点的附近
  2. 最大的地址(maxA):什么是最大的地址数(分)每一集?
  3. 分地址(minA):最低每个群集的地址

设置 limitA=maxA. 主迭代： 初始化空洞的名单 possibleSolutions. 外迭代： 每个点 p 在 ps.初始化空洞的名单 pclusters.工作清单点 wps=copy(ps) 定义。工分 wp=p. 内迭代： 同时 wps 不是空的。除去点 wp 在 wps.确定的所有要点 wpsInRadius 在 wps 这是在一个距离 < r 从 wp.排序 wpsInRadius ascendingly根据的距离 wp.保留第一 min(limitA, sizeOf(wpsInRadius)) 点 wpsInRadius.这些要点形成一个新集群(列表中的点) pcluster.添加 pcluster 要 pclusters.除去点 pcluster 从 wps.如果 wps 不是空的， wp=wps[0] 和继续的内的迭代。结束内的迭代。 一个列表中的集群 pclusters 获得。增加这来 possibleSolutions. 结束外的迭代。

我们已经为每 p 在 ps 一个列表中的集群 pclusters 在 possibleSolutions.每 pclusters 然后加权。如果 avgPC 是的平均数点，每个集群中 possibleSolutions (全球)和 avgCSize 是平均数的群每 pclusters (全球)，那么这是一个功能，使用这两个变量来确定的重量：

  private static WeightedPClusters weigh(List<Cluster> pclusters, double avgPC, double avgCSize)
  {
    double weight = 0;
    for (Cluster cluster : pclusters)
    {
      int ps = cluster.getPoints().size();
      double psAvgPC = ps - avgPC;
      weight += psAvgPC * psAvgPC / avgCSize;
      weight += cluster.getSurface() / ps;
    }
    return new WeightedPClusters(pclusters, weight);
  }

最好的解决办法是现在 pclusters 与少的重量。我们重复的主要迭代，只要我们可以找到一个更好的解决方案(小量的)比以前最好有一个 limitA=max(minA,(int)avgPC). 结束主要的迭代。

请注意，对于相同的输入数据这种算法将始终产生相同的结果。列表用于保留以及没有 没有随机的 参与。

看看这个算法的行为，这是一个形象的结果在测试模式的32分。如果 maxA=minA=16, 然后我们发现2个集群的16地址。

alt text

接下来，如果我们减少的最低数量的地址每个集群的设定 minA=12, 我们发现3群12/12/8点。

alt text

并表明，算法是远远不够完善，这里是输出 maxA=7, 但我们得到6中的集群，他们中的一些小。所以你还是要想太多的时确定的参数。注意， r 这里只有5.

alt text

只是出于好奇，我想算法在更大的组随机选择点。我加入下面的图片.

结论呢？这个我花了半天，就是效率低的，该代码看起来很丑陋的，并且它是比较缓慢。但它表示，这是可以产生 一些 结果在很短的一段时间。当然，这只是为了乐趣；把这的东西，实际上是有用的是难的部分。

alt text

alt text

什么你描述的是一(多)-车路线的问题(VRP).有相当多的学术文献的不同的变体这一问题，使用大量的各种技术(试探，现成的解决等)。通常作者试图找到良好或者最佳的解决方案的一个具体实例，其后还意味着一个群集的网站(所有地点的路线上的一个车辆)。

然而，集群可能受到重大变化只有略微不同的情况下，这是什么你想要避免的。仍然，什么东西在VRP文件可能激发你...

如果你决定要坚持明确的聚类步骤，不要忘记，包括分布在所有集群，作为它的一部分，每一个路线。

评估集群的使用图表表示的街道格可能会产生更多的实际结果比连接点上的一个白色的地图的(虽然两者都TSP-变种)。如果一个图表模型是不可利用，可以使用的出租车-指标(|x_1-x_2|+|y_1-y_2|)作为一个近似的距离。

你有没有想过用一个经济/市场为基础的解决方案吗？分设立的一个任意的(但不变，以避免的随机性，效果)的分割成更亚(作为确定数量的货人)。

分配成本函各点通过多少增加了图，并得到每个额外点一经济价值。

迭代使每个人在转向拍卖他们的最糟糕的一点，并给每个人一个最大的预算。

这可能是匹配的相当如何传送人们会认为在现实生活中，因为人们会发现，全部门办法，或者会说"我的生活会如此容易得多，如果我没有做到这一点的一个或两个。它也是相当灵活的(例如，将允许一点英里远离任何其他人被给予一个高级相当容易地).

我会做法不同的看法：考虑到街道网络作为一个图表中，与的一个边缘每个侧的每个街道，找到一个分区的图进入n段，每次不超过一定的长度，这样每个报童可以骑一个单一连续的道路从一开始到结束他们的路线。这种方式，可以避免给人们的路线，要求他们乘坐同一段反复(例如，当问到盖两边的街上没有复盖所有周边街道).

这是一个非常快速的和肮脏的方法的发现你的"集群"的谎言。这个灵感来自游戏"扫雷。"

把你的整个运送空间达成一个正方形网格。注意-这将需要一些调整，大小电网之前，这将会很好地工作。我的直觉告诉我这一平方尺寸大小的物理区块将是一个良好的起点。

通过循环的各个方和储存的数量的交货地点(房屋)在每个区块。使用第二循环(或一些聪明的方法在第一轮)储存的数量的交货点对每个毗邻区块。

现在你可以操作，在这种网格中的一个类似的方式照片的软件。你可以检测到的边缘群寻找块在一些邻近的街区有没有交付点。

最后你需要一个系统，结合了量交付的货物以及总距离创造和分配的路线。可能有一些孤立的群只有几分娩，以及一个或两个超级簇与许多家彼此非常接近，需要多个送货的人在相同的集群。每一个家庭必须访问，所以这是你第一次的约束。

获得允许的最大距离以前往任何一个送货的人在一个单一的运行。下做同样的数目交付的货物每人。

有史以来第一次运行的路由选择算法将分配一个单一的递送人，把他们送到任何随机的集群并不是所有交付完毕，让他们交付，直到他们击中了他们输送的限制，或者他们已经传递给所有家庭中的集群。如果他们有打输送的限制，端的路线，通过将他们送回家的基础。如果他们能安全地旅行，以最近的集群，然后回家没有击中他们的最大的旅行距离，这样做和重复，如上。

一旦路线，完成了对当前的传递人，检查是否存在家庭已没有交货。如果是，分配另一个送货的人，并且重复上述的算法。

这将产生的初始路线。我将存储所有信息的位置和尺寸的每平方米，住房的数量在广场及其所有直接邻国，该集群的每一方所属的运送人和他们的路线-我会存储的所有这些在一个数据库。

我会离开的重新计算的过程给你的-但是所有目前的线路，集群等在一个数据库将使你能够让所有历史性的路线，也可以尝试各种情况下，看看如何以最好的适应变化创造尽可能少的改动现有路线。

这是一个典型的例子的一个问题，值得 优化的解决方案 而不是试图解决的"最佳".它是类似的，在某些方面的"旅行推销员问题"但是你也需要分段的位置在最优化。

我已经用三种不同的优化算法以良好的效果问题是这样的：

  1. 模拟退火
  2. 伟大的洪水的算法
  3. 遗传Algoritms

使用最优化算法，我认为你已经描述了下面的"目标":

  1. 地理区域的每个纸 孩子应该最小。
  2. 订户的数量由 每个人都应该可以大致相等。
  3. 距离走过的每一个 应该是关于平等的。
  4. (一你没状态，但有可能 问题)的路线应该结束在那里 它开始。

希望这会让你开始！

*编辑*

如果你不关心自己的路线，即可消除目标3和目标4所述，也许可使问题更适合你的奖金要求。

如果你把人口信息考虑进去(例如人口密度，订阅用率和订购的取消率)你也许可以利用的优化技术上消除需要重新运算法在为所有用户采用或丢弃你的服务。一旦集群进行了优化，他们将保持平衡，因为利率的每个单个集群匹配的利率对于其他集群。

唯一的时候你会必须重新运算法是时候和外部因素(例如经济衰退/抑郁症)所引起的改变行为的一人口群体。

而不是一个集群模型，我认为你真的想要某些变体中设定复盖的位置模式，与一个附加的约束复盖的地址数量所复盖的每个设施。我不能真的找到一个很好的解释。你可以看看 这页, 但是他们解决其使用面积单位和您可能想要解决它在欧氏或网络空间。如果你愿意挖什么东西在死树格式，检查了第4章的网络和离散的位置，通过Daskin.

好的调查简单的聚类的算法.有更多，但：http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html

也许是一个最低的生成树的客户破碎成套根据当地的文男孩。 Prims 或 验 获得MST之间的距离房屋的重量。

我知道一个很新颖的方法对这个问题，我已经看到应用于生物信息，虽然它是有效的任何种类的集群的问题。它肯定不是最简单的解决方案，但一个我认为是非常有趣的。基本的前提是，集群涉及多个目标。一个你想要减少的数群，繁琐解决方案是一个单一的群集的所有数据。第二个标准的目的是尽量减少量的差异在一个集群、琐碎的解决方案的许多集群中的每一个只有一个单一的数据点。有趣的解决方案来有关当你尝试包括这两个目标及优化贸易。

在核心建议的方法是什么叫一个 模因算法 这有点像一个遗传算法，史蒂夫所提到的，但是它不仅能探索的空间解决方案，但也有能力集中在有趣的地区，即解决方案。至少我推荐读其中一些文件在这个问题作为模因算法是一个不寻常的做法，虽然一词的警告；它可以导致你读自私的基因我还没有决定是否这是一件好事...如果算法不感兴趣，你那么也许你可以尝试和表达你的问题，因为该格式需要和使用源码提供。相关的文件和代码可以在这里找到： 多目标群集

这不是直接相关的问题，但有些事我已经听到，应该考虑如果这确实是一个路线规划问题。这将影响订货的地址内的设定分配给每个驱动程序。

UPS有软件，该软件产生最佳路线，为他们传递的人民跟随。该软件试图最大限度数量的右转，期间采取的路线。这节省了很多时间在交付。

人们不是生活在美国这样做的原因可能不会立即显而易见的。在美国人的驱动器上的右边的路，因此制作时右转，你不必等待迎面而来的流量，如果光是绿色的。此外，在美国，当把在红色的光你(通常)不必等待绿色之前，你可以走了。如果你总是右转，那么你从来不需要等待灯。

有一篇文章关于：http://abcnews.go.com/wnt/story?id=3005890

你可以有K装置或预期最大化保持不变，尽可能通过使用先前的集群，作为一个集群的特征。得到每一群有相同的物品数量似乎有点棘手。我可以想想如何做到这一点作为后聚类步骤的做k装置，然后洗牌的一些要点，直到东西的平衡，但这似乎并不非常有效的。

一个简单的答案这没有得到任何奖励点：

一个人每一个地址。

  • 你有一套的街道 地址、每一个地理编码.
    • 你想要群集的地址使每一个集群是 分配给运送人。
    • 数量的货人或集群，不是固定的。如果需要， 我总是可以聘请更多的交付 人，或把它们关掉。
    • 每个集群应具有约同样数量的地址。但是， 集群可能有较少的地址如果一个 群集的地址有更多的传播 出。(措辞的另一种方法：最低 数群集在那里的每个群集 包含一个最大数量 地址，并且任何内的地址 集群必须分开最大 距离。)
    • 奖励点，当数据集被改变(增加或者地址 删除)，算法是重新运行 它是好的，如果集群 仍然不变为可能的(ie。这一规则简单的k-装置 集群，这是随机的性质)。否则输送的人会去 疯狂。

正如已经提到的车辆路线问题可能是更适合...虽然严格是不是设计用聚类中心，它将优化分配的基础上最近的地址。因此，你们簇将实际上建议的路线。

如果你提供最大数量的商之后和试图达到最佳的解决方案，这应该告诉你分钟，你需要的。这涉及第2点

相同的地址数量可以通过提供有限数量的地址被访问，基本上分配库存价值(现在其一capcitated车辆路线问题)。

增加时间或工时的交付人员的工作有助于降低负载如果地址更多的传播(现在capcitated车辆路线问题时windows)。

如果您使用的一个最近的邻居算法，然后你可以得到相同的结果，每一次，除一个地址不该有太多影响你的最终结果应该这样处理最后一点。

实际上，我在工作C#类图书馆，以实现这样的事情，并且认为它也许是最好的路线走下去，虽然不neccesairly易impelement.

我承认，这不一定会提供的集群的大致相等的尺寸:

一个最好的当前技术，在数据聚类证据积累。(弗雷德和贾恩，2005年) 你要做的就是:

鉴于数据集与n的模式。

  1. 使用算法的k-意味着在一定范围的k。或者使用一套不同的算法，目的是产生一个整体的分区。

  2. 创建一个有关联阵C的尺寸x n n.

  3. 对于每个分区p奏:
    3.1更新共同协会基体：每个模式对(i，j)属于相同集群在p,C(i，j)=C(i，j)+1/N

  4. 使用聚类algorihm如单的链接，并应用该矩阵C为接近的措施。单的链接给人一种树作为结果，我们在其选择的群集的最长寿命。

我会提供的说明SL和k-意味着，如果你有兴趣。

我会用一个基本的算法，以创造一个第一组的报童路线，根据他们住在哪里，以及当前地点的用户，则：

当paperboys是：

  • 添加：他们采取的位置，从一个或多个paperboys工作在同一地区，从那里新来的家伙的生活。
  • 删除：他的位置给其他paperboys，使用最接近的地点，以他们的路线。

当位置是：

  • 添加：同样的事情，位置是添加到最近的路线。
  • 删除：只是从那个男孩的路线。

每季度一次，你可以重新计算整个事情和改变所有的路线。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top