运费无差异的多品种流交通网络最小费用算法

寇玮华，崔皓莹

(西南交通大学交通运输与物流学院，610031成都)

最小费用流问题是网络与流的核心问题之一，最基本的算法是Ford-Fulkerson算法，其他的算法还有网络单纯形算法(graph simplex algorithm)、松弛算法(relaxation algorithm)、消圈算法(cycle-canceling algorithm)、瑕疵算法(out-ofkilter algorithm)等等［1-8］，这些算法都可以解决单一品种流的最小费用流分配问题.在实际的交通网络应用中，普遍出现了多品种流问题，所以有了流变换、流分解、组合应用、多品种流及预流推进等新的理论和方法［9-13］，但这些算法都没有彻底解决多品种流的最小费用流分配问题.针对交通运输领域出现的多品种流交通网络，有必要对其最小费用流分配问题作进一步研究，并在其他算法的基础上，构造可行的最小费用流分配算法.

本文主要对运送费用无差异的多品种流交通网络相关问题进行分析，再基于连续最短路算法(successive shortestpath algorithm)和 Ford-Fulkerson算法的思路，构造相应的多品种流交通网络的最小费用流算法.

1 运送费用无差异的多品种流交通网络分析

1.1 运送费用无差异的多品种流的交通网络引例

为了解运送费用无差异的多品种流交通网络最小费用流问题，也为清晰地阐述相关算法的研究，先给出运送费用无差异的多品种流交通网络的一个引例.

引例 有一交通网络如图1所示，图中的边分别给出了运送能力和运送量，即边的容量、流量(零流)、费用.其中x1有Ⅰ、Ⅱ两种产品，质量分别为18、8 t;x2有Ⅱ、Ⅲ两种产品，质量分别为6、19 t．y1、y2、y3为3 个需求地，y1需要Ⅰ、Ⅱ 两种产品，需求量分别为6、7 t;y2需要Ⅱ、Ⅲ两种产品，需求量……