algorithm - 多源多目的地

Question

我有一个优化问题。

假设我有一组目的地和另一组相应的起点。我需要将每个目的地与一个起点联系起来。一组车辆从每个起点出发前往各自的目的地。提供每辆车的速度。

网络中在单位时间内只允许一辆车通过一个路口，所以当网络中一个路口点有多个车辆时，车辆可以等待通过路口，也可以先走一个路口不同的路径。

主要目标是尽量减少所有车辆到达目的地的总体延迟。

关于解决该问题的方法的想法？

Answer 1

这不是一个完整的解决方案，但我希望能提供一个下降方向:

我认为你应该使用“Maximum Flow Problem”
在 Flow-network 上像

1. 给定'n'辆汽车
2. 定义 S - 来源
3. 定义 O1,O2,O3...,On - 车辆的起源。假设原点是第一个路口
4. 定义边 S-(O1,O2,O3...,On) - 每个起点的容量 = 1，等于车辆总数
5. 定义 E - Sink
6. 定义 D1,D2,D3...,Dn - 目的地
7. 定义边 (D1,D2,D3...,Dn)-E - 每个目的地容量 = 1
8. 每个交点由两个顶点(in)和(out)定义，边缘 cap=1

这将帮助您为所有卡车找到一条好的路线，但会完全避免通过“已使用”的十字路口...
我认为在流经后立即增加指定路口的通行能力应该很接近。