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

寇玮华，崔皓莹

（西南交通大学 交通运输与物流学院，四川 成都 610031）

最小费用流问题是网络与流的核心问题之一，基本算法是Ford-Fulkerson算法，还有网络单纯形算 法 （Graph Simplex Algorithm）、松 弛 算 法（Relaxation Algorithm）、消圈算法（cycle-canceling algorithm）、瑕疵算法（Out-Of-Kilter Algorithm）等等［1－8］，这些算法都只能解决单一品种流的最小费用流分配，而且每个单一品种流在每一个阶段即在每个边上的费用代价是相同的.在实际交通网络应用中，普遍出现了多品种流问题，所以有了流变换、流分解、组合应用、多品种流及预流推进等新的理论和方法［9－10］，但这些算法都没有彻底解决多品种流的最小费用流分配问题，尤其是针对不同品种流在同一个阶段的运费有差异的问题还没有很好地解决.

针对交通运输领域出现的运费有差异的多品种流交通网络有必要做深入研究.本文首先对运费有差异的多品种流交通网络相关问题进行分析，再基于连续最短路算法（Successive Shortest Path Algorithm）和Ford-Fulkerson算法的思路构造费用有差异的多品种流交通网络的最小费用流算法.

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

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

为了了解运费有差异的多品种流交通网络最小费用流问题，先给出运费有差异的多品种流交通网络的一个简单引例.

有一交通网络如图1所示，x1，x2为发送地，v1，v2，v3为中转地，y1，y2，y3为接收地，图中的边分别给出了运送能力和运送量，即边的容量、流量（零流）.其中x1有产品Ⅰ，Ⅱ，数量分别为18t和8t；x2有产品Ⅱ，Ⅲ，数量分别为6t和19t.y1需要产品Ⅰ，Ⅱ，需求量分别为6t和7t；y2需要产品Ⅱ，Ⅲ，需求量分别为4t和9t；y3需要产品Ⅰ，Ⅲ，需求量分别为8t和13t.另外，每种品种在每条边上的运费如表1所示，其中运费按照品种序号排序，即为（wⅠ，wⅡ，wⅢ），如果与某品种无关，运费设为＋∞.现在需要设计的方案是，在满足总运费最少的前提下将尽可能多的产品运送到需求地.

图1 多品种流交通网络Fig.1 Multi-commodity flow traffic network

针对此引例，如果再利用传统的最小费用流算法，就不能设计出可行的最小费用流分配方案，所以有必要研究运费有差异的多品种流交通网络最小费用流问题.

1.2 运费有差异的多品种流交通网络问题分析

先给定单一品种流的交通网络G＝（V，E，C，F，W，X，Y），其中C为容量集合，F为流量集合，W为费用集合，顶点集合V＝（v1，v2，…，vn），边E＝（e1，e2，…，em），对集合V取定2个非空子集X和Y，X为只发出流量的顶点集合，Y为只接收流量的顶点集合，且X∩Y＝φ，把X中的顶点x称为网络G的源，Y中的顶点y称为网络G的汇.针对边（vi，vj）赋予3个非负的整数参数cij，fij，wij，分别为容量、流量、费用.设顶点vi∉X，vi∉Y，即vi为转运点，用f＋（vi）表示顶点vi发出的流量之和，f－（vi）表示顶点vi接收的流量之和.设分配目标流的流值为A，fA为流值为A的网络流，用Valf表示流量的状态值，此时有Valf＝A.

表1 不同品种流的运费Tab.1 The conveyance cost of different commodity flows

以上描述是针对单一品种流的，而且每一种品种在每一个阶段即在每个边上的费用是相同的.在实际的交通网络中，多品种流现象普遍存在，而且在同一个阶段的不同品种流运费可能不尽相同.下面对运费有差异的多品种流交通网络特点进行分析.

基于以上分析，运费有差异的多品种流交通网络最小费用流线性规划模型如模型（1）所示.

2 运费有差异的多品种流交通网络最小费用流算法设计

