基于非線性規(guī)模經(jīng)濟(jì)效應(yīng)的軸輻式網(wǎng)絡(luò)樞紐選址研究

胡志華，王雅琪

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

2.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200331)

?

基于非線性規(guī)模經(jīng)濟(jì)效應(yīng)的軸輻式網(wǎng)絡(luò)樞紐選址研究

胡志華1，2，王雅琪1

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

2.同濟(jì)大學(xué)經(jīng)濟(jì)與管理學(xué)院，上海 200331)

[摘要]在軸輻式網(wǎng)絡(luò)單分配模型的基礎(chǔ)上，改變傳統(tǒng)將規(guī)模經(jīng)濟(jì)效應(yīng)處理為折扣系數(shù)常量的方法，建立了基于可變規(guī)模經(jīng)濟(jì)效應(yīng)的非線性規(guī)劃模型.將以流量為自變量的樞紐間非線性轉(zhuǎn)運(yùn)成本函數(shù)進(jìn)行分段線性化，從而將其轉(zhuǎn)化為混合整數(shù)線性規(guī)劃模型，應(yīng)用Gurobi進(jìn)行求解.通過(guò)算例討論了單調(diào)可變的規(guī)模經(jīng)濟(jì)效應(yīng)對(duì)樞紐點(diǎn)選擇的影響，研究了在p-Hub問(wèn)題中p的變化對(duì)樞紐網(wǎng)絡(luò)的影響.結(jié)果表明，建立的模型能夠拓展于處理任意非線性規(guī)模效應(yīng)關(guān)系.

[關(guān)鍵詞]軸輻式網(wǎng)絡(luò)；規(guī)模經(jīng)濟(jì)效應(yīng)；樞紐選址問(wèn)題；干線運(yùn)輸

0引言

軸輻式網(wǎng)絡(luò)是指OD (Origin to Destination)流一般先從起始點(diǎn)匯集于一個(gè)樞紐，然后轉(zhuǎn)運(yùn)到另一個(gè)樞紐，再配送到終點(diǎn).軸輻式網(wǎng)絡(luò)能夠充分發(fā)揮物流網(wǎng)絡(luò)貨物運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效應(yīng)，優(yōu)化物流成本.對(duì)于樞紐之間的干線運(yùn)輸，貨物集中后運(yùn)量大，通過(guò)優(yōu)化運(yùn)輸工具和運(yùn)輸方式以提高運(yùn)輸滿(mǎn)載率，從而使得樞紐之間的干線運(yùn)輸具有規(guī)模經(jīng)濟(jì)效應(yīng)，使單位運(yùn)輸成本降低.人們對(duì)軸輻式網(wǎng)絡(luò)進(jìn)行了大量的研究，考慮到干線運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效應(yīng)，Abdinnour-Helm引入運(yùn)輸折扣系數(shù)，即在樞紐點(diǎn)之間的干線運(yùn)輸上定義運(yùn)輸折扣系數(shù)α(0≤α≤1)，表示在樞紐間干線貨流所產(chǎn)生的規(guī)模效益相對(duì)于輻節(jié)點(diǎn)與樞紐之間運(yùn)輸成本的折扣，以此揭示干線規(guī)模經(jīng)濟(jì)效應(yīng)對(duì)軸輻式網(wǎng)絡(luò)模型的影響.[1-18]

在規(guī)模經(jīng)濟(jì)效應(yīng)可變的條件下，對(duì)以總成本最低為目標(biāo)的軸幅式網(wǎng)絡(luò)樞紐選址的問(wèn)題進(jìn)行了研究.將目標(biāo)函數(shù)中的轉(zhuǎn)運(yùn)成本剝離出來(lái)，將其轉(zhuǎn)換為關(guān)于可變折扣系數(shù)的非線性函數(shù)，并進(jìn)一步通過(guò)分段線性化使之轉(zhuǎn)化為分段線性函數(shù)進(jìn)行計(jì)算.在引入折扣系數(shù)的基礎(chǔ)上，通過(guò)考慮非線性的可變規(guī)模經(jīng)濟(jì)效應(yīng)反映軸輻式網(wǎng)絡(luò)干線規(guī)模運(yùn)輸問(wèn)題，研究非線性規(guī)模效應(yīng)對(duì)軸輻式網(wǎng)絡(luò)設(shè)計(jì)的影響，為軸輻式網(wǎng)絡(luò)設(shè)計(jì)提供參考.

1分段線性化模型

