楊 斌，尹宇起，胡志華

(上海海事大學 物流研究中心，上海 201306)

樞紐多級容量限制下輻點分配模式的比較

楊 斌，尹宇起，胡志華

(上海海事大學 物流研究中心，上海 201306)

針對軸輻式網(wǎng)絡中輻點的單分配和多分配模式的現(xiàn)實差異，提出樞紐多級容量限制下的輻點分配模式的比較問題，研究需求不確定條件下兩種分配模式的特點?；谳S輻式網(wǎng)絡設計的基本模型，構(gòu)建樞紐多級容量限制下考慮運營成本的兩種分配模式的混合整數(shù)規(guī)劃模型。根據(jù)預測的多個需求場景及其概率分布求解兩種網(wǎng)絡模型的最優(yōu)期望成本以設計軸輻式網(wǎng)絡。通過設置網(wǎng)絡最優(yōu)設計、預先給定樞紐點數(shù)目和總需求量變動3項實驗，比較輻點的單分配和多分配模式在各實驗結(jié)果中的網(wǎng)絡成本、樞紐配置和樞紐利用率，發(fā)現(xiàn)多分配網(wǎng)絡具有較低的網(wǎng)絡總成本、較少的樞紐數(shù)目及較高的樞紐利用率。

交通運輸工程；單分配；多分配；軸輻式網(wǎng)絡；多級容量限制；需求不確定性

在軸輻式網(wǎng)絡中輻點的分配模式包括單分配和多分配，其中，輻點的單分配模式被廣泛地應用于航空、快遞等運輸網(wǎng)絡的研究[1-3]中。簡化模型及突出問題特點是研究者選擇單分配模式的主要原因，然而單分配模式可能并非網(wǎng)絡設計的最優(yōu)選擇。筆者將對樞紐多級容量限制條件下輻點的單分配和多分配模式進行比較。

樞紐點的容量限制影響樞紐點配置及輻點分配。在軸輻式網(wǎng)絡中，樞紐點的建設需要投入一定的建設成本，并且由于建設成本及選址區(qū)位的限制，樞紐點有限的設施和設備限制了自身的處理能力。軸輻式網(wǎng)絡中OD(origin destination)流的運輸都要經(jīng)過一個樞紐點或一條干線，因此樞紐點處理能力會影響其覆蓋的輻點范圍。相對于無容量限制的網(wǎng)絡而言，滿足相同客戶的收集、運輸和配送需求，具有容量限制的網(wǎng)絡就需要更多的樞紐點。

由于干線運輸?shù)囊?guī)模效應是軸輻式網(wǎng)絡的利潤源頭，OD流的不確定性成為網(wǎng)絡設計的關鍵。雖然可以通過預測得到網(wǎng)絡的需求，但是市場經(jīng)濟波動環(huán)境下的OD流需求具有波動性。筆者在網(wǎng)絡設計時考慮多種需求場景及其出現(xiàn)概率，采用求解多場景下網(wǎng)絡的最優(yōu)期望成本的策略進行網(wǎng)絡設計，以彌補不確定性的影響。

在樞紐點容量限制的情況下，比較兩種模式選擇最優(yōu)網(wǎng)絡設計時的網(wǎng)絡成本、樞紐配置、樞紐利用率。預先確定樞紐點數(shù)目，求解并比較此時網(wǎng)絡的成本、樞紐配置、樞紐利用率。通過改變OD流需求，比較兩種模式在需求變動中的穩(wěn)定性。同時，對多分配網(wǎng)絡設計中的單位運營成本的敏感性進行了討論。通過進行算例仿真實驗，發(fā)現(xiàn)多分配模式的網(wǎng)絡總成本總是比單分配模式網(wǎng)絡的總成本低，并且運營成本占網(wǎng)絡總成本比例較低時單位運營成本的變動對網(wǎng)絡設計沒有影響。多分配網(wǎng)絡中樞紐的利用率較高，而且當OD流需求總量有變化時多分配網(wǎng)絡穩(wěn)定性更高，但是多分配網(wǎng)絡比單分配網(wǎng)絡更復雜，貨流的調(diào)度更加困難。

1 軸輻式網(wǎng)絡

