羅玉宏，張 琳

（上海對(duì)外經(jīng)貿(mào)大學(xué)統(tǒng)計(jì)與信息學(xué)院，上海201620）

軸輻式物流網(wǎng)絡(luò)模型的參數(shù)算法

羅玉宏，張 琳

（上海對(duì)外經(jīng)貿(mào)大學(xué)統(tǒng)計(jì)與信息學(xué)院，上海201620）

為了及時(shí)高效地為企業(yè)尋找到最優(yōu)的軸輻式物流網(wǎng)絡(luò)，將經(jīng)典運(yùn)輸問(wèn)題的網(wǎng)絡(luò)模型抽象成平面圖的形式，將軸輻式網(wǎng)絡(luò)優(yōu)化問(wèn)題轉(zhuǎn)化為構(gòu)造一棵總運(yùn)輸費(fèi)用最小的共享樹問(wèn)題。借助參數(shù)算法理論，提出一種啟發(fā)式算法，首先通過(guò)構(gòu)造一棵包括所有起訖節(jié)點(diǎn)的最小連通生成樹，然后依次向樹中添加能減少共享樹總權(quán)值的非終端節(jié)點(diǎn)，最終生成一棵節(jié)點(diǎn)總數(shù)不超過(guò)參數(shù)k的最小共享樹。實(shí)驗(yàn)表明，該算法具有較好的準(zhǔn)確性和更高的時(shí)間效率，適用于網(wǎng)絡(luò)規(guī)模大、終端配送節(jié)點(diǎn)較少的物流網(wǎng)絡(luò)。

運(yùn)輸網(wǎng)絡(luò)；規(guī)模效應(yīng)；共享樹；參數(shù)算法

1　軸輻式物流網(wǎng)絡(luò)研究現(xiàn)狀

物流網(wǎng)絡(luò)是一個(gè)復(fù)雜的網(wǎng)絡(luò)系統(tǒng)，網(wǎng)絡(luò)優(yōu)化的核心是確定合適的物流節(jié)點(diǎn)位置、規(guī)模和數(shù)量，選擇合適的連接線路及運(yùn)輸方式，使物流網(wǎng)絡(luò)在滿足服務(wù)要求的基礎(chǔ)上總的運(yùn)輸成本最低。軸輻式物流網(wǎng)絡(luò)是以一個(gè)或多個(gè)樞紐節(jié)點(diǎn)為軸 (hub)，環(huán)繞在這些節(jié)點(diǎn)周圍的非樞紐節(jié)點(diǎn)為輻 (spoke)，網(wǎng)絡(luò)中通過(guò)線路 (link) 連接軸輻節(jié)點(diǎn)，實(shí)現(xiàn)貨物傳遞的一種網(wǎng)絡(luò)結(jié)構(gòu)。軸輻式物流網(wǎng)絡(luò)便于集中運(yùn)輸，達(dá)到規(guī)模經(jīng)濟(jì)的效益，對(duì)批次多、批量小、貨點(diǎn)分散的快速物流網(wǎng)絡(luò)而言尤其有效，對(duì)解決國(guó)內(nèi)物流成本居高不下的問(wèn)題能起到積極的作用，是未來(lái)物流網(wǎng)絡(luò)的發(fā)展方向。

軸輻式網(wǎng)絡(luò)的概念最早是由 Gordon 和 Neufville提出[1]，O’KELLY M E[2-3]首次提出軸輻式網(wǎng)絡(luò)樞紐選址問(wèn)題，指出樞紐選址問(wèn)題是一種 NP 問(wèn)題。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)擴(kuò)大到一定規(guī)模時(shí)，受軸輻式物流網(wǎng)絡(luò)模型復(fù)雜性的限制，大多數(shù)精確算法在求解軸輻式物流網(wǎng)絡(luò)的現(xiàn)實(shí)問(wèn)題中很難獲得最優(yōu)解，算法的效率和精度一直是構(gòu)建軸輻式網(wǎng)絡(luò)面臨的問(wèn)題。許多學(xué)者對(duì)軸輻式物流網(wǎng)絡(luò)算法進(jìn)行研究，TOPCUOGLU H 等[4]提出用遺傳算法求解軸輻式物流網(wǎng)絡(luò)模型，該算法能大幅節(jié)省計(jì)算所消耗的時(shí)間；PIRKUL H 等[5]設(shè)計(jì)基于拉格朗日松弛的啟發(fā)式算法，能夠控制在 5 min 之內(nèi)求解軸輻式物流網(wǎng)絡(luò)模型；SUNG C S 等[6]研究混合軸輻式網(wǎng)絡(luò)，采用二次上升、二次調(diào)整的方法確定并縮小解空間，直到得出滿意解；MENG Q 等[7]為多式聯(lián)運(yùn)的軸輻式物流網(wǎng)絡(luò)模型開發(fā)基于遺傳算法的混合啟發(fā)式算法，具有快速、精確的特點(diǎn)。

