基于連接成本的快遞網絡擁塞控制

楊從平，鄭世玨，黨永杰，楊 青

(1.廣西民族大學商學院，廣西 南寧 530006；2.華中師范大學計算機學院，湖北 武漢 430079)

?

基于連接成本的快遞網絡擁塞控制

楊從平1，2，鄭世玨2，黨永杰2，楊 青2

(1.廣西民族大學商學院，廣西 南寧 530006；2.華中師范大學計算機學院，湖北 武漢 430079)

本文采用圖論的方法研究快遞網絡擁塞控制問題。通過分析快遞網絡流量特性，研究快遞網絡結構對網絡傳輸能力的影響，平衡網絡傳輸能力和連接成本之間的關系。首先，介紹介數的概念，考慮介數與貨物流量的關系，修改了介數定義，并設計了介數的計算方法；接下來，根據介數計算公式推導快遞網絡傳輸能力與節點介數和節點能力的關系；然后，構建滿足預期網絡傳輸能力的最小連接成本擁塞控制模型，并設計了通過不斷加邊、重連和刪除邊的方法迭代尋找最優的快遞網絡結構；最后通過廣西某快遞公司的配送網絡為算例驗證模型和算法的有效性。研究結果顯示算法能夠有效地找出最優的快遞網絡，研究發現瓶頸節點的處理能力和介數決定網絡的傳輸能力，網絡傳輸能力與連接成本悖反。

快遞網絡；圖論；擁塞控制；傳輸能力；連接成本

1 引言

近年來，隨著電子商務的高速增長，與電子商務密切相關的快遞業也呈現出欣欣向榮的蓬勃發展之勢。然而我國快遞業跟不上電子商務業迅猛增長的勢頭，成為電子商務供應鏈中的“瓶頸”[1]。快遞企業在處理突然劇增的快件時，難以快速分揀和配送，造成大量快件在站點擁塞，甚至出現短時癱瘓的現象，給快遞公司、電子商務企業和消費者帶來了不同程度的影響。隨著網絡節點越來越多和網絡流量的日益增長，快遞網絡擁塞問題變得越來越嚴重，導致配送時間的顯著增加以及網絡整體性能的急劇下降。如何有效避免擁塞，確保快遞網絡通暢具有重要的現實意義。

網絡中存在一個臨界值，當網絡中待處理的數據包超過臨界值，網絡由自由流轉向擁塞狀態[2]。增加網絡臨界值則可以提高網絡傳輸能力，目前學術界對提高網絡傳輸能力的研究基本圍繞著路由策略和網絡結構兩個方面展開。

目前路由策略的研究主要有全局、局部和混合型。1)在全局型路由策略研究方面，Yan Gang等[3]提出ER路由策略；Danila等[4]通過不斷增加介數較高節點連接邊的權重，使路徑從最高介數節點調整到低介數節點；王開等[5]提出基于以節點度連乘積最小化的隨機行走機理的優化路由策略；劉偉彥和劉斌[6]提出用節點的介數作為節點邊的權重，加權網絡最短路徑的路由策略。2)在局部型路由策略研究方面，Wang Wenxu等[7]提出一種考慮鄰居節點度的局部路由策略。3)混合型路由策略研究方面，Echenique等[8]提出綜合考慮最短路徑距離和鄰居節點的等待時間的混合路由策略；Zhang Huan等[9]提出綜合最短路徑策略和鄰居節點度信息的路由策略。

學者們在研究網絡結構對網絡傳輸能力的影響主要有提高鏈路或節點處理能力、刪除鏈路、增加鏈路策略和鏈路重連等。1)提高鏈路或節點處理能力研究方面，Zhao Liang等[10]、Wu Zhixi等[11]、Ling Xiang等[12]、Zheng Jianfeng等[13]提出了節點或邊的能力分配策略。2)刪除鏈路策略方面，Liu Zhe等[14]提出了關閉具有連接度大的節點之間的鏈路；Zhang Guoqing等[15]提出了關閉具有較大介數節點之間的鏈路；張國清和程蘇琦[16]提出了通過刪除網絡上的一些邊，并把基于介數的基尼系數變化用于度量刪邊擴容的效果；蔡君和余順爭[17]提出一種通過邏輯關閉或刪除對網絡社團特性貢獻度大的鏈路以提高網絡傳輸性能的拓撲管理策略。3)增加鏈路策略，Newman和Girvan[18]、Huang Wei和Chow[19]提出了通過增加具有連接度較小的節點之間的鏈路以提高網絡負載容量。4)鏈路重連策略，Jiang Zhengyuan等[20]采用隨機重連、按度值重連和按介數重連三種方式研究對網絡傳輸能力的影響。