輻點的分配方式是軸輻式網(wǎng)絡設計的一個重要方面，其主要考慮兩種模式：單分配模式和多分配模式。單分配軸輻式網(wǎng)絡[4-10]中一個輻點只能分配給一個樞紐點；多分配軸輻式網(wǎng)絡[11-18]中一個輻點可以分配多個樞紐點。倪玲霖等[19]認為由于多分配網(wǎng)絡可以根據(jù)快遞量靈活分配中轉(zhuǎn)樞紐，因此比單分配網(wǎng)絡具有更加優(yōu)越的性能。但是文獻并未對多分配網(wǎng)絡的優(yōu)越性及網(wǎng)絡的經(jīng)濟成本進行研究，缺乏理論基礎。單分配與多分配網(wǎng)絡[20-24]的研究主要集中于對兩種分配模式的模型與算法的研究，并未涉及兩種模式優(yōu)劣的比較。

樞紐點的建設成本是網(wǎng)絡總成本重要組成本部分，且樞紐點的容量不可能是沒有限制的，為了適應網(wǎng)絡的整體規(guī)劃，筆者考慮樞紐點的多級容量限制。I.CONTRERAS等[25]考慮了單分配問題的樞紐點容量限制，并且利用拉格朗日松弛放松樞紐點容量限制，使其模型能夠處理較大規(guī)模的算例。I.CORREIA等[26]針對有容量限制的單分配樞紐選址問題，考慮樞紐點的流量均衡，在已有的混合整數(shù)規(guī)劃模型的基礎上，提出了改進的混合整數(shù)規(guī)劃模型，并且驗證改進模型具有更優(yōu)越可計算性，然而文獻并未考慮節(jié)點間流量的不確定性。

軸輻式網(wǎng)絡設計中準確地預測OD流需求是困難的。胡青蜜等[27]針對確定性OD流需求的零擔物流網(wǎng)絡設計方案往往導致網(wǎng)絡資源非均衡利用問題，分析了零擔物流節(jié)點之間OD流不確定性特點與不確定OD流需求的物流網(wǎng)絡設計難點，結(jié)合庫存理論，建立了不確定OD流需求的物流網(wǎng)絡混合整數(shù)規(guī)劃模型。S.A.ALUMUR等[28]針對選址問題的戰(zhàn)略決策特性，在軸輻式網(wǎng)絡設計的模型基礎上，提出了考慮OD流需求和建設成本不確定性的單分配和多分配的軸輻式網(wǎng)絡設計模型，并驗證模型的可行性。I.CONTRERAS等[29]等研究了具有隨機不確定性需求與運輸成本的無容量限制樞紐位置問題。筆者在以上研究的基礎上，考慮了在不確定OD流需求情況下樞紐點的多級容量限制，通過求解最優(yōu)期望成本得到最優(yōu)的網(wǎng)絡設計，包括樞紐配置和輻點分配，比較單分配與多分配網(wǎng)絡的優(yōu)劣。

2 問題定義

2.1 問題概述

筆者研究的軸輻式網(wǎng)絡是二層軸輻網(wǎng)絡，其中，樞紐點承擔貨流的收集、分配和轉(zhuǎn)運功能，輻點被分配給樞紐點。單分配模式指任一輻點只能被分配給一個樞紐點；多分配模式指任一輻點可以被分配給r(r≥1)個樞紐點。分配模式影響著網(wǎng)絡的運營成本，相對于單分配的網(wǎng)絡來說，多分配的網(wǎng)絡中輻點的貨物需要分批地運送到不同的樞紐點，同樣，貨物在樞紐點需要更多次數(shù)的分揀，這些活動都會增加網(wǎng)絡的運營成本。為了體現(xiàn)不同分配模式間運營成本的差異，筆者定義比例系數(shù)α(α>1)表示多分配模式單位運營成本與單分配模式單位運營成本的比例。

不論如何選擇輻點分配方式，樞紐點容量限制都會影響樞紐點的配置及輻點的分配。在多級樞紐點容量限制的情況下，樞紐點的配置包括樞紐節(jié)點的選擇和樞紐點容量等級的選擇。對同一節(jié)點而言，其建設為樞紐的投入與其所選擇的容量等級有關，因此靈敏的建設成本成為網(wǎng)絡設計模型的重點。

OD流需求的不確定性增加了網(wǎng)絡設計的難度，增加了樞紐節(jié)點及其容量的等級選擇的困難，難以合理地分配輻點。為應對季節(jié)性、市場的波動造成的需求不確定性，考慮多種需求場景并確定相應的概率分布，通過求解多場景下的最優(yōu)期望成本，確定樞紐點的配置和輻點的分配。