运费无差异的单一品种流最小费用流Ford-Fulkerson算法是先构造增流网络，在增流网络中寻找关于费用代数和最小的路径，再针对此路径所对应原网络中的增流链进行流量调整.针对运费有差异的多品种流交通网络，如果再构造增流网络势必会造成增流网络结构庞大而且复杂，同时计算过程更为繁琐，所以直接利用Ford-Fulkerson算法可行但不是优化的方法.

2.1 算法思想

在借鉴连续最短路算法和Ford-Fulkerson算法的基础上，将网络图中边的属性设计为复合参数的形式，再针对流量分配构建复合指标，从而建立运费有差异的多品种流交通网络最小费用流算法.

（1）复合参数.费用没有差异的单一品种流交通网络中，边（vi，vj）的属性参数为（cij，fij，wij）.针对运费有差异的多品种流，把边（vi，vj）的属性设计为复合参数形式，即为［cij，fij（fij1，…，fijr，…，fijq），（wij1，…，wijr，…，wijq）］，其中fij（fij1，…，fijr，…，fijq）表示边（vi，vj）的总流量fij中每个品种的分流量各为多少；（wij1，…，wijr，…，wijq）表示每个品种在边（vi，vj）上的运费.

（2）复合指标.连续最短路算法中，顶点vj的指标为（l（vj），vi），其中l（vj）表示从起点经顶点vi到顶点vj关于费用的最短路长度，vi表示vj前一个顶点.Ford-Fulkerson算法针对流量调整，设定u表示被标识点vj前一个顶点；D表示边的方向，通过“＋”或“－”来标识是前向边还是后向边；δ表示流量的调整量，构建顶点vj的指标 （u，D，δ）.针对多品种流交通网络，既要考虑最短路指标和流量调整指标，也要考虑多品种及运费有差异的问题，所以构建复合指标［…，（l（r）（vj），vi，D，δr），…］｜（m，δ），其中l（r）（vj）表示第r个品种从起点经过前一个顶点vi到顶点vj关于运费最低的最短路长度；vi表示顶点vj的前一个顶点；“边的方向”表明边（vi，vj）是前向边还是后向边，即（vi，vj）的流量是增加还是减少；δr表示关于第r个品种最短路所对应的第r个品种的流量调整量；m表示在所有品种的最短路径中路径长度 最 小 所 对 应 的 品 种，即 有l（m）（vj）＝min｛（l（1）（vj），…，l（r）（vj）…，l（q）（vj）｝；δ表示第m品种的流量调整量，即有δ＝δm.

（3）算法思路.利用给出的复合参数和复合指标能找出费用最低的最短路，并可以确定出其对应的品种，再判断此最短路是否为增流链，如果是增流链，就对相应的品种进行流量调整，即通过修改复合参数值来分配流量，这样就可以避免先指定某一品种进行最小费用流分配的错误.以上思路是二次求解法，即先寻找关于费用最低的最短路，再判断此最短路是否为增流链.但本文算法的核心思路是，随着所求最短路的延伸，同时消除非增流边，这样既杜绝了二次求解问题，也避免了全枚举的问题.

2.2 算法步骤

步骤1：设源X＝｛x1，…，xi，…，xn｝，转运点V＝｛v1，…，vi，…，vn｝，汇yi＝｛y1，…，yi，…，yn｝.设源xi具有第r品种的数量为s（r），i，汇yi需要第r品种的数量为t（r），i.设δr＝＋∞.被标识的顶点写入集合S中，初始时S＝Ø，设顶点集合T＝｛x1，…，xi，…，xn，v1，…，vi，…，vn，y1，…，yi，…，yn｝.

步骤2：对运费有差异的多品种流交通网络在平凡流基础上利用给出的容量、费用把边的属性设为复合参数形式，即［cij，fij（fij1，…，fijr，…，fijq），（wij1，…，wijr，…，wijq）］，此时初始的流量fij（fij1，…，fijr，…，fijq）均为0（0，…，0，…，0），即有Valf＝0.

步骤3：设l（r）（xi）＝0，对起点xi赋予复合指标，即［（0，0，＋，＋∞），…，（0，0，＋，＋∞），…，（0，0，＋，＋ ∞）］｜（0，＋ ∞）；设 其余顶点l（r）（vi）＝＋∞，l（r）（yi）＝＋∞，则其余顶点均可以赋予复合指标，即［（＋∞，0，＋，＋∞），…，（＋∞，0，＋，＋∞），…，（＋∞，0，＋，＋∞）］｜（0，＋∞）.

