容量及转运点限制的多品种交通网最小代价流

寇玮华，王雪



容量及转运点限制的多品种交通网最小代价流

寇玮华，王雪

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

传统的运送问题是在运送品种单一、运送条件理想情况下的最小代价流分配, 但在实际的交通网络应用中, 往往会出现多品种流的运送问题。同时，由于设备的限制, 在同一个阶段的不同品种流的容量限制也可能不尽相同, 不同品种在转运点的接发能力也不尽相同。本文主要考虑解决各品种的容量约束以及转运点的最大接发能力问题, 分情况讨论复合指标修改规则, 通过增流链调整规则修改复合参数, 并根据汇的调整量修改复合指标, 构造不需要改变网络拓扑结构的最小代价流算法。此算法不需要构造增流网络, 也避免了二次求解问题。最后通过示例给出了具体的算法步骤, 为以后在此基础上的优化研究提供基础。

多品种流；交通网络；容量限制；转运点接发能力；最小代价流。

0 引 言

在图与网络理论中，需要在运送代价最小的前提下，考虑网络流量的最大分配。而传统的算法[1-8]都无法解决实际问题中出现的多品种流问题，于是有了顺推重构法解决运送路径有限制的多品种流问题[9]，但这样会使网络的结构发生变化，适用性不强。于是，研究运送费用无差异以及有差异的多品种流算法[10-12]出现了。本文针对交通运输网络，给出容量及转运点接发能力有限制的最小代价流算法。

1 多品种流网络分析

2 算法设计

2.1 算法思想

此算法的核心思路是给顶点赋予复合指标、边赋予复合参数，通过复合指标寻找顶点间的最短路，再通过连接构成最短的边的复合参数判断当前最短路是否为增流链以及各品种的最大调整量，随着所求步骤的延伸，得到当前能增流的最短路以简化求解步骤。

2.2 复合参数

2.3 复合指标

2.4 计算步骤

步骤六 回到步骤二反复进行，直到找不到可增流的最短路为止。

3 示例求解

图1 多品种流交通网络图

图2 某一过程流量调整后的状态图

第二步 根据图2继续求解。

表1 复合指标结果表

Tab.1 The results of composite indicators

表2 复合指标结果表

Tab.2 The results of composite indicators

表3 复合指标结果表

Tab.3 The results of composite indicators

表4 复合指标结果表

Tab.4 The results of composite indicators

表5 复合指标结果表

Tab.5 The results of composite indicators

表6 复合指标结果表

Tab.6 The results of composite indicators

第三步：根据图3继续计算得出图4。

至此，因为转运点1接发能力已饱和，该网络找不到可增流链，循环结束。根据图4计算运送代价结果如下所示：

（1）品种I代价：

I=7×8+5×14+1×6+1×5+1×5+1×5+1×8+2×7+5×23=284

（2）品种II代价：

II=7×6+7×5+2×5+1×5+1×5+1×5+1×13+1×6=116

（3）品种III代价：

III=1×15+1×13+8×5+8×5+6×6+2×7+7×21=305

（4）代价和：=I+II+III=705

图3 流量调整后的状态图

图4 多品种流的最小代价流最终分布状态图

4 结束语

在连续最短路算法和Ford-Fulkerson算法基础上，通过构建的复合指标建立了不同品种运送路径上容量有限制的多品种流最小代价流分配方法。另外，通过设计的复合参数，也可以标定容量及转运点接发能力均有限制的多品种流的流量分配状态。本文构造的基于复合参数和复合指标的算法，避免了传统算法需要改变网络图结构的不足，在算法实现上也体现了便利，使其在大型复杂的实际交通网络中有更强的适用性。

[1] 寇玮华编著. 运筹学[M]. 成都: 西南交通大学出版社, 2013.

[2] 甘爱英等. 运筹学[M]. 北京: 清华大学出版社, 2002.

[3] Network Optimization. 麻省理工学院开放课件[EB/OL]. http: //www. core. org. cn/OcwWeb/index. htm

[4] Transportation Flow System. 麻省理工学院开放课件[EB/OL]. http: //www. core. org. cn/OcwWeb/index. htm.

[5] Bruce Shepherd, Lisa Zhang. A cycle augmentation algorithm for minimum cost multicommodity flows on a ring [J]. Global Telecommunications Conference, 1999: 1535-1543.

[6] 寇玮华, 崔皓莹. 满足交通网络流量增长态势的扩能优化研究[J]. 交通运输工程与信息学报, 2012(4): 19-25.

[7] 宁宣熙. 求解最小费用流的复合标号法[J]. 系统工程理论与实践, 1990, 10(3): 11-15.

[8] 刘冰, 卢虎生, 高学东, 等. 最小费用流问题的一种改进算法[J]. 运筹与管理, 2004, 13(3): 56-60.

[9] 寇玮华, 崔皓莹. 有运送路径限制的多品种流交通网络最小费用流算法研究[J]. 兰州交通大学学报, 2013, 32(6): 97-103.

[10] 寇玮华, 崔皓莹. 运费无差异的多品种流交通网络最小费用算法[J]. 哈尔滨工业大学学报, 2014, 46(8): 122-128.

[11] 寇玮华, 崔皓莹. 运费有差异的多品种流交通网络最小费用算法[J]. 同济大学学报. 自然科学版, 2014, 42(8): 1196-1202.

[12] 张宏雨, 寇玮华, 贾雨竹. 基于多品种流划分的最小费用流算法研究[J]. 交通运输工程与信息学报, 2016, 14(3): 83-90.

（中文编辑：刘娉婷，英文审改：梁宏斌）

An Minimum Cost Flow Algorithm for the Transmission-site Limited and Capacity Restriction Multicommodity Flow Traffic Network

KOU Wei-hua，WANG Xue

（School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China）

The multicommodity flow distribution usually refers to a single species and simple ideal in aspect of the traffic and network, but the issue about the flow distribution of many varieties transportation has been concerned because of its frequent appearance in the practical application. In addition, due to the device capabilities, the capacity restriction of different varieties of the same stage flow may vary, and the delivery capacity of different varieties of transmission-site is also different. This paper considers the limited transmission-site and the capacity restriction of different varieties, and discusses the adjustment rules of composite indicators, which we can search for the edge to modify the composite parameters, and then modify composite indicators according to the amount of adjustment .We can build a minimum cost flow algorithm which does not need to change the network topology structure through this way. Our research shows that the proposed algorithm does not need to build growing flow network and avoid solving quadratic problems compared with the traditional single species. Finally, a case study is designed to illustrate how the algorithm solves the problem of the multicommodity flow traffic network, and the algorithm provides the basis to solve the related issues in actual traffic network.

the multicommodity flow; traffic network; capacity restriction; the receiving and sending ability of transmission-site; minimum-cost flow

1672-4747（2018）03-0059-07

U113

A

10.3969/j.issn.1672-4747.2018.03.009

2017-05-02

寇玮华（1967—），男，蒙古族，博士，副教授，硕士生导师，主要研究方向为交通网络控制及应用、交通信息工程及 控制。

寇玮华，王雪. 容量及转运点限制的多品种交通网最小代价流[J]. 交通运输工程与信息学报, 2018, 16(3): 59-65.