-1

我目前正在解决一个路由问题，我必须为工人创建每日时间表来修复一些安装。有 200,000 个装置，一个工人每次只能工作 8 小时。目标是每天制定最佳路线；因此优化了他每天必须访问的不同点之间的距离，但每个安装的优先级也受到限制。事实上，每个安装都有一个介于 0 和 1 之间的优先级，更高优先级的点应该被赋予更高的权重。

我只是在寻找一些建议，因为我尝试实施一些解决方案（https://developers.google.com/optimization/routing/tsp），但由于我有很多观点，这会导致计算时间过长。

谢谢你。

此致，

查尔斯

4

3 回答 3

0

如您所知，您的问题没有完美的答案，但也许我可以指导您的研究：

  • Alpha-Beta pruning：我一直在使用它来减少 AI 玩 Hex 游戏的可能性。
  • A* 寻路：我一直在用它来模拟一个未来派的类似超循环胶囊的网络，作为 Dijkstra 算法的补充。

您可以根据需要自定义这两种算法。

希望有用！

于 2019-04-26T06:40:23.027 回答
0

这是一个巨大的问题。在处理它之前，您需要将其聚类为较小的子问题。我们已经应用了复杂的模糊聚类技术来实验性地解决 20,000 个位置问题。对于 200,000，您可能需要按地理区域（例如邮政编码/邮政编码）进行聚合，但在您尝试运行某种聚类将其拆分之前。或者，您可能只想首先根据地理位置尝试进行硬拆分。

于 2019-06-02T04:29:27.437 回答
0

由于所描述问题的规模很大，几乎不可能为每种情况实现最佳解决方案。您可以尝试基于混合整数编程的方法，尤其是在TSP或车辆路线问题中，但我认为它不适用于您的情况。

至少在我看来，你应该尝试的是解决 TSP/VRP 的启发式方法：禁忌搜索、模拟退火、爬山。给定足够的时间和一组适当的约束，其中一种方法将产生“足够好”的解决方案，这比随机猜测要好得多。看看像Google OR-Tools这样的东西

于 2019-04-26T06:53:39.487 回答