郝 爽，董 明

(1.上海交通大學(xué)中美物流研究院，上海200030;2.上海交通大學(xué)安泰經(jīng)濟與管理學(xué)院，上海200240)

近年來隨著我國物流行業(yè)的飛速發(fā)展，各物流企業(yè)加強了在服務(wù)質(zhì)量方面的競爭，紛紛推出了不同形式的限時配送業(yè)務(wù)，即物流企業(yè)對商品的配送完成時間做出承諾，若商品的實際配送時間超過承諾時間，物流企業(yè)將對客戶做出某種形式的賠償.多商品網(wǎng)絡(luò)問題(Multicommodity Network Design Problem，MNDP)作為長期以來制定商品配送路徑的主要依據(jù)及方法，已得到學(xué)術(shù)界的廣泛研究.多商品網(wǎng)絡(luò)問題中需要為多種商品安排路徑，將其從各自的起點運輸至終點，各商品的路徑由網(wǎng)絡(luò)中的弧及節(jié)點組成，其中的弧具有固定成本、單位運輸成本及容量限制.

小規(guī)模的多商品網(wǎng)絡(luò)問題常用分枝定界法[1]，割平面法[2]，Benders 分解法[3]求解.對于較大規(guī)模的實際問題主要采用啟發(fā)式算法求解，Crainic等[4]針對大規(guī)模問題設(shè)計了基于單純形的禁忌搜索算法，Ghamlouche等[5]在其基礎(chǔ)上進一步優(yōu)化了禁忌搜索算法中的鄰域結(jié)構(gòu);Crainic等[6]提出了一種多層次合作并行搜索算法，由多層次算法框架控制各搜索線程間的信息交換;Martín 和 González[7]提出了利用一般的整數(shù)規(guī)劃求解器作為黑箱的局部分枝算法，通過分枝策略確定鄰域結(jié)構(gòu)，使用求解器進行當前解的鄰域搜索;Bai等[8]提出了基于禁忌表的導(dǎo)向局部搜索算法以提高搜索效率，試驗證明其算法的運算時間較一般的禁忌搜索算法縮短了三分之一;Yaghini等[9]提出了基于單純形的模擬退火算法，通過單純形法的轉(zhuǎn)軸操作確定解的鄰域結(jié)構(gòu)，使用對偶單純形法產(chǎn)生鄰域解.

目前的多商品網(wǎng)絡(luò)問題均以物流網(wǎng)絡(luò)的固定成本與商品的運輸成本為優(yōu)化目標，沒有考慮商品配送過程中的時間因素，所得配送路徑會不可避免的產(chǎn)生配送延遲違約成本，已無法滿足限時配送業(yè)務(wù)的要求.因此，本文在以往多商品網(wǎng)絡(luò)問題的研究基礎(chǔ)上分析了造成商品配送延遲的原因，建立了限時配送業(yè)務(wù)中的商品配送路徑選擇模型，并設(shè)計了基于最短路徑的模擬退火算法.

1 商品配送延遲的成因

商品的實際配送時間由在途運輸時間及商品在物流節(jié)點的作業(yè)時間組成，隨著交通設(shè)施的不斷完善及GPS等信息技術(shù)的普及，商品的在途運輸時間已經(jīng)能夠被精確地掌握，商品在物流節(jié)點的作業(yè)時間包括商品的實際作業(yè)時間及作業(yè)等待時間，由于受到物流節(jié)點的處理能力、實際處理貨物量等多方面因素的影響，呈現(xiàn)出較大的波動性及不確定性，特別是節(jié)點作業(yè)能力不足，而商品大量涌入時，商品被迫滯留在物流節(jié)點等待作業(yè)，作業(yè)等待時間大幅增長使得商品配送出現(xiàn)延遲.此類現(xiàn)象時有發(fā)生，例如每逢電商網(wǎng)站促銷，物流企業(yè)因分揀能力不足造成的物流爆倉[10];進出港繁忙時由于港口裝卸能力不足造成的貨船長時間壓港[11].

商品在物流節(jié)點的作業(yè)等待時間同樣得到了國外研究人員的關(guān)注，F(xiàn)ernandez等[12]曾指出北美地區(qū)的貨運列車在貨運站內(nèi)進行檢查、分類、編組等作業(yè)時耗費的總時間占其運營周期時間的77%，F(xiàn)ernandez將商品在物流節(jié)點進行作業(yè)及相應(yīng)產(chǎn)生的作業(yè)等待時間稱為商品在節(jié)點的作業(yè)延遲，并提出了如下延遲函數(shù)以刻畫作業(yè)延遲與節(jié)點作業(yè)能力及節(jié)點實際作業(yè)量之間的關(guān)系:

其中:sj表示單位商品在節(jié)點j的平均作業(yè)延遲，F(xiàn)j為一個技術(shù)參數(shù)，表示單位商品在節(jié)點j的理論作業(yè)時間，cj表示節(jié)點的作業(yè)能力，xj為實際作業(yè)量，α、β為校準參數(shù).