步骤4：选择起点xi检查，将起点xi复合指标标上＊，表示顶点vi已被检查.同时设集合S＝｛xi｝，xi∉T.

步骤5：若xi与其他顶点没有直接连线，其他顶点的复合指标保持不变；若有直接连线，则计算其他顶点的复合指标值，计算方法如下.

（1）（xi，vj）为前向边.①若fij＝cij，此时流量不能增加，边（xi，vj）不能成为增流链的边，那么最短路不能经过该边，此时顶点vj复合指标不变.②若fij＜cij，此时流量可以增加，边（xi，vj）可以成为增流链的边，最短路就可以经过该边.复合指标的各指标计算如下.设l（r）（vj）＝min｛l（r）（vj），l（r）（xi）＋Wijr｝，若l（r）（vj）值来自第1项l（r）（vj），那么顶点vj复合指标第1复合项关于第r品种的子指标组保持不变；若l（r）（vj）值来自第2 项l（r）（xi）＋Wijr，当vj∈V时，δr＝min｛cij－fij，s（r），i－f＋（xir），δr｝；当vj∈Y时，若s（r），i－f＋（xir）＝0或t（r），j－f－（yjr）＝0，顶点vj复合指标中第1复合项关于第r品种的子指标 组 保 持 不 变，否 则δr＝min｛cij－fij，s（r），if＋（xir），t（r），j－f－（yjr），δr｝，此时将顶点vj复合指标中第1复合项关于第r品种的子指标组修改为（l（r）（vj），xi，＋，δr）.设 第m个 品 种 的l（m）（vj）＝min｛（l（1）（vj），…，l（r）（vj）…，l（q）（vj）｝，令δ＝ ｛δm，A－Valf｝，将顶点vj复合指标中的第2复合项修改为（m，δ）.

（2）（xi，vj）为后向边.①若fij＝0，此时流量不能减少，边（xi，vj）不能成为增流链的边，那么最短路不能经过该边，此时顶点vj复合指标保持不变.②若fij＞0，此时流量可以减少，边（xi，vj）可以成为增流链的边，最短路就可以经过该边.复合指标的各个指标计算如下.设l（r）（vj）＝min｛l（r）（vj），l（r）（xi）－Wijr｝，如果l（r）（vj）值来自第1项l（r）（vj），那么顶点vj复合指标中第1复合项关于第r品种的子指标组保持不变；如果l（r）（vj）值来自第 2 项l（r）（xi）－Wijr，当vj∈V时，δr＝min｛fij，fijr，s（r），i－f＋（xir），δr｝；当vj∈Y时，若s（r），i－f＋（xir）＝0 或t（r），jf－（yjr）＝0，顶点vj复合指标中第1复合项关于第r品种的子指标组保持不变，否则δr＝min｛fij，fijr，s（r），i－f＋（xir），t（r），j－f－（yjr），δr｝，此 时 将 顶点vj复合指标中第1复合项关于第r品种的子指标组修改 为 （l（r）（vj），xi，－，δr）.设 第m个 品 种 的l（m）（vj）＝min｛（l（1）（vj），…，l（r）（vj）…，l（q）（vj）｝，令δ＝｛δm，A－Valf｝，将顶点vj复合指标中的第2复合项修改为（m，δ）.

步 骤 6：针 对 顶 点vj，计 算l（m）（vj）＊＝min｛l（m）（vj）；其中j＝1，2，…，n；vj∉S｝.将顶点vj复合指标标上＊，表示顶点vj已被检查，设集合S＝｛xi，…，vj｝，vj∉T.当vj∈Y时，转步骤9.

步骤7：从顶点vj出发，求其他顶点vk的复合指标.若顶点vj与顶点vk没有直接连线，顶点vk的复合指标保持不变；若有直接连线，则计算顶点vk的复合指标值，计算方法如下.

