樞紐多級(jí)容量限制下輻點(diǎn)分配模式的比較

楊 斌，尹宇起，胡志華

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

樞紐多級(jí)容量限制下輻點(diǎn)分配模式的比較

楊 斌，尹宇起，胡志華

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

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

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

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

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

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

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

1 軸輻式網(wǎng)絡(luò)

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

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

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

2 問題定義

2.1 問題概述

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

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

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

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

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

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

2.2 問題假設(shè)和符號(hào)定義

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

2.2.1 集合與索引

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

2.2.2 參 數(shù)

2.2.3 變 量

3 模 型

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

3.1 基本模型

3.1.1 單分配軸輻式網(wǎng)絡(luò)設(shè)計(jì)的基本模型

[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)絡(luò)設(shè)計(jì)的基本模型

[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 擴(kuò)展模型

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

3.2.1 樞紐多級(jí)容量限制的單分配軸輻式網(wǎng)絡(luò)設(shè)計(jì)

[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 樞紐多級(jí)容量限制的多分配軸輻式網(wǎng)絡(luò)設(shè)計(jì)

[M4]：

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

(32)

式[(22),(24)]

(33)

(34)

(35)

(36)

(37)

(38)

(39)

(40)

(41)

(42)

(43)

(44)

4 仿真實(shí)驗(yàn)

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

4.1 基本算例

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

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

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

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

4.2 實(shí)驗(yàn)設(shè)置及實(shí)驗(yàn)結(jié)果

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

4.2.1 實(shí)驗(yàn)1

實(shí)驗(yàn)?zāi)康模罕容^最優(yōu)網(wǎng)絡(luò)總成本及其中各部分成本構(gòu)成、網(wǎng)絡(luò)設(shè)施資源的利用率，探究兩種網(wǎng)絡(luò)的特性。

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

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

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

分配模式樞紐點(diǎn)等級(jí)樞紐點(diǎn)容量Cq利用量Ck利用率γ/%分配輻點(diǎn)單分配模式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)絡(luò)布局Fig.2 Optimum network layout

4.2.2 實(shí)驗(yàn)2

實(shí)驗(yàn)?zāi)康模簠?shù)α的敏感性分析。

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

實(shí)驗(yàn)結(jié)果如表3。

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

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

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

4.2.3 實(shí)驗(yàn)3

實(shí)驗(yàn)?zāi)康模侯A(yù)先確定樞紐點(diǎn)數(shù)目情況下，比較兩種模式的優(yōu)劣。

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

[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)]

實(shí)驗(yàn)結(jié)果如表4，圖3、圖4。

表4 樞紐配置

注：括號(hào)內(nèi)為樞紐等級(jí)

圖3 各項(xiàng)成本比較Fig.3 Comparisons of various costs

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

4.2.4 實(shí)驗(yàn)4

實(shí)驗(yàn)?zāi)康模涸贠D流變動(dòng)的情況下，比較兩種網(wǎng)絡(luò)模式的穩(wěn)定性。

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

實(shí)驗(yàn)結(jié)果如圖5、圖6，及表7。

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

圖6 新OD流場景下的成本變動(dòng)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)

注：括號(hào)內(nèi)為樞紐等級(jí)。

4.3 實(shí)驗(yàn)分析

下面對4.2小節(jié)中4個(gè)實(shí)驗(yàn)的結(jié)果進(jìn)行分析：

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

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

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

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

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

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

5 結(jié) 語

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

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

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

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

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

[1] 倪玲霖, 史峰, 方曉平,等. 全連通快遞網(wǎng)絡(luò)與軸輻快遞網(wǎng)絡(luò)的比較[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] 楊忠振, 陸婧. 軸-輻式機(jī)場長途巴士線網(wǎng)運(yùn)營時(shí)刻表優(yōu)化設(shè)計(jì)[J]. 系統(tǒng)工程理論與實(shí)踐, 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)絡(luò)的樞紐選擇與分配優(yōu)化方法[J].系統(tǒng)工程理論與實(shí)踐,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] 胡青蜜, 胡志華, 陶莎. 二級(jí)軸輻式零擔(dān)物流網(wǎng)絡(luò)設(shè)計(jì)的資源均衡利用問題[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

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

楊 斌(1975—)，男，山東招遠(yuǎn)人，教授，博士，主要從事綠色物流、知識(shí)發(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