國(guó)內(nèi)對(duì)軸輻式物流網(wǎng)絡(luò)研究起步較晚。倪玲霖等[8]分析研究軸輻式物流網(wǎng)絡(luò)和全連通物流網(wǎng)絡(luò)的特點(diǎn)，得出軸輻式物流網(wǎng)絡(luò)在一般情況下效果要優(yōu)于全連通物流網(wǎng)絡(luò)；崔小燕等[9]研究無(wú)容量限制的單分配軸輻式物流網(wǎng)絡(luò)，提出基于蟻群算法的啟發(fā)式求解算法；王玉勤[10]利用主成分分析法對(duì)貴州省各個(gè)城市的物流能力進(jìn)行評(píng)價(jià)，并借助城市空間引力模型構(gòu)建貴州省軸輻式物流網(wǎng)絡(luò)；張銀花[11]研究基于服務(wù)能力的軸輻式物流網(wǎng)絡(luò)設(shè)計(jì)；劉沛[12]研究具有專線的混合軸輻式物流網(wǎng)絡(luò)規(guī)劃問(wèn)題，并采用遺傳算法進(jìn)行求解；劉四輩等[13]研究考慮時(shí)間窗的軸輻式物流網(wǎng)絡(luò)問(wèn)題，并設(shè)計(jì)啟發(fā)式算法用來(lái)求解；衛(wèi)嬋嬋等[14]研究基于多式聯(lián)運(yùn)的軸輻式物流網(wǎng)絡(luò)，各樞紐之間采用分段函數(shù)來(lái)表示規(guī)模運(yùn)輸?shù)恼劭巯禂?shù)，并且采用禁忌搜索算法進(jìn)行求解。

構(gòu)建軸輻式物流網(wǎng)絡(luò)是一個(gè) NP 難問(wèn)題，隨著網(wǎng)絡(luò)規(guī)模的增大，上述算法在時(shí)間性能和準(zhǔn)確度方面都有較大程度的下降，影響實(shí)際的應(yīng)用。參數(shù)理論是近年發(fā)展起來(lái)的解決該難題的一項(xiàng)有效技術(shù)。參數(shù)理論的研究最初來(lái)源于觀察到很多計(jì)算問(wèn)題都與一個(gè)取值范圍很小的重要參數(shù)相聯(lián)系，利用參數(shù)的性質(zhì)可以在一定程度上加速計(jì)算。將物流網(wǎng)絡(luò)模型抽象成平面圖的形式，將軸輻式網(wǎng)絡(luò)優(yōu)化問(wèn)題轉(zhuǎn)化為構(gòu)造一棵最小共享樹問(wèn)題，然后借助參數(shù)算法理論，提出一種啟發(fā)式優(yōu)化算法。

2　軸輻式物流網(wǎng)絡(luò)模型

2.1問(wèn)題提出

定義運(yùn)輸起點(diǎn) (起始節(jié)點(diǎn)) Ai，i = 1，2，…，p，其中 p 為起始節(jié)點(diǎn)個(gè)數(shù)。需要從 Ai運(yùn)輸?shù)呢浳锪繛?ai，運(yùn)往目的地 (終端節(jié)點(diǎn)) Bj的貨物量為 bj， j = 1，2，…，q，其中 q 為終端節(jié)點(diǎn)個(gè)數(shù)，。問(wèn)題是如何最快構(gòu)造軸輻式物流網(wǎng)絡(luò)，使總運(yùn)輸費(fèi)用最低。

2.2模型假設(shè)

（1）構(gòu)成的軸輻式物流網(wǎng)絡(luò)中至少包含 m 個(gè)節(jié)點(diǎn)，其中 m = p + q。

（2）起始節(jié)點(diǎn)與終端節(jié)點(diǎn)之間的運(yùn)輸沒(méi)有容量和時(shí)間限制，運(yùn)輸費(fèi)用包括：非中心節(jié)點(diǎn)到中心樞紐的運(yùn)輸成本；中心樞紐之間的規(guī)模運(yùn)輸成本；中心樞紐站到目標(biāo)節(jié)點(diǎn)的運(yùn)輸成本。

（3）采用單一樞紐指派，即網(wǎng)絡(luò)中的非中心節(jié)點(diǎn)僅和一個(gè)中心樞紐連接。

