基于連接成本的快遞網(wǎng)絡(luò)擁塞控制

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

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

?

基于連接成本的快遞網(wǎng)絡(luò)擁塞控制

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

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

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

快遞網(wǎng)絡(luò)；圖論；擁塞控制；傳輸能力；連接成本

1 引言

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

網(wǎng)絡(luò)中存在一個(gè)臨界值，當(dāng)網(wǎng)絡(luò)中待處理的數(shù)據(jù)包超過臨界值，網(wǎng)絡(luò)由自由流轉(zhuǎn)向擁塞狀態(tài)[2]。增加網(wǎng)絡(luò)臨界值則可以提高網(wǎng)絡(luò)傳輸能力，目前學(xué)術(shù)界對提高網(wǎng)絡(luò)傳輸能力的研究基本圍繞著路由策略和網(wǎng)絡(luò)結(jié)構(gòu)兩個(gè)方面展開。

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

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

學(xué)者們的研究成果為下一步研究打下良好的研究基礎(chǔ)，然而學(xué)者們在研究提高網(wǎng)絡(luò)傳輸能力時(shí)基本上沒有考慮網(wǎng)絡(luò)的連接成本，然而連接成本是不可忽略的。復(fù)雜網(wǎng)絡(luò)如何精確控制、如何實(shí)行最小成本控制和如何選擇最佳控制點(diǎn)，具有非常關(guān)鍵而且有著廣泛科學(xué)意義和應(yīng)用價(jià)值的研究問題[21]?；诖耍疚目紤]不同節(jié)點(diǎn)的處理能力約束，以最小化連接成本為優(yōu)化目標(biāo)對廣西某快遞公司的配送網(wǎng)絡(luò)進(jìn)行擁塞控制，目的是研究快遞網(wǎng)絡(luò)結(jié)構(gòu)與快遞網(wǎng)絡(luò)傳輸能力的關(guān)系，為快遞網(wǎng)絡(luò)的擁塞分析和控制提供理論依據(jù)。

2 節(jié)點(diǎn)介數(shù)概念與介數(shù)的計(jì)算

2.1 介數(shù)的概念

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

(1)

其中，V為網(wǎng)絡(luò)節(jié)點(diǎn)的集合；如果起點(diǎn)為s終點(diǎn)為t的最短路經(jīng)過節(jié)點(diǎn)i，則δ(s,i,t)= 1，否則δ(s,i,t)= 0。

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

(2)

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

假設(shè)快遞流量及流向都均勻分布，且都是沿著最短路徑流動，則可以用介數(shù)來反映相應(yīng)的節(jié)點(diǎn)或者邊流量大小，當(dāng)節(jié)點(diǎn)或邊的介數(shù)越大，通過的貨物流量也會越多，節(jié)點(diǎn)和邊就越繁忙。

2.2 將子網(wǎng)看成為含權(quán)重的節(jié)點(diǎn)的介數(shù)計(jì)算方法

為了降低為了算法復(fù)雜度，快速將關(guān)鍵節(jié)點(diǎn)的介數(shù)計(jì)算出來，可以快遞網(wǎng)絡(luò)的子網(wǎng)看成為含權(quán)重的節(jié)點(diǎn)，其權(quán)重等于子網(wǎng)的節(jié)點(diǎn)數(shù)目。如圖1所示，將含有節(jié)點(diǎn)a的子網(wǎng)變成權(quán)重為7的節(jié)點(diǎn)，將含有節(jié)點(diǎn)b的子網(wǎng)變成權(quán)重為6的節(jié)點(diǎn)，將含有節(jié)點(diǎn)c的子網(wǎng)變成權(quán)重為5的節(jié)點(diǎn)。

圖1 將快遞網(wǎng)絡(luò)的子網(wǎng)看成含權(quán)重節(jié)點(diǎn)

以節(jié)點(diǎn)a為例分兩步計(jì)算介數(shù)，第一步計(jì)算主干網(wǎng)絡(luò)的最短路徑通過節(jié)點(diǎn)a的數(shù)目，第二步計(jì)算子網(wǎng)內(nèi)部通過節(jié)點(diǎn)a的最短路徑，然后進(jìn)行求和。

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

表1 主干網(wǎng)絡(luò)中最短路徑通過節(jié)點(diǎn)a的數(shù)目

