有约束的网络中的连续动态路由和调度

Question

我正在尝试解决网络中的调度和路由问题。该图如下所示，其属性随后描述。

每个节点都有一个字母标签、一个常量值（capability）和一个变量值（used）。 capacity值代表我们想要避免超过的限制，而used值代表已经消耗了多少。 used值不断增加，直到它被称为重置机器的网络绑定机器重置。

节点的

used 值可能会超过其 capacity 值，此时我们将处于赤字状态 - 应尽可能避免这种情况。期望重置机器重置接近或超过其关联节点的 capability 值的 used 值。

节点之间的距离以数值表示。机器可以在节点之间双向移动。

目标是开发一条无止境的路线，确定机器接下来应该访问哪些节点，同时确保最终访问所有节点。

必须考虑以下限制：

最小化节点的赤字运行（“已使用”>“容量”）
最小化总行程距离，以便彼此靠近的节点可能首先被重置。

并不是说重置过程会花费时间和精力，因此，我们不期望机器重置其路径上的每个节点。这意味着它可以跳过节点。

我考虑过的方法：

使用最短路径算法 - 我们没有目的地，解决方案需要是连续的。
开发一种算法来确定每次节点访问后的
• 下一个节点。这在一定程度上是有效的，但是，我们仍然需要确保所有节点最终都被访问。更全面的方法可能会有所帮助。

任何有关如何解决此问题的建议将不胜感激。我更喜欢使用 Python 编写代码，但是，非常感谢伪代码、解决方案框架和任何其他形式的建议。

Answer 1

纯属建议，如有不妥之处，请指出。 那么，如果遍历从已使用的最大值与容量相比开始，然后根据其邻居中最高已使用/上限比率等选择 nxt 节点，如果它到达没有未遍历的邻居的节点，会怎么样？它可以原路返回，你可以无限地继续这样下去