學者們的研究成果為下一步研究打下良好的研究基礎，然而學者們在研究提高網絡傳輸能力時基本上沒有考慮網絡的連接成本，然而連接成本是不可忽略的。復雜網絡如何精確控制、如何實行最小成本控制和如何選擇最佳控制點，具有非常關鍵而且有著廣泛科學意義和應用價值的研究問題[21]。基于此，本文考慮不同節點的處理能力約束，以最小化連接成本為優化目標對廣西某快遞公司的配送網絡進行擁塞控制，目的是研究快遞網絡結構與快遞網絡傳輸能力的關系，為快遞網絡的擁塞分析和控制提供理論依據。

2 節點介數概念與介數的計算

2.1 介數的概念

介數的概念最早由Freeman[22]于1977年給出，并將介數分為節點介數和邊介數兩種，定義節點介數為最短路徑通過某一節點的數目。用Bi表示節點i的介數，則Bi可以用式(1)來表示：

(1)

其中，V為網絡節點的集合；如果起點為s終點為t的最短路經過節點i，則δ(s,i,t)= 1，否則δ(s,i,t)= 0。

根據Freeman對節點介數的定義，最短路徑不包含節點i作為起點或終點的路徑。本文為了更好地反映通過節點的貨物流量，將通過節點i最短路徑數量定義為包含節點i作為起點或終點的路徑，則Bi可以用式(2)來表示：

(2)

其中，δ(i,j)表示起點為節點i的最短路徑，δ(j,i)表示終點為節點i的最短路徑。

假設快遞流量及流向都均勻分布，且都是沿著最短路徑流動，則可以用介數來反映相應的節點或者邊流量大小，當節點或邊的介數越大，通過的貨物流量也會越多，節點和邊就越繁忙。

2.2 將子網看成為含權重的節點的介數計算方法

為了降低為了算法復雜度，快速將關鍵節點的介數計算出來，可以快遞網絡的子網看成為含權重的節點，其權重等于子網的節點數目。如圖1所示，將含有節點a的子網變成權重為7的節點，將含有節點b的子網變成權重為6的節點，將含有節點c的子網變成權重為5的節點。

圖1 將快遞網絡的子網看成含權重節點

以節點a為例分兩步計算介數，第一步計算主干網絡的最短路徑通過節點a的數目，第二步計算子網內部通過節點a的最短路徑，然后進行求和。

第一步計算主干網絡中最短路徑通過節點a的數目。首先求出主干網絡中通過節點a的最短路徑，然后再使路徑上的節點的最短路徑通過數目加上ki×kj(其中ki為最短路徑起點的權重，kj為最短路徑終點的權重)，如表1所示。在主干網絡a→h→b的最短路徑中，a的權重為7，b的權重為6，所以在主干網絡a→h→b的最短路徑中，通過節點a的最短路徑數目為ki×kj= 7×6=42條。同樣的方法可以計算出其他主干網絡路徑考慮起點和終點權重后通過節點a的最短路徑數目，將表1中所有通過節點a的最短路徑數目求和得到168條，168條最短路徑數目為含節點a子網與子網外節點的最短路徑通過節點a的數目。

表1 主干網絡中最短路徑通過節點a的數目

第二步計算子網節點之間通過節點a的數目，由于子網內的最短路徑均需通過節點a，所以子網內部最短路徑通過節點a的路徑數目ki(ki-1)=7×6= 42條(ki為子網的節點數目)。

最后對兩步計算的最短路徑求和，得到通過節點a的最短路徑為210條。

通過將子網看成為含權重的節點分兩步計算主要目的是為了降低算法的復雜度，全局計算求最短路徑的規模為整個網絡，通過將子網看成為含權重的節點分兩步計算可以將計算規模變為主干網絡的節點數目。在規模較大的分層級的軸輻式快遞網絡中可以逐級把下一層級網絡看成一個含權的節點，可以大大降低算法的復雜度，避免網絡規模較大時節點的介數計算復雜度太大導致無法在有效時間計算出來。

3 快遞網絡傳輸能力