（4）采用多樞紐軸輻式物流網(wǎng)絡(luò)，即允許存在多個(gè)中心樞紐，非中心樞紐依靠一定規(guī)則分配給這些中心樞紐，與不同中心樞紐連接的非中心節(jié)點(diǎn)通過(guò)樞紐間的運(yùn)輸與再轉(zhuǎn)運(yùn)實(shí)現(xiàn)貨物運(yùn)輸。

（5）采用多式聯(lián)運(yùn)，即在運(yùn)輸貨物的過(guò)程中，經(jīng)過(guò) 2 種或 2 種以上的運(yùn)輸方式 (如鐵路、公路、航空、水運(yùn)等)，將貨物從起始節(jié)點(diǎn)運(yùn)送到終端節(jié)點(diǎn)。幾種不同的運(yùn)輸方式都有各自不同的成本費(fèi)率；一般情況下，鐵路的單位運(yùn)輸成本費(fèi)率最低，而航空的單位運(yùn)輸成本最高[15]。

（6）中心樞紐之間運(yùn)輸具有規(guī)模效應(yīng)，即通過(guò)擴(kuò)大規(guī)模的方式來(lái)減少成本，并帶來(lái)收益的提高。規(guī)模效應(yīng)的折扣系數(shù)隨著貨物流量的變化而變化。

2.3模型構(gòu)建

構(gòu)建一個(gè)無(wú)向圖G = (V，E)，V 為節(jié)點(diǎn)集合，V = {A，R，B}。其中，A 為起始節(jié)點(diǎn)集，A = {A1，A2，…，Ap}；B 為終端節(jié)點(diǎn)集，B = {B1，B2，…，Bq}；R 為中轉(zhuǎn)節(jié)點(diǎn)集，R = {R1，R2，…，Rn-p-q}，n 為集合 V 中節(jié)點(diǎn)個(gè)數(shù)； E 為鏈路 (邊) 集合，E = {eij| i，j ∈ V}。

共享樹是以源節(jié)點(diǎn)為樹根節(jié)點(diǎn)，以多個(gè)樞紐節(jié)點(diǎn)為軸節(jié)點(diǎn)，以非樞紐節(jié)點(diǎn)為輻節(jié)點(diǎn)，按照總運(yùn)輸費(fèi)用最小建立的樹型結(jié)構(gòu)。在共享樹中，任一運(yùn)輸源節(jié)點(diǎn)可以通過(guò)共享樹向樹中指定的多個(gè)目標(biāo)節(jié)點(diǎn)發(fā)送貨物。以 s 為樹根節(jié)點(diǎn)，其他黑色節(jié)點(diǎn)為軸節(jié)點(diǎn)，白色節(jié)點(diǎn)為輻節(jié)點(diǎn)，構(gòu)建以 s 為源節(jié)點(diǎn)的共享樹如圖1所示。

圖1　以 s 為源節(jié)點(diǎn)的共享樹

基于源節(jié)點(diǎn) s 的共享樹 T 中節(jié)點(diǎn) i 的運(yùn)輸費(fèi)用可表示為

式中：Vi為輻節(jié)點(diǎn) i 單位質(zhì)量貨物聯(lián)運(yùn)的中轉(zhuǎn)費(fèi)用，元/kg；Eij為單位質(zhì)量貨物從節(jié)點(diǎn) i 運(yùn)輸?shù)狡溧徆?jié)點(diǎn)j 所產(chǎn)生的費(fèi)用，元/kg；λij為從節(jié)點(diǎn) i 到其鄰節(jié)點(diǎn) j 運(yùn)輸貨物的量，kg；Eih為單位質(zhì)量貨物從軸節(jié)點(diǎn) i 運(yùn)輸?shù)狡溧徆?jié)點(diǎn) h 所產(chǎn)生的費(fèi)用，元/kg；λih為從軸節(jié)點(diǎn) i 到其鄰節(jié)點(diǎn) h 運(yùn)輸貨物的量，kg；δ 為節(jié)點(diǎn) i 鄰節(jié)點(diǎn)的個(gè)數(shù)；δ1為軸節(jié)點(diǎn) i 鄰居軸節(jié)點(diǎn)的個(gè)數(shù)；δ2為軸節(jié)點(diǎn) i 鄰居輻節(jié)點(diǎn)的個(gè)數(shù)；d為軸節(jié)點(diǎn)之間規(guī)模運(yùn)輸時(shí)的運(yùn)費(fèi)折扣系數(shù)。

貨物運(yùn)輸?shù)目傎M(fèi)用，即共享樹 T的總權(quán)值可表示為

因此，上述運(yùn)輸問(wèn)題轉(zhuǎn)換為求最小共享樹問(wèn)題，這類問(wèn)題屬于 NP 難問(wèn)題。擬采用參數(shù)算法理論求解。

