基于非線性規模經濟效應的軸輻式網絡樞紐選址研究

胡志華，王雅琪

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

2.同濟大學經濟與管理學院，上海 200331)

?

基于非線性規模經濟效應的軸輻式網絡樞紐選址研究

胡志華1，2，王雅琪1

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

2.同濟大學經濟與管理學院，上海 200331)

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

[關鍵詞]軸輻式網絡；規模經濟效應；樞紐選址問題；干線運輸

0引言

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

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

1分段線性化模型

在軸輻式網絡單分配模型[M1]的基礎上，建立了基于可變規模經濟效應的非線性規劃模型[M2].在模型[M2]中，將樞紐間非線性轉運成本函數進行分段線性化，從而將非線性規劃模型轉化為混合整數線性規劃模型，再進行求解.

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

(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)，有序集的元素取非零值，但必須是相鄰的.大多數混合整數線性規劃(MILP)求解器能夠自動處理類型1和2的特殊有序集.本文將折扣系數α定義為SOS2變量，利用此方法將非線性的轉運成本函數轉化為線性成本函數.

2問題定義

2.1問題描述與假設

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

2.2符號定義

相關參數和變量定義如下：

(1) 集合與索引

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

(2) 參數

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

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

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

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

(e) Wij為從節點i到j的流量；

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

(3) 決策變量

(a)yikl為從節點i出發，經過樞紐k和l的流量；

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

3模型

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

3.1基本模型

在基本模型[M1]中，總成本分為4部分：建設成本，樞紐點的設施建設及設備購買等成本；收集成本，由非樞紐點運往樞紐點的貨物流量所產生的物流成本；配送成本，由樞紐點運往非樞紐點的貨物流量所產生的物流成本；樞紐點間的轉運成本，在樞紐點間進行的貨物運輸所產生的物流成本.

[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]的基礎上，考慮表示干線運輸成本折扣系數的非線性函數的線性化，得到[M2].

(20)

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

(21)

s.t.

約束((14)—(19))

(22)

(23)

(24)

(25)

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

4實驗部分

4.1算例

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

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

表1　節點的樞紐建設成本　萬元

4.2實驗步驟與實驗結果

具體的實驗步驟和模型調整與分析見表2，相應的結果見表3—7以及圖2.

表2　實驗步驟

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

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

表5　規模經濟效應不同時的各項成本對比　萬元

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

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

圖2　不同樞紐點數目下的各項成本

從表7可以看出，采用固定的規模經濟效應常數和采用非線性的規模經濟效應的樞紐序列有一定差別.因此，當按照基本模型采用固定折扣系數來設計軸輻式網絡是不合理的.

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

5結論

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

[參考文獻]

[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]張世翔，霍佳震. 基于軸輻式網絡模型的長三角地區城市群物流配送體系規劃研究[J]. 管理學報，2005，2(2)：194-199.

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

[18]倪玲霖，史峰. 多分配快遞軸輻網絡的樞紐選址與分配優化方法[J]. 系統工程理論與實踐，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.

(責任編輯：石紹慶)

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[學科代碼]580·2099

[文獻標志碼]A

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

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

[收稿日期]2014-10-16

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

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