（1）（vj，vk）为前向边.①若fjk＝cjk，此时流量不能增加，边（vj，vk）不能成为增流链的边，那么最短路不能经过该边，此时顶点vk复合指标保持不变.②若fjk＜cjk，此时流量可以增加，边（vj，vk）可以成为增流链的边，最短路就可以经过该边.复合指标的各个 指 标 计 算 如 下.设l（r）（vk）＝min｛l（r）（vk），l（r）（vj）＋Wjkr｝，若l（r）（vk）值来自第1项l（r）（vk），那么顶点vk复合指标中第1复合项关于第r品种的子指标组保持不变；若l（r）（vk）值来自第2项l（r）（vj）＋Wjkr，当vk∈V时，δr＝min｛cjk－fjk，δr｝；当vj∈Y时，若t（r），j－f－（yjr）＝0，顶点vj复合指标中第1复合项关于第r品种的子指标组保持不变，否则δr＝min｛cij－fij，t（r），j－f－（yjr），δr｝，此时将顶点vj复合指标中第1复合项关于第r品种的子指标组修改为（l（r）（vk），vj，＋，δr）.设第m个品种的l（m）（vk）＝min｛（l（1）（vk），…，l（r）（vk）…，l（q）（vk）｝，令δ＝｛δm，A－Valf｝，将顶点vj复合指标第2复合项修改为（m，δ）.

（2）（vj，vk）为后向边.①若fjk＝0，此时流量不能减少，边（vj，vk）不能成为增流链中的边，那么最短路不能经过该边，此时顶点vk复合指标保持不变.②若fjk＞0，此时流量可以减少，边（vj，vk）可以成为增流链的边，最短路就可以经过该边.复合指标的各个指 标 计 算 如 下.设l（r）（vk）＝ min｛l（r）（vk），l（r）（vj）－Wijr｝，若l（r）（vk）值来自第1项l（r）（vk），那么顶点vk复合指标中第1复合项关于第r品种的子指标组保持不变；若l（r）（vk）值来自第2项l（r）（vj）－Wjkr，当vk∈V时，δr＝min｛fjk，fjkr，δr｝；当vk∈Y时，若t（r），j－f－（yjr）＝0，顶点vj复合指标中第1复合项关于第r品种的子指标组保持不变，否则δr＝min｛fjk，fjkr，t（r），j－f－（yjr），δr｝，此时将顶点vk复合指标中第1复合项关于第r品种的子指标组修改为 （l（r）（vk），vj，－，δr）.设 有 第m个 品 种 的l（m）（vk）＝min｛（l（1）（vk），…，l（r）（vk）…，l（q）（vk）｝，令δ＝｛δm，A－Valf｝，将顶点vj复合指标第2复合项修改为（m，δ）.

步 骤 8：针 对 顶 点vk，计 算l（m）（vk）＊＝min｛l（m）（vk），其中j＝1，2，…，n；vk∉S｝.将顶点vk复合指标标上＊，表示顶点vk已被检查，设集合S＝｛xi，…，vk｝，vk∉T.当vk∈Y时，转步骤9.

步骤9：当yi⊆S时，说明已经找到了品种m的关于运费最短的增流链.自汇yi逆向追踪，沿着每个顶点复合指标中第1复合项第m个子指标组的vi即可得出关于品种m的最短路，路长为l（m）（yi），流量调整量为δ.将最短路中前向边（vi，vj）的复合参数修改为［cij，fij＋δ（fij1，…，fijm＋δ，…，fijq）］；将最短路中后向边（vi，vj）的复合参数修改为［cij，fijδ（fij1，…，fijm－δ，…，fijq）］.

步骤10：转到步骤3，反复进行，直到找不到关于运费最低的增流链为止.

其中步骤1～3为初始化过程，步骤4～8为寻找费用最低增流链的过程，步骤9～10为流量调整过程.此算法是基于构建的复合参数和复合指标在Ford-Fulkerson算法基础上对运费有差异的多品种流交通网络进行了最小费用流分配.

3 示例求解

最小费用最大流是最小费用流的一种情况，即最小费用最大流的目标流是最大流的流值，此时只需将本文算法中第m品种的流量调整量δ＝｛δm，A－Valf｝的A－Valf去掉即可.利用前面的引例进行多品种流的最小费用最大流分配以更清晰地说明本文算法.由于图显示的局限，在图中不标出费用（wij1，…，wijr，…，wijq），也不对顶点进行复合指标的标号；另外因篇幅限制，将相应的计算过程省略.