第二步計(jì)算子網(wǎng)節(jié)點(diǎn)之間通過節(jié)點(diǎn)a的數(shù)目，由于子網(wǎng)內(nèi)的最短路徑均需通過節(jié)點(diǎn)a，所以子網(wǎng)內(nèi)部最短路徑通過節(jié)點(diǎn)a的路徑數(shù)目ki(ki-1)=7×6= 42條(ki為子網(wǎng)的節(jié)點(diǎn)數(shù)目)。

最后對兩步計(jì)算的最短路徑求和，得到通過節(jié)點(diǎn)a的最短路徑為210條。

通過將子網(wǎng)看成為含權(quán)重的節(jié)點(diǎn)分兩步計(jì)算主要目的是為了降低算法的復(fù)雜度，全局計(jì)算求最短路徑的規(guī)模為整個(gè)網(wǎng)絡(luò)，通過將子網(wǎng)看成為含權(quán)重的節(jié)點(diǎn)分兩步計(jì)算可以將計(jì)算規(guī)模變?yōu)橹鞲删W(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目。在規(guī)模較大的分層級的軸輻式快遞網(wǎng)絡(luò)中可以逐級把下一層級網(wǎng)絡(luò)看成一個(gè)含權(quán)的節(jié)點(diǎn)，可以大大降低算法的復(fù)雜度，避免網(wǎng)絡(luò)規(guī)模較大時(shí)節(jié)點(diǎn)的介數(shù)計(jì)算復(fù)雜度太大導(dǎo)致無法在有效時(shí)間計(jì)算出來。

3 快遞網(wǎng)絡(luò)傳輸能力

快遞網(wǎng)絡(luò)傳輸能力Rc是指快遞網(wǎng)絡(luò)在單位時(shí)間內(nèi)能夠處理的最大快遞量，在單位時(shí)間內(nèi)快遞網(wǎng)絡(luò)需要配送的快遞量小于或等于Rc，快遞網(wǎng)絡(luò)處在自由流動的穩(wěn)定狀態(tài)；單位時(shí)間內(nèi)快遞網(wǎng)絡(luò)中需要配送的快遞量大于Rc，則快遞網(wǎng)絡(luò)從自由流狀態(tài)轉(zhuǎn)變?yōu)閾砣麪顟B(tài)。

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

(3)

其中，n為快遞網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量，Bi為節(jié)點(diǎn)i的介數(shù)。

如果快遞網(wǎng)絡(luò)在單位時(shí)間內(nèi)需要配送的快件數(shù)量為R，則通過節(jié)點(diǎn)i的快件數(shù)量Qi如式(4)所示：

(4)

反過來，如果已知節(jié)點(diǎn)i的快件數(shù)量Qi，則可知整個(gè)網(wǎng)絡(luò)的配送的快件數(shù)量R如式(5)所示：

(5)

假設(shè)各節(jié)點(diǎn)的處理快件能力為ci，如果快遞網(wǎng)絡(luò)中任何節(jié)點(diǎn)的處理快件能力ci大于或等于通過節(jié)點(diǎn)的快遞流量Qi，即min(ci-Qi) ≥ 0，則任何節(jié)點(diǎn)接收和發(fā)出的快件數(shù)量能夠平衡，整個(gè)快遞網(wǎng)絡(luò)處于自由流狀態(tài)；如果快遞網(wǎng)絡(luò)中存在某個(gè)節(jié)點(diǎn)的處理快件能力小余通過該節(jié)點(diǎn)的快遞流量，即min(ci- Qi) < 0，產(chǎn)生的快件不能完全及時(shí)送達(dá)目標(biāo)節(jié)點(diǎn)，在快遞網(wǎng)絡(luò)中就會出現(xiàn)擁塞。可見當(dāng)min(ci-Qi) = 0時(shí)，快遞網(wǎng)絡(luò)處理的快遞量R為最大網(wǎng)絡(luò)傳輸能力Rc，則快遞網(wǎng)絡(luò)傳輸能力Rc可以如式(6)所示：

(6)

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

4 優(yōu)化模型建立及算法設(shè)計(jì)

4.1 優(yōu)化模型

首先根據(jù)快遞企業(yè)的需要給定快遞網(wǎng)絡(luò)一個(gè)期望網(wǎng)絡(luò)傳輸能力，然后找出滿足期望網(wǎng)絡(luò)傳輸能力下的最優(yōu)連接成本的網(wǎng)絡(luò)結(jié)構(gòu)，模型如式(7)和(8)表示：

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

(7)

s.t.Rc≥RE

(8)

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

式(7)為優(yōu)化目標(biāo)，使快遞網(wǎng)絡(luò)連接成本Total_L最?。皇?8)為約束，要求快遞網(wǎng)絡(luò)必須滿足期望的傳輸能力要求。

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

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

