羅玉宏，張 琳

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

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

羅玉宏，張 琳

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

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

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

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

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

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

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

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

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

2.1問題提出

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

2.2模型假設

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

（2）起始節(jié)點與終端節(jié)點之間的運輸沒有容量和時間限制，運輸費用包括：非中心節(jié)點到中心樞紐的運輸成本；中心樞紐之間的規(guī)模運輸成本；中心樞紐站到目標節(jié)點的運輸成本。

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

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

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

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

2.3模型構(gòu)建

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

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

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

基于源節(jié)點 s 的共享樹 T 中節(jié)點 i 的運輸費用可表示為

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

貨物運輸?shù)目傎M用，即共享樹 T的總權值可表示為

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

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

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

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

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

3.2啟發(fā)式算法

3.2.1算法描述

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

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

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

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

3.2.2算法性能分析

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

4　案例分析

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

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

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

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

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

4.2案例分析

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

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

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

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

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

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

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

5　結(jié)束語

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

[1] 朱宇清. 多式聯(lián)運軸輻式物流網(wǎng)絡的設計優(yōu)化研究[D]. 西安：長安大學，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)絡與軸輻快遞網(wǎng)絡的比較[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ǎng)絡設計[J]. 交通運輸系統(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)絡構(gòu)建研究[J]. 鐵道運輸與經(jīng)濟，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ǎng)絡構(gòu)建研究[D]. 北京：北京交通大學，2012.

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

[13] 劉四輩，胡大偉. 帶時間窗的公路快速貨運軸輻式網(wǎng)絡設計研究[D]. 西安：長安大學，2011.

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

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

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

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

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

責任編輯：王 靜

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)新重點項目 (12ZS170)