圖1更加直觀的反映了當節(jié)點j的實際作業(yè)量xj逐漸增大時，商品作業(yè)延遲xj·sj的變化趨勢.可見當節(jié)點的實際作業(yè)量較xj小時，商品的作業(yè)延遲約等于其理論上的作業(yè)時間;隨著xj的增加，雖然商品的實際作業(yè)時間保持線性增長，但作業(yè)等待時間逐漸增大，作業(yè)延遲現(xiàn)象愈加明顯，商品在物流節(jié)點進行作業(yè)所耗費的總時間迅速增長，最終導(dǎo)致商品配送出現(xiàn)延遲[13].

圖1 作業(yè)延遲現(xiàn)象

2 限時配送業(yè)務(wù)中的商品配送路徑選擇模型

設(shè)有向圖G=(N，A)表示一個物流網(wǎng)絡(luò)，其中N={i|i=1，2，…，n}表示網(wǎng)絡(luò)中的物流節(jié)點集合，表示網(wǎng)絡(luò)中節(jié)點間的弧的集合，A={(i，j)|i，j∈N，i≠j}表示節(jié)點 i的后向點集，N－i={j∈N|(i，j)∈A}表示節(jié)點 i的前向點集.P={p|p=1，2，…，m}表示需要配送的商品集合，對于任意商品p∈P，用op、dp分別其起點和終點，wp表示其運量，Lp表示其承諾配送時間，Cp為其延遲違約成本，若實際配送時間大于承諾配送時間，配送商需根據(jù)商品運量及延遲時間支付延遲違約成本.對于網(wǎng)絡(luò)中的任意弧，(i，j)∈A，fij、uij、tij分別表示其固定成本、最大容量、運輸時間，cpij表示商品 p 在弧(i，j)上的單位運輸成本.對于任意節(jié)點i∈N，ci表示其作業(yè)能力，si為商品在此節(jié)點作業(yè)時產(chǎn)生的平均作業(yè)延遲.

決策變量包括:yij∈{0，1}，若最終的配送路徑中包括弧(i，j)，則 yij=1，否則;yij=0，xpij∈{0，1}若商品p的配送路徑中包括弧(i，j)，則xpij=1，否則xpij=0.限時配送業(yè)務(wù)中的商品配送路徑選擇模型表述如下:

目標函數(shù)(2)中 Z1= Σ(i，j)∈Afijyij表示固定成本，Zz= Σ(i，j)∈AΣp∈P表示運輸成本，表示商品 p的在途運輸時間，Σi∈N表示商品p在其配送過程中在各個節(jié)點的作業(yè)延遲之和，其實際配送時間可表示為，相應(yīng)的所有商品的配送延遲違約成本 Z3表示為.Σp∈Pmax{0，約束條件(3)為流量守恒約束，約束條件(4)為弧容量約束，約束條件(5)為延遲函數(shù)，對于任意節(jié)點i，其實際作業(yè)量為，約束條件(6)、(7)為變量約束.

3 基于最短路徑的模擬退火算法

具有固定成本的多商品網(wǎng)絡(luò)問題是NP難問題，本文建立的限時配送業(yè)務(wù)中商品路徑選擇模型在其基礎(chǔ)上進一步考慮了配送延遲違約成本，仍然屬于NP難問題，為有效求解此問題，本文設(shè)計了基于最短路徑的模擬退火算法.

1)解的表示方式

本文使用維數(shù)為n×n的0－1矩陣Xp表示商品p的路徑，其中的元素xpij=1表示商品p的路徑中包含弧(i，j)，將所有商品的路徑所構(gòu)成的三維0－1矩陣X作為模擬退火算法中的解.

2)初始解及鄰域解的產(chǎn)生方式

當不考慮配送時間及弧容量約束等限制條件時，可通過求解以下的最短路問題得到任意商品p的一條配送路徑.

生成初始解X時，為保證初始解的隨機性，可隨機生成一組時間向量tij，對所有商品分別求解最短路問題(8)～(10).生成鄰域解X時，隨機選擇一種商品p，并隨機選擇其現(xiàn)行路徑中的某條弧(i，j)，令其運輸時間無限大，求解最短路問題(8)～(10)則可以得到一條新的路徑.

3)解的評價方式

4)冷卻進度表

本文設(shè)控制參數(shù)t的初值t0=1000，終值tf=1，衰減函數(shù)ti+1=0.95ti;針對不同規(guī)模的問題令Markov鏈的長度=100×m.

5)模擬退火算法的步驟

第1步:初始化控制參數(shù)t0，生成初始解X，計算其評價值E，轉(zhuǎn)第2步.

第2步:生成鄰域解X'，計算評價值增量ΔE=E'－E，轉(zhuǎn)第3步.

第3步:若 ΔE≤0，接受鄰域解，令 X=X';否則生成 ζ=U(0，)，若 ζ≤exp(－ ΔE/ti);接受鄰域解，令X=X';否則拒絕鄰域解;并轉(zhuǎn)第4步.

