基于分支定界法甩掛運輸站場選址研究

王爾媚，馬成林，李慧子，王秋霏，周 沫，張一珠

(東北林業(yè)大學(xué) 工程技術(shù)學(xué)院，哈爾濱 150040)

中國經(jīng)濟的快速發(fā)展和人民物質(zhì)需求的日益增長，為物流行業(yè)提供了廣闊的市場。但是整個物流運輸業(yè)也面臨著前所未有的挑戰(zhàn)，勞動力成本上升、專業(yè)人才匱乏、信息系統(tǒng)的不完善以及低碳物流的興起都給物流企業(yè)帶來了沖擊[1]。在這個機遇與挑戰(zhàn)并存的環(huán)境下，甩掛運輸作為一種節(jié)能減排、低碳高效的運輸方式，在國家的大力倡導(dǎo)下，受到越來越多物流企業(yè)的青睞。

在全國范圍內(nèi)開展甩掛運輸，選址分配是一個重要環(huán)節(jié)，在整個物流系統(tǒng)中起著承上啟下的作用，其目標是促進貨運運輸向組織化、綜合化、合理化和現(xiàn)代化的方向發(fā)展[2]。目前，關(guān)于選址問題的研究大部分考慮的是針對傳統(tǒng)運輸模式下的物流配送中心選址問題進行研究，M.T.Melo等人提出了多期選址模型，用來結(jié)局參數(shù)可以預(yù)測的方式隨時間變化的情況[3]。A.Klose將選址模型由單一產(chǎn)品模型擴展為多產(chǎn)品模型[4]。孫會君，高自友從系統(tǒng)的角度研究了配送設(shè)施的選址規(guī)劃。對于不同的選址模型，傳統(tǒng)的研究方法主要有整數(shù)規(guī)劃法、圖上作業(yè)法、重心法以及仿真方法等，也有許多新的方法例如遺傳算法、模擬退火法以及蟻群算法等等[5]。陳曦、傅明在《GIS環(huán)境下的物流配送中心選址模型與算法研究》一文中采用了遺傳算法對選址問題進行研究。但是目前針對甩掛運輸站場選址的研究很少，本文針對多產(chǎn)品供應(yīng)鏈網(wǎng)絡(luò)對甩掛運輸站場的選址問題進行研究，建立了一個兩階段多產(chǎn)品甩掛站場的選址及用戶分配模型[6-7]，并采用分支定界法[8]借助Matlab對所建立的模型進行求解[9-11]。

1 選址模型的建立

1.1 模型描述

本文選取某汽車物流公司整車運輸網(wǎng)絡(luò)為實例進行分析。已知該公司的整車運輸遵循“兩級分撥發(fā)運”體系。即：各生產(chǎn)基地的成品整車由整車分撥中心(VDC)運至各整車倉儲中心(VSC)，然后交付于授權(quán)經(jīng)銷商或直銷客戶，如因業(yè)務(wù)需要，也會考慮由VDC直接發(fā)運至經(jīng)銷商或直銷客戶，如圖1所示。

針對該公司的實際情況，考慮涉及多階段選址的多產(chǎn)品供應(yīng)鏈網(wǎng)絡(luò)優(yōu)化問題。由于主機廠與VDC距離很近且一一對應(yīng)，故將整車分撥中心視為工廠，將中轉(zhuǎn)庫或直銷商視為用戶，經(jīng)過甩掛站場完成供需環(huán)節(jié)。由于甩掛站場也可能是用戶或者工廠，所以這里包括由工廠直接為用戶供貨的情況。

圖1 某公司整車物流業(yè)務(wù)模式

1.2 模型的基本假設(shè)

模型的基本假設(shè)如下：

(1)由于同一工廠不同品牌的車可以拼裝，所以不考慮品牌因素，認為一個工廠生產(chǎn)的是同一種產(chǎn)品。

(2)甩掛站場選擇租用的形式，認為每個甩掛站場的容量已知且能夠滿足需求。其固定租用費用已知。

(3)工廠對每個用戶均有供貨。每個用戶對各個工廠的產(chǎn)品均有需求。

(4)工廠生產(chǎn)的產(chǎn)能已知，各用戶對不同產(chǎn)品的需求已知。

(5)工廠的生產(chǎn)總量等于用戶的需求總量。即供需平衡。

1.3 模型及其意義

針對上述實例，建立一個基于“工廠—甩掛站場—用戶”兩階段多產(chǎn)品甩掛站場的選址及用戶分配模型。目標函數(shù)是包括運輸成本，甩掛站場的租用成本及產(chǎn)品管理成本在內(nèi)的總成本最低。具體數(shù)學(xué)模型如下：

(1)

S.t.

(2)

(3)

(4)

(5)

i=1,2,……,a,j=1,2,……,b,k=1,2,……,c。