基本模型[28]是樞紐無容量限制、完全干線網(wǎng)絡的單分配和多分配軸輻式網(wǎng)絡模型，在此基礎上分別建立樞紐有容量限制的網(wǎng)絡模型。

首先，基本模型([M1]和[M2]，見第3.1節(jié))的目標函數(shù)包括建設成本、集散成本及轉(zhuǎn)運成本3個部分。其中建設成本是某一節(jié)點被選為樞紐點后需要投入的樞紐建設成本，集散成本是指樞紐點與輻點間貨物收集和配送的運輸成本，轉(zhuǎn)運成本是指樞紐點間的轉(zhuǎn)運貨物的運輸成本。

然后在基本模型上增加運營成本以突出單分配與多分配的差異?？紤]樞紐點的多級容量限制更新約束及變量，按照不確定需求的處理方法，改進目標函數(shù)，最終得到樞紐多級容量限制下的單分配與多分配的軸輻式網(wǎng)絡比較問題的擴展模型([M3]和[M4]，見第3.2小節(jié))。

2.2 問題假設和符號定義

筆者所研究的軸輻式網(wǎng)絡包括單分配和多分配兩種模式，其中，干線網(wǎng)絡是全連通網(wǎng)絡，網(wǎng)絡節(jié)點間的距離滿足三角不等式準則，每一個輻點只與樞紐點相連，輻點間無直接聯(lián)系，樞紐點的處理能力有多級容量限制。

2.2.1 集合與索引

N={1,2，…,LN}為節(jié)點集合，由i，j，k和l索引；Q={1,2，…,LQ}為樞紐點容量狀態(tài)集合，由q索引；S={1,2，…,LS}為需求狀態(tài)場景集合，由s索引。

2.2.2 參 數(shù)

2.2.3 變 量

3 模 型

在基本模型上擴展得到的軸輻式網(wǎng)絡設計模型([M3]和[M4])。由于在擴展的過程中存在約束條件等的變化，下面在給出模型的同時也將對其中相應的約束進行闡述。

3.1 基本模型

3.1.1 單分配軸輻式網(wǎng)絡設計的基本模型

[M1]：

minftotal=fsetup+fcd+ftran

(1)

fsetup=∑kfkxkk

(2)

fcd=∑i,kλ·(Oi+Di)Dikxik

(3)

(4)

s.t.?i∈N,∑k∈Nxik=1

(5)

?i,k∈N,xik≤xkk

(6)

(7)

(8)

(9)

?i,k∈N,xik∈{0,1}

(10)

3.1.2 多分配軸輻式網(wǎng)絡設計的基本模型

[M2]：

minftotal=fsetup+fcd+ftran

(11)

式[(2),(4)]

(12)

s.t.?i∈N,∑k∈Nuik=Oi

(13)

(14)

(15)

(16)

?i,k∈N,uik≤xkkOi

(17)

(18)

(19)

?k∈N,xkk∈{0,1}

(20)

3.2 擴展模型

通過變換目標和約束得到[M3]和[M4]，其中樞紐存在多級量限制且考慮了OD貨流需求的不確定性，下面更新某些變量。

3.2.1 樞紐多級容量限制的單分配軸輻式網(wǎng)絡設計

[M3]：

minftotal=fsetup+∑s(fcd+ftran+fope)Ps

(21)

(22)

(23)

(24)

(25)

s.t. 式[(5)～(6),(10)]

(26)

(27)

(28)

(29)

(30)

(31)

3.2.2 樞紐多級容量限制的多分配軸輻式網(wǎng)絡設計

[M4]：

minftotal=fsetup+∑s(fcd+ftran+fope)Ps

(32)

式[(22),(24)]

(33)

(34)

(35)

(36)

(37)

(38)

(39)

(40)

(41)

(42)

(43)

(44)

4 仿真實驗

考慮20個節(jié)點(LN=20)的軸輻式網(wǎng)絡，其中，樞紐點容量限制有3個等級(LQ=3)，需求場景有3種(Ls=3)。為了求解混合整數(shù)規(guī)劃模型，在仿真實驗中采用MATLAB編寫代碼調(diào)用CPlEX求解器進行求解。針對單分配與多分配軸輻式網(wǎng)絡基礎模型([M1]&[M2])分別編寫基礎代碼，然后在基礎代碼基礎上根據(jù)實驗設置及改進模型要求修改得到其他模型代碼，最后應用算例數(shù)據(jù)進行實驗。