3　軸輻式物流網(wǎng)絡(luò)的參數(shù)算法

參數(shù)算法是基于參數(shù)復(fù)雜度理論設(shè)計(jì)的一類算法，其運(yùn)行時(shí)間復(fù)雜度具有特殊的形式。如果某個(gè)算法的時(shí)間復(fù)雜度為 f (k) nc，則稱該算法為固定參數(shù)算法。其中，k 是問(wèn)題的參數(shù)，n 是問(wèn)題輸入規(guī)模的大小，c 是一個(gè)獨(dú)立于 k 和 n 的常數(shù)，f (k) 是以 k 為自變量的可計(jì)算函數(shù)。在參數(shù)算法中，用參數(shù)理論來(lái)求解 NP 難問(wèn)題，需要將問(wèn)題轉(zhuǎn)換為參數(shù)算法中連接的節(jié)點(diǎn)覆蓋問(wèn)題，并提出解決該問(wèn)題的啟發(fā)式算法。

3.1參數(shù)問(wèn)題轉(zhuǎn)換

第一，輸入一個(gè)給定的無(wú)向連通圖G (V，E)及一個(gè)正整數(shù) k，k≥m = p + q。第二，問(wèn)題轉(zhuǎn)換：圖G 是否存在一個(gè)數(shù)量不超過(guò) k 個(gè)節(jié)點(diǎn)的覆蓋 G' ? G，G' 是包含 m 個(gè)指定節(jié)點(diǎn)的連通的樹，并且樹的總權(quán)值最小。為方便參數(shù)問(wèn)題的求解，在無(wú)向連通圖G 中，共享樹 T 有 m 個(gè)終端節(jié)點(diǎn)和一些非終端節(jié)點(diǎn)，令 σ = max (Eij) / min (Eij)，所以共享樹本質(zhì)上是一棵 Steiner 樹，具有如下性質(zhì)：①如果終端節(jié)點(diǎn)導(dǎo)出的子圖為連通圖，對(duì) T 中任一非終端節(jié)點(diǎn) v，節(jié)點(diǎn) v 的度 d (v)≥[σ / (σ－1)]。②如果終端節(jié)點(diǎn)導(dǎo)出子圖為連通圖，對(duì) T 中非終端節(jié)點(diǎn)的個(gè)數(shù) l≤[m (σ－1)]；如果終端節(jié)點(diǎn)導(dǎo)出子圖是不連通的，非終端節(jié)點(diǎn)的個(gè)數(shù) l≤[m (σ－1)] + σ |V1|，V1是讓終端節(jié)點(diǎn)導(dǎo)出子圖連通的非終端節(jié)點(diǎn)的集合。③在連接的節(jié)點(diǎn)覆蓋問(wèn)題中，最小共享樹 T 的節(jié)點(diǎn)數(shù) k≤m + l。

3.2啟發(fā)式算法

3.2.1算法描述

（1）采用分布式算法，直接構(gòu)造一棵包含 m 個(gè)終端節(jié)點(diǎn)的最小連通生成樹 T (非終端節(jié)點(diǎn)盡可能地少，只為了維持樹的連通性，添加必不可少的非終端節(jié)點(diǎn))。對(duì)生成樹 T 中所有非終端節(jié)點(diǎn)的葉子節(jié)點(diǎn)剪枝，作為備選節(jié)點(diǎn)存放在集合 B 中。為方便計(jì)算，對(duì)樹中任一節(jié)點(diǎn) i，增加選路表和費(fèi)用信息表。選路表由三元組 (vd，vn，Cmin) 構(gòu)成，其中vd為目的節(jié)點(diǎn)，vn為由節(jié)點(diǎn) i 運(yùn)輸貨物到達(dá) vd節(jié)點(diǎn)要選擇的鄰居節(jié)點(diǎn)，Cmin為由節(jié)點(diǎn) i 運(yùn)送單位質(zhì)量貨物到達(dá) vd的最小費(fèi)用。費(fèi)用信息表由四元組 (j，λij，vi，d)構(gòu)成，分別用來(lái)存放節(jié)點(diǎn) i 到其任一鄰居節(jié)點(diǎn)j 的貨物運(yùn)輸量λij、聯(lián)運(yùn)費(fèi)用 vi和折扣率 d。處理過(guò)程如下：①任一節(jié)點(diǎn)計(jì)算到鄰居節(jié)點(diǎn)最小費(fèi)用 Cmin，建立選路表，然后將選路表告訴它所有的鄰居節(jié)點(diǎn)；②任一節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的選路信息后，對(duì)其選路表進(jìn)行添加、刪除或修改，并將新的選路信息告訴所有的鄰居節(jié)點(diǎn)；③重復(fù)步驟②，直到所有節(jié)點(diǎn)不再有選路信息的更新；④所有的運(yùn)輸起點(diǎn)將要運(yùn)送貨物的數(shù)量和目的地等信息告訴它的鄰節(jié)點(diǎn) (假設(shè)為 i)；⑤鄰節(jié)點(diǎn) i 收到該信息后，根據(jù)選路表的信息，選擇不同的轉(zhuǎn)發(fā)鄰節(jié)點(diǎn) (假設(shè)為j)，分別計(jì)算λij，vi，d，將這些信息存放在費(fèi)用信息表中，然后將要通過(guò)j 運(yùn)送貨物的數(shù)量和目的地等信息轉(zhuǎn)發(fā)給j；⑥重復(fù)步驟⑤，直到所有的信息都傳遞到目的節(jié)點(diǎn)。