步骤1：设集合S＝Ø，集合T＝｛x1，x2，v1，v2，v3，y1，y2，y3｝.此时初始的流量fij（fij1，…，fijr，…，fijq）均为0（0，…，0，…，0）.此问题涉及品种Ⅰ，Ⅱ，Ⅲ，用1，2，3序号来标识.对起点xi均赋予复合指标［（0，0，＋，＋ ∞），（0，0，＋，＋ ∞），（0，0，＋，＋∞）］｜（0，＋∞）；对其余各个顶点均赋予复合指标［（＋∞，0，＋，＋∞），（＋∞，0，＋，＋∞），（＋∞，0，＋，＋∞）］｜（0，＋∞）.图2为求解过程中流量调整以后的一种状态.

步骤2：对图2继续寻找关于运费最低的增流链.表2为分别从源x1，x2出发的复合指标计算结果，此计算过程省略.

图2 某一过程流量调整后的状态Fig.2 The state after a flow adjustment

表2 复合指标结果1Tab.2 Result 1of composite indicators

针对表2取l（m）（vj）＊＝min｛l（m）（vj）；vj∉S｝＝min｛9，4，23｝＝4＝l（2）（v2）＊，将表2中顶点v2的指标标记＊，此时S＝｛x1，x2，v2｝，集合T＝｛v1，v3，y1，y2，y3｝.从顶点v2出发，继续求复合指标，顶点v2与顶点v1，v3，y3有直接连线，只需计算这3个顶点的复合指标即可，其余顶点复合参数保持不变，详细计算过程如下.

（1）（v2，v1）为前向边，此时f21＝0＜c21＝4，此边可以成为增流链中的边.①针对第I品种有l（1）（v1）＝min｛l（1）（v1），l（1）（v2）＋W211｝＝min｛＋∞，＋∞＋8｝＝＋∞，l（1）（v1）值来自第1项，顶点v1复合指标中关于第Ⅰ品种的子指标组保持不变.②针对第Ⅱ品种有l（2）（v1）＝min｛l（2）（v1），l（2）（v2）＋W212｝＝min｛＋∞，4＋7｝＝11，l（2）（v1）值来自第2项，关于第Ⅱ品种的流量调整量δ2＝min｛c21－f21，δ2｝＝min｛4－0，＋∞｝＝4，此时将顶点v1复合指标中关于第Ⅱ品种的子指标组修改为（11，v2，＋，4）.③ 针 对 第 Ⅲ 品 种 有l（3）（v1）＝ min｛l（3）（v1），l（3）（v2）＋W213｝＝min｛9，8＋7｝＝9，l（3）（v1）值来自第1项，顶点v1复合指标中关于第Ⅲ品种的子指标组保持不变.

（2）（v2，v3）为前向边，同时f23＝c23＝8，说明流量不能增加，即边（v2，v3）不能成为增流链中的边，那么最短路也就不能经过该边，此时顶点v3的复合指标保持不变.

（3）（v2，y3）为前向边，同时f23＝c23＝5，说明流量不能增加，即边（v2，y3）不能成为增流链中的边，那么最短路也就不能经过该边，此时顶点y3的复合指标保持不变.

修改后的复合指标如表3所示.

表3 复合指标结果2Tab.3 Result 2of composite indicators

针对表3取l（m）（vj）＊＝min｛l（m）（vj）；vj∉S｝＝min｛9，23｝＝9＝l（3）（v1）＊，将表3中顶点v1指标标记＊.此时S＝｛x1，x2，v2，v1｝，集合T＝｛v3，y1，y2，y3｝.从顶点v1出发求复合指标，顶点v1与顶点v3，y1，y2有直接连线，只计算这3个顶点复合指标即可，其余顶点复合参数保持不变，计算过程省略.复合指标如表4所示.

表4 复合指标结果3Tab.4 Result 3of composite indicators

