algorithm - 一个节点开始时间受限的调度/路径规划

Question

我一直在做一个行程规划项目，但在想出一个在特定约束下工作的最佳调度/路径规划算法时遇到了困难——即路径必须在给定时间停在特定节点。我构建了如下问题陈述:

行程有开始和结束时间(t_s 和 t_e)，并由事件 {a₁.. .a_n}。每个事件 a_i 都有一个开始时间 t_i 和一个持续时间 d_i。第一项事件不一定要在 t_s 开始。

此外，每项事件之间都有交通费用。 I 在邻接矩阵 C 中表示旅行成本，其中 C[i][j] 是从 a_i 到 a_j 的旅行成本。

这就是它变得棘手的地方。有一个这样的事件 a_f ∈ {a₁...a_n} 使得 t_f 是固定 - 事件必须在时间 t_f 开始。同时，我们希望尽可能减少旅行时间。我知道有一些算法可以找到最短的哈密顿路径，我已经利用它来找到最佳顺序。当最佳顺序不允许固定事件在其要求的时间开始时出现问题，因为它与行程的开始/结束时间冲突。

是否有一种有效的算法来找到仍然满足事件 a_f 约束的最优顺序？

节点数不会超过 6 或 7 个左右。因此，我不是过度关注运行时增长，但仍希望尽可能避免暴力搜索。

Answer 1

我假设我们可以在 tf 之前到达 af ，否则解决方案可能存在也可能不存在，具体取决于输入。

所以我认为这可以通过将问题分解为两个问题来完成，即最小化从 (a1 到 af) 和 (af 到 an) 的成本。我们将约束在 tf 之前或在 tf 达到 af。由于 af 的时间是固定的，我们总是会在时间 tf+df 开始从 af 到 an 的路径。所以我们现在必须找到最短的路径，这可以在 Dijkstra Algorithm 的帮助下找到。 .