步驟1 給期望快遞網(wǎng)絡(luò)傳輸能力RE賦值。

步驟2 根據(jù)網(wǎng)絡(luò)G(V,L)求出鄰接矩陣A，導(dǎo)入權(quán)重矩陣W。

步驟3 根據(jù)式(6)計(jì)算出初始網(wǎng)絡(luò)的傳輸能力Rc，再根據(jù)G的鄰接矩陣A和權(quán)重矩陣W計(jì)算出連接成本Total_L。

步驟4 令快遞網(wǎng)絡(luò)邊數(shù)目m=n-1。

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

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

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

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

③如果Rc

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

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

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

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

①如果max(Rci)>RE

A、如果存在Rci>RE且Total_Li

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

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

②如果max(Rci)=RE

A、存在Rci=RE且Total_Li

B、如果不存在滿足A，存在Rci=RE且Total_Li=Total_L的網(wǎng)絡(luò)，在這些網(wǎng)絡(luò)中任意選擇一個(gè)網(wǎng)絡(luò)Gi，并令G=Gi、Total_L=Total_Li、Rc=Rci，同時(shí)結(jié)束算法跳至第14步。

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

③如果Rc

A、存在Rc

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

C、如果不存在滿足A或B，存在RcTotal_L的網(wǎng)絡(luò)，在這些網(wǎng)絡(luò)中找出max((Rci-Rc)/(Total_Li-Total_L))的網(wǎng)絡(luò)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 刪除邊操作。獨(dú)立100次在快遞網(wǎng)絡(luò)G中隨機(jī)刪除一條邊(刪除邊后保持所有節(jié)點(diǎn)連通)，記為Gi(i= 1,2,…100)，分別算出G1、G2、…、G100的連接成本Total_L1、Total_L2、…、Total_L100和網(wǎng)絡(luò)傳輸能力Rc1、Rc2、…、Rc100。

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

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

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

③如果Rc

④如果max(Rci)=Rc，在Rci=Rc的網(wǎng)絡(luò)中找出滿足max (Total_L-Total_Li)的網(wǎng)絡(luò)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步，進(jìn)行下一次迭代。

步驟14 輸出G、Total_L、Rc。

4.3 算法時(shí)間復(fù)雜度分析

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

由于整個(gè)快遞網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模較大，如順豐速運(yùn)目前在國內(nèi)的營業(yè)網(wǎng)點(diǎn)有12000多個(gè)，如果直接對這個(gè)快遞網(wǎng)絡(luò)進(jìn)行優(yōu)化計(jì)算，其計(jì)算量非常龐大，無法在有效時(shí)間內(nèi)完成計(jì)算。但由于快遞網(wǎng)絡(luò)是分層級的網(wǎng)絡(luò)，可以采取分級優(yōu)化，先對由一級樞紐節(jié)點(diǎn)組成的網(wǎng)絡(luò)進(jìn)行優(yōu)化，然后對某一樞紐節(jié)點(diǎn)內(nèi)的二級節(jié)點(diǎn)進(jìn)行優(yōu)化，直至末端配送節(jié)點(diǎn)。

5 算例分析

本文選擇廣西某快遞公司進(jìn)行擁塞控制，廣西某快遞公司的配送網(wǎng)絡(luò)以南寧為樞紐節(jié)點(diǎn)，各地級市設(shè)有轉(zhuǎn)運(yùn)節(jié)點(diǎn)，各縣設(shè)有末端配送點(diǎn)，除了極少數(shù)交通發(fā)達(dá)的鄉(xiāng)鎮(zhèn)外，大部分鄉(xiāng)鎮(zhèn)還沒有布點(diǎn)，目前在廣西共有142個(gè)節(jié)點(diǎn)。

5.1 數(shù)據(jù)

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

圖2 廣西某快遞公司主干網(wǎng)絡(luò)結(jié)構(gòu)

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

5.2 優(yōu)化仿真結(jié)果

工作電腦為CPU主頻2.1GHZ、內(nèi)存2.0G的聯(lián)想臺式機(jī)， Matlab R2012a編程實(shí)現(xiàn)算法。

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