式中：a為工廠的個數(shù)及產(chǎn)品的種數(shù)；b為甩掛站場的個數(shù)；c為用戶的個數(shù)；Wij為工廠i是否為甩掛站場j提供產(chǎn)品i，提供為1，反之為0；Cij為工廠i到甩掛站場j的單位運價，單位：萬元；Xij為工廠i到甩掛站場j的運量，單位：輛；Sjki為甩掛站場j是否為用戶k提供產(chǎn)品i的單位運價，單位：萬元；Yjki為甩掛站場j為用戶k提供產(chǎn)品i的量，單位：輛；Bj為甩掛站場j是否被選中；Ei為甩掛站場j的租賃費用，單位：萬元；Ui為甩掛站場j的單位產(chǎn)品管理費用，單位：萬元；Wi為工廠i生產(chǎn)的產(chǎn)品i的量，單位：輛；Gj為甩掛站場j的容量，單位：輛；Hki為用戶k對產(chǎn)品i的需求量，單位：輛。

2 模型的求解

2.1 分支定界法

分支定界(branch and bound)算法是一種在問題的解空間樹上搜索問題的解的方法，采用廣度優(yōu)先或最小耗費優(yōu)先的方法搜索解空間樹。在分支定界算法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。

利用分支定界算法對問題的解空間樹進行搜索，它的搜索策略是：

(1)產(chǎn)生當前擴展結(jié)點的所有子結(jié)點。

(2)在產(chǎn)生的子結(jié)點中，拋棄那些不可能產(chǎn)生可行解(或最優(yōu)解)的結(jié)點。

(3)將其余的子結(jié)點加入活結(jié)點表。

(4)從活結(jié)點表中選擇下一個活結(jié)點作為新的擴展結(jié)點。

如此循環(huán)，直到找到問題的可行解(最優(yōu)解)或活結(jié)點表為空。

2.2 利用Matlab求解步驟

為了得到上述模型的解，采用分支定界法進行計算并借助Matlab工具箱運行計算過程。在Matlab中對整數(shù)規(guī)劃模型進行編程，調(diào)用Matlab的自嵌函數(shù)Bintprog，通過分支定界法對該模型進行求解。主要步驟如下：

(1)計算工廠到甩掛站場的費用，得到矩陣A。

(2)計算甩掛站場到用戶的費用，得到矩陣B。

(3)甩掛站場的建設(shè)費用設(shè)為矩陣C。

(4)設(shè)置變量Xijk表示工廠i是否通過甩掛站場j給用戶k運送貨物，X∈{0，1}，得到的矩陣記為X。假設(shè)有m個工廠n個用戶，則共有m×n條路徑，每條路徑有l(wèi)個甩掛站場可供選擇，則X為一個m×n×l的矩陣。

(5)設(shè)置變量Yj甩掛站場j是否需要建設(shè)，Yj∈{0，1}，得到的矩陣記為Y。因為甩掛站場j是否建設(shè)決定于有無路徑通過該處，與通過的次數(shù)無關(guān)，故Y為1×l的矩陣。

(6)目標函數(shù)變?yōu)椋簃inZ=AX+BX+CY，由于工廠到用戶的路徑是唯一且連續(xù)的，即工廠—甩掛站場—用戶模式，故A對應(yīng)的X與B對應(yīng)的X為同一矩陣，所以目標函數(shù)可以合并為minZ=(A+B)X+CY。

(7)約束變量公式為：

(7)

(8)

k=1,2,......,b。

(9)

(8)編寫程序代碼，調(diào)用函數(shù)bintprog，利用分支定界法對模型求解。

3 實例分析

3.1 實例數(shù)據(jù)

已知該汽車物流公司的整車物流運作流程圖如圖1所示，在全國范圍內(nèi)有7個工廠，對應(yīng)圖1中的VDC，有37個用戶，對應(yīng)圖1中的VSC及經(jīng)銷商。現(xiàn)欲從11個甩掛站場候選地中選擇合適的地點建立甩掛運輸站場。為了對模型進行求解，需要已知以下數(shù)據(jù)：工廠的生產(chǎn)量及各用戶對工廠的需求量，工廠到甩掛候選站場的單位運價和距離，甩掛候選站場到用戶的單位運價和距離，甩掛候選中心，固定投資費用及建設(shè)容量，分別見表1～表7。

表1 工廠生產(chǎn)各產(chǎn)品的量 輛

表2工廠的供貨量以及各用戶對各工廠的需求量輛

Tab.2 Factory shipments and users’demand of each plant vehicles

