郝 爽，董 明

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

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

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

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

1 商品配送延遲的成因

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

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

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

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

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

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

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

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

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

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

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

1)解的表示方式

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

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

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

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

3)解的評價(jià)方式

4)冷卻進(jìn)度表

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

5)模擬退火算法的步驟

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

第2步:生成鄰域解X'，計(jì)算評價(jià)值增量Δ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àn)

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

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

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

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

[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]王寶友.唐山港全力緩解礦石運(yùn)輸船舶壓港[N].中國水運(yùn)報(bào)，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]徐耀群，尹遜芹.基于實(shí)時(shí)路況的配送路徑優(yōu)化問題研究[J].哈爾濱商業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2012，28(5):537－540.