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

胡志華，王雅琪

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

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

?

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

胡志華1，2，王雅琪1

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

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

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

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

0引言

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

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

1分段線性化模型

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

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

(1)

(2)

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

(3)

(4)

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

(5)

(6)

(7)

(8)

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

2問題定義

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

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

2.2符號定義

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

(1) 集合與索引

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

(2) 參數(shù)

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

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

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

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

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

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

(3) 決策變量

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

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

3模型

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

3.1基本模型

在基本模型[M1]中，總成本分為4部分：建設(shè)成本，樞紐點的設(shè)施建設(shè)及設(shè)備購買等成本；收集成本，由非樞紐點運往樞紐點的貨物流量所產(chǎn)生的物流成本；配送成本，由樞紐點運往非樞紐點的貨物流量所產(chǎn)生的物流成本；樞紐點間的轉(zhuǎ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擴展模型

在[M1]的基礎(chǔ)上，考慮表示干線運輸成本折扣系數(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)運成本則修訂為關(guān)于α的非線性函數(shù)；(21)式體現(xiàn)運輸規(guī)模經(jīng)濟效應(yīng)；新約束(22)式是干線流量約束等式；(23)式表示SOS2變量的和為1；(24)式表示干線運量可由給定間斷點橫坐標(biāo)以SOS2的組合形式表示；(25)式表示干線單位距離運價可由給定間斷點縱坐標(biāo)以SOS2的組合形式表示.從而通過分段線性處理把非線性的轉(zhuǎn)運成本函數(shù)轉(zhuǎn)化為線性函數(shù).

4實驗部分

4.1算例

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

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

表1　節(jié)點的樞紐建設(shè)成本　萬元

4.2實驗步驟與實驗結(jié)果

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

表2　實驗步驟

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

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

表5　規(guī)模經(jīng)濟效應(yīng)不同時的各項成本對比　萬元

表6　樞紐點數(shù)目不同時的各項成本　萬元

表7　[M1]與[M2]選取樞紐點比較

圖2　不同樞紐點數(shù)目下的各項成本

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

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

5結(jié)論

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

[參考文獻]

[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ò)模型的長三角地區(qū)城市群物流配送體系規(guī)劃研究[J]. 管理學(xué)報，2005，2(2)：194-199.

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

[18]倪玲霖，史峰. 多分配快遞軸輻網(wǎng)絡(luò)的樞紐選址與分配優(yōu)化方法[J]. 系統(tǒng)工程理論與實踐，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

[中圖分類號]U 491.1[學(xué)科代碼]580·2099

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

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

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

[收稿日期]2014-10-16

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

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