旅行时间最小化算法

Question

旅行时间最小化算法

algorithmshortest-pathtraveling-salesman

4

我正在寻求关于创建一个算法的指导，该算法可以最小化一组旅行者到达一组固定目的地的总旅行时间。这些旅行者并不都来自同一地方，但是在场景被视为完成之前，每个目的地必须由一名旅行者访问（类似于TSP）。

我考虑生成一个矩阵，其中位于（x，y）的值将是从起始位置x到目的地y的旅行距离，然后执行某种矩阵操作/算法以选择值，使得每行/列仅选择一个值，并且这些值的总和最小。有没有人对此类算法有背景知识？

根据评论进行澄清：

- 每个目的地必须由一个旅行者访问。并非所有旅行者都必须访问所有目的地。 - 如果目的地比旅行者多，则旅行者只需尝试访问一个任意目的地（仍然最小化旅行时间），然后重复该问题，但目的地减少两个。 - 目的地和旅行者的最大数量应该在30个目的地和10个旅行者左右，因此不是很多。尽可能避免使用纯暴力方法。

- alexgerst

那么每个旅行者都必须访问每个目的地（这些目的地对所有旅行者都是共同的）吗？ - unkulunkulu

你的使用场景是什么？它需要多优化？时间复杂度和空间复杂度是多少？你需要处理的旅行者和目的地的最大数量是多少？所有这些因素都会影响算法需要有多“高级”。 - Patashu

6

想把标题改为“时间旅行最小化算法”…… - Undo

初步想法： 1）首先生成一个贪婪路径，例如在每一步中，任何旅行者可以采取的最低成本路径都会被选择，直到所有目的地都被访问。 2）然后针对每个旅行者的路径，尝试迭代改进（http://en.wikipedia.org/wiki/Travelling_salesman_problem#Iterative_improvement） 3）然后对于每个目的地，看看是否将其分配给其他旅行者（插入到他们的路径中最有意义/任何点/尝试重新计算最佳路径？如果看起来没有希望，就提前失败），以改善总体成本。这不会是最优的，只是优化的一部分。 - Patashu

实际上，我想要进一步澄清，旅行者是从固定的目的地出发还是您需要先“安排”他们？ - Patashu

3个回答

2

如果我理解您的问题，我怀疑旅行者的数量与快速找到解决方案无关。因此，我们通过一些启发式方法来解决基本的旅行推销员问题，然后将旅行者移动到该循环中。

有各种构建方法和迭代改进方法的文档记录。以下是一些示例（从学术到精妙的动画示例）：

- David Cummins

你是说你的方法是 1）像解决TSP一样解决问题 2）对于路径上每个最高成本边缘，只要你还有旅行者，“穿越”它，将旅行者放在远端节点上并让其继续路径？因为这将错过那些能够利用忽略N个最高成本边缘的解决方案，对吗？（尽管它在其他方面是好的） - Patashu

1

由于旅行商问题的复杂度呈现阶乘级增长，它很快就会超出在CPY上运行的合理范围。幸运的是，新型电脑都配备了完全有能力比CPU快数百或数千倍地解决此类问题的图形处理器。

我在这里发布了对TSP一个相当简单的解决方案的分析和比较，其中包括在NVIDIA图形处理器上运行的C#代码。还需要下载CUDAfy CUDAfy库才能直接运行代码。

使用我的四核i7、16GB内存笔记本电脑和一块NVIDIA GEFORCE GT图形处理器，将问题从单个CPU核心移植到GPU后，11个城市的性能提高了近70倍（从14.7秒降至0.2秒）。

CUDA调优项目中的代码采用MIT许可证，因此可以在归属下免费使用。

- Pieter Geerkens

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

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

- Umar Farooq Khawaja · Accepted Answer

请看Floyd-Warshall算法和归并排序算法。

假设要访问的地点数（顶点）为V，旅行者人数为T，如果应用Floyd-Warshall算法，则可以在图形中的顶点对之间提供最短路径，并具有O(V^3)的复杂度。

然后，您可以按升序对最短路径的长度进行排序，这将是一个具有O(V lg V)复杂度的操作。

由于您按顺序应用这些算法，因此总体复杂度仍为O(V^3)。

您将不得不执行第二阶段K次，其中K是ceiling(V / T)，因为在第一次迭代中，您已经访问了T个顶点，但V大于T，因此您还需要访问更多的顶点。在下一次迭代中，您将从计算中删除已访问的顶点，并对剩余的距离（您已经在上一步中找到）进行排序，然后继续从T个旅行者的新位置访问它们。

您可以通过选择每个顶点的最小距离来获得更好的结果，因此您选择的下一个顶点是提供的最接近的顶点。

因此，您的总体复杂度将开始看起来像O（V ^ 3）+ K x O（V lg V），我认为这往往趋近于O（V ^ 3）。

这些只是一些让您开始的想法。