王雁鳳， 黃有方

(1.上海海洋大學 經(jīng)濟管理學院， 上海 201306； 2.上海海事大學 物流研究中心， 上海 201306)

?

大規(guī)模零擔物流軸輻式網(wǎng)絡決策優(yōu)化

王雁鳳1,2*， 黃有方2

(1.上海海洋大學 經(jīng)濟管理學院， 上海 201306； 2.上海海事大學 物流研究中心， 上海 201306)

經(jīng)濟的發(fā)展和公路運輸?shù)臅惩?，使零擔物流得到迅猛發(fā)展.本文針對大規(guī)模零擔物流網(wǎng)絡優(yōu)化問題，構建了基于雙層規(guī)劃的大規(guī)模零擔物流軸輻式網(wǎng)絡模型，并基于進化博弈和多目標優(yōu)化思想，設計分層遺傳算法來求解模型，最后以算例進行模型及算法驗證，得出大規(guī)模零擔物流網(wǎng)絡的樞紐選址、流量分配等決策.靈敏度分析表明節(jié)點間流量、單位運輸成本等參數(shù)會對零擔物流網(wǎng)絡產(chǎn)生不同程度的影響，增量優(yōu)化表明當貨流量變化時，對建設成本權重較小的情景，決策者宜優(yōu)先采取改變樞紐點數(shù)量來滿足需求，而權重系數(shù)較大時則應當考慮改變原有樞紐點能級來應對變化.

零擔物流； 軸輻式網(wǎng)絡； 雙層規(guī)劃； 分層遺傳算法； 決策優(yōu)化

近年來，隨著經(jīng)濟的發(fā)展和公路運輸?shù)臅惩ǎ銚锪鞯玫搅搜该桶l(fā)展，全國數(shù)十萬家零擔物流運營商提供的服務網(wǎng)絡遍及全國各地.零擔物流是將多批次貨物合并運輸，以達到提高車輛滿載率、降低空駛率和運輸成本的集約化目標，軸輻式物流網(wǎng)絡是零擔物流網(wǎng)絡的典型形式[1].軸輻式網(wǎng)絡作為一種特殊結構的網(wǎng)絡，最先指航空公司將一個或幾個適當?shù)臋C場作為中樞，中樞周邊較小的城市間不直接通航，而是通過在中樞進行有效中轉(zhuǎn)完成銜接的一種航線網(wǎng)絡布局模式，這種網(wǎng)絡最早由Goldman在1969 年首次提出[2]，之后O'Kelly在1987年研究美國航空網(wǎng)絡時提出了軸輻式網(wǎng)絡的數(shù)學模型[3]，后來該模式得到了諸多學者的廣泛關注和深入研究.與傳統(tǒng)的網(wǎng)絡結構相比，軸輻式網(wǎng)絡簡化了網(wǎng)絡結構，減少了網(wǎng)絡成本，對貨物的集中處理和分類使貨物的運輸實現(xiàn)了規(guī)模經(jīng)濟.目前在全國名列前茅的零擔物流運營商有德邦、天地華宇、新時代等，它們的服務網(wǎng)絡遍及全國各地，擁有如此大規(guī)模貨流量的物流企業(yè)迫切需要構建有效合理的物流網(wǎng)絡來降低總成本、提高車輛滿載率，并保障貨物及時有效到達目的地.

國外學者對軸輻式網(wǎng)絡研究的一個重要視角是關于輻節(jié)點與樞紐點的指派問題，據(jù)此軸輻式網(wǎng)絡問題一般分為單分配和多分配問題.單分配問題是指每個輻節(jié)點指派且僅指派給一個樞紐點，而多分配問題是指每個輻節(jié)點可以指派給多個樞紐點.國外學者分別針對單分配、多分配軸輻式網(wǎng)絡問題進行了研究[4-7]，還有學者同時針對這兩種指派方式進行了研究[8].此外，考慮到是否有容量約束，學者分別針對樞紐點容量以及節(jié)點間流量限制的軸輻式網(wǎng)絡問題進行了研究[9-10].國內(nèi)學者的研究主要集中在軸輻式網(wǎng)絡的應用方面，分別針對公路貨運系統(tǒng)、海運網(wǎng)絡、民用航空等諸多物流領域進行了研究[11-15].然而，上述文獻大多針對較小規(guī)模的軸輻式網(wǎng)絡進行研究，對現(xiàn)實中規(guī)模龐大、布局復雜的大型物流企業(yè)構建軸輻式物流網(wǎng)絡而言略顯不足.