在軸輻式網(wǎng)絡(luò)單分配模型[M1]的基礎(chǔ)上，建立了基于可變規(guī)模經(jīng)濟(jì)效應(yīng)的非線性規(guī)劃模型[M2].在模型[M2]中，將樞紐間非線性轉(zhuǎn)運(yùn)成本函數(shù)進(jìn)行分段線性化，從而將非線性規(guī)劃模型轉(zhuǎn)化為混合整數(shù)線性規(guī)劃模型，再進(jìn)行求解.

圖1　一個(gè)單變量函數(shù)的分段線性近似

(1)

(2)

求出.采用斜率(F(Xi+1)-F(Xi))/(Xi+1-Xi)描述時(shí)，得到

(3)

(4)

αi≤hi-1+hi，?i=1，…，n；

(5)

(6)

(7)

(8)

(4)—(8)式可以簡(jiǎn)化特殊有序集約束.定義一組變量成為特殊有序集k(SOSk)，有序集的元素取非零值，但必須是相鄰的.大多數(shù)混合整數(shù)線性規(guī)劃(MILP)求解器能夠自動(dòng)處理類(lèi)型1和2的特殊有序集.本文將折扣系數(shù)α定義為SOS2變量，利用此方法將非線性的轉(zhuǎn)運(yùn)成本函數(shù)轉(zhuǎn)化為線性成本函數(shù).

2問(wèn)題定義

2.1問(wèn)題描述與假設(shè)

本文考慮了單分配軸輻式網(wǎng)絡(luò)樞紐選址及非樞紐分配問(wèn)題.單分配軸輻式網(wǎng)絡(luò)要求每條OD流必須經(jīng)過(guò)1個(gè)或2個(gè)樞紐點(diǎn)，進(jìn)而使樞紐之間貨物流量增加，這是規(guī)模經(jīng)濟(jì)效應(yīng)的基礎(chǔ).在研究軸輻式網(wǎng)絡(luò)時(shí)，通常會(huì)假設(shè)干線運(yùn)輸具有規(guī)模經(jīng)濟(jì)效應(yīng).能否取得規(guī)模經(jīng)濟(jì)效應(yīng)以及能夠取得多少規(guī)模經(jīng)濟(jì)效應(yīng)是軸輻式網(wǎng)絡(luò)設(shè)計(jì)的重點(diǎn)，如果建成網(wǎng)絡(luò)后，發(fā)現(xiàn)規(guī)模經(jīng)濟(jì)效應(yīng)較低，勢(shì)必會(huì)造成浪費(fèi).本文考慮的規(guī)模經(jīng)濟(jì)效應(yīng)體現(xiàn)在干線運(yùn)輸?shù)恼劭巯禂?shù)上，隨著干線貨流的變化，規(guī)模經(jīng)濟(jì)效應(yīng)發(fā)生變化，因此折扣系數(shù)也發(fā)生變化.為了研究規(guī)模經(jīng)濟(jì)效應(yīng)的變化對(duì)軸幅式網(wǎng)絡(luò)樞紐選址的影響，通過(guò)設(shè)置規(guī)模效應(yīng)函數(shù)的離散斷點(diǎn)，引入SOS2變量，將由折扣系數(shù)變化造成的非線性函數(shù)轉(zhuǎn)化為線性函數(shù).在此基礎(chǔ)上研究可變規(guī)模經(jīng)濟(jì)效應(yīng)對(duì)軸幅式網(wǎng)絡(luò)的影響，為了凸顯運(yùn)量對(duì)折扣系數(shù)的影響，不考慮運(yùn)輸距離對(duì)折扣系數(shù)的影響.首先，考慮固定折扣系數(shù)，建立軸輻式網(wǎng)絡(luò)樞紐選擇的基本模型.然后，將折扣系數(shù)設(shè)定為關(guān)于貨流的函數(shù)，此時(shí)軸輻式網(wǎng)絡(luò)樞紐間干線運(yùn)輸?shù)囊?guī)模經(jīng)濟(jì)效應(yīng)為運(yùn)量的非線性函數(shù)，對(duì)基本模型進(jìn)行擴(kuò)展.將基本模型與擴(kuò)展模型進(jìn)行對(duì)比，分析對(duì)最優(yōu)樞紐個(gè)數(shù)popt等的影響.將p值由n變?yōu)閚+1時(shí)樞紐點(diǎn)集合中新加入(相互替換)的節(jié)點(diǎn)定義為樞紐選入點(diǎn)Hp(p=n+1).通過(guò)求解p值下的模型，得到一個(gè)樞紐選入序列，通過(guò)樞紐選入序列的變化，說(shuō)明某一或同一節(jié)點(diǎn)在不同的規(guī)模經(jīng)濟(jì)衡量模式下呈現(xiàn)的成本節(jié)約貢獻(xiàn)程度.