4.1 基本算例

對于模型中的參數(shù)，設置λ=1，ω=0.7，ν=1。兩種模式的單位運營成本比例系數(shù)α=1.5。在[M3]和[M4]中節(jié)點選為樞紐時在實驗中多級容量限制的值為[15 000,20 000,25 000]，并且第一容量限制等級的樞紐建設成本由均勻分布α=U[10 000,50 000]生成，則各級成本按照[a,1.25a,1.5a]方式處理。

實驗中節(jié)點的位置坐標由(U[0,120],U[0,120])均勻分布生成。OD流值狀態(tài)場景概率隨機取自區(qū)間[0,1]。其狀態(tài)場景劃分為：場景1為節(jié)點貨流需求量在某區(qū)間大范圍波動，貨流不穩(wěn)定的情形；場景2為節(jié)點貨流需求量在某區(qū)間小范圍波動，貨流較穩(wěn)定的情形；場景3為節(jié)點具有貨流低需求量或貨流高需求量的情形。例如，表1中樞紐點3到樞紐點4的OD流值在場景1下OD流值隨機取自區(qū)間[100,200]，場景2下OD流值隨機取自區(qū)間[120,150]，場景3下OD流值取自區(qū)間[170,200]。

表1 生成需求場景的數(shù)據(jù)表

表1中集合A1表示除節(jié)點4,5,12,18以外的其他任意節(jié)點，例如始發(fā)點為節(jié)點3時，A1={1,2,6,7,8,9,10,11,13,14,15,16,17,19,20}，集合A2，A3同理。

4.2 實驗設置及實驗結(jié)果

為了求解[M3]與[M4]的實驗結(jié)果以及比較二者之間的差異選擇較優(yōu)的分配模式，筆者設置了4個實驗。

4.2.1 實驗1

實驗目的：比較最優(yōu)網(wǎng)絡總成本及其中各部分成本構(gòu)成、網(wǎng)絡設施資源的利用率，探究兩種網(wǎng)絡的特性。

實驗過程：①樞紐點數(shù)目不限制，對[M3]和[M4]進行實驗；②采用4.1小節(jié)生成的數(shù)據(jù)及參數(shù)。

統(tǒng)計實驗結(jié)果得網(wǎng)絡總成本及各部分成本，如圖1。樞紐點配置及實際利用情況，如表2及圖2。

圖1 成本對比Fig.1 Comparison of costs

分配模式樞紐點等級樞紐點容量Cq利用量Ck利用率γ/%分配輻點單分配模式2115000947563.179,19101150001269284.6116,1811115000170211.35—12115000893959.596,7171150001310887.395,8,13,15201150001306887.121,3,4,14多分配模式81150001228481.891,2,3,4,5,9,13,14,15,17,19101150001317787.853,4,6,7,16,1811115000800953.392,3,5,9,13,17,19121150001474898.322,3,4,6,7,9,17,19201150001076571.771,3,4,14,16,19

圖2 最優(yōu)網(wǎng)絡布局Fig.2 Optimum network layout

4.2.2 實驗2

實驗目的：參數(shù)α的敏感性分析。

實驗過程：①樞紐點數(shù)目不限制，對[M3]和[M4]進行實驗；②按照-75%，-50%，-25%，25%，50%，75%調(diào)節(jié)參數(shù)α大小。

實驗結(jié)果如表3。

表3 參數(shù)α的敏感性分析實驗結(jié)果

Table 3 Experiment results of sensitivity analysis of parameterα/%

參數(shù)α變動范圍-75-50-25255075運營成本fope-75-50-25255075集散成本fcd000000轉(zhuǎn)運成本ftran000000建設成本fsetup000000網(wǎng)絡總成本ftotal-3.87-2.58-1.291.292.583.86

4.2.3 實驗3

實驗目的：預先確定樞紐點數(shù)目情況下，比較兩種模式的優(yōu)劣。

實驗過程：①增加約束條件，調(diào)整后的模型，如[M5]與[M6]；②確定樞紐點數(shù)目P=3，4，5，6，7，分別對[M5]和[M6]進行實驗。

[M5]：

minftotal=fsetup+∑s(fcd+ftran+fope)Ps