快遞網絡傳輸能力Rc是指快遞網絡在單位時間內能夠處理的最大快遞量，在單位時間內快遞網絡需要配送的快遞量小于或等于Rc，快遞網絡處在自由流動的穩定狀態；單位時間內快遞網絡中需要配送的快遞量大于Rc，則快遞網絡從自由流狀態轉變為擁塞狀態。

最容易產生擁塞的節點大多位于多條路徑的交匯處，這些節點都具有相對較大的介數[23]。在節點規模為n的快遞網絡中共有n(n-1)條路徑，假設每一快件隨機地選擇源節點和目標節點，則該快件通過節點i的概率Pi如式(3)所示：

(3)

其中，n為快遞網絡的節點數量，Bi為節點i的介數。

如果快遞網絡在單位時間內需要配送的快件數量為R，則通過節點i的快件數量Qi如式(4)所示：

(4)

反過來，如果已知節點i的快件數量Qi，則可知整個網絡的配送的快件數量R如式(5)所示：

(5)

假設各節點的處理快件能力為ci，如果快遞網絡中任何節點的處理快件能力ci大于或等于通過節點的快遞流量Qi，即min(ci-Qi) ≥ 0，則任何節點接收和發出的快件數量能夠平衡，整個快遞網絡處于自由流狀態；如果快遞網絡中存在某個節點的處理快件能力小余通過該節點的快遞流量，即min(ci- Qi) < 0，產生的快件不能完全及時送達目標節點，在快遞網絡中就會出現擁塞。可見當min(ci-Qi) = 0時，快遞網絡處理的快遞量R為最大網絡傳輸能力Rc，則快遞網絡傳輸能力Rc可以如式(6)所示：

(6)

式(6)說明，快遞網絡整體傳輸能力不僅與節點介數有關，還與節點的處理能力有關。min(Ci×n(n-1) /Bi)的節點為瓶頸節點，由于n(n-1)為常量，即min(Ci/Bi)的節點為瓶頸節點，只需增加瓶頸節點的處理能力或使瓶頸節點的介數降低則可以提升快遞網絡整體傳輸能力。

4 優化模型建立及算法設計

4.1 優化模型

首先根據快遞企業的需要給定快遞網絡一個期望網絡傳輸能力，然后找出滿足期望網絡傳輸能力下的最優連接成本的網絡結構，模型如式(7)和(8)表示：

f=min(sum(sum(A.×W)))

(7)

s.t.Rc≥RE

(8)

其中，A= (aij)n×n為網絡G的鄰接矩陣；W= (wij)n×n為網絡G的距離權重矩陣；sum(sum( ))表示對矩陣的所有元素求和，即求快遞網路的總連接成本Total_L；Rc為快遞網絡實際傳輸能力；RE為快遞企業設定的期望快遞網絡傳輸能力。

式(7)為優化目標，使快遞網絡連接成本Total_L最小；式(8)為約束，要求快遞網絡必須滿足期望的傳輸能力要求。

4.2 算法設計

算法設計從初始的軸輻快遞網絡開始，不斷貪婪迭代尋找滿足期望快遞網絡傳輸能力RE最低成本的網絡結構，在每一次迭代中，進行一次加邊操作、一次重新連邊操作和一次刪除邊操作，每一次操作使更優的網絡替代原來的網絡，不斷優化直到找到最優的網絡結構為止，具體步驟如下：

步驟1 給期望快遞網絡傳輸能力RE賦值。

步驟2 根據網絡G(V,L)求出鄰接矩陣A，導入權重矩陣W。

步驟3 根據式(6)計算出初始網絡的傳輸能力Rc，再根據G的鄰接矩陣A和權重矩陣W計算出連接成本Total_L。

步驟4 令快遞網絡邊數目m=n-1。

步驟5 加邊操作。獨立100次在快遞網絡G中隨機添加一條邊，記為Gi(i= 1,2,…100)，分別算出G1、G2、…、G100的連接成本Total_L1、Total_L2、…、Total_L100和網絡傳輸能力Rc1、Rc2、…、Rc100。

步驟6 判斷max(Rci)與Rc和RE關系，并進行選擇操作。

①如果max(Rci)>RE，在Rci>RE的網絡中找出滿足max((Rci-RE)/(Total_Li-Total_L))的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，同時結束算法跳至第14步。