2.2符號(hào)定義

相關(guān)參數(shù)和變量定義如下：

(1) 集合與索引

(b) S={1，…，LS}為間斷點(diǎn)集合，即S索引.

(2) 參數(shù)

(a) Fk為在k點(diǎn)建立樞紐的固定成本；

(b) Dij為從節(jié)點(diǎn)i到j(luò)的距離，且認(rèn)為距離滿(mǎn)足三角不等式；

(c) χ為單位距離內(nèi)單位流量的收集成本；

(d) δ為單位距離內(nèi)單位流量的配送成本；

(e) Wij為從節(jié)點(diǎn)i到j(luò)的流量；

(h)Xs為間斷點(diǎn)s的橫坐標(biāo)；

(3) 決策變量

(a)yikl為從節(jié)點(diǎn)i出發(fā)，經(jīng)過(guò)樞紐k和l的流量；

(c)ykl為經(jīng)過(guò)樞紐k和l的流量；

3模型

在以下模型中，αkls是SOS2變量，其向量分量中至多有2個(gè)分量不為零，且必須相鄰.

3.1基本模型

在基本模型[M1]中，總成本分為4部分：建設(shè)成本，樞紐點(diǎn)的設(shè)施建設(shè)及設(shè)備購(gòu)買(mǎi)等成本；收集成本，由非樞紐點(diǎn)運(yùn)往樞紐點(diǎn)的貨物流量所產(chǎn)生的物流成本；配送成本，由樞紐點(diǎn)運(yùn)往非樞紐點(diǎn)的貨物流量所產(chǎn)生的物流成本；樞紐點(diǎn)間的轉(zhuǎn)運(yùn)成本，在樞紐點(diǎn)間進(jìn)行的貨物運(yùn)輸所產(chǎn)生的物流成本.

[M1]Minimizef1=fsetup+fcol+fdist+fhh；

(9)

(10)

(11)

(12)

(13)

s.t.

(14)

xik≤xkk，?i，k∈N；

(15)

(16)

(17)

(18)

yikl≥0，?i，k，l∈N.

(19)

3.2擴(kuò)展模型

在[M1]的基礎(chǔ)上，考慮表示干線運(yùn)輸成本折扣系數(shù)的非線性函數(shù)的線性化，得到[M2].

(20)

where約束((10)—(12))

(21)

s.t.

約束((14)—(19))

(22)

(23)

(24)

(25)

其中：目標(biāo)函數(shù)(20)式包括[M1]的約束(10)—(12)，即建設(shè)成本、收集成本和配送成本，而在[M1]中的樞紐間的轉(zhuǎn)運(yùn)成本則修訂為關(guān)于α的非線性函數(shù)；(21)式體現(xiàn)運(yùn)輸規(guī)模經(jīng)濟(jì)效應(yīng)；新約束(22)式是干線流量約束等式；(23)式表示SOS2變量的和為1；(24)式表示干線運(yùn)量可由給定間斷點(diǎn)橫坐標(biāo)以SOS2的組合形式表示；(25)式表示干線單位距離運(yùn)價(jià)可由給定間斷點(diǎn)縱坐標(biāo)以SOS2的組合形式表示.從而通過(guò)分段線性處理把非線性的轉(zhuǎn)運(yùn)成本函數(shù)轉(zhuǎn)化為線性函數(shù).

4實(shí)驗(yàn)部分

4.1算例

下面算例是應(yīng)用p-hub問(wèn)題CAB數(shù)據(jù)集[19].CAB數(shù)據(jù)集包括25個(gè)節(jié)點(diǎn)，記為N={1，2，…，25}.設(shè)置p的初值為3.通過(guò)改變p值，可以確定最優(yōu)樞紐數(shù)popt.

已知節(jié)點(diǎn)之間的貨流量Wij、距離Dij(i，j∈N)，假定Dij=Dji，利用Gurobi(www.gurobi.com)求解模型.設(shè)非樞紐點(diǎn)與樞紐間的單位距離單位運(yùn)量的運(yùn)輸成本為1，即收集與分配成本均為1.而樞紐的固定成本采用表1設(shè)置.

表1　節(jié)點(diǎn)的樞紐建設(shè)成本　萬(wàn)元

4.2實(shí)驗(yàn)步驟與實(shí)驗(yàn)結(jié)果

具體的實(shí)驗(yàn)步驟和模型調(diào)整與分析見(jiàn)表2，相應(yīng)的結(jié)果見(jiàn)表3—7以及圖2.

