我正在尝试开始一个个人研究项目，我已经集思广益了几年了。我知道图表和算法可以找到以最快的时间访问地点的最佳顺序。然而我陷入了下一步的研究，是否有研究论文/算法可以解决这个问题？给定一个起点和一个终点，以及许多必须访问的“路径点”。有些航点有时间限制，例如航点 3 必须在下午 4:00 之前到达。因此，算法必须首先根据位置的时间限制(如果有的话)对位置进行排序，然后找到访问每个路径点的最佳顺序。
我研究了许多不同的算法/启发式方法，并且搜索了有关该主题的研究论文，但我找不到任何明确的内容。
感谢您提前提供的帮助。
最佳答案
从未做过类似的事情，但是...详细说明 BlueRaja 已经告诉您的内容，我不得不说，您很可能已经找到了您的 chalice (也许，您只是没有意识到)。
您试图解决的与时间相关的问题看起来只是重新陈述您在图表中移动时必须解决的相同的与空间相关的路径查找问题的另一种方式。
换句话说，看起来您有两个图表需要遍历。第一个是空间，由您必须访问的航路点网络表示。第二个是您必须满足的“时间窗口”的时间(又名“时间相关”)图，以便不错过任何公共(public)汽车/火车/轮船/飞机/任何东西。
据我所知，您可以使用常规的寻路/图交叉算法(Dijkstra、A*、收缩层次结构等)来遍历空间图并重复使用相同的 算法(或非常相似的算法)也可以遍历时间相关图。
毕竟，这两个图都只是“约束”网(要遍历的点，是空间中的点还是时间上的点)的数学表示，并且可以使用相同的算法进行遍历。最有可能的是，如果您查看用于整理“时间窗口”的代码，您会发现它已经与非常简单的与空间相关的图遍历算法非常相似。主要问题似乎是找到时间图的良好表示(您必须尊重的“时间窗口”网络)。最有可能的是，它必须是时间受限的空间路径点的图表(空间点或“门”，每个点都附加一个“时间窗口”)。
无论如何，一次操作不可能解决两个问题。首先，您必须在时间图中找到连接所有时间窗口(按所需顺序)的“最短路径”(也就是说:您必须将它们整理出来，就像您已经在做的那样)。其次，您必须找到空间图中任意一对时间窗口之间的最短路径(并检查最短/最快路径是否足够快以满足下一个时间窗口)。
关于algorithm - 如何在有时间限制的多个地点之间找到最快路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12609330/