（2）對(duì)生成樹 T 進(jìn)行優(yōu)化，減少生成樹 T 的總權(quán)值。按輪對(duì)生成樹 T 進(jìn)行優(yōu)化，每一輪優(yōu)化過(guò)程都從生成樹根節(jié)點(diǎn) s 開始。①按照固定的次序依次遍歷樹 T 的每一個(gè)節(jié)點(diǎn)，如果一輪遍歷結(jié)束后，樹的結(jié)構(gòu)沒(méi)有發(fā)生變化，則終止優(yōu)化。②當(dāng)遍歷經(jīng)過(guò)節(jié)點(diǎn) i 時(shí)，節(jié)點(diǎn) i 的處理過(guò)程如圖2所示。節(jié)點(diǎn) i 的任一鄰居節(jié)點(diǎn) p ( p 不在節(jié)點(diǎn) i 的子樹中)，假設(shè)節(jié)點(diǎn) i 更改其父節(jié)點(diǎn) v 為節(jié)點(diǎn) p，計(jì)算生成樹費(fèi)用的減少，記為 Gainv-＞p。當(dāng)節(jié)點(diǎn) i 更改父節(jié)點(diǎn)由 v 到 p 時(shí)，運(yùn)輸費(fèi)用受到影響的節(jié)點(diǎn)是從節(jié)點(diǎn) v 指向根節(jié)點(diǎn)的路徑 (v-＞u) 和節(jié)點(diǎn) p 指向根節(jié)點(diǎn)的路徑(p-＞u)，節(jié)點(diǎn) u 為節(jié)點(diǎn) v 和 p 的共同祖先。分別運(yùn)用公式 ⑴ 計(jì)算路徑 i-v-u-p 中各個(gè)節(jié)點(diǎn)的費(fèi)用變化情況，并匯總為 Gainv-＞p。節(jié)點(diǎn) i 選擇最大的正的Gainv-＞p所在的 p 節(jié)點(diǎn) (如果這樣的點(diǎn)存在) 為新的父節(jié)點(diǎn)，節(jié)點(diǎn) i 更改父節(jié)點(diǎn)后，向鄰居節(jié)點(diǎn)通告新的選路信息并更新自身的費(fèi)用信息表。生成樹中其他節(jié)點(diǎn)收到新的信息后，更新自身的選路表和費(fèi)用信息表。遍歷下一個(gè)節(jié)點(diǎn)。③刪除可能存在的非終端葉子節(jié)點(diǎn)，并且更新生成樹 T 的信息。顯然，這時(shí)樹 T 中盡可能只包含所有起始節(jié)點(diǎn)和終端節(jié)點(diǎn)，并且 |T |≤k ( |T | 表示樹 T 中節(jié)點(diǎn)的個(gè)數(shù))，總費(fèi)用接近最優(yōu)。

圖2　節(jié)點(diǎn) i 更改父節(jié)點(diǎn)由 v 到 p

