無(wú)容量限制的混合軸輻式零擔(dān)運(yùn)營(yíng)網(wǎng)絡(luò)優(yōu)化

方曉平，何開先，陳維亞，倪玲霖

(1．中南大學(xué)交通運(yùn)輸工程學(xué)院，湖南長(zhǎng)沙410075;2．浙江財(cái)經(jīng)大學(xué)東方學(xué)院，浙江 杭州310018)

物流企業(yè)的運(yùn)營(yíng)網(wǎng)絡(luò)可分為直通運(yùn)輸網(wǎng)絡(luò)，軸輻式運(yùn)輸網(wǎng)絡(luò)和混合軸輻式運(yùn)輸網(wǎng)絡(luò)。其中，軸輻式網(wǎng)絡(luò)還可以從不同方向進(jìn)行細(xì)分，比如可分為非樞紐節(jié)點(diǎn)單分配網(wǎng)絡(luò)和多分配網(wǎng)絡(luò)，樞紐有能力約束的運(yùn)輸網(wǎng)絡(luò)和樞紐無(wú)容量約束的運(yùn)輸網(wǎng)絡(luò)，有運(yùn)量折扣和無(wú)運(yùn)量折扣的運(yùn)輸網(wǎng)絡(luò)。另外，還有不同折扣方式的運(yùn)輸網(wǎng)絡(luò)，貨物流量可以分割的運(yùn)輸網(wǎng)絡(luò)和不可以分割的運(yùn)輸網(wǎng)絡(luò)，貨物允許混裝的運(yùn)輸網(wǎng)絡(luò)和不允許混裝的運(yùn)輸網(wǎng)絡(luò)。很多學(xué)者針對(duì)不同的細(xì)分類型對(duì)軸輻式網(wǎng)絡(luò)進(jìn)行了優(yōu)化研究。

各種分類的不同組合均能構(gòu)成一個(gè)不同的問(wèn)題。大類來(lái)講，可先從軸輻式網(wǎng)絡(luò)和混合軸輻式網(wǎng)絡(luò)細(xì)分。關(guān)于軸輻式網(wǎng)絡(luò)，李有梅等［1］研究了P－中位問(wèn)題的啟發(fā)式算法，段生虎［2］建立了針對(duì)云南地區(qū)的軸輻式網(wǎng)絡(luò)優(yōu)化模型，張世翔等［3］對(duì)長(zhǎng)三角地區(qū)城市群建立了P－中位選址模型，并進(jìn)行優(yōu)化。還有學(xué)者從其他方面對(duì)軸輻式網(wǎng)絡(luò)問(wèn)題再進(jìn)行細(xì)分，如文獻(xiàn)［4］考慮了機(jī)場(chǎng)定價(jià)環(huán)境費(fèi)用，建立了軸輻式網(wǎng)絡(luò)優(yōu)化模型，李紅啟等［5］研究了允許沿途?？康呢浳镞\(yùn)輸網(wǎng)絡(luò)樞紐選址問(wèn)題，文獻(xiàn)［6］將規(guī)模效應(yīng)加入軸輻式網(wǎng)絡(luò)優(yōu)化模型并求解，文獻(xiàn)［7］也在優(yōu)化模型中加入了規(guī)模效應(yīng)，并使用了非線性的折扣函數(shù)，這使他們的研究更接近實(shí)際。關(guān)于混合軸輻式網(wǎng)絡(luò)的研究相對(duì)較少，具有代表性的有:文獻(xiàn)［8］對(duì)貨物允許混裝的混合軸輻式網(wǎng)絡(luò)進(jìn)行了研究，得出了允許混裝的運(yùn)輸網(wǎng)絡(luò)成本比不允許混裝的更低的結(jié)論，文獻(xiàn)［9］建立了競(jìng)爭(zhēng)下的混合軸輻式網(wǎng)絡(luò)的選擇構(gòu)建優(yōu)化模型，Lin等將規(guī)模效應(yīng)應(yīng)用到航空混合軸輻式網(wǎng)絡(luò)中［10］。此外，還有學(xué)者綜合考慮選址和路線，將兩者一并優(yōu)化，文獻(xiàn)［11］和［12］分別建立了基于軸輻式和混合軸輻式網(wǎng)絡(luò)的選址和線路優(yōu)化模型。Z?pfel等［13］在考慮運(yùn)輸費(fèi)用和分揀費(fèi)用最小化，自由選擇樞紐站的情況下，其中運(yùn)輸車分為配帶1個(gè)或2個(gè)集裝箱2種，建立了混合軸輻式的數(shù)學(xué)模型，并闡述了混合軸輻式網(wǎng)絡(luò)與軸輻式相比可以節(jié)約成本。Barcos等［14］研究在保證一定服務(wù)水平，考慮運(yùn)輸費(fèi)用和中轉(zhuǎn)處理費(fèi)用最小情況下，設(shè)計(jì)了可不經(jīng)過(guò)樞紐，并帶有沿途?？奎c(diǎn)的零擔(dān)貨物運(yùn)營(yíng)網(wǎng)絡(luò)。上述文獻(xiàn)說(shuō)明了混合軸輻式網(wǎng)絡(luò)可以比軸輻式網(wǎng)絡(luò)節(jié)約成本，但均沒(méi)有考慮實(shí)體網(wǎng)絡(luò)的新建與改造問(wèn)題。翁克瑞［15］指出軸輻式網(wǎng)絡(luò)產(chǎn)生了“繞道運(yùn)輸”，而混合軸輻式網(wǎng)絡(luò)可以避免該問(wèn)題，又提出以往軸輻式網(wǎng)絡(luò)模型中的樞紐間折扣函數(shù)不合理。在函數(shù)斷點(diǎn)處，細(xì)微的流量變化導(dǎo)致巨大的成本差異，為此，將折扣函數(shù)改成折扣率函數(shù)的拓展形式，雖然效果得到改善，但總運(yùn)量與總運(yùn)費(fèi)倒掛問(wèn)題依然存在。

