崔皓莹 寇玮华 丁 振

0 引 言

交通网络中的最大流量的分配问题，通常是针对单一品种的流量分配，在保持流量约束与守恒的条件下，一般选择基于Ford-Fulkerson算法对流量进行调整，以达到交通网络的最大流状态[1-10]。但在实际应用中，多品种流的最大流分配常常会在交通网络中出现，但是，针对于多品种流的研究成果却很少，因此，本文在借鉴传统的网络流理论及算法的基础上，构建了可行的多品种流交通网络最大流分配算法。

本文首先介绍多品种流交通网络问题并对其进行分析，在保证流量约束的条件下，基于 Ford-Fulkerson算法的思路，构造多品种流交通网络的最大流算法，在保证网络流量分配为最大流的状态下，明确每一个品种在网络中的流量分配。

1 多品种流交通网络的引例

为了解释说明交通网络的多品种流问题，也为了清晰地阐述多品种流交通网络最大流分配的算法研究，先给出多品种流交通网络的一个引例。

图1 交通网络的引例Fig.1 An example of transportation network

引例 有交通网络如图1所示，它分别给出了运送能力和运送费用，即边的容量、费用。其中 x1生产Ⅰ和Ⅲ两种产品，数量分别为7 t和4 t；x2生产Ⅱ和Ⅲ两种产品，数量分别为5 t和8 t；x3生产Ⅰ和Ⅱ两种产品，数量分别为 6 t和 3 t。y1、y2、y3分别为三个需求地，y1需要Ⅰ和Ⅲ两种产品，需求量分别为6 t和7 t；y2需要Ⅱ和Ⅲ两种产品，需求量分别为 3 t和9 t；y3需要Ⅰ和Ⅱ两种产品，需求量分别为7 t和8 t。

针对此引例，传统的交通网络最大流分配算法就不能完全适用于多品种交通网络的流量分配问题，所以，有必要研究多品种流交通网络的最大流分配算法。……