第4步:若內(nèi)循環(huán)迭代次數(shù)大于轉(zhuǎn)第5步，否則內(nèi)循環(huán)迭代次數(shù)加1，并轉(zhuǎn)第2步.

第5 步:衰減控制參數(shù) ti，令 i=i+1，若 ti＜ tf，算法終止;否則，轉(zhuǎn)第2步.

4 數(shù)值試驗

為了說明限時配送業(yè)務(wù)中的商品配送路徑選擇模型及本文設(shè)計的基于最短路徑的模擬退火算法的有效性，本文首先使用Matlab將模擬退火算法編程實現(xiàn)，在處理器主頻2.5 GHz，內(nèi)存4.00 GB的個人電腦中對算例問題進行求解，其次使用Cplex對同一問題的多商品網(wǎng)絡(luò)模型求解，并計算同樣參數(shù)下所得結(jié)果的配送延遲違約成本作為對照.

數(shù)值試驗中的問題為 Gendron和 Crainic[1]設(shè)計的多商品網(wǎng)絡(luò)問題算例集中的R類問題，由于算例問題均未考慮時間因素，本文對算例進行了調(diào)整，為每條弧賦予運輸時間tij，為每個節(jié)點賦予作業(yè)能力ci、延遲函數(shù)中所需參數(shù) Fi、α、β，為每種商品賦予承諾配送時間Lp、延遲違約成本Cp.由于求解結(jié)果受參數(shù)選擇的影響較大，本文進行了大量的靈敏度分析，表1為參數(shù)組合為tij=10，cj=100，F(xiàn)i=0.1，α =3，β =0.1，Lp=24，Cp=1 時的試驗結(jié)果.

表1 數(shù)值試驗結(jié)果

對試驗結(jié)果進行分析，可以得到以下結(jié)論:1)在模型方面，多商品網(wǎng)絡(luò)模型所得配送路徑雖然具有最優(yōu)的固定成本及運輸成本，但均產(chǎn)生了巨額的延遲違約成本，而本文建立的限時配送業(yè)務(wù)中的路徑選擇模型所得配送路徑，由于考慮到了配送過程中的時間因素，較多商品網(wǎng)絡(luò)模型實現(xiàn)了總成本的優(yōu)化;2)在求解方面，由于問題屬于NP難問題，對于大規(guī)模問題，如 r15.1，r17.1，r18.1 多商品網(wǎng)絡(luò)模型的求解難度大，而本文設(shè)計的模擬退火算法仍然可以有效求解.

[1]GENDRON B，CRAINIC T.Relaxations for multicommodity capacitated network design problems[R].Quebec Canada:Universite de Montreal，1994.

[2]G NL K O.A branch－and－cut algorithm for capacitated network design problems[J].Mathematical Programming，1999，86(1):17－39.

[3]MAGNANTI T L，MIREAULT P，WONG R T.Tailoring benders decomposition for uncapacitated network design problem[M].Springer Berlin Heidelberg，1986:112－154.

[4]CRAINIC T G，GENDREAU M，F(xiàn)ARVOLDEN J M.A Simplex－ based tabu search method for capacitated network design[J].INFORMS Journal on Computing，2000，12(3):223－236.

[5]GHAMLOUCHE I，CRAINIC T G，GENDREAU M.Cyclebased neighbourhoods for fixed－charge capacitated multicommodity network design[J].Operations Research，2003，51(4):655－667.

[6]CRAINIC T G，LI Y，TOULOUSE M.A first multilevel cooperative algorithm for capacitated multicommodity network design[J].Computers＆ Operations Research，2006，33(9):2602－2622.

[7]I R MARTIN，J S GONZALEZ.A local branching heuristic for the capacitated fixed－charge network design problem [J].Computers＆ Operations Research，2010，37(3):575－581.

[8]BAI R，KENDALL G，QU R.Tabu assisted guided local search approaches for freight service network design[J].Information Sciences，2012，189:266 －281.

[9]YAGHINI M，M MOMENI，SARMADI M.A Simplex－based simulated annealing algorithm for node－arc capacitated multicommodity network design[J].Applied Soft Computing，2010，12(9):2997－3003.

[10]朱 芳.快遞企業(yè)爆倉問題的研究[J].物流工程與管理，2012，34(222):33－34.

[11]王寶友.唐山港全力緩解礦石運輸船舶壓港[N].中國水運報，2009－2－20(6).

[12]J E FERN NDEZ L，J DE CEA CH，R GIESEN E.A Strategic Model for Freight Operations on Rail Transportation Systems[J].Transportation Planning and Technology，2004，27(4):231 －260.

[13]徐耀群，尹遜芹.基于實時路況的配送路徑優(yōu)化問題研究[J].哈爾濱商業(yè)大學(xué)學(xué)報:自然科學(xué)版，2012，28(5):537－540.