（3）用參數(shù) k 來(lái)控制生成樹 T 的規(guī)模，向樹 T中逐步加入符合優(yōu)化條件的非終端節(jié)點(diǎn)，尋找總費(fèi)用趨向最優(yōu)的共享樹。①如果 |T | ＜ k，重復(fù)以下步驟②-⑤；②依次從備選集 B 中取出一個(gè)節(jié)點(diǎn) v (v 必須是樹 T 中節(jié)點(diǎn)的鄰居節(jié)點(diǎn))；③節(jié)點(diǎn) v 在它的鄰居節(jié)點(diǎn)中尋找屬于生成樹 T 中的節(jié)點(diǎn) u，使節(jié)點(diǎn) v 連接到節(jié)點(diǎn) u 后距離最??；④對(duì)節(jié)點(diǎn) v 在生成樹中的任一鄰居節(jié)點(diǎn)j (節(jié)點(diǎn) u 除外) 進(jìn)行是否更改父節(jié)點(diǎn)判斷，如果j 選擇 v 作為其父節(jié)點(diǎn)，則證明節(jié)點(diǎn) v 的加入將減少生成樹的總費(fèi)用，那么：將 v 連接到節(jié)點(diǎn) u，將 |T | 加 1；將 j 連接到節(jié)點(diǎn) v；節(jié)點(diǎn) v，j 更新各自的選路表和費(fèi)用信息表，向鄰居節(jié)點(diǎn)通告新的選路信息；生成樹中其他節(jié)點(diǎn)收到新的信息后，更新自身的選路表和費(fèi)用信息表；刪除 T 中存在的非終端葉子節(jié)點(diǎn)，每刪除 1 個(gè)，進(jìn)行|T |減 1 的操作，更新生成樹 T 的信息。⑤如果備選集 B 中符合條件的任一節(jié)點(diǎn)加入，生成樹中不再改變，終止上述操作。

3.2.2算法性能分析

第一階段構(gòu)造初始的生成樹 T 和對(duì)生成樹 T 進(jìn)行剪枝，時(shí)間復(fù)雜度為 O (nlogn)； 第二階段中優(yōu)化初始的生成樹 T 的過(guò)程中，時(shí)間復(fù)雜度為O (kδT)，δT是樹的度；第三階段生成樹優(yōu)化過(guò)程中，最多會(huì)分析 kδG個(gè)結(jié)點(diǎn)是否改變連接節(jié)點(diǎn)的判斷，δG是圖G 的度，時(shí)間復(fù)雜度為 O (kδGδT)。因此，啟發(fā)式算法總的時(shí)間復(fù)雜度為 O (nlogn + kδGδT)，參數(shù) k 很好地控制了算法的規(guī)模。當(dāng) k 值相對(duì) n 較小時(shí)，算法具有明顯的性能優(yōu)勢(shì)；當(dāng) k 值增大時(shí)，算法的性能會(huì)有所下降，當(dāng) k→n，算法的時(shí)間性能達(dá)到O (nlogn + nδG)。

4　案例分析

4.1基礎(chǔ)數(shù)據(jù)

物流網(wǎng)絡(luò)規(guī)模由全國(guó) 100 個(gè)大中城市 (以 2014年全國(guó) GDP 排名前 100 名的城市為例) 構(gòu)成。聯(lián)運(yùn)僅考慮常用的鐵路和公路 2 種情況，各城市之間的鐵路和公路運(yùn)輸距離數(shù)據(jù)分別來(lái)自列車時(shí)刻網(wǎng)[16]和長(zhǎng)途吧網(wǎng)[17]。

鐵路運(yùn)輸費(fèi)用按照《國(guó)家發(fā)展改革委關(guān)于調(diào)整鐵路貨運(yùn)價(jià)格進(jìn)一步完善價(jià)格形成機(jī)制的通知》[18]執(zhí)行。案例中采用零擔(dān)貨物方式，其中，鐵路零擔(dān)以 10 kg 為單位，不足 10 kg 按照 10 kg 計(jì)算，鐵路運(yùn)輸費(fèi)用公式為 Eij= 0.280 + 0.001 55×dij。其中，Eij為從節(jié)點(diǎn) i 到節(jié)點(diǎn)j 采用鐵路運(yùn)輸 10 kg 貨物的費(fèi)用，元；dij為節(jié)點(diǎn) i 和j 之間的距離，km；0.280 為 10 kg 貨運(yùn)起運(yùn)價(jià)，元；0.001 55 為每 1 km每 10 kg 貨運(yùn)的價(jià)格，元。

公路零擔(dān)以 1 kg 為單位，普通貨物的公路運(yùn)輸費(fèi)用公式為 Eij= 0.000 3×dij。其中，Eij為從節(jié)點(diǎn) i 到節(jié)點(diǎn)j 采用公路零擔(dān)運(yùn)輸 1 kg 普通貨物的費(fèi)用，元；0.000 3 為每 1 km 每 1 kg 普通貨物全國(guó)貨運(yùn)平均價(jià)格，元。

記規(guī)模運(yùn)輸?shù)恼劭巯禂?shù)為 d = 1－λij/ 100 000 (假設(shè)計(jì)費(fèi)重量超過(guò) 1 000 kg 才開始使用折扣系數(shù)，最大折扣系數(shù)不小于 0.8)；鐵路和公路間轉(zhuǎn)運(yùn)的費(fèi)用Vi= 0.011 元/kg；貨物運(yùn)送的起訖點(diǎn)隨機(jī)產(chǎn)生，每個(gè)起點(diǎn)的貨運(yùn)量在 [500，5 000] (kg) 之間隨機(jī)產(chǎn)生。