(45)

s.t. 式(22)～(31)

(46)

[M6]：

minftotal=fsetup+∑s(fcd+ftran+fope)Ps

(47)

s.t. 式[(22),(24),(33)～(44),(46)]

實驗結(jié)果如表4，圖3、圖4。

表4 樞紐配置

注：括號內(nèi)為樞紐等級

圖3 各項成本比較Fig.3 Comparisons of various costs

圖4 樞紐數(shù)目P=3,4,5,6,7的網(wǎng)絡總成本Fig.4 Total network costs with the number of hub P=3, 4,5,6,7

4.2.4 實驗4

實驗目的：在OD流變動的情況下，比較兩種網(wǎng)絡模式的穩(wěn)定性。

實驗過程：①由場景2生成一組新的OD流需求數(shù)據(jù)，并且生成其100%，120%，140%，160%倍的一系列數(shù)據(jù)；②其他參數(shù)不變，對每組進行實驗。

實驗結(jié)果如圖5、圖6，及表7。

圖5 新OD流場景下樞紐的利用率變動Fig.5 Utilization rate changes of hub in new OD flow scenarios

圖6 新OD流場景下的成本變動Fig.6 Costs changes in new OD flow scenarios

需求增加比例ΔγOD/%單分配模式樞紐配置多分配模式樞紐配置02(1),10(1),11(1),12(1),17(1),20(1)8(1),10(1),11(1),12(1),20(1)202(1),8(1),10(2),11(1),12(1),20(1)2(1),10(1),11(1),12(1),17(1),20(1)401(1),2(1),10(2),11(1),12(1),17(2),20(1)1(1),2(1),10(1),11(1),12(1),17(1),20(1)601(1),2(1),8(1),10(3),11(1),12(1),17(1),20(1)1(1),2(1),10(2),11(1),12(1),17(1),20(1)

注：括號內(nèi)為樞紐等級。

4.3 實驗分析

下面對4.2小節(jié)中4個實驗的結(jié)果進行分析：

實驗1中，由圖1中兩種分配模式的各項成本對比可以清楚地看出，建設最優(yōu)的軸輻式網(wǎng)絡時，單分配軸輻式網(wǎng)絡的建設成本、運輸成本明顯高于多分配網(wǎng)絡的相應成本；由表4、表5可知，單分配網(wǎng)絡所需要的樞紐數(shù)量多于多分配網(wǎng)絡，而且由公式樞紐的平均利用率=(∑i樞紐i的利用率)/(樞紐個數(shù))可得，單分配網(wǎng)絡樞紐的平均利用率為65.54%低于多分配網(wǎng)絡樞紐的平均利用率(78.64%)。然而，多分配網(wǎng)絡中樞紐點輻射的輻點個數(shù)遠多于單分配網(wǎng)絡的。

在多分配軸輻式網(wǎng)絡中，輻點分配約束的取消使得集散運輸過程的隱含成本釋放出來，也使得網(wǎng)絡樞紐設施的利用率有所提高，而且樞紐利用率的提高可以減少樞紐點的建設數(shù)目，確保了核心節(jié)點(例如節(jié)點10，其在兩種模式中同時存在且具有較高的利用率)的規(guī)模效應。然而，多分配網(wǎng)絡的缺點就像圖2中情況一樣，不僅增加了運營成本，而且網(wǎng)絡復雜、網(wǎng)絡流混亂、貨物分揀頻繁和調(diào)度困難。

由實驗2可知，在多分配軸輻式網(wǎng)絡中，運營成本占網(wǎng)絡總成本的比例較小。當單位運營成本(α)變動時，網(wǎng)絡總成本只產(chǎn)生輕微的變動，而且樞紐點的配置和輻點的分配并未發(fā)生變化，總成本的變動只與運營成本有關。因此，當運營成本占網(wǎng)絡總成本的比例較小時，α的變動并不會影響輻點的分配和樞紐點的配置。

