寇瑋華，王雪

?

容量及轉(zhuǎn)運(yùn)點(diǎn)限制的多品種交通網(wǎng)最小代價(jià)流

寇瑋華，王雪

（西南交通大學(xué)，交通運(yùn)輸與物流學(xué)院，成都 610031）

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

多品種流；交通網(wǎng)絡(luò)；容量限制；轉(zhuǎn)運(yùn)點(diǎn)接發(fā)能力；最小代價(jià)流。

0 引 言

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

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

2 算法設(shè)計(jì)

2.1 算法思想

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

2.2 復(fù)合參數(shù)

2.3 復(fù)合指標(biāo)

2.4 計(jì)算步驟

步驟六 回到步驟二反復(fù)進(jìn)行，直到找不到可增流的最短路為止。

3 示例求解

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

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

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

表1 復(fù)合指標(biāo)結(jié)果表

Tab.1 The results of composite indicators

表2 復(fù)合指標(biāo)結(jié)果表

Tab.2 The results of composite indicators

表3 復(fù)合指標(biāo)結(jié)果表

Tab.3 The results of composite indicators

表4 復(fù)合指標(biāo)結(jié)果表

Tab.4 The results of composite indicators

表5 復(fù)合指標(biāo)結(jié)果表

Tab.5 The results of composite indicators

表6 復(fù)合指標(biāo)結(jié)果表

Tab.6 The results of composite indicators

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

至此，因?yàn)檗D(zhuǎn)運(yùn)點(diǎn)1接發(fā)能力已飽和，該網(wǎng)絡(luò)找不到可增流鏈，循環(huán)結(jié)束。根據(jù)圖4計(jì)算運(yùn)送代價(jià)結(jié)果如下所示：

（1）品種I代價(jià)：

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

（2）品種II代價(jià)：

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

（3）品種III代價(jià)：

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

（4）代價(jià)和：=I+II+III=705

圖3 流量調(diào)整后的狀態(tài)圖

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

4 結(jié)束語

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

[1] 寇瑋華編著. 運(yùn)籌學(xué)[M]. 成都: 西南交通大學(xué)出版社, 2013.

[2] 甘愛英等. 運(yùn)籌學(xué)[M]. 北京: 清華大學(xué)出版社, 2002.

[3] Network Optimization. 麻省理工學(xué)院開放課件[EB/OL]. http: //www. core. org. cn/OcwWeb/index. htm

[4] Transportation Flow System. 麻省理工學(xué)院開放課件[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)絡(luò)流量增長態(tài)勢的擴(kuò)能優(yōu)化研究[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 2012(4): 19-25.

[7] 寧宣熙. 求解最小費(fèi)用流的復(fù)合標(biāo)號(hào)法[J]. 系統(tǒng)工程理論與實(shí)踐, 1990, 10(3): 11-15.

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

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

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

[11] 寇瑋華, 崔皓瑩. 運(yùn)費(fèi)有差異的多品種流交通網(wǎng)絡(luò)最小費(fèi)用算法[J]. 同濟(jì)大學(xué)學(xué)報(bào). 自然科學(xué)版, 2014, 42(8): 1196-1202.

[12] 張宏雨, 寇瑋華, 賈雨竹. 基于多品種流劃分的最小費(fèi)用流算法研究[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 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—），男，蒙古族，博士，副教授，碩士生導(dǎo)師，主要研究方向?yàn)榻煌ňW(wǎng)絡(luò)控制及應(yīng)用、交通信息工程及 控制。

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