本文研究在實(shí)體運(yùn)營(yíng)網(wǎng)絡(luò)的限制下，考慮累進(jìn)式折扣價(jià)格策略的中轉(zhuǎn)樞紐選址和路線優(yōu)化問(wèn)題，旨在針對(duì)確定的OD需求，設(shè)計(jì)混合軸輻式運(yùn)營(yíng)網(wǎng)絡(luò)，即:在軸輻式網(wǎng)絡(luò)的基礎(chǔ)上允許部分非樞紐節(jié)點(diǎn)之間直通運(yùn)輸和只經(jīng)過(guò)1次樞紐中轉(zhuǎn)的運(yùn)輸來(lái)設(shè)計(jì)貨物運(yùn)輸路線。運(yùn)輸路段上的運(yùn)輸單價(jià)采用累進(jìn)式折扣函數(shù)，考慮運(yùn)輸費(fèi)用和樞紐節(jié)點(diǎn)中轉(zhuǎn)費(fèi)用，使得總成本最小。

1 模型的建立

很多物流企業(yè)已建成實(shí)體網(wǎng)絡(luò)，即節(jié)點(diǎn)設(shè)施。在現(xiàn)有的實(shí)體網(wǎng)絡(luò)下，如何選擇最優(yōu)運(yùn)輸路線是運(yùn)營(yíng)決策的核心問(wèn)題?，F(xiàn)針對(duì)國(guó)內(nèi)1家已經(jīng)完成實(shí)體網(wǎng)絡(luò)布局的全國(guó)性零擔(dān)貨物運(yùn)輸服務(wù)商，其具有完善的2級(jí)樞紐。其中1級(jí)樞紐是中轉(zhuǎn)樞紐，2級(jí)樞紐作為最低節(jié)點(diǎn)，不考慮2級(jí)樞紐以下的營(yíng)業(yè)站。模型中的樞紐必須取自現(xiàn)有的1級(jí)樞紐集合中，并作如下假設(shè):(1)任何OD對(duì)之間的流量都是確定的，車型固定，發(fā)車頻率根據(jù)路段流量確定，且滿足服務(wù)商承諾的服務(wù)水平。(2)允許所有的OD流直通運(yùn)輸，單點(diǎn)中轉(zhuǎn)運(yùn)輸和兩點(diǎn)中轉(zhuǎn)運(yùn)輸。(3)OD流可分，即一對(duì)OD點(diǎn)間的貨物可以分開采取不同路線。(4)總的成本費(fèi)用包含運(yùn)輸成本和中轉(zhuǎn)成本。