零擔物流軸輻式網(wǎng)絡的構建是一個長期戰(zhàn)略決策過程，其決策結果將對未來發(fā)展產(chǎn)生持久的影響.面對規(guī)模龐大、網(wǎng)點布局復雜的大規(guī)模零擔物流網(wǎng)絡，本文針對問題特征構建了基于雙層規(guī)劃的大規(guī)模零擔物流軸輻式網(wǎng)絡，并設計了分層遺傳算法來解決問題，最后運用算例進行模型算法驗證和靈敏度分析，為零擔物流企業(yè)構建大規(guī)模物流網(wǎng)絡提供有效支持和決策依據(jù).

1 模型構建

1.1問題描述

軸輻式網(wǎng)絡結構包括節(jié)點和連線.節(jié)點通常包括樞紐點和輻節(jié)點(本文指需求點).連線是各節(jié)點之間的連接路線，承載節(jié)點之間的OD流.大部分OD流通過網(wǎng)絡中的一個或多個樞紐點實現(xiàn)集貨和散貨，從而在樞紐點之間形成集中貨流的規(guī)模效應，降低系統(tǒng)的總物流成本.軸輻式網(wǎng)絡規(guī)劃問題的核心任務是確定樞紐點，以及非樞紐點對樞紐點之間的分配關系.

本文研究的是單分配、有容量限制的大規(guī)模零擔物流軸輻式網(wǎng)絡問題，涉及到的成本主要考慮樞紐點的建設成本和節(jié)點之間的運輸成本，而運輸成本又包括需求點到樞紐點的收集成本、樞紐點到需求點的配送成本及樞紐點之間的中轉(zhuǎn)成本.決策者需要綜合考慮上述成本做出決策，從而在滿足需求的情況下使網(wǎng)絡總成本最小.此外，由于本文研究的是大規(guī)模零擔物流網(wǎng)絡優(yōu)化，傳統(tǒng)的計算方法很難在較短時間內(nèi)得到全局最優(yōu)解.因此，本文基于進化博弈和多目標優(yōu)化思想，設計分層遺傳算法來求解問題，并通過算例進行模型算法驗證和分析，得出較為理想的大規(guī)模零擔物流網(wǎng)絡樞紐選址、流量分配等決策.最后通過靈敏度等分析研究參數(shù)變化對軸輻式網(wǎng)絡產(chǎn)生的影響，得出結論和啟示.

1.2參數(shù)和變量定義

1.3數(shù)學模型

綜合考慮零擔物流軸輻式網(wǎng)絡的建設成本、運輸成本(收集成本、中轉(zhuǎn)成本及配送成本)，構建以總成本最小為目標的數(shù)學模型如下：

min f=λf1+θf2,

(1)

(2)

(3)

s.t

(4)

xikxkk,i,k∈N,

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

2 算法設計

近年來，多目標進化算法因具有較優(yōu)的全局搜索能力以及對目標函數(shù)要求不高的優(yōu)勢，逐步被用于雙層規(guī)劃研究中，一些學者分別用多目標進化算法、混合遺傳算法、層次混沌量子遺傳算法解決了雙層規(guī)劃問題[16-18].本文基于進化博弈和多目標優(yōu)化思想，設計分層遺傳算法來求解基于雙層規(guī)劃的大規(guī)模零擔物流軸輻式網(wǎng)絡問題.求解思路是：上層規(guī)劃中零擔物流企業(yè)給出一些備選節(jié)點，下層規(guī)劃的每個需求點依據(jù)自身利益選擇各自運輸成本最小的樞紐點，綜合所有需求點的分配關系和需求量，可求得上層規(guī)劃中需要建設的樞紐點數(shù)量、能級與位置，從而計算出物流企業(yè)構建零擔物流網(wǎng)絡的總成本；物流企業(yè)想要降低總成本，通過調(diào)整備選樞紐點個數(shù)、能級及位置，從而使需求點將貨物送往較遠的但對企業(yè)總體有利的樞紐點，這時建設成本有所下降，運輸成本上升.如此反復迭代運算，不斷調(diào)整網(wǎng)絡節(jié)點和分配關系，直到滿足一定的收斂條件，運算終止.

設計步驟包括：