工 廠小 計沈 陽南 京上 海煙 臺青 島柳 州儀 征北 京45287706877882340天 津418103666656812224沈 陽8274775011855444042南 京4 6363001 167992483613265815上 海2 3301262811 283143158138201煙 臺2 244203194568601440103134青 島2 244174355566434481103131成 都1 928148391310196282381220重 慶64845124109607015584鄭 州9918925615511015748174武 漢5673915411056635590哈爾濱25074313335461119長 春445123606272721938營 口496230697046312128石家莊9072111271281521524195呼和浩特49289737294942249太 原389386453771021838晉 中38945515779912047西 安490361088359783295咸 陽29421564838691942濟 南2 244180375464448519106151銀 川1751829243540821蘭 州27021584138541543杭 州2 414162526763257284140281

續(xù)表2工廠的供貨量以及各用戶對各工廠的需求量輛

Tab.2 Factory shipments and users’demand of each plant vehicles

工 廠小 計沈 陽南 京上 海煙 臺青 島柳 州儀 征南 昌4943511210648545187長 沙60042117104576413087昆 明5994198114536515870貴 陽21914383620236127福 州5724512014866664878拉薩424777728烏魯木齊38629835953762164合 肥63041159132687132128廣 州1 43497243282130160341180東 莞86063181158787920199南 寧25617404223267929海 口1068191810103011西 寧21517503927261343合 計32 9533 4956 0027 4884 3434 8362 9753 814

表3 工廠到甩掛站場候選集的距離 km

表4 從工廠到甩掛站場候選集的單位運價 元

表5 甩掛站場候選集到用戶的距離 km

表6 甩掛站場候選集到用戶的單位運價 元

表7 甩掛候選站場的固定投資費用及建設(shè)容量

3.2 模型求解

根據(jù)本文2.2所示求解步驟進行求解。其中，m為7，n為37，l為11，故X為一個259×11的矩陣，Y為1×11的矩陣。依模型的求解步驟程序進行求解，得到結(jié)果見表8。其中Ji等于0表示甩掛候選站場i未被選中，Ji等于1表示甩掛候選站場i被選中。

表8 甩掛候選站場求解結(jié)果

最終從11個甩掛候選站場中選擇了8個，作為該公司開展整車甩掛運輸?shù)闹修D(zhuǎn)站場。

4 結(jié)束語

甩掛運輸站場的選址與其他物流中心的選址比較，具有其特殊性。本文將傳統(tǒng)的物流選址理論及方法與甩掛運輸?shù)奶攸c相結(jié)合，在解決甩掛運輸站場選址問題時，以某汽車物流公司整車運輸網(wǎng)絡(luò)為研究原型，考慮了多產(chǎn)品兩階段甩掛運輸?shù)墓?yīng)鏈網(wǎng)絡(luò)結(jié)構(gòu)，建立了以總成本最小為目標的整數(shù)規(guī)劃模型，將甩掛運輸站場的選址與上游供應(yīng)商和下游用戶相互依存，使選址結(jié)果更加合理，降低了甩掛運輸成本，為社會帶來環(huán)境效益的同時也為企業(yè)帶來經(jīng)濟效益。采用分支定界法并借助Matlab工具箱對整數(shù)規(guī)劃模型進行求解，既保證了結(jié)果的合理性，又有效的簡化了運算的復(fù)雜程度。

【參 考 文 獻】

[1]吳 宇，曾傳華，楊 偉.道路運輸組織甩掛運輸策略研究[J].物流工程與管理，2010(8)：83-85.

[2]Andre L,Diane R.Logistics systems design and optimization[M].New York:Springer,2005.

[3]Melo M T,Mallik S,Saldanha-da-Gama F.Dynamic multi-commodity capacitated facility location:A mathematical modeling framework for strategic supply chain planning[J].Computers & Operations Research,2006，33:181-208.

[4]Klose A,Drexl A.Facility location models for distribution system design[J].European Journal of Operations Research,2005，162(1):4-29.

[5]張春民，楊 濤.公路貨運樞紐選址方法的研究[J].交通科技，2006(6)：100-103.

[6]鄭稱德，黃 達.客戶需求驅(qū)動的多層物流網(wǎng)絡(luò)選址規(guī)劃模型與算法[J].系統(tǒng)管理學(xué)報，2009，18(2)：232-236.

[7]孫 焰.建模理論及算法設(shè)計[M].上海：同濟大學(xué)出版社，2004.

[8]胡運權(quán).運籌學(xué)基礎(chǔ)及應(yīng)用[M].北京：高等教育出版社，2008.

[9]Hanselman D,Littlefield B.精通Matlab 7[M].北京：清華大學(xué)出版社，2006.

[10]范德林，龔 靜，于慧伶.基于TRIZ理論汽車供應(yīng)鏈核心企業(yè)的供應(yīng)物流優(yōu)化研究[J].森林工程，2012，28(6)：107-109.

[11]郭志軍.分支定界算法的Matlab實現(xiàn)[J].江西教育學(xué)院學(xué)報，2007(20)：4-7.