實驗3中樞紐點數(shù)目的變化并未改變單分配軸輻式網(wǎng)絡的高成本特點。由圖3可知，隨著樞紐點的增加，干線網(wǎng)絡的規(guī)模效應減弱，而支線的集散成本減少，最終使得兩種模式網(wǎng)絡總成本的變化趨勢具有一定的相似性。然而在樞紐點數(shù)目的變化過程中，存在某些“職業(yè)樞紐”的節(jié)點——始終被選擇為樞紐的節(jié)點，例如單分配模式下的節(jié)點10和節(jié)點17、多分配模式下的節(jié)點10，筆者把這種節(jié)點稱為核心節(jié)點。核心節(jié)點不僅是“職業(yè)樞紐”，而且具有較高的利用率。這種高利用率表明節(jié)點具有較高的效益，同樣，表明節(jié)點在網(wǎng)絡中具有較大權重，相對于普通節(jié)點而言，當核心節(jié)點由于管理等原因失效時，正常的網(wǎng)絡流會受到較大的沖擊。因此，在確定樞紐數(shù)目的網(wǎng)絡設計中，核心節(jié)點是軸輻式網(wǎng)絡管理的重點，而且單分配網(wǎng)絡中核心節(jié)點的比重較大。

從成本的角度看，OD流需求的增加會引起網(wǎng)絡總成本的增加，且兩者存在近似線性的變動關系；多分配網(wǎng)絡的總成本依舊低于單分配網(wǎng)絡的總成本，而且多分配網(wǎng)絡總成本的變化趨勢略緩，這與實驗1中分析的多分配網(wǎng)絡特性有關；樞紐點配置能夠?qū)ㄔO成本與轉(zhuǎn)運成本產(chǎn)生相同影響。從樞紐利用率的角度看，由于單分配網(wǎng)絡中存在輻點分配約束，當OD流需求增加時，網(wǎng)絡中樞紐的平均利用率分布較為離散。從樞紐點的配置角度看，OD流需求的增加導致網(wǎng)絡中樞紐點數(shù)目的增加、樞紐等級的提高；需求量的變動過程中，多分配網(wǎng)絡中樞紐配置表現(xiàn)得更穩(wěn)定，其中核心節(jié)點的作用更突出。

綜合以上分析，比較兩種模式軸輻式網(wǎng)絡，多分配網(wǎng)絡的成本更經(jīng)濟，并且運營成本的變動不會影響網(wǎng)絡中樞紐點的配置；多分配網(wǎng)絡中由樞紐點組成的干線網(wǎng)絡相對簡單，樞紐點的平均利用率較高；多分配網(wǎng)絡中樞紐點輻射的輻點數(shù)目過多導致網(wǎng)絡復雜，并且同一OD流的貨物被分批零散地運輸導致貨流調(diào)度的困難；在OD流需求的變動過程中，多分配網(wǎng)絡的穩(wěn)定性更高，而且樞紐的利用率波動較少。

5 結(jié) 語

選擇不同的輻點分配方式，二級軸輻式網(wǎng)絡將被分為單分配軸輻式網(wǎng)絡和多分配軸輻式網(wǎng)絡。在考慮樞紐多級容量限制的情況下，筆者對兩種網(wǎng)絡模式進行對比研究，提出了樞紐多級容量限制下單分配與多分配的軸輻式網(wǎng)絡的比較問題。為了處理OD流需求的波動性，采用多個需求場景并確定需求場景的概率分配，通過求解網(wǎng)絡最優(yōu)期望成本以實現(xiàn)網(wǎng)絡設計的要求。首先，選擇單分配和多分配的軸輻式網(wǎng)絡設計基本模型；然后，基于基礎模型，分別建立關于單分配與多分配的OD流需求不確定情況下考慮樞紐多級容量限制的網(wǎng)絡設計模型。為了比較單分配與多分配的優(yōu)劣，筆者進行了以下對比實驗：

1)比較兩種模式選擇最優(yōu)網(wǎng)絡設計時的網(wǎng)絡成本、樞紐配置、樞紐利用率。

2)預先確定樞紐點數(shù)目，求解并比較此時網(wǎng)絡的成本、樞紐配置、樞紐利用率。

3)通過改變OD流需求，比較兩種模式在需求變動中的穩(wěn)定性。