针对表4取l（m）（vj）＊＝min｛l（m）（vj）；vj∉S｝＝min｛16，23｝＝16＝l（2），v3）＊，将表4中顶点v3的指标标记＊，此时S＝｛x1，x2，v2，v1，v3｝，集合T＝｛y1，y2，y3｝.从顶点v3出发，继续求复合指标，顶点v3与顶点y1，y2，y3有直接连线，只需要计算这3个顶点的复合指标即可，其余顶点复合参数保持不变，详细计算过程如下：

（1）（v3，y1）为前向边，此时f31＝2＜c31＝4，此边可以成为增流链中的边.①针对第I品种有l（1）（y1）＝min｛l（1）（y1），l（1）（v3）＋W311｝＝min｛23，＋∞＋6｝＝23，l（1）（y1）值来自第1项，顶点y1复合指标中关于第Ⅰ品种的子指标组保持不变.②针对第Ⅱ品种，有t（r），j－f－（yjr）＝y1（2）－f－（y12）＝7－（5＋2）＝0，此时顶点y1不再需要接收第Ⅱ品种，顶点y1复合指标中关于第Ⅱ品种的子指标组保持不变.③顶点y1本身不需要接收第Ⅲ品种，那么顶点y1复合指标中关于第Ⅲ品种的子指标组保持不变.

（2）（v3，y2）为前向边，此时f32＝c32＝6，此时流量不能增加，即边（v3，y2）不能成为增流链中的边，那么最短路也就不能经过该边，此时顶点y2的复合指标保持不变.

（3）（v3，y3）为前向边，此时f33＝1＜c33＝6，此边可以成为增流链中的边.①针对第Ⅰ品种有l（1）（y3）＝min｛l（1）（y3），l（1）（v3）＋W331｝＝min｛＋∞，＋∞＋5｝＝＋∞，l（1）（y3）值来自第1项，顶点y3复合指标中关于第Ⅰ品种的子指标组保持不变.②顶点y3本身不需要接收第Ⅱ品种，那么顶点y3复合指标中关于第Ⅱ品种的子指标组保持不变.③针对第Ⅲ 品 种 有l（3）（y3）＝min｛l（3）（y3），l（3）（v3）＋W333｝＝min｛＋∞，17＋6｝＝23，l（3）（y3）值来自第2项，又有t（r），j－f－（yjr）＝y（3），3－f－（y33）＝13－（7＋1）＝5，那么关于第Ⅲ品种的流量调整量δ3＝min｛c33－f33，y（3），3－f－（y33），δ3｝＝min｛6－1，5，2｝＝2.此时将顶点y3复合指标中关于第Ⅲ品种的子指标组修改为（23，v3，＋，2）.

修改后的复合指标如表5所示.

表5 复合指标结果4Tab.5 The results of composite indicators

针对表5取l（m）（vj）＊＝min｛l（m）（vj）；vj∉S｝＝min｛23，23｝＝23＝l（1）（y1）＊＝l（3）（y3）＊.将表5中顶点y1，y3的指标标记＊，此时S＝｛x1，x2，v1，v2，v3，y1，y3｝，集合T＝｛y2｝.出现y1⊆S，y3⊆S情况，说明已经找到关于品种Ⅰ和品种Ⅲ的运费最低的2条增流链.

自汇y1沿着每个顶点复合指标中第1复合项的第1个子指标组逆向追踪，可得出关于品种Ⅰ的最短路为x1→y1，路长为23，流量调整量为3.

自汇y3沿着每个顶点复合指标的第1复合项中第3个子指标组逆向追踪，可得出关于品种Ⅲ最短路为x2→v1→v3→y3，路长为23，流量调整量为2.

最终流量分配结果如图3所示.

步骤3：针对图3继续寻找关于运费最低的增流链，余下过程省略，最终的最小费用最大流分配结果如图4所示.

图3 图2流量调整后的状态Fig.3 The state after flow adjustment in Fig.2