運(yùn)輸成本是和路段上流量相關(guān)的函數(shù)，有學(xué)者在此只針對(duì)樞紐之間使用固定折扣［16］。為了避免費(fèi)用倒掛現(xiàn)象，本文針對(duì)全路段的分段累進(jìn)式折扣函數(shù)f(·)。中轉(zhuǎn)成本一般分為固定成本和變動(dòng)成本。而文中所要研究的是在有形網(wǎng)絡(luò)布局基礎(chǔ)上，對(duì)運(yùn)營(yíng)網(wǎng)絡(luò)，即無(wú)形網(wǎng)絡(luò)進(jìn)行優(yōu)化。所以樞紐的固定成本就不是本問(wèn)題的決策成本，故中轉(zhuǎn)成本均是與通過(guò)樞紐節(jié)點(diǎn)流量成正比的費(fèi)用g(·)。

所涉及的符號(hào)說(shuō)明如下:

本模型是以運(yùn)輸成本和中轉(zhuǎn)成本之和作為目標(biāo)函數(shù)的。即

累進(jìn)折扣定義如下:

式中:lr為每個(gè)區(qū)間的左端點(diǎn);ur為每個(gè)區(qū)間的右端點(diǎn);αr為對(duì)應(yīng)區(qū)間的折扣值;l1=0，u1=l2，…，uR－1=lR，則平均折扣為

只有變動(dòng)中轉(zhuǎn)費(fèi)用是決策成本，設(shè)其與流量成正比，樞紐節(jié)點(diǎn)k的中轉(zhuǎn)成本定義如下:

式中:λk為樞紐節(jié)點(diǎn)k的單位流量處理費(fèi)用。由此，目標(biāo)函數(shù)可以寫成:

當(dāng)m=k時(shí)，i－k－k－j路線被計(jì)算2次，故而減去1項(xiàng)。約束條件如下:

經(jīng)過(guò)k－m的全部流量，式(6)中的i≠k∪j≠m是為了避免k－m－k－m中路段k－m被計(jì)算2次。

2 模型的求解與結(jié)果

2．1 數(shù)據(jù)來(lái)源及初步處理

數(shù)據(jù)來(lái)自1家在國(guó)內(nèi)全境從事公路零擔(dān)物流服務(wù)的公司2011年全年的營(yíng)業(yè)數(shù)據(jù)，一共128 018條，包括全國(guó)11大運(yùn)營(yíng)區(qū)下屬的49個(gè)專線(含每條專線下屬的收發(fā)站點(diǎn))之間的OD貨物流。另外，假設(shè)每輛運(yùn)輸車載質(zhì)量平均為28 t。數(shù)據(jù)初步處理時(shí)，因計(jì)算條件限制，選取該公司18個(gè)城市，得出這18個(gè)城市之間的OD矩陣(如表1所示)。

表1 需求量OD矩陣Table 1 OD matrix of demand kg

續(xù)表1

2．2 計(jì)算結(jié)果

該數(shù)學(xué)模型是1個(gè)線性規(guī)劃模型。本文直接使用lingo11．0軟件在型號(hào)為AMD Athlon(tm)64*2 Dual－Core Processor TK－53的CPU環(huán)境下求解。

本算例中的18個(gè)節(jié)點(diǎn)，除了5個(gè)樞紐站屬于1級(jí)節(jié)點(diǎn)外，其他均為2級(jí)節(jié)點(diǎn)，如表2所示。

表2 網(wǎng)絡(luò)節(jié)點(diǎn)構(gòu)成Table 2 Hubs and nodes

Lingo軟件求解此類混合整數(shù)規(guī)劃的算法是指數(shù)算法，也就是計(jì)算時(shí)間隨著樞紐數(shù)量或節(jié)點(diǎn)數(shù)量的增加而急劇增加。模型中不同樞紐數(shù)的計(jì)算結(jié)果與計(jì)算時(shí)間比較如表3所示。

比較含有5個(gè)節(jié)點(diǎn)的軸輻式網(wǎng)絡(luò)和混合軸輻式網(wǎng)絡(luò)，目標(biāo)總費(fèi)用分別為8 686 950元和7 994 138元，總派車次數(shù)分別為145 974次和123 601?；旌陷S輻式網(wǎng)絡(luò)比軸輻式網(wǎng)絡(luò)節(jié)約了8．0%的費(fèi)用和15．3%的派車次數(shù)。模型求得的混合軸輻式網(wǎng)絡(luò)圖如圖1所示。

表3 不同樞紐數(shù)時(shí)的計(jì)算結(jié)果比較Table 3 Comparison on total cost and computing time of different hub set

圖1 混合軸輻式網(wǎng)絡(luò)的線路圖Fig．1 Operational network of mixed hub － and － spoke resulted from sample data

3 結(jié)論