4.2案例分析

實(shí)驗(yàn)隨機(jī)貨物運(yùn)送起點(diǎn) ( p) 和目的地 (q) 的總和m 取值為 (10，20，…，100)，實(shí)驗(yàn)平臺(tái)采用的主要配置為 Windows 7 操作系統(tǒng)，intel? CoreTMi3 CPU M380@2.53GHz， 2GB 內(nèi)存，使用 C++ 編寫算法并使用 GCC 4.8.5 進(jìn)行編譯。分別模擬 100次，取 95% 的置信區(qū)間，實(shí)驗(yàn)結(jié)果如下。

（1）算法準(zhǔn)確性比較。將啟發(fā)式算法所生成的共享樹的總運(yùn)輸費(fèi)用，與通過(guò)枚舉法 (精確算法) 獲得的運(yùn)算結(jié)果進(jìn)行比較，二者費(fèi)用的總比值用準(zhǔn)確度表示，如表1 所示。

表1　啟發(fā)式算法和精確算法總運(yùn)輸費(fèi)用及比值

結(jié)果顯示啟發(fā)式算法的準(zhǔn)確性隨著 m 的增大而得到提高，當(dāng) m 接近 100 時(shí)，準(zhǔn)確度達(dá)到 104% 左右；當(dāng) m = 10 時(shí)，準(zhǔn)確度最差，達(dá)到 106.2%?？傮w上算法具有較高的準(zhǔn)確性。

（2） 算法運(yùn)行效率比較。記算法的運(yùn)行效率為啟發(fā)式算法和精確算法運(yùn)行時(shí)間的比值，啟發(fā)式算法和精確算法的運(yùn)行時(shí)間如表2 所示。

表2　啟發(fā)式算法和精確算法運(yùn)行時(shí)間及比值

可以看出，啟發(fā)式算法具有較好的運(yùn)行效率，運(yùn)行時(shí)間只有枚舉法的 1%～2% 之間。隨著 m 的增大，二者運(yùn)行的時(shí)間都在增大，但是啟發(fā)式算法增大的幅度更大一些。實(shí)驗(yàn)表明，啟發(fā)式算法在 m 遠(yuǎn)小于網(wǎng)絡(luò)規(guī)模 n 時(shí)，更加能體現(xiàn)出算法的時(shí)間性能。

5　結(jié)束語(yǔ)

參數(shù)理論是近年來(lái)發(fā)展起來(lái)的解決 NP 難問(wèn)題的一項(xiàng)有效技術(shù)，利用參數(shù)的性質(zhì)可以在一定程度上降低問(wèn)題的規(guī)模，加速計(jì)算。借助參數(shù)算法理論，運(yùn)用啟發(fā)式算法構(gòu)造了一棵節(jié)點(diǎn)總數(shù)不超過(guò)參數(shù) k 的最小共享樹，用非常少的時(shí)間對(duì)軸輻式物流網(wǎng)絡(luò)進(jìn)行了優(yōu)化，相對(duì)傳統(tǒng)的算法具有較好的準(zhǔn)確性和更高的時(shí)間效率，特別適應(yīng)于網(wǎng)絡(luò)規(guī)模大，終端配送節(jié)點(diǎn)較少的物流網(wǎng)絡(luò)。今后的研究將結(jié)合航運(yùn)、空運(yùn)，綜合考慮最短時(shí)限運(yùn)輸問(wèn)題，帶時(shí)間窗的路徑優(yōu)化問(wèn)題、帶車容量限制的路徑優(yōu)化問(wèn)題等，使算法更趨向于實(shí)際應(yīng)用。

[1] 朱宇清. 多式聯(lián)運(yùn)軸輻式物流網(wǎng)絡(luò)的設(shè)計(jì)優(yōu)化研究[D]. 西安：長(zhǎng)安大學(xué)，2013.

[2] O’KELLY M E. The Location of Interacting Hub Facilities[J]. Transportation Science，1986，20(2)：92-106.

[3] O’KELLY M E. A Quadratic Integer Program for the Location of Interacting Hub Facilities[J]. Euro Journal of Operational Research，1987，32(3)：393-404.

[4] TOPCUOGLU H，CORUTA F，ERMIS M，et al. Solving the Uncapacitated Hub Location Problem Using Genetic Algorithms[J]. Computer&Operations Research，2005，32(4)：967-984.

[5] PIRKUL H，SCHILLING D A. An Efficient Procedure for Designing Single Allocation Hub and Spoke Systems[J]. Management Science，1998，44(12)：235-242.

[6] SUNG C S，JIM H W. Dual-Based Approach for a Hub Network Design Problem under Non-Restrictive Policy[J]. European Journal of Operational Research，2001，132(1)：88-105.

