容量及轉運點限制的多品種交通網(wǎng)最小代價流

寇瑋華，王雪

?

容量及轉運點限制的多品種交通網(wǎng)最小代價流

寇瑋華，王雪

（西南交通大學，交通運輸與物流學院，成都 610031）

傳統(tǒng)的運送問題是在運送品種單一、運送條件理想情況下的最小代價流分配, 但在實際的交通網(wǎng)絡應用中, 往往會出現(xiàn)多品種流的運送問題。同時，由于設備的限制, 在同一個階段的不同品種流的容量限制也可能不盡相同, 不同品種在轉運點的接發(fā)能力也不盡相同。本文主要考慮解決各品種的容量約束以及轉運點的最大接發(fā)能力問題, 分情況討論復合指標修改規(guī)則, 通過增流鏈調整規(guī)則修改復合參數(shù), 并根據(jù)匯的調整量修改復合指標, 構造不需要改變網(wǎng)絡拓撲結構的最小代價流算法。此算法不需要構造增流網(wǎng)絡, 也避免了二次求解問題。最后通過示例給出了具體的算法步驟, 為以后在此基礎上的優(yōu)化研究提供基礎。

多品種流；交通網(wǎng)絡；容量限制；轉運點接發(fā)能力；最小代價流。

0 引 言

在圖與網(wǎng)絡理論中，需要在運送代價最小的前提下，考慮網(wǎng)絡流量的最大分配。而傳統(tǒng)的算法[1-8]都無法解決實際問題中出現(xiàn)的多品種流問題，于是有了順推重構法解決運送路徑有限制的多品種流問題[9]，但這樣會使網(wǎng)絡的結構發(fā)生變化，適用性不強。于是，研究運送費用無差異以及有差異的多品種流算法[10-12]出現(xiàn)了。本文針對交通運輸網(wǎng)絡，給出容量及轉運點接發(fā)能力有限制的最小代價流算法。

1 多品種流網(wǎng)絡分析

2 算法設計

2.1 算法思想

此算法的核心思路是給頂點賦予復合指標、邊賦予復合參數(shù)，通過復合指標尋找頂點間的最短路，再通過連接構成最短的邊的復合參數(shù)判斷當前最短路是否為增流鏈以及各品種的最大調整量，隨著所求步驟的延伸，得到當前能增流的最短路以簡化求解步驟。

2.2 復合參數(shù)

2.3 復合指標

2.4 計算步驟

步驟六 回到步驟二反復進行，直到找不到可增流的最短路為止。

3 示例求解

圖1 多品種流交通網(wǎng)絡圖

圖2 某一過程流量調整后的狀態(tài)圖

第二步 根據(jù)圖2繼續(xù)求解。

表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

第三步：根據(jù)圖3繼續(xù)計算得出圖4。

至此，因為轉運點1接發(fā)能力已飽和，該網(wǎng)絡找不到可增流鏈，循環(huán)結束。根據(jù)圖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 流量調整后的狀態(tài)圖

圖4 多品種流的最小代價流最終分布狀態(tài)圖

4 結束語

在連續(xù)最短路算法和Ford-Fulkerson算法基礎上，通過構建的復合指標建立了不同品種運送路徑上容量有限制的多品種流最小代價流分配方法。另外，通過設計的復合參數(shù)，也可以標定容量及轉運點接發(fā)能力均有限制的多品種流的流量分配狀態(tài)。本文構造的基于復合參數(shù)和復合指標的算法，避免了傳統(tǒng)算法需要改變網(wǎng)絡圖結構的不足，在算法實現(xiàn)上也體現(xiàn)了便利，使其在大型復雜的實際交通網(wǎng)絡中有更強的適用性。

[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] 寇瑋華, 崔皓瑩. 滿足交通網(wǎng)絡流量增長態(tài)勢的擴能優(yōu)化研究[J]. 交通運輸工程與信息學報, 2012(4): 19-25.

[7] 寧宣熙. 求解最小費用流的復合標號法[J]. 系統(tǒng)工程理論與實踐, 1990, 10(3): 11-15.

[8] 劉冰, 盧虎生, 高學東, 等. 最小費用流問題的一種改進算法[J]. 運籌與管理, 2004, 13(3): 56-60.

[9] 寇瑋華, 崔皓瑩. 有運送路徑限制的多品種流交通網(wǎng)絡最小費用流算法研究[J]. 蘭州交通大學學報, 2013, 32(6): 97-103.

[10] 寇瑋華, 崔皓瑩. 運費無差異的多品種流交通網(wǎng)絡最小費用算法[J]. 哈爾濱工業(yè)大學學報, 2014, 46(8): 122-128.

[11] 寇瑋華, 崔皓瑩. 運費有差異的多品種流交通網(wǎng)絡最小費用算法[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—），男，蒙古族，博士，副教授，碩士生導師，主要研究方向為交通網(wǎng)絡控制及應用、交通信息工程及 控制。

寇瑋華，王雪. 容量及轉運點限制的多品種交通網(wǎng)最小代價流[J]. 交通運輸工程與信息學報, 2018, 16(3): 59-65.