(1)混合軸輻式模型較單純軸輻式模型可以節(jié)省費(fèi)用，并減少派車次數(shù)。

(2)累進(jìn)折扣費(fèi)率的運(yùn)用可避免簡(jiǎn)單折扣點(diǎn)附近運(yùn)量與運(yùn)價(jià)倒掛現(xiàn)象。

(3)隨著樞紐數(shù)量的增加，計(jì)算時(shí)間呈指數(shù)增長(zhǎng)。

(4)模型對(duì)于網(wǎng)絡(luò)內(nèi)的樞紐數(shù)量與OD結(jié)構(gòu)的變化的適應(yīng)性，使得該模型可以支持企業(yè)的日常運(yùn)營(yíng)決策。

［1］李有梅，陳曄．一種新的求解約束P－中位問(wèn)題的啟發(fā)式算法［J］．計(jì)算機(jī)工程，2005，31(19):162－164．LI Youmei，CHEN Ye．A new heuristic algorithm for capacitated pmedian problem［J］．Computer Engineering，2005，31(19):162 －164．

［2］段生虎．云南樞紐輻射式航空網(wǎng)絡(luò)的構(gòu)建［J］．航空制造技術(shù)，2005(2):53－55．DUAN Shenghu．Build a hub－and－spoke airline network for Yunnan［J］．Aeronautical Manufacturing Technology，2005(2):53－55．

［3］張世翔，霍佳震．基于軸輻式網(wǎng)絡(luò)模型的長(zhǎng)三角地區(qū)城市群物流配送體系規(guī)劃研究［J］．管理學(xué)報(bào)，2005，2(增Ⅱ):194－199．ZHANG Shixiang，HUO Jiazhen．Research of city group logistics distribution system planning in Changjiang River Delta based on hub － and － spoke network model［J］．Chinese Journal of Management，2005，2(Sup Ⅱ):194 －199．

［4］Nero G，Black J A．Hub－and－spoke networks and the inclusion of environmental costs on airport pricing［J］．Transportation Research Part D:Transport and Environment，1998，3(5):275 － 296．

［5］李紅啟，劉魯．Hub－and－Spoke型運(yùn)輸網(wǎng)絡(luò)改善方法及其應(yīng)用［J］．運(yùn)籌與管理，2007，16(6):63－68．LI Hongqi，LIU Lu．Improvement and application of the hub－and－spoke transportation network［J］．Operations Research and Management Science，2007，16(6):63 －68．

［6］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．

［7］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．

［8］Liu J，Li C L，Chan C Y．Mixed truck delivery systems with both hub － and － spoke and direct shipment［J］．Transportation Research Part E:Logistics and Transportation Review，2003，39(4):325 －339．

［9］Adler N．Hub－spoke network choice under competition with an application to Western Europe［J］．Transportation Science，2005，39(1):58 －72．

［10］Lin C C，Lin Y J，Lin D Y．The economic effects of center－to－center directs on hub－and－spoke networks for air express common carriers［J］．Journal of Air Transport Management，2003，9(4):255 －265．

［11］Aykin T．The hub location and routing problem［J］．European Journal of Operational Research，1995，83(1):200－219．

［12］Melkote S，Daskin M S．An integrated model of facility location and transportation network design［J］．Transportation Research Part A:Policy and Practice，2001，35(6):515－538．

［13］Z?pfel G，Wasner M．Planning and optimization of hub－and－spoke transportation networks of cooperative third － party logistics providers［J］．International Journal of Production Economics，2002，78(2):207 －220．

［14］Barcos L，Rodríguez V M，álvarez M J，et al．Routing design for less－than－truckload motor carriers using ant colony techniques［J］．Workings Paper．Business Economics，2004 －14，2004．

［15］翁克瑞．軸輻式物流網(wǎng)絡(luò)設(shè)計(jì)的選址與路線優(yōu)化研究［D］．武漢:華中科技大學(xué)，2007．WENG Kerui．Research on location and routing optimization for hub－and－spoke logistics network design［D］．Wuhan:Huazhong University of Science and Technology，2007．

［16］張得志，李雙艷．無(wú)容量約束單分配軸－輻式物流網(wǎng)絡(luò)設(shè)計(jì)［J］．鐵道科學(xué)與工程學(xué)報(bào)，2011，8(5):96－100．ZHANG Dezhi，LI Shuangyan．Research on an optimization model for logistics nodes dynamic location and its solution algorithm［J］．Journal of Railway Science and Engineering，2010，8(5):96 －100．