丁 振 寇玮华 崔皓莹

0 引 言

最大流问题是图论的核心问题之一，传统的最大流算法只能对单一品种的流量进行分配[1-4]。而对于多品种问题，虽然可以通过按品种拆分结点重构网络来求解最大流，但是，这种解法经常使得运算过程很繁琐[5,6]。多品种流交通网络中，特定品种在结点上的流量有要求的问题，类似于运输问题中的多品种问题，在实际交通网络中频繁出现，而在图论中暂时没有很好的求解方法。本文先对求解最大流的 Ford-Fulkerson算法进行改进，构造求解多品种问题最大流的算法，然后在这个基础上构造了特定品种在结点上的流量有要求的交通网络最大流算法。

1 基于多品种问题的Ford-Fulkerson算法描述

1.1 多品种流的交通网络特性分析

多品种流可以定义为在交通网络中存在的多股相互独立的流。

传统的交通网络中，只针对单一品种流进行分析，而实际的交通网络常常涉及多品种流的输送。多品种流网络具有以下几个特点：

（1）独立性。除非有特别说明，否则各品种流之间不能相互代替，具有独立性。

（2）结点的准入特性。与一般交通网络不同，多品种流交通网络上每个结点对流的进入有品种限制。

（3）发出点与接收点。多品种流交通网络有特定的一个或多个发出点与接收点。

目前求网络最大流主流的算法有 Ford-Fulkerson算法等，而为求多品种流网络的最大流势必要对原有算法进行改进。

通过对多品种流交通网络特性的分析，基于多品种问题的 Ford-Fulkerson算法与一般 Ford-Fulkerson算法的区别主要有以下几个方面：