表2　實(shí)驗(yàn)步驟

表3　規(guī)模經(jīng)濟(jì)效應(yīng)不變時(shí)(p=3，[M1])和變化時(shí)(p=3，[M2])樞紐選址與非樞紐分配

表4　規(guī)模經(jīng)濟(jì)效應(yīng)不變時(shí)([M1])和變化時(shí)([M2])各項(xiàng)成本　萬(wàn)元

表5　規(guī)模經(jīng)濟(jì)效應(yīng)不同時(shí)的各項(xiàng)成本對(duì)比　萬(wàn)元

表6　樞紐點(diǎn)數(shù)目不同時(shí)的各項(xiàng)成本　萬(wàn)元

表7　[M1]與[M2]選取樞紐點(diǎn)比較

圖2　不同樞紐點(diǎn)數(shù)目下的各項(xiàng)成本

從表7可以看出，采用固定的規(guī)模經(jīng)濟(jì)效應(yīng)常數(shù)和采用非線性的規(guī)模經(jīng)濟(jì)效應(yīng)的樞紐序列有一定差別.因此，當(dāng)按照基本模型采用固定折扣系數(shù)來(lái)設(shè)計(jì)軸輻式網(wǎng)絡(luò)是不合理的.

綜合上述實(shí)驗(yàn)及其分析結(jié)果可知：在樞紐點(diǎn)數(shù)目相同時(shí)，樞紐點(diǎn)選擇以及非樞紐點(diǎn)對(duì)樞紐的分配關(guān)系也存在差異；增加樞紐點(diǎn)數(shù)目會(huì)增加建設(shè)成本、收集成本，而配送成本會(huì)減少，轉(zhuǎn)運(yùn)成本無(wú)明顯變化.

5結(jié)論

軸輻式網(wǎng)絡(luò)干線運(yùn)輸規(guī)模經(jīng)濟(jì)效應(yīng)的實(shí)現(xiàn)可以降低網(wǎng)絡(luò)成本.本文將干線運(yùn)輸規(guī)模效應(yīng)的折扣系數(shù)作為一個(gè)變量來(lái)考慮.隨著貨流量的增加，通過(guò)改變運(yùn)輸工具或運(yùn)輸方式以提高滿(mǎn)載率，規(guī)模經(jīng)濟(jì)效應(yīng)將發(fā)生明顯變化.考慮可變的規(guī)模經(jīng)濟(jì)效應(yīng)使得轉(zhuǎn)運(yùn)成本變?yōu)榱髁康姆蔷€性函數(shù)，從而建立軸輻式網(wǎng)絡(luò)設(shè)計(jì)的非線性混合整數(shù)規(guī)劃模型.本文通過(guò)分段線性近似法對(duì)非線性函數(shù)設(shè)置分段點(diǎn)，將非線性函數(shù)轉(zhuǎn)化為線性函數(shù).通過(guò)對(duì)模型求解結(jié)果比較發(fā)現(xiàn)，非線性規(guī)模效應(yīng)會(huì)影響樞紐點(diǎn)的選擇.在實(shí)際情況中，運(yùn)價(jià)依賴(lài)于貨流量，貨流量越大運(yùn)價(jià)越低，規(guī)模經(jīng)濟(jì)效應(yīng)越顯著.在這種情況下，采用固定折扣系數(shù)，不能反映運(yùn)量對(duì)成本的動(dòng)態(tài)影響.因此，基于非線性規(guī)模經(jīng)濟(jì)效應(yīng)的軸輻式網(wǎng)絡(luò)模型能夠更好地反映貨流量規(guī)模對(duì)成本的影響.

[參考文獻(xiàn)]

[1]ABDINNOUR-HELM S. A hybrid heuristic for the uncapacitated hub location problem[J]. European Journal of Operational Research，1998，106(2/3)：489-499.

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

[3]JEONG S J，LEE C G，BOOKBINDERC J H. The European freight railway system as a hub-and-spoke network[J]. Transportation Research Part A，2007，41(6)：523-536.

[4]HORNER M W，O’KELLY M E. Embedding economies of scale concepts for hub network design[J]. Journal of Transport Geography，2001，9(4)：255-265.

[5]ABDINNOUR-HELM S，VENKATARAMANAN M A. Solution approaches to hub location problems[J]. Annals of Operations Research，1998，78(1)：31-50.

[6]ALUMUR S A，NICKEL S，SALDANHA-DA-GAMA F. Hub location under uncertainty[J]. Transportation Research Part B Methodological，2012，46(4)：529-543.