同時，筆者也對多分配網(wǎng)絡設計中的單位運營成本的敏感性進行了討論。通過進行算例仿真實驗，發(fā)現(xiàn)多分配模式的網(wǎng)絡總成本總是比單分配模式網(wǎng)絡的總成本低，并且運營成本占網(wǎng)絡總成本比例較低時單位運營成本的變動對網(wǎng)絡設計沒有影響；多分配網(wǎng)絡中樞紐的利用率較高、建設成本較低有利于網(wǎng)絡的快速建成，而且當OD流需求總量有變化時多分配網(wǎng)絡穩(wěn)定性更高；然而，多分配網(wǎng)絡比單分配網(wǎng)絡更復雜，貨流的調(diào)度對節(jié)點企業(yè)來說是較大的考驗。筆者的模型和分析將拓展到實際零擔物流和航空運輸網(wǎng)絡的優(yōu)化，進行驗證和修正；考慮到模型求解的復雜性，將研制適應大規(guī)模軸輻式網(wǎng)絡中環(huán)保多車型策略分析的算法。

[1] 倪玲霖, 史峰, 方曉平,等. 全連通快遞網(wǎng)絡與軸輻快遞網(wǎng)絡的比較[J].系統(tǒng)工程, 2009, 27(12): 45-50. NI Linglin, SHI Feng, FANG Xiaoping,et al. Comparative study on fully-connected and hub-and-spoke express operational network[J].SystemsEngineering, 2009,27(12):45-50.

[2] 楊忠振, 陸婧. 軸-輻式機場長途巴士線網(wǎng)運營時刻表優(yōu)化設計[J]. 系統(tǒng)工程理論與實踐, 2012, 32(9): 2050-2056. YANG Zhongzhen, LU Jing. Optimization of the timetable for a hub-spoke airport coach network[J].SystemsEngineering-Theory&Practice, 2012, 32(9): 2050-2056.

[3] ADLERA N,SMILOWITZB K. Hub-and-spoke network alliances and mergers: price-location competition in the airline industry[J].TransportationResearchPartB:Methodological, 2007,41(4):394-409.

[4] ABDINNOUR-HELM S. A hybrid heuristic for the uncapacitated hub location problem[J].EuropeanJournalofOperationalResearch,1998,106(2/3):489-499.

[5] ERNST A T, KRISHNAMOORTHY M. Efficient algorithms for the uncapacitated single allocation p-hub median problem[J].LocationScience,1996,4(3):139-154.

[6] ERNST A T,KRISHNAMOORTHY M. Solution algorithms for the capacitated single allocation hub location problem[J].AnnalsofOperationsResearch,1999,86(1):141-159.

[7] LABBé M, YAMAN H. Projecting the flow variables for hub location problems[J].Networks,2004,44(2):84-93.

[8] LABBé M, YAMAN H, GOURDIN E. A branch and cut algorithm for hub location problems with single assignment[J].MathematicalProgramming,2005,102(2):371-405.

[9] PIRKUL H,SCHILLING D A. An efficient procedure for designing single allocation hub and spoke systems[J].ManagementScience,1998,44(12):235-242.

[10] SKORIN-KAPOV D, SKORIN-KAPOV J. On tabu search for the location of interacting hub facilities[J].EuropeanJournalofOperationalResearch,1994,73(3):502-509.

[11] BOLAND N, KRISHNAMOORTHY M, ERNST A T, et al. Preprocessing and cutting for multiple allocation hub location problems[J].EuropeanJournalofOperationalResearch,2004,155(3):638-653.

[12] CONTRERAS I, FERNNDEZ E, MARN A. Tight bounds from a path based formulation for the tree of hub location problem[J].Computers&OperationsResearch,2009,36(12):3117-3127.

[13] CONTRERAS I, CORDEAU J F, LAPORTE G. Benders decomposition for large-scale uncapacitated hub location [J].OperationsResearch,2011,59(6):1477-1490.

[14] EBERY J, KRISHNAMOORTHY M, ERNST A, et al. The capacitated multiple allocation hub location problem: formulations and algorithms[J].EuropeanJournalofOperationalResearch,2000,120(3):614-631.

[15] ERNST A T, KRISHNAMOORTHY M. Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem[J].EuropeanJournalofOperationalResearch,1998,104(1):100-112.

[16] HAMACHER H W, LABBé M,NICKEL S. Adapting polyhedral properties from facility to hub location problems[J].DiscreteAppliedMathematics,2004,145(1):104-116.

[18] MAYER G, WAGNER B. Hub locator: an exact solution method for the multiple allocation hub location problem[J].Computers&OperationsResearch,2002,29(6):715-739.

