1

我正在开发一个拥有资源流网络的系统,这应该考虑时间。

例如:

考虑一个标准流网络,其中每个节点都是一个仓库,用于分发具有有效期的物品。此外,将一个项目从一个节点传输到另一个节点也需要时间,因此当一个项目从源发送时,它到达接收器之前的时间应该最小化。

网络包含源(供应商)和汇(客户),另外,节点(仓库)可能有库存,如果一个项目已经存在。

对这个项目的需求在不同的时间点分布在整个网络中,应该计算一个合适的流量。

但是,您可能会在时间线中间对现有流量网络的需求发生变化,从而迫使您更改网络中的流量。这样做时,我希望避免从一开始就重新计算所有内容,而只需对网络进行细微的更改,以便将新的需求考虑在内。

我看过标准流算法,很难找到任何以同样方式考虑时间的东西。我正在寻找能够将我推向正确方向的东西。

有谁知道解决此类问题或类似问题的任何算法?或者对处理时间方面的良好数据结构有什么建议?

4

1 回答 1

0

这类问题有很多算法:

Dijkstra - 在您的情况下:边缘成本 = 将信息从一个节点发送到另一个节点的时间(如果您不知道此类信息,您可以使用 Dijkstra 计算最短路径并认为最短路径是最快的)。复杂性:O(|V|lg|V| + |E|) - 其中 V=顶点,E=边

A* - 如果您确定有许多不可预测的变化,您可以为您的问题找到一个很好的启发式函数。我发现 A* 很难实现,但它具有很好的复杂性。

贝尔曼福特,约翰逊- 这也可能有帮助

也许你可以在这里找到有用的东西: https ://www.sics.se/~seif/DistributedAlgorithms/routing.pdf

或者

http://page.math.tu-berlin.de/~skutella/WAOA09-lncs.pdf

于 2015-09-03T08:29:34.720 回答