設(shè)定期望傳輸能力RE為12萬件/天，將數(shù)據(jù)輸入Matlab程序，計(jì)算運(yùn)行時(shí)間為37.166 s，得到快遞網(wǎng)絡(luò)傳輸能力Rc=12.501萬件/天，網(wǎng)絡(luò)連接成本為Total_L=1835 km，快遞網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。當(dāng)快遞網(wǎng)絡(luò)的流量為12.501萬件/天，各節(jié)點(diǎn)的快遞流量如圖4所示，柳州節(jié)點(diǎn)為瓶頸節(jié)點(diǎn)，其快遞流量與其處理能力相等為8萬件/天，其余節(jié)點(diǎn)的處理能力均大于通過快遞流量，北海節(jié)點(diǎn)的能力利用率最低。

表2 節(jié)點(diǎn)間公路直達(dá)距離(單位：km)

數(shù)據(jù)來源：tool.2345.com

表3 各子網(wǎng)的節(jié)點(diǎn)數(shù)目

數(shù)據(jù)來源：廣西某快遞公司

圖3 RE=12萬件/天最低連接成本網(wǎng)絡(luò)結(jié)構(gòu)

圖4 Rc=12.501萬件/天各節(jié)點(diǎn)快遞流量

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

設(shè)定期望快遞網(wǎng)絡(luò)傳輸能力RE為14萬件/天，程序計(jì)算運(yùn)行時(shí)間為42.104 s，得到快遞網(wǎng)絡(luò)傳輸能力Rc=14.5703萬件/天，網(wǎng)絡(luò)連接成本為Total_L=2725 km，快遞網(wǎng)絡(luò)結(jié)構(gòu)如圖5所示。

圖5 RE=14萬件/天最低連接成本網(wǎng)絡(luò)結(jié)構(gòu)

當(dāng)快遞網(wǎng)絡(luò)的流量為14.5703萬件/天，各節(jié)點(diǎn)的快遞流量如圖6所示，瓶頸節(jié)點(diǎn)為南寧節(jié)點(diǎn)，南寧節(jié)點(diǎn)的快遞流量與其處理能力相等為10萬件/天，其余節(jié)點(diǎn)的處理能力均大于通過快遞流量，北海節(jié)點(diǎn)的能力利用率最低。

圖6 Rc=14.5703萬件/天各節(jié)點(diǎn)快遞流量

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

設(shè)定期望快遞網(wǎng)絡(luò)傳輸能力RE為16萬件/天，程序計(jì)算運(yùn)行時(shí)間為48.710 s，得到快遞網(wǎng)絡(luò)傳輸能力Rc=16.3171萬件/天，網(wǎng)絡(luò)連接成本為Total_L=2905 km，快遞網(wǎng)絡(luò)結(jié)構(gòu)如圖7所示。

圖7 RE=16萬件/天最低連接成本網(wǎng)絡(luò)結(jié)構(gòu)

圖8 Rc=16.3171萬件/天各節(jié)點(diǎn)快遞流量

當(dāng)快遞網(wǎng)絡(luò)的流量為16.3171萬件/天，各節(jié)點(diǎn)的快遞流量如圖8所示，瓶頸節(jié)點(diǎn)為柳州節(jié)點(diǎn)，柳州節(jié)點(diǎn)的快遞流量與其處理能力相等為8萬件/天，其余節(jié)點(diǎn)的處理能力均大于通過的快遞流量，北海節(jié)點(diǎn)的能力利用率最低。

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

設(shè)定期望快遞網(wǎng)絡(luò)傳輸能力RE為18萬件/天，計(jì)算運(yùn)行時(shí)間為62.093 s，得到快遞網(wǎng)絡(luò)傳輸能力Rc=18.3129萬件/天，網(wǎng)絡(luò)連接成本為Total_L=4570 km，快遞網(wǎng)絡(luò)結(jié)構(gòu)如圖9所示。

圖9 RE=18萬件/天最低連接成本網(wǎng)絡(luò)結(jié)構(gòu)

當(dāng)快遞網(wǎng)絡(luò)的流量為18.3129萬件/天，各節(jié)點(diǎn)的快遞流量如圖10所示，瓶頸節(jié)點(diǎn)為柳州節(jié)點(diǎn)，柳州節(jié)點(diǎn)的快遞流量與其處理能力相等為8萬件/天，其余節(jié)點(diǎn)的處理能力均大于通過快遞流量，北海節(jié)點(diǎn)的能力利用率最低。

圖10 Rc=18.3129萬件/天各節(jié)點(diǎn)快遞流量

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

設(shè)定期望快遞網(wǎng)絡(luò)傳輸能力RE為20萬件/天，程序計(jì)算運(yùn)行時(shí)間為81.961 s，得到快遞網(wǎng)絡(luò)傳輸能力Rc=20.8187萬件/天，網(wǎng)絡(luò)連接成本為Total_L=5701 km，快遞網(wǎng)絡(luò)結(jié)構(gòu)如圖11所示。

