Ford–Fulkerson算法铁路运输系统中车辆流问题的研究(7)
图3.5 输入数据初始化网络
图3.6 输出网络的最大流
3.3 铁路运输系统中车辆流问题
由下图3.7所示铁路干线所组成的铁路网络是我国最繁忙的客运线路，尤其是在春运等节假日期间，客运压力非常大。
图 3.7 中国铁路营业线路（部分）示意图
3.3.1 车辆流问题模型建立
考虑从广州至北京的铁路运输网络（如上图3.7所示）中的车辆流问题[5]，为建立网络模型，我们作以下假设：
1、假设只考虑京广线、京九线、浙赣线、京沪线以及陇海线的几条主干线的整条或部分线路组成的铁路运输网络（不包括高铁）；
2、以广州为源点 ，以北京为收点 ，中间顶点包括株洲 、南昌 、上海 、郑州 和徐州 ，为了建立模型的方便，其他的顶点则不考虑；
3、京广线、京九线并未汇于广州，但由于广州和深圳靠得比较近，为了建模的方便，将其视为一个顶点；而京九线和浙赣线相交于向塘，并非南昌，所以在株洲-南昌-上海这条路线上，分为株洲-南昌、株洲-上海、南昌-上海三条线路；
4、假设只考察每天的车流量，并且两站之间的车流量等于每天从一站到另一相邻站点的列车班次之和。例如从广州到株洲车辆流为一天中所有经过广州和株洲的列车班次之和。而其他情况，例如从南昌到杭州，杭州到上海的两趟列车并不考虑，但是从南昌沿浙赣线、京沪线到南京的列车则算作从南昌到上海的一趟列车。并且全部列车都只考虑单一方向；
5、通过查询因特网，统计各相邻站点间的每天的列车班次，整理得到下表3.1中的车辆流数据；
表3.1 各相邻站点间的班次（单向）
起点 - 终点 班次（趟）
广州 - 株洲 53
广州 （深圳）- 南昌（京九线） 8
株洲 - 南昌 11
南昌 - 上海 10
株洲 - 上海 23
株洲 - 郑州 16
上海 - 徐州 38
徐州 - 郑州 34
郑州 - 北京 31
徐州 - 北京 17
南昌 - 北京 10
根据以上假设及相关数据，建立网络模型如下图3.8所示：
图 3.8 车辆流问题网络流模型
3.3.2 车辆流问题求解
运行标号法程序label.exe，输入各条弧的数据（假设给定的可行流 ），如下图3.9所示。
图3.9 输入数据初始化网络
图3.10 输出网络的最大流
输出结果如图3.10所示，车辆流问题网络模型的最大流为58，即相当于每天从广州（或深圳）可到北京的列车班次最大为58车次。最大流的各条弧的流量情况如图3.11所示。
图 3.11 车辆流网络的最大流
四 全文总结
Ford-Fulkerson算法是被广泛使用的一种经典算法，其缺点是跟其他算法相比效率不是很高，时间复杂度很大，它的复杂度不仅依赖于网络容量的规模（顶点数和弧数），还和各条弧的容量有关。但是在网络的顶点数和弧数不多，弧的容量不是很大的情况下，尤其是在弧的容量为正整数情况下，Ford-Fulkerson算法实际上跟其他算法的效率相差并不是很大。而且该算法不需要对网络作特殊的处理和复杂的转化，可以直接求解，实现非常简单——这也是本文选择其作为研究对象和应用的重要原因。
本文研究的都是单源点和单收点的网络。但是，在现实情况中可能碰到的是有多个始发站和终点站，而不仅是单个的运输网络。然而，这种更一般的情况可以通过简化为只有单一源点和收点的网络的一种情况，即虚拟一个源点，使其到每一个源点的弧的容量等于该源点的最大输出容量；虚拟一个收点，使每一个收点到其的弧的容量等于该收点的最大输入容量。这样就得到一个单一源点和收点的网络，所以我们的研究是有意义的。