1) 編碼設計，本文采用分層編碼方式，第一層表示hub選址決策，每條染色體有I個基因位，I代表備選的樞紐點個數(shù)，每個基因位采用0-1編碼，1表示選擇在該點建設樞紐點，0表示不建設；第二層表示樞紐點與需求點(輻節(jié)點)的分配關系，每條染色體有J個基因位，J是需求點的數(shù)量，每個基因位代表需求點對樞紐點的分配關系.以圖1為例說明，一種可能的方案為：選擇在1、3、5備選點建設樞紐點，且需求點1運到其它節(jié)點的貨物需途徑第3個樞紐點中轉(zhuǎn)，需求點2運到其它節(jié)點的貨物需經(jīng)過第1個樞紐點中轉(zhuǎn)，以此類推.

圖1 分層編碼設計Fig.1 Hierarchical coding design

2) 種群數(shù)量為N，設定最大進化代數(shù)、交叉率、變異率，隨機生成一組染色體，構成初始種群F0，并設t=0,Ft=F0.

3)求解下層規(guī)劃模型f2，每個需求點按自身運輸成本最小化原則選擇樞紐點，并將需求點的選擇及需求量等信息反饋到上層模型中.

4)求解上層規(guī)劃目標函數(shù)f1，并把總目標值f作為適應度函數(shù)，對種群Ft進行選擇、交叉、變異、合并等操作得到新種群Pt.其中選擇操作采用輪盤賭方式，變異操作采用隨機變異方式，交叉操作的思路是：對于每一對父代染色體，在每條父代染色體中尋找為1的基因位，將父代染色體融合產(chǎn)生子代，判斷子代染色體中為1的基因位個數(shù)，如大于K，則去掉距離太近的兩個樞紐點中的一個，若小于K，則父代染色體出現(xiàn)錯誤，需重新選擇.

5)對新種群Pt進行快速非劣排序[17]，得到Ft+1.

6)此時，t=t+1，判斷是否滿足終止條件，若不滿足返回到步驟3，若滿足則運算終止，得出結果.

3 算例分析

某零擔物流企業(yè)配送網(wǎng)絡中共有200個需求點，決策者擬從中選擇個別節(jié)點作為樞紐點構建配送中心以滿足子公司(需求點)之間的貨運需求，這就構成了初始的大規(guī)模零擔物流軸輻式網(wǎng)絡.隨機產(chǎn)生200個節(jié)點，各節(jié)點之間的貨運需求量服從0-1的隨機分布.假定每個配送中心均有4個能級，這4個能級的容量分別為：2 000、2 800、3 600、4 800，對應的固定成本分別為：22 000、32 000、40 000、46 000.取單位貨物單位距離的收集成本、中轉(zhuǎn)成本及配送成本分別為3、0.75、2，建設成本與運輸成本的權重均為0.5.之后，隨著外界環(huán)境的變化，節(jié)點間需求量、單位運輸成本等參數(shù)會發(fā)生一定變化，決策者需要考慮這些參數(shù)的影響，并通過調(diào)整原有網(wǎng)絡來滿足需求并降低總成本.

依據(jù)本文構建的軸輻式網(wǎng)絡模型和分層遺傳算法，設置參數(shù)包括：種群為200，進化代數(shù)為300代，交叉率為0.9，變異率為0.02，運用Matlab7.0編程計算求得最優(yōu)解.圖2中(a)～(d)分別表示不同場景下配送中心的選址以及需求點與配送中心之間貨物分配關系情況，其中需求點用空心點表示，所選的配送中心用實心點表示，節(jié)點之間的分配關系用直線表示.當所選配送中心的個數(shù)依次為6、8、10、12時，所選配送中心的位置有所不同，且需求點與配送中心的分配關系也有相應變化，每個配送中心負責周邊幾個需求點貨物的中轉(zhuǎn)，這主要是由需求場景的不確定性和配送中心的容量能力共同決定的.此外，圖3中(a)～(d)表示運用分層遺傳算法計算大規(guī)模零擔物流網(wǎng)絡的運行過程，運行時間短，約1 min，且算法收斂性較好.

在上述初始網(wǎng)絡結構基礎上，考慮實際運營過程中，由于市場的不確定性，貨流量、單位運輸成本等因素會發(fā)生變化，因此決策者需要針對變化作相應調(diào)整.本文設計了如表1所示的3個實驗，分別針對模型中變量對軸輻式網(wǎng)絡的影響以及流量變化時的增量優(yōu)化進行研究.

圖2 不同場景下大規(guī)模零擔物流網(wǎng)絡樞紐選址及流量分配情況Fig.2 Hub location and flow allocation decisions for the large-scale LTL logistics network in different schemes