②如果max(Rci)=RE，在Rci=RE的網絡中找出滿足min (Total_Li-Total_L)的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，同時結束算法跳至第14步。

③如果Rc

④如果max(Rci)≤Rc，保持G、Rc和Total_L不變，令add= 0。

步驟7 判斷是否滿足m=n(n-1)/2，如果滿足，結束算法跳至第14步，并輸出“找不到滿足條件的網絡”。

步驟8 重新連邊操作。找到網絡中的瓶頸節點min(Ci/Bi)，刪除一條與瓶頸節點相連接的邊，然后獨立100次在快遞網絡G中隨機添加一條邊(重新連接后保持快遞網絡連通)，記為Gi(i= 1,2,…100)，分別算出G1、G2、…、G100的連接成本Total_L1、Total_L2、…、Total_L100和網絡傳輸能力Rc1、Rc2、…、Rc100。

步驟9 判斷max(Rci)與Rc和RE關系，并進行選擇操作。

①如果max(Rci)>RE

A、如果存在Rci>RE且Total_Li

B、如果不存在滿足A，存在Rci>RE且Total_Li=Total_L的網絡，在這些網絡中找出max(Rci-RE)的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，同時結束算法跳至第14步。

C、如果不存在滿足A或B，存在Rci>RE且Total_Li>Total_L的網絡，在這些網絡中找出max((Rci-RE)/(Total_Li-Total_L))的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，同時結束算法跳至第14步。

②如果max(Rci)=RE

A、存在Rci=RE且Total_Li

B、如果不存在滿足A，存在Rci=RE且Total_Li=Total_L的網絡，在這些網絡中任意選擇一個網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，同時結束算法跳至第14步。

C、如果不存在滿足A或B，存在Rci=RE且Total_Li>Total_L的網絡，在這些網絡中找出min(Total_Li-Total_L)的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，同時結束算法跳至第14步。

③如果Rc

A、存在Rc

B、如果不存在滿足A，存在Rc

C、如果不存在滿足A或B，存在RcTotal_L的網絡，在這些網絡中找出max((Rci-Rc)/(Total_Li-Total_L))的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci。 ④如果max(Rci)=Rc

A、存在Rci=Rc且Total_Li

B、如果不存在Rci=Rc且Total_Li

⑤如果max(Rci)

步驟10 刪除邊操作。獨立100次在快遞網絡G中隨機刪除一條邊(刪除邊后保持所有節點連通)，記為Gi(i= 1,2,…100)，分別算出G1、G2、…、G100的連接成本Total_L1、Total_L2、…、Total_L100和網絡傳輸能力Rc1、Rc2、…、Rc100。

步驟11 判斷max(Rci)與Rc和RE關系，并進行選擇操作。

①如果max(Rci)>RE，在Rci>RE的網絡中找出滿足max ((Rci-RE)/RE×(Total_L-Total_Li)/Total_L))的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，結束算法跳至第14步。

②如果max(Rci)=RE，在Rci=RE的網絡中找出滿足max(Total_L-Total_Li)的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，結束算法跳至第14步。

③如果Rc

④如果max(Rci)=Rc，在Rci=Rc的網絡中找出滿足max (Total_L-Total_Li)的網絡Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，m=m-1。

⑤如果max(Rci)

步驟12 判斷是否滿足add= 0且reconnect= 0且delete= 0且Rc

步驟13 判斷是否滿足Rc≥RE，如果不滿足，跳至第4步，進行下一次迭代。

步驟14 輸出G、Total_L、Rc。

4.3 算法時間復雜度分析

計算所有節點介數的時間復雜度為O(D×n3)，D為網絡最大跳數距離，每一迭代中進行加邊、重連和刪邊操作都需要重新計算所有節點介數，假設最多需要迭代m次，則算法時間復雜度為O(m×3×D×n3)。由于網絡的小世界特征，網絡的最大跳數距離D一般都較小，所以算法復雜度為O(m×n3)。

由于整個快遞網絡節點規模較大，如順豐速運目前在國內的營業網點有12000多個，如果直接對這個快遞網絡進行優化計算，其計算量非常龐大，無法在有效時間內完成計算。但由于快遞網絡是分層級的網絡，可以采取分級優化，先對由一級樞紐節點組成的網絡進行優化，然后對某一樞紐節點內的二級節點進行優化，直至末端配送節點。

5 算例分析