[7] MENG Q，WANG X C. Intemodal Hub-and-Spoke Network Design：Incorporating Multiple Stakeholders and Multi-Type Containers[J]. Transportation Research Part B，2011，45(4)：724-742.

[8] 倪玲霖，史 峰，方曉平，等. 全連通快遞網(wǎng)絡(luò)與軸輻快遞網(wǎng)絡(luò)的比較[J]. 系統(tǒng)工程，2009，27(12)：45-50.

NI Ling-lin，SHI Feng，F(xiàn)ANG Xiao-ping，et al. Comparative Study on Fully-Connected and Hub-and-Spoke Express Operational Networks[J]. Systems Engineering，2009，27(12)：45-50.

[9] 崔小燕，李旭宏，毛海軍，等. 無(wú)容量約束單分配軸-輻式物流網(wǎng)絡(luò)設(shè)計(jì)[J]. 交通運(yùn)輸系統(tǒng)工程與信息，2010，10(5)：175-181.

CUI Xiao-yan，LI Xu-hong，MAO Hai-jun，et al. Design of Uncapacitated Hub-and-Spoke Logistics Networks with Single Allocation[J]. Journal of Transportation Systems Engineering and Information Technology，2010，10(5)：175-181.

[10] 王玉勤. 貴州省軸輻式物流網(wǎng)絡(luò)構(gòu)建研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2015，37(12)：41-46.

WANG Yu-qin. Study on Establishment of Hub-and-Spoke Logistic Network in Guizhou Province[J]. Railway Transport and Economy，2015，37(12)：41-46.

[11] 張銀花. 基于服務(wù)能力的軸輻式物流網(wǎng)絡(luò)構(gòu)建研究[D]. 北京：北京交通大學(xué)，2012.

[12] 劉 沛. 軸輻式快遞貨運(yùn)網(wǎng)絡(luò)規(guī)劃研究[D]. 濟(jì)南：山東大學(xué)，2007.

[13] 劉四輩，胡大偉. 帶時(shí)間窗的公路快速貨運(yùn)軸輻式網(wǎng)絡(luò)設(shè)計(jì)研究[D]. 西安：長(zhǎng)安大學(xué)，2011.

[14] 衛(wèi)嬋嬋，胡大偉. 多式聯(lián)運(yùn)樞紐網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)研究[D].西安：長(zhǎng)安大學(xué)，2012.

[15] 李珍萍，周文峰. 物流配送中心選址與路徑優(yōu)化問(wèn)題—建模與求解[M]. 北京：機(jī)械工業(yè)出版社，2014.

[16] 列車時(shí)刻網(wǎng). 距離[EB/OL]. (2009-01-01) [2015-07-01]. http://juli.liecheshike.com/.

[17] 長(zhǎng)途吧網(wǎng). 距離[EB/OL]. (2009-01-01)[2015-07-01]. http://www.changtu8.com/.

[18] 國(guó)家發(fā)展和改革委員會(huì)價(jià)格司. 關(guān)于調(diào)整鐵路貨運(yùn)價(jià)格進(jìn)一步完善價(jià)格形成機(jī)制的通知：發(fā)改價(jià)格[2015]183號(hào)[A/ OL]. (2015-01-29)[2015-07-01]. http://jgs.ndrc.gov.cn/ zcfg/201501/t20150130_662799.html.

責(zé)任編輯：王 靜

The Parameterized Algorithm for Hub-and-Spoke Logistics Network

LUO Yu-hong，ZHANG Lin

(School of Statistics and Information, Shanghai University of International Business and Economics, Shanghai 201620, China)

In order to find the optimal hub-and-spoke logistics network in time for companies, the network model of classical transportation problem is abstracted into the planar graph, and the optimization problem of logistics network is transformed into the problem of constructing a minimum shared tree. Then, a heuristic approximation algorithm is proposed based on the theory of parameter algorithm. First, the algorithm builds a connected minimum spanning tree including all origin-destinations (OD), and then adds the non-OD node to the tree one by one, which can reduce the total weight of the spanning tree, and lastly generates a minimum shared tree with nodes no more than k, and k is a small parameter. Experimental results show that the algorithm uses parameter k to reduce the complexity of the problem and has good accuracy and time efficiency, especially adapted to the large logistic network with less OD.

Transportation Network; Economy of Scale; Shared Tree; Parameterized Algorithm

1003-1421(2016)11-0035-06

F259.27

A

10.16668/j.cnki.issn.1003-1421.2016.11.08

2016-04-05

上海市教委科研創(chuàng)新重點(diǎn)項(xiàng)目 (12ZS170)