圖3 運用分層遺傳算法求解大規(guī)模零擔物流網(wǎng)絡運行情況Fig.3 Running status for solving the large-scale LTL logistics network using the hierarchical genetic algorithm

實驗序號場景模型調(diào)整和分析過程1分析流量wij變化對網(wǎng)絡的影響1)保持建設成本的權重λ和運輸成本的權重θ為0．5不變；2)調(diào)節(jié)wij的大小，使wij∈0．2wij，2wij[]；3)實驗結果見表2；4)分析實驗結果．2分析單位運輸成本變化對網(wǎng)絡的影響1)保持建設成本的權重λ和運輸成本的權重θ為0．5不變；2)按照-45%、-35%、-25%、25%、…、25%、35%、45%調(diào)節(jié)單位運輸成本的大??；3)實驗結果見表3；4)分析實驗結果．3分析流量變化時建設成本權重對增量優(yōu)化網(wǎng)絡的影響1)調(diào)節(jié)建設成本權重λ=0．01，0．02，…，0．99，則θ=1-λ；2)對每一對λ、θ，在初始網(wǎng)絡基礎上，將流量按照1．15、1．25、1．35、1．45、1．55、1．65的倍數(shù)增加或減少；3)多次計算并分析實驗結果．

表2 節(jié)點間流量wij變化對零擔物流軸輻式網(wǎng)絡的影響

表3 單位運輸成本變化對零擔物流軸輻式網(wǎng)絡的影響

此外，實驗3設計的零擔物流網(wǎng)絡增量優(yōu)化顯示，當節(jié)點間貨流量發(fā)生變化時，建設成本權重系數(shù)較小情景下的軸輻式網(wǎng)絡優(yōu)化傾向于采用新建或關閉樞紐點數(shù)量策略來滿足需求，原有樞紐點能級幾乎不變，而對于權重系數(shù)較大的情景，網(wǎng)絡增量優(yōu)化則優(yōu)先選擇改變原有樞紐點能級，樞紐點數(shù)量變化不明顯.究其原因，主要是建設成本對總成本的影響較大，賦予建設成本的權重越大，其對總成本的影響就越大.一般而言，改變原有樞紐能級的調(diào)整成本比新建樞紐點的固定成本要小很多，因此，為尋求總成本最低，建設成本權重系數(shù)較大的情景優(yōu)先選擇改變原有樞紐點能級，直到超出這些樞紐點最大容量時，才選擇新建樞紐點.反之，當建設成本權重系數(shù)較小時，其對總成本的影響也較小，運輸成本反而上升成為總成本的重要影響因素，此時僅僅改變原有樞紐點能級可能造成運輸成本及總成本急劇增加，因此該情景下的網(wǎng)絡增量優(yōu)化優(yōu)先選擇新建或關閉樞紐點的決策.

4 結語

現(xiàn)實環(huán)境的多變性和需求的不確定性，使得零擔物流網(wǎng)絡更加復雜多變，零擔物流運營商的服務網(wǎng)絡遍及全國各地，構建合理的物流網(wǎng)絡結構已經(jīng)成為大型零擔物流企業(yè)迫在眉睫的挑戰(zhàn).本文針對大規(guī)模零擔物流網(wǎng)絡優(yōu)化問題，構建了基于雙層規(guī)劃的大規(guī)模零擔物流軸輻式網(wǎng)絡模型，并基于進化博弈和多目標優(yōu)化思想，設計分層遺傳算法來求解模型，最后以算例進行驗證，得出大規(guī)模零擔物流網(wǎng)絡的樞紐選址、流量分配等決策.靈敏度分析表明節(jié)點間流量、單位運輸成本等參數(shù)會對零擔物流網(wǎng)絡產(chǎn)生不同程度的影響；增量優(yōu)化表明當貨流量變化時，對建設成本權重較小的情景，決策者宜優(yōu)先采取改變樞紐點數(shù)量來滿足需求，而權重系數(shù)較大時則應當考慮改變原有樞紐點能級來應對變化.本文深化了對大規(guī)模零擔物流網(wǎng)絡問題的優(yōu)化研究，為決策者解決大規(guī)模零擔物流網(wǎng)絡樞紐選址及流量分配問題提供了依據(jù)和參考，未來可以針對更加符合現(xiàn)實的動態(tài)復雜網(wǎng)絡設計模型和算法，提高文章對現(xiàn)實的指導意義.

[1] 胡青蜜， 胡志華， 陶 莎. 二級軸輻式零擔物流網(wǎng)絡設計的資源均衡利用問題[J]. 公路交通科技，2013, 30(4):124-131.