圖11 RE =20萬件/天最低連接成本網(wǎng)絡(luò)結(jié)構(gòu)

當(dāng)快遞網(wǎng)絡(luò)的流量為20.8187萬件/天，各節(jié)點(diǎn)的快遞流量如圖12所示，瓶頸節(jié)點(diǎn)為南寧節(jié)點(diǎn)，南寧節(jié)點(diǎn)的快遞流量與其處理能力相等為10萬件/天，其余節(jié)點(diǎn)的處理能力均大于通過快遞流量，北海節(jié)點(diǎn)的能力利用率最低。

圖12 Rc=20.8187萬件/天各節(jié)點(diǎn)快遞流量

5.3 結(jié)果分析

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

(1)瓶頸節(jié)點(diǎn)的處理能力和介數(shù)決定網(wǎng)絡(luò)傳輸能力

瓶頸節(jié)點(diǎn)的處理能力和介數(shù)決定快遞網(wǎng)絡(luò)的最大整體傳輸能力Rc，快遞企業(yè)可以通過改變瓶頸節(jié)點(diǎn)的處理能力和改變瓶頸節(jié)點(diǎn)的介數(shù)均可調(diào)節(jié)快遞網(wǎng)絡(luò)的傳輸能力。當(dāng)改善瓶頸節(jié)點(diǎn)的的處理能力和介數(shù)后，瓶頸節(jié)點(diǎn)可能發(fā)生轉(zhuǎn)移，如在軸輻網(wǎng)絡(luò)中南寧節(jié)點(diǎn)為瓶頸節(jié)點(diǎn)，在期望快遞網(wǎng)絡(luò)傳輸能力RE=12萬件/天的最低連接成本網(wǎng)絡(luò)中瓶頸節(jié)點(diǎn)轉(zhuǎn)移到柳州節(jié)點(diǎn)，只有不斷尋找瓶頸節(jié)點(diǎn)并對其改善才能提升快遞網(wǎng)絡(luò)的整體傳輸能力。

(2)目前快遞企業(yè)選擇的軸輻式網(wǎng)絡(luò)結(jié)構(gòu)抗擁塞性能較差

目前廣西某快遞企業(yè)選擇單樞紐純軸輻式結(jié)構(gòu)，其抗擁塞性能是較差的，因?yàn)樗械淖泳W(wǎng)之間的路徑均需通過樞紐節(jié)點(diǎn)，造成在樞紐節(jié)點(diǎn)的介數(shù)非常大。

(3)網(wǎng)絡(luò)傳輸能力Rc與連接成本悖反

在節(jié)點(diǎn)處理能力不變的情況下，提高網(wǎng)絡(luò)傳輸能力Rc則需提高快遞網(wǎng)絡(luò)的連接成本。為了節(jié)約網(wǎng)絡(luò)連接成本，提高運(yùn)營效果，快遞企業(yè)應(yīng)根據(jù)企業(yè)服務(wù)定位決定其傳輸能力。

6 結(jié)語

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

[1] 于寶琴，武淑萍，杜廣偉. 網(wǎng)購快遞物流服務(wù)系統(tǒng)測評的枝模型仿真[J]. 中國管理科學(xué)，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ī)行走機(jī)理的優(yōu)化路由改進(jìn)策略[J]. 物理學(xué)報(bào)，2011，60(11)：118903.

[6] 劉偉彥，劉斌. 基于加權(quán)路由策略的復(fù)雜網(wǎng)絡(luò)擁塞控制研究[J]. 系統(tǒng)工程理論實(shí)踐，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] 張國清，程蘇琦. 小世界網(wǎng)絡(luò)中的刪邊擴(kuò)容效應(yīng)[J]. 中國科學(xué)：信息科學(xué)，2012，42(2)：151-160.

[17] 蔡君，余順爭. 一種有效提高無標(biāo)度網(wǎng)絡(luò)負(fù)載容量的管理策略[J]. 物理學(xué)報(bào)，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] 周濤，張子柯，陳關(guān)榮，等. 復(fù)雜網(wǎng)絡(luò)研究的機(jī)遇與挑戰(zhàn)[J]. 電子科技大學(xué)學(xué)報(bào)，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

國家自然科學(xué)基金資助項(xiàng)目(61170017)

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

1003-207(2017)04-0143-09

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

F252.3

A