我有一个优化问题。
假设我有一组目的地和另一组对应的起源地。我需要把每个目的地和一个出发地联系起来。一组车辆从每个出发地开往各自的目的地。提供每辆车的速度。
在网络中，一个单位时间内只允许一辆车通过一个交叉口，因此当网络中的一个交叉点上有多辆车时，车辆可以等待穿过交叉口，也可以走不同的路径。
主要目标是尽量减少所有车辆到达目的地的总晚点。
想办法解决这个问题吗？
最佳答案
这不是一个完整的解决方案，但我希望能提供一个下降方向：
我觉得你应该用“Maximum Flow Problem”
流式网络
给定“n”个车辆数
定义S源
定义O1，O2，O3…，关于车辆的来源。假设原点是路上的第一个交叉点
定义边缘S-（O1，O2，O3…，开）-每个原点的容量=1，等于车辆总数
定义电子接收器
定义d1、d2、d3…、dn-目的地
定义边缘（D1，D2，D3…，Dn）-E-容量=每个目的地1个
每个交叉点由两个顶点（in）和（out）定义，边帽为1
这将帮助你为所有的卡车找到一条好的路线，但将完全避免通过一个“二手”的十字路口。。。
我认为在通过后增加指定交叉口的通行能力应该很接近。