[19] 倪玲霖, 史峰.多分配快遞軸輻網(wǎng)絡的樞紐選擇與分配優(yōu)化方法[J].系統(tǒng)工程理論與實踐,2012,32(2):441-448. NI Linglin, SHI Feng. Hub location and allocation optimization ofmultiple allocation hub-and-spoke express networks[J].SystemsEngineering-Theory&Practice, 2012, 32(2):441-448.

[20] CAMPBELL J F. Integer programming formulations of discrete hub location problems[J].EuropeanJournalofOperationalResearch,1994,72(2):387-405.

[21] CAMPBELL J F. Hub Location and the p-hub median problem[J].OperationsResearch,1996,44(6):1-13.

[22] ERNST A T, KRISHNAMOORTHY M. An exact solution approach based on shortest-paths for p-hub median problems[J].InformsJournalonComputing,1998,10(2):149-162 .

[23] O'KELLY M E, BRYAN D. Hub network design with single and multiple allocation: A computational study[J].LocationScience,1996,4(3):125-138.

[24] SKORIN-KAPOV D,SKORIN-KAPOV J,O'KELLY M. Tight linear programming relaxations of uncapacitated p-hub median problems[J].EuropeanJournalofOperationalResearch,1996,94(3):582-593.

[25] CONTRERAS I, DAZ J A, FERNNDEZ E. Lagrangean relaxation for the capacitated hub location problem with single assignment[J].ORSpectrum,2009,31(3):483-505.

[26] CORREIA I, NICKEL S,SALDANHA-DA-GAMA F. Hub and spoke network design with single-assignment, capacity decisions and balancing requirements[J].AppliedMathematicalModelling, 2011, 35(10): 4841-4851.

[27] 胡青蜜, 胡志華, 陶莎. 二級軸輻式零擔物流網(wǎng)絡設計的資源均衡利用問題[J].公路交通科技, 2013, 30(4): 124-131. HU Qingmi, HU Zhihua, TAO Sha. Resource balanced usage problem for bi-level hub-and-spoke LTL logistics network design[J].JournalofHighwayandTransportationResearchandDevelopment, 2013, 30(4):124-131.

[28] ALUMUR S A, NICKEL S,SALDANHA-DA-GAMA F. Hub location under uncertainty[J].TransportationResearchPartB:Methodological,2012,46(4):529-543.

[29] CONTRERAS I, JEAN-FRANGOIS, LAPORTE G. Stochastic uncapacitated hub location[J].EuropeanJournalofOperationalResearch,2011,212(3):518-528.

Contradistinction between Spoke Allocation Models in Hub-Spoke Network with Multistage Capacitated

YANG Bin, YIN Yuqi, HU Zhihua

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, P.R.China)

In order to find the practical differences between single allocation and multi-allocation of spokes in hub-spoke network (HSN), the problem of the contradistinction between spokes’ allocation patterns in HSN under multi-stage capacitated was proposed, and the characteristics of two allocation patterns with uncertain demand were studied. Based on the basic model of HSN design, the mixed integer programming models of two kinds of distribution modes were established, which took the operating costs of HSN with multistage capacitated into consideration. According to the predicted demand scenes and their probability distribution, the optimal expected costs of the two network models were solved to design the hub and spoke network. Through setting three HSN design experiments, that is the optimal network design, the pre-specified number of hubs to locate and the changes in total demand, the network cost, the hub configuration and utilization rate of single allocation and multi-allocation models of spokes in the above experiments were contrasted. It is discovered that the multi-allocation network has the advantages of lower network cost, less number of hubs and higher utilization rate of the hub.

traffic and transportation engineering; single allocation; multi-allocation; hub-spoke network; multistage capacitated; demand uncertainty

10.3969/j.issn.1674-0696.2016.03.30

2014-11-20；

2015-05-06

國家自然科學基金面向項目(71471109)；交通運輸部科技項目(2015328810160)；上海市科委科研計劃項目(14DZ2280200, 14511107402)；上海市教委科研創(chuàng)新項目(14YZ100)；上海市曙光計劃項目(13SG48)；上海海事大學研究生創(chuàng)新基金項目(2014ycx013)

楊 斌(1975—)，男，山東招遠人，教授，博士，主要從事綠色物流、知識發(fā)現(xiàn)與智能系統(tǒng)方面的研究。E-mail：binyang@shmtu.edu.cn。

尹宇起(1991—)，男，山東萊陽人，碩士研究生，主要從事綠色物流方面的研究。E-mail：yyq5403@163.com。

U49

A

1674-0696(2016)03-147-08