[7]O’KELLY M E，BRYAN D L. Hub location with flow economies of scale[J]. Transportation Research Part B Methodological，1998，32(8)：605-616.

[8]O’KELLY M，SKORIN-KAPOV D，SKORIN-KAPOV J. Lower bounds for the hub location problem[J]. Management Science，1995，41(4)：713-721.

[9]CAMPBELL J F，STIEHR G，ERNST A T，et al. Solving hub arc location problems on a cluster of workstations[J]. Parallel Computing，2003，29(5)：555-574.

[10]EBERY J，KRISHNAMOORTHY M，ERNST A，et al. The capacitated multiple allocation hub location problem formulations and algorithms[J]. European Journal of Operational Research，2000，120(3)：614-631.

[11]KRATICA J，STANIMIROVIC Z，TOSIC D，et al. Two genetic algorithms for solving the uncapacitated single allocationp-hub median problem[J]. European Journal of Operational Research，2007，182(1)：15-28.

[12]PAMUK F S，SEPIL C. A solution to the hub center problem via a single-relocation algorithm with tabu search[J]. IIE Transactions (Institute of Industrial Engineers)，2001，33(5)：399-411.

[13]SUNG C S，JIN 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.

[14]CAMPBELL A M，LOWE T J，ZHANG L. Thep-hub center allocation problem[J]. European Journal of Operational Research，2007，176(2)：819-835.

[16]張世翔，霍佳震. 基于軸輻式網(wǎng)絡(luò)模型的長(zhǎng)三角地區(qū)城市群物流配送體系規(guī)劃研究[J]. 管理學(xué)報(bào)，2005，2(2)：194-199.

[17]翁克瑞. 帶固定軸線成本的軸輻式網(wǎng)絡(luò)設(shè)計(jì)問(wèn)題[J]. 運(yùn)籌學(xué)學(xué)報(bào)，2012，16(1)：88-96.

[18]倪玲霖，史峰. 多分配快遞軸輻網(wǎng)絡(luò)的樞紐選址與分配優(yōu)化方法[J]. 系統(tǒng)工程理論與實(shí)踐，2012，32(2)：441-448.

[19]O’KELLY M E. A quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research，1987，32(3)：393-404.

(責(zé)任編輯：石紹慶)

Hub location problem of hub-and-spoke network with non-linear effects of economies of scale

HU Zhi-hua1，2，WANG Ya-qi1

(1.Logistics Research Center，Shanghai Maritime University，Shanghai 201306，China；2.School of Economics and Management，Tongji University，Shanghai 200331，China)

Abstract:So based on a single allocation model of hub-and-spoke network whose effects of economies of scale are treated by constant discount factors，a nonlinear programming model is devised to present the nonlinear effects of economies of scale by the transported volume. The approach based on piecewise linearization on the nonlinear cost function of transported volumes among hub-hub trunks is applied. Therefore，the nonlinear programming model is transferred into a mixed-integer linear programming model，which can be solved by Gurobi. Compared to the method that uses constant discount factors to calculate the hub-hub transportation cost，the proposed model considers variable effects of economies of scale presents practical relations between the transportation costs and transported volumes. By the linearization method，this model can be effectively solved. In the experimental study，the paper analyzed the influences made by variable monotonous effects of economies of scale on hub selection and the influence of the selection of p in p-Hub problems on the design of hub network. The established model can be expanded to deal with any nonlinear effects of economies of scale.

Keywords:hub-and-spoke network；economies of scale；hub location problem；trunk transportation

[中圖分類(lèi)號(hào)]U 491.1[學(xué)科代碼]580·2099

[文獻(xiàn)標(biāo)志碼]A

[作者簡(jiǎn)介]胡志華(1977—)，男，博士，副教授；主要從事港航與物流運(yùn)作優(yōu)化、社會(huì)科學(xué)計(jì)算實(shí)驗(yàn)、計(jì)算智能研究.

[基金項(xiàng)目]國(guó)家自然科學(xué)基金資助項(xiàng)目(71101088，71171129，71390521)；上海市曙光計(jì)劃項(xiàng)目(13SG48)；教育部博士點(diǎn)基金資助項(xiàng)目(20113121120002，20123121110004)；上海市科委項(xiàng)目(11510501900，12510501600，12ZR1412800)；教育部人文社會(huì)科學(xué)研究項(xiàng)目(09YJA630072).

[收稿日期]2014-10-16

[文章編號(hào)]1000-1832(2016)01-0090-07

[DOI]10.16163/j.cnki.22-1123/n.2016.01.019