本文選擇廣西某快遞公司進行擁塞控制，廣西某快遞公司的配送網絡以南寧為樞紐節點，各地級市設有轉運節點，各縣設有末端配送點，除了極少數交通發達的鄉鎮外，大部分鄉鎮還沒有布點，目前在廣西共有142個節點。

5.1 數據

為了簡化計算，本文只對由樞紐節點和轉運節點組成的主干網絡進行優化。主干網絡為軸輻式結構，桂林、柳州、梧州、河池、百色、玉林、欽州、北海、防城港和崇左等10個轉運中心以南寧為軸進行連接，主干網絡如圖2所示。主干節點間直達公路距離如表2所示，各主干節點分配的末端快遞節點數目mi如表3所示。南寧節點的快件處理能力為10萬件/天，柳州節點的快件處理能力為8萬件/天，桂林節點的快件處理能力為8萬件/天，其他主干節點的快件處理能力均為5萬件/天。

圖2 廣西某快遞公司主干網絡結構

先通過式(6)對廣西某快遞公司初始軸輻式網絡傳輸能力進行計算，得到傳輸能力Rc=11.15萬件/天，網絡連接成本Total_L=2342 km，瓶頸節點為南寧節點。

5.2 優化仿真結果

工作電腦為CPU主頻2.1GHZ、內存2.0G的聯想臺式機， Matlab R2012a編程實現算法。

5.2.1 期望傳輸能力RE=12萬件/天

設定期望傳輸能力RE為12萬件/天，將數據輸入Matlab程序，計算運行時間為37.166 s，得到快遞網絡傳輸能力Rc=12.501萬件/天，網絡連接成本為Total_L=1835 km，快遞網絡結構如圖3所示。當快遞網絡的流量為12.501萬件/天，各節點的快遞流量如圖4所示，柳州節點為瓶頸節點，其快遞流量與其處理能力相等為8萬件/天，其余節點的處理能力均大于通過快遞流量，北海節點的能力利用率最低。

表2 節點間公路直達距離(單位：km)

數據來源：tool.2345.com

表3 各子網的節點數目

數據來源：廣西某快遞公司

圖3 RE=12萬件/天最低連接成本網絡結構

圖4 Rc=12.501萬件/天各節點快遞流量

5.2.2 期望傳輸能力RE=14萬件/天

設定期望快遞網絡傳輸能力RE為14萬件/天，程序計算運行時間為42.104 s，得到快遞網絡傳輸能力Rc=14.5703萬件/天，網絡連接成本為Total_L=2725 km，快遞網絡結構如圖5所示。

圖5 RE=14萬件/天最低連接成本網絡結構

當快遞網絡的流量為14.5703萬件/天，各節點的快遞流量如圖6所示，瓶頸節點為南寧節點，南寧節點的快遞流量與其處理能力相等為10萬件/天，其余節點的處理能力均大于通過快遞流量，北海節點的能力利用率最低。

圖6 Rc=14.5703萬件/天各節點快遞流量

5.2.3 期望傳輸能力RE=16萬件/天

設定期望快遞網絡傳輸能力RE為16萬件/天，程序計算運行時間為48.710 s，得到快遞網絡傳輸能力Rc=16.3171萬件/天，網絡連接成本為Total_L=2905 km，快遞網絡結構如圖7所示。

圖7 RE=16萬件/天最低連接成本網絡結構

圖8 Rc=16.3171萬件/天各節點快遞流量

當快遞網絡的流量為16.3171萬件/天，各節點的快遞流量如圖8所示，瓶頸節點為柳州節點，柳州節點的快遞流量與其處理能力相等為8萬件/天，其余節點的處理能力均大于通過的快遞流量，北海節點的能力利用率最低。

5.2.4 期望傳輸能力RE=18萬件/天

設定期望快遞網絡傳輸能力RE為18萬件/天，計算運行時間為62.093 s，得到快遞網絡傳輸能力Rc=18.3129萬件/天，網絡連接成本為Total_L=4570 km，快遞網絡結構如圖9所示。

圖9 RE=18萬件/天最低連接成本網絡結構

當快遞網絡的流量為18.3129萬件/天，各節點的快遞流量如圖10所示，瓶頸節點為柳州節點，柳州節點的快遞流量與其處理能力相等為8萬件/天，其余節點的處理能力均大于通過快遞流量，北海節點的能力利用率最低。