[2] GOLDMAN A J. Optimal location for centers in a network[J]. Transportation Science, 1969, 3(4): 352-360.

[3] 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.

[4] CAMARGO R S, MIRANDA G. Single allocation hub location problem under congestion: Network owner and user perspectives [J]. Expert Systems with Applications, 2012, 39(3):3385-3391.

[6] SENDER J, CLAUSEN U. Heuristics for solving a capacitated multiple allocation hub location problem with application in German wagonload traffic[J]. Electronic Notes in Discrete Mathematics, 2013(41):13-20.

[7] KRATICA J. An electromagnetism-like metaheuristic for the uncapacitated multiple allocation p- hub median problem[J]. Computers & Industrial Engineering, 2013, 66(4): 1015-1024.

[8] ALUMUR S A, NICKEL S, SALDANHA G F. Hub location under uncertainty[J]. Transportation Research Part B, 2012, 46(4):529-543.

[9] CORREIA I, NICKEL S, SALDANHA G F. Single-assignment hub location problems with multiple capacity levels[J]. Transportation Research Part B, 2010, 44(8) :1047-1066.

[10] ALUMUR S, KARA B Y. Network hub location problems: the state of the art[J]. European Journal of Operational Research, 2008, 190 (1):1-21.

[11] 張 健， 吳耀華， 劉 沛， 等. 公路快速貨運復合軸輻式網(wǎng)絡規(guī)劃分析[J].山東大學學報(工學版)， 2008, 38(5):6-9.

[12] 汪傳旭. 基于軸-輻運輸系統(tǒng)的區(qū)域港口群二級物流運輸網(wǎng)絡優(yōu)化[J]. 系統(tǒng)工程理論與實踐, 2008(9): 152-158.

[13] 楊晗熠． 樞紐確定單連接軸—輻網(wǎng)絡結構在中國民用航空網(wǎng)絡中的應用[J].北京理工大學學報(社會科學版)， 2010, 12(2):27-30.

[14] 計明軍， 陳 哲， 王清斌. 集裝箱船舶支線運輸航線優(yōu)化算法[J].交通運輸工程學報，2011, 11(4): 68-75.

[15] 吳旗韜， 張虹鷗， 葉玉瑤， 等. 基于軸輻網(wǎng)絡模型的中歐集裝箱航線優(yōu)化[J].中山大學學報(自然科學版)，2012, 51(6): 131-138.

[16] 何 波， 孟衛(wèi)東. 考慮顧客選擇行為的逆向物流網(wǎng)絡設計問題研究[J].中國管理科學, 2009, 17(6): 104-108.

[17] 李 硯， 杜 綱， 劉 波. 基于混合遺傳算法的魯棒雙層規(guī)劃求解[J].統(tǒng)計與決策, 2012(19): 44-47.

[18] 李昌兵， 杜茂康， 付德強. 求解雙層規(guī)劃問題的層次混沌量子遺傳算法[J].系統(tǒng)工程學報, 2013, 28(2): 159-166.

Optimization for large-scale LTL logistics hub-and-spoke network

WANG Yanfeng1,2， HUANG Youfang2

(1. School of Economics and Management, Shanghai Ocean University, Shanghai 201306;2.Logistics Research Center, Shanghai Maritime University, Shanghai 201306)

The development of economy and smoothing of highway transportation make the less-than-truckload (LTL) logistics grow rapidly. In this paper, facing the large-scale LTL logistics network optimization problem, an optimization model is constructed based on bi-level programming for large-scale LTL logistics hub-and-spoke network. Based on the evolutionary game theory and multiple objective optimization, a hierarchical genetic algorithm is designed to solve the model. Then a numerical example is employed to validate the model and the algorithm. The hub location and flow allocation decisions for large-scale LTL logistics network are obtained. Sensitivity analysis shows that the flow and unit transportation cost have different influence on LTL logistics network. Incremental optimization suggests that changing hubs is the prior choice in the case of smallconstruction costs weigh, while greater weight requires adjustment on the capacities of hubs.

less-than-truckload logistics; hub-and-spoke network; bi-level programming; hierarchical genetic algorithm; optimization decision

2015-12-07.

教育部博士點基金項目(20123121110004)；上海海事大學研究生創(chuàng)新基金資助項目(2013ycx061)；上海海事大學優(yōu)秀博士學位論文培育項目(2014bxlp002).

1000-1190(2016)04-0530-06

F252.21

A

*E-mail: guiyan_1234@163.com.