针对图4，从源x1，x2出发的边中只有边（x1，y1）为不饱和边，但汇y1需要的Ⅰ，Ⅱ品种已经得到全部满足，所以没有办法再找到增流链.由图4可以知道该引例中各个品种的具体运送方案，把该引例的总体方案、各个品种的具体方案列于表6，发送和接收的总量都为42，则3个品种的费用WⅠ，WⅡ，WⅢ分别为：WⅠ＝23×3＋3×3＋6×7＋9×3＋4×2＋8×2＋7×5＋5×2＝216，WⅡ＝8×4＋4×1＋6×6＋8×5＋6×4＋5×1＋8×1＋4×2＝157，WⅢ＝9×3＋8×8＋16×7＋5×1＋8×3＋8×1＋6×7＋5×6＋6×4＝336.总费用W＝WⅠ＋WⅡ＋WⅢ＝216＋157＋336＝709.

图4 多品种流的最小费用最大流最终分布状态Fig.4 Minimum cost of the maximum flow distribution of multi-commodity flow

表6 最小费用最大流具体分配方案Tab.6 Specific allocation scheme for the minimum cost of the maximum flow

4 结语

在连续最短路算法和Ford-Fulkerson算法基础上，通过构建复合指标建立了运费有差异的多品种流最小费用流分配方法，另外，通过设计的复合参数也标定了多品种流的流量分配状态.本文构造的基于复合参数和复合指标的多品种流最小费用流算法避免了传统算法需要改变网络图结构的不足，在算法实现上也体现了便利.在交通运输领域，运费有差异的多品种流分配问题普遍存在，但针对此类问题的研究文献很少，本文算法也为解决交通网络的一系列相关实际问题提供了参考.

［1］ 寇玮华.运筹学［M］.成都：西南交通大学出版社，2013.

KOU Weihua.Operational research［M］.Chengdu：Southwest Jiaotong University Press，2013.

［2］ 寇玮华，崔皓莹.有运送路径限制的多品种流交通网络最小费用流算法研究［J］.兰州交通大学学报，2013，32（6）：1.

KOU Weihua，CUI Haoying.An algorithm for the minimum cost flow which has limited transmission-path in multi-species flow traffic network ［J］. Journal of Transportation Engineering and Information，2013，32（6）：1.

［3］ 寇玮华，崔皓莹.满足交通网络流量增长态势的扩能优化研究［J］.交通运输工程与信息学报，2012，10（4）：19.

KOU Weihua，CUI Haoying.Optimizing study on enlarging the capacity of traffic network to meet the need of the increscent flow［J］.Journal of Transportation Engineering and Information，2012，10（4）：19.

［4］ 寇玮华，董雪，吕林剑.交通运输网络中两个结点间有流量约束的最小费用最大流算法［J］.兰州交通大学学报，2009，28（6）：104.

KOU Weihua，DONG Xue，LÜLinjian.An algorithm for the minimum cost max-flow which has limited flow between two notes in the traffic and transportation network［J］.Journal of Lanzhou Jiaotong University，2009，28（6）：104.

［5］ 程琳，王炜.Dial交通量分配模型和选择率问题的研究［J］.交通运输系统工程与信息，2002，2（3）：29.

CHENG Lin，WANG Wei.On dial assignment and choice probabilities［J］.Journal of Transportation Systems Engineering and Information Technology，2002，2（3）：29.

［6］ 陈光亚.带有向量值费用函数的交通网络平衡问题——模型与分析［J］.交通运输系统工程与信息，2006，6（5）：56.

CHEN Guangya.Equilibrium problems of traffic networks with vector cost functions：model and analysis［J］.Journal of Transportation Systems Engineering and Information Technology，2006，6（5）：56.

［7］ 任刚，王炜.可直接计算转向流量的改进型Dial交通分配算法［J］.中国公路学报，2005，18（4）：83.

REN Gang，WANG Wei.Improved Dial’s traffic assignment algorithm for directly computation on turning flows［J］.China Journal of Highway and Transport，2005，18（4）：83.

［8］ Orlin B J.Network optimization［EB／OL］.［2013-04-01］.http：／／www.core.org.cn／OcwWeb／index.htm.

［9］ Chabini I，Odoni R A.Transportation flow system.MIT open courseware［EB／OL］.［2013-04-20］.http：／／www.core.org.cn／OcwWeb／index.htm.

［10］ Shepherd B，Zhang L.A cycle augmentation algorithm for minimum cost multicommodity flows on a ring［C］／／Global Telecommunications Conference. Rio de Janeiro：IEEE Commumcations Society，1999：1535-1543.