圖10 Rc=18.3129萬件/天各節點快遞流量

5.2.5 期望傳輸能力RE=20萬件/天

設定期望快遞網絡傳輸能力RE為20萬件/天，程序計算運行時間為81.961 s，得到快遞網絡傳輸能力Rc=20.8187萬件/天，網絡連接成本為Total_L=5701 km，快遞網絡結構如圖11所示。

圖11 RE =20萬件/天最低連接成本網絡結構

當快遞網絡的流量為20.8187萬件/天，各節點的快遞流量如圖12所示，瓶頸節點為南寧節點，南寧節點的快遞流量與其處理能力相等為10萬件/天，其余節點的處理能力均大于通過快遞流量，北海節點的能力利用率最低。

圖12 Rc=20.8187萬件/天各節點快遞流量

5.3 結果分析

本文假設快遞流量及流向都均勻分布，且快遞總是沿著最短的路徑流動，通過分析及仿真，得到如下結果。

(1)瓶頸節點的處理能力和介數決定網絡傳輸能力

瓶頸節點的處理能力和介數決定快遞網絡的最大整體傳輸能力Rc，快遞企業可以通過改變瓶頸節點的處理能力和改變瓶頸節點的介數均可調節快遞網絡的傳輸能力。當改善瓶頸節點的的處理能力和介數后，瓶頸節點可能發生轉移，如在軸輻網絡中南寧節點為瓶頸節點，在期望快遞網絡傳輸能力RE=12萬件/天的最低連接成本網絡中瓶頸節點轉移到柳州節點，只有不斷尋找瓶頸節點并對其改善才能提升快遞網絡的整體傳輸能力。

(2)目前快遞企業選擇的軸輻式網絡結構抗擁塞性能較差

目前廣西某快遞企業選擇單樞紐純軸輻式結構，其抗擁塞性能是較差的，因為所有的子網之間的路徑均需通過樞紐節點，造成在樞紐節點的介數非常大。

(3)網絡傳輸能力Rc與連接成本悖反

在節點處理能力不變的情況下，提高網絡傳輸能力Rc則需提高快遞網絡的連接成本。為了節約網絡連接成本，提高運營效果，快遞企業應根據企業服務定位決定其傳輸能力。

6 結語

網絡擁塞是各大快遞企業常見的現象，有效避免擁塞，確保快遞網絡通暢具有重要的現實意義。本文采用圖論的方法研究快遞網絡擁塞控制問題。提出一種考慮網絡連接成本的快遞網絡擁塞控制方法，通過分析快遞網絡流量特性，研究快遞網絡結構對網絡傳輸能力的影響，平衡網絡傳輸能力和連接成本之間的關系。構建滿足預期網絡傳輸能力的最小連接成本擁塞控制模型，并通過不斷貪婪迭代算法尋找滿足期望快遞網絡傳輸能力最低連接成本的網絡結構。仿真結果顯示，該算法能有效地找出預期快遞網絡傳輸能力下的最低連接成本網絡結構。

[1] 于寶琴，武淑萍，杜廣偉. 網購快遞物流服務系統測評的枝模型仿真[J]. 中國管理科學，2014，22(12)：72- 78.

[2] Arenas A, Díaz-Guilera A, Guimera R. Communication in networks with hierarchical branching[J]. Physical Review Letters, 2001, 86(14): 3196-3199.

[3] Yan Gang, Zhou Tao, Hu Bo, et al. Efficient routing on complex networks[J]. Physical Review E, 2006, 73(4): 046108-1—046108-5.

[4] Danila B, Yu Yong, Marsh J, et al. Optimal transport on complex networks[J]. Physical Review E, 2006, 74(4): 046106-1—046106-4.

[5] 王開，周思源，張毅鋒，等. 一類基于隨機行走機理的優化路由改進策略[J]. 物理學報，2011，60(11)：118903.

[6] 劉偉彥，劉斌. 基于加權路由策略的復雜網絡擁塞控制研究[J]. 系統工程理論實踐，2015，35(4): 1063- 1068.

[7] Wang W Xenxu, Wang Binghong, Yin Chuanyang, et al. Traffic dynamics based on local routing protocol on a scale-free network[J]. Physical Review E, 2006, 73(2): 026111-1—026111-7.

[8] Echenique P, Gómez-Gardees J, Moreno Y. Improved routing strategies for Internet traffic delivery[J]. Physical Review E, 2004, 70(5): 056105-1—056105-4.

[9] Zhang Huan, Liu Zonghua, Tang Ming, et al. An adaptive routing strategy for packet delivery in complex networks[J]. Physics letters A, 2007, 364(3-4): 177-182.

[10] Zhao Liang, Lai Y C, Park K, et al. Onset of traffic congestion in complex networks[J]. Physical Review E, 2005, 71(2): 026125-1—026125-8.

[11] Wu Zhixi, Peng Gang, Wong W M, et al. Improved routing strategies for data traffic in scale-free networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008,(11): 1459-1475.

[12] Ling Xiang, Hu Maobin, Du Wenbo, et al. Bandwidth allocation strategy for traffic systems of scale-free network[J]. Physics Letters A, 2010, 374(48): 4825-4830.

[13] Zheng Jianfeng, Zhu Zhihong, Du Haoming, et al. Congestion and efficiency in complex traffic networks[J]. International Journal of Modern Physics C, 2013, 24(10): 1350072-1—1350072-12.

[14] Liu Zhe, Hu Maobin, Jiang Rui, et al. Method to enhance traffic capacity for scale-free networks[J]. Physical Review E, 2007, 76(3): 037101-1—037101-4.

[15] Zhang Guoqing, Wang Di, Li Guojie. Enhancing the transmission efficiency by edge deletion in scale-free networks[J]. Physical Review E, 2007, 76(1): 017101-1—017101-4.

[16] 張國清，程蘇琦. 小世界網絡中的刪邊擴容效應[J]. 中國科學：信息科學，2012，42(2)：151-160.

[17] 蔡君，余順爭. 一種有效提高無標度網絡負載容量的管理策略[J]. 物理學報，2013，62(5)：058901.

[18] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113-1—026113-16.

[19] Huang Wei, Chow T W S. Effective strategy of adding nodes and links for maximizing the traffic capacity of scale-free network[J]. Chaos, 2010, 20(3): 033123.

[20] Jiang Zhongyuan, Liang Mangui, An Wenjuan. Effects of efficient edge rewiring strategies on network transport efficiency[J]. Physica A: Statistical Mechanics and its Applications, 2014, 394: 379-385.

[21] 周濤，張子柯，陳關榮，等. 復雜網絡研究的機遇與挑戰[J]. 電子科技大學學報，2014，43(1)：1-5.

[22] Freeman L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977, 40(1): 35- 41.

[23] Barthelemy M. Betweenness centrality in large complex networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2004, 38(2): 163-168.

Congestion Control of Express Delivery Network Based on Connection Cost

YANG Cong-ping1,2, ZHENG Shi-jue2, DANG Yong-jie2, YANG Qing2

(1.College of Business, Guangxi University for Nationalities, Nanning 530006, China;2.School of Computer, Central China Normal University, Wuhan 430079, China)

By adopting graph theory，congestion control of express network is studied in this paper. Through the analysis of the characteristics of the network traffic flow and the study on the effect of the structure of express network on the network transmission capability, balancing the relationship between the network transmission capability and the connection cost. First of all, the concept of betweenness is introduced. Considering the relationship between the betweenness and cargo flow, the betweenness definition is modified, and the calculation method of betweenness is designed. Next, according to the betweenness calculation formula, the relationship of express network transmission capacity, node betweenness and node capacity are derived. Then, by taking the minimum connection cost as the optimization goal, an optimization model of express delivery network with the constraint of expect transmission capacity is constructed, and an algorithm is designed to seek the network with the optimal structure by gradually adding edge, reconnecting edge and deleting edge. Finally, the example of the backbone network of an express delivery company in Guangxi province is taken to verify the effectiveness of the model and algorithm. The result of simulation indicates that the algorithm can effectively find out the optimal delivery network. Through the research, it is found that processing power and betweenness of the bottleneck node decision network transmission capacity, and there is a contradiction between network transmission capacity and connection cost.

express network; graph theory; congestion control; transmission capacity; connection cost

2015-06-24；

2015-12-18

國家自然科學基金資助項目(61170017)

楊從平(1975-)，男(苗族)，廣西資源縣人，廣西民族大學商學院副教授，博士，研究方向：物流網絡，E-mail:1007843722@qq.com.

1003-207(2017)04-0143-09

10.16381/j.cnki.issn1003-207x.2017.04.017

F252.3

A