冷鏈物流越庫(kù)調(diào)度的拉格朗日松弛算法

周炳海,宗 師

(同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院,上海 201804)

1 引言

越庫(kù)(cross-docking)是一種物流策略,旨在使貨物在供應(yīng)鏈中快速的運(yùn)輸和分揀.越庫(kù)也是一種倉(cāng)儲(chǔ)策略,目的是減少或消除倉(cāng)儲(chǔ),從而降低供應(yīng)鏈的成本.越庫(kù)這一策略現(xiàn)已經(jīng)廣泛地應(yīng)用于零售、制造等各個(gè)行業(yè).

多年來(lái),越庫(kù)調(diào)度問(wèn)題引起了國(guó)內(nèi)外學(xué)者的關(guān)注,并針對(duì)不同的應(yīng)用場(chǎng)景進(jìn)行了深入的研究.Nassief等[1]研究了帶有臨時(shí)存儲(chǔ)區(qū)域的越庫(kù)門分配問(wèn)題(cross-dock assignment problems,CDAPs),給出了兩個(gè)整數(shù)規(guī)劃模型,并對(duì)模型參數(shù)進(jìn)行了靈敏度分析.Yin等[2]考慮了綠色環(huán)保的越庫(kù)調(diào)度問(wèn)題,在越庫(kù)模型中增添了二氧化碳濃度的約束,并提出一種新的記憶人工蜂群算法進(jìn)行求解.Karimi等[3]研究了越庫(kù)網(wǎng)絡(luò)在伊朗郵政系統(tǒng)內(nèi)的應(yīng)用,通過(guò)設(shè)置郵件的預(yù)設(shè)到達(dá)時(shí)間以控制和提高整個(gè)郵政系統(tǒng)的送件速度.Serrano等[4]考慮在雷諾汽車供應(yīng)鏈的越庫(kù)內(nèi)部加入包裝車間,實(shí)現(xiàn)了運(yùn)輸和加工同時(shí)進(jìn)行的需求.Nassief 等[5]采用了拉格朗日松弛算法研究越庫(kù)調(diào)度問(wèn)題,但是僅研究了卡車到門的分配,未考慮卡車的排序問(wèn)題.上述文獻(xiàn)研究了越庫(kù)在各類不同供應(yīng)鏈或物流中的應(yīng)用,其研究成果為接下來(lái)越庫(kù)調(diào)度問(wèn)題的研究提供了很好的參考和借鑒.

冷鏈物流作為一種特殊的物流方式,其最大的技術(shù)難點(diǎn)在于嚴(yán)格的時(shí)間和低溫控制.冷鏈物流強(qiáng)調(diào)貨物運(yùn)輸過(guò)程中的全局控制,如果有環(huán)節(jié)出現(xiàn)“斷鏈”,即貨物溫度高于其最高貯藏溫度,就會(huì)影響到產(chǎn)品質(zhì)量與安全,使得整個(gè)供應(yīng)鏈的可靠性大大降低.此外,高昂的冷庫(kù)存儲(chǔ)成本也阻礙著冷鏈物流的應(yīng)用和發(fā)展.許多學(xué)者和企業(yè)也一直在尋找一種針對(duì)冷鏈物流的及時(shí)且高效的運(yùn)作方法.越庫(kù)調(diào)度策略在物流系統(tǒng)中具有及時(shí)性、高效性、低成本的特點(diǎn),越庫(kù)作為供應(yīng)鏈上的中轉(zhuǎn)站和連接點(diǎn)大大提升了物流效率,降低了倉(cāng)儲(chǔ)成本.因此,將越庫(kù)調(diào)度策略運(yùn)用到冷鏈物流中,一方面,減少了冷庫(kù)存儲(chǔ)需求,大大降低了成本;另一方面,越庫(kù)使得貨物具有了快速被分揀并裝載的能力,貨物暴露在常溫下的時(shí)間大大降低,減少了“斷鏈”的風(fēng)險(xiǎn).

針對(duì)冷鏈物流的特點(diǎn),提出了越庫(kù)內(nèi)的貨物時(shí)間窗口,要求每種貨物在規(guī)定的時(shí)間內(nèi)通過(guò)越庫(kù)[6].此外為了貼合實(shí)際應(yīng)用,考慮設(shè)置越庫(kù)門前臨時(shí)存儲(chǔ)區(qū)域,內(nèi)設(shè)冷庫(kù),并分別給定不同的存儲(chǔ)容量.基于越庫(kù)的基本運(yùn)作原理和冷鏈物流的特殊要求,提出了冷鏈物流越庫(kù)調(diào)度的數(shù)學(xué)模型,并采用拉格朗日松弛算法,根據(jù)決策變量松弛復(fù)雜約束,提高模型求解速度和穩(wěn)定性[7].

2 數(shù)學(xué)建模

2.1 問(wèn)題描述

研究的越庫(kù)配送調(diào)度主要包含3個(gè)部分,示意圖見(jiàn)圖1.

圖1 冷鏈物流中的越庫(kù)調(diào)度問(wèn)題Fig.1 Cross-dock scheduling problem in cold-chain logistics

圖1中:1)入庫(kù)卡車到越庫(kù)門的分配和入庫(kù)卡車的排序:將裝載著貨物的入庫(kù)卡車分別分配至一入庫(kù)門,并對(duì)分配到同一入庫(kù)門的卡車進(jìn)行排序,按照排序進(jìn)入越庫(kù).2)貨物的庫(kù)內(nèi)運(yùn)輸:入庫(kù)卡車進(jìn)入越庫(kù)后,將貨物卸載于入庫(kù)門前的臨時(shí)存儲(chǔ)區(qū)域,然后立即將貨物運(yùn)輸至為其分配的出庫(kù)門,暫存在出庫(kù)門的臨時(shí)存儲(chǔ)區(qū)域內(nèi)等待裝載.此階段考慮冷鏈物流中,每個(gè)貨物在庫(kù)內(nèi)的時(shí)間窗口約束,根據(jù)不同的貨物種類,要求貨物在規(guī)定的時(shí)間內(nèi)完成庫(kù)內(nèi)運(yùn)輸.3)出庫(kù)卡車到越庫(kù)門的分配和出庫(kù)卡車的排序:將出庫(kù)卡車分別分配至一出庫(kù)門,并對(duì)分配到同一出庫(kù)門的卡車進(jìn)行排序,按照排序進(jìn)入越庫(kù),裝貨后離開(kāi)越庫(kù)[8].

2.2 數(shù)學(xué)模型

基于上述的問(wèn)題描述,建立如下數(shù)學(xué)模型:

1)模型假設(shè).

①每個(gè)越庫(kù)門在同一時(shí)間只能服務(wù)于一輛運(yùn)輸卡車;②貨物在越庫(kù)內(nèi)部運(yùn)輸時(shí),越庫(kù)門距離越遠(yuǎn),運(yùn)輸時(shí)間越長(zhǎng);③將貨物分為k個(gè)種類,每個(gè)種類的貨物對(duì)應(yīng)于一個(gè)時(shí)間窗口約束tk,每種貨物從入庫(kù)到出庫(kù)必須要在此時(shí)間窗口約束內(nèi)完成;④臨時(shí)存儲(chǔ)區(qū)域設(shè)有冷庫(kù),可保證貨物在低溫下的存儲(chǔ).同時(shí),每個(gè)臨時(shí)存儲(chǔ)區(qū)域設(shè)有容量限制,區(qū)域內(nèi)貨物之和不得超出此容量限制.

2)參數(shù).

k ∈P為貨物的種類;i ∈I為入庫(kù)門編號(hào);j ∈J為出庫(kù)門編號(hào);m ∈M為入庫(kù)卡車編號(hào);n ∈N為出庫(kù)卡車編號(hào);ULT為一輛入庫(kù)卡車的卸貨時(shí)間;LT為一輛出庫(kù)卡車的裝貨時(shí)間;wk為貨物k的數(shù)量;sm為入庫(kù)卡車m裝載的貨物數(shù)量;rn為出庫(kù)卡車n裝載的貨物數(shù)量;Si為入庫(kù)門i前的臨時(shí)存儲(chǔ)區(qū)域容量;Rj為出庫(kù)門j前的臨時(shí)存儲(chǔ)區(qū)域容量;dij為入庫(kù)門i到出庫(kù)門j的運(yùn)輸時(shí)間成本;tk為貨物k在越庫(kù)內(nèi)部運(yùn)輸?shù)臅r(shí)間窗口.

3)決策變量.

zkij:0～1變量,表示貨物k是否由入庫(kù)門i卸載并發(fā)往出庫(kù)門j裝載;xmi:0～1變量,表示入庫(kù)卡車m是否被分配到入庫(kù)門i進(jìn)行卸貨;ynj:0～1變量,表示出庫(kù)卡車n是否被分配到出庫(kù)門j進(jìn)行卸貨;pmn,qmn:0～1變量,表示入(出)庫(kù)卡車m在卡車入(出)庫(kù)排序中是否排在入(出)庫(kù)卡車n的前面;Pm,Qn:整數(shù)變量,表示卡車在卡車入(出)庫(kù)排序中的位次;Cm:整數(shù)變量,表示入庫(kù)卡車m進(jìn)入越庫(kù)進(jìn)行卸貨的時(shí)間;Ln:整數(shù)變量,表示出庫(kù)卡車n裝貨完成后離開(kāi)越庫(kù)的時(shí)間.

根據(jù)上述問(wèn)題描述、模型假設(shè)、參數(shù)以及決策變量,對(duì)所研究的越庫(kù)模型建模如下:

上述模型中,目標(biāo)函數(shù)(1)是庫(kù)內(nèi)運(yùn)輸成本之和;目標(biāo)函數(shù)(2)是卡車等待時(shí)間之和;約束(3)表明每種貨物只能且必須被分配給一個(gè)入庫(kù)門和一個(gè)出庫(kù)門;約束(4)–(7)表明每輛卡車只能且必須分配給一個(gè)越庫(kù)門;約束(8)–(11)給定了每個(gè)越庫(kù)門前臨時(shí)存儲(chǔ)區(qū)域的容量限制;約束(12)表明每一種貨物k在庫(kù)內(nèi)運(yùn)輸時(shí)與其對(duì)應(yīng)的時(shí)間窗口;約束(13)–(16)表明卡車在越庫(kù)門前等待隊(duì)列中相互的先后順序;約束(17)–(18)表明了每輛卡車在越庫(kù)門前等待隊(duì)列中的位次;約束(19)為入庫(kù)卡車的入庫(kù)卸貨時(shí)間;約束(20)表明了入庫(kù)卡車的卸貨時(shí)間與出庫(kù)卡車的裝貨時(shí)間的關(guān)系;約束(21)為出庫(kù)卡車裝貨時(shí)間的先后關(guān)系;約束(22)為0～1變量約束.

3 拉格朗日松弛算法

3.1 松弛約束

將原模型中的約束(4)–(5)和約束(10)–(11)松弛到目標(biāo)函數(shù)(1)中,引入拉格朗日乘子μ,ν,λ和γ,形成如下的松弛問(wèn)題:

將原模型中的約束(19)松弛到目標(biāo)函數(shù)(2)中,引入拉格朗日乘子η,形成如下的松弛問(wèn)題:

拉格朗日對(duì)偶問(wèn)題可表示為

3.2 求解子問(wèn)題

根據(jù)拉格朗日分解思想,可將L(μ,ν,λ,γ)和L(η)根據(jù)不同的決策變量分解成多個(gè)子問(wèn)題:1)關(guān)于決策變量z的子問(wèn)題Lz(μ,ν,λ,γ);2)關(guān)于決策變量x的子問(wèn)題Lx(ν,λ);3)關(guān)于決策變量y的子問(wèn)題Ly(ν,γ);4)關(guān)于決策變量Pm的子問(wèn)題Lp(η);5)關(guān)于決策變量Ln的子問(wèn)題Lq(η)[9].

1)求解子問(wèn)題Lz(μ,ν,λ,γ).

Lz(μ,ν,λ,γ)為關(guān)于決策變量z的子問(wèn)題,是貨物在越庫(kù)內(nèi)部運(yùn)輸路線的分配問(wèn)題,可以被分解為基于貨物種類k的獨(dú)立子問(wèn)題

基于決策變量約束(23)和貨物的時(shí)間窗口約束(24),求解出子問(wèn)題Lz,從而得到貨物k在越庫(kù)中的由入庫(kù)門到出庫(kù)門的移動(dòng)路線.

2)求解子問(wèn)題Lx(μ,λ)和Ly(ν,γ).

Lx為關(guān)于決策變量x的子問(wèn)題,是入庫(kù)卡車到入庫(kù)門的分配問(wèn)題,可以被分解為基于入庫(kù)門i的獨(dú)立子問(wèn)題

同理,Ly為關(guān)于決策變量y的子問(wèn)題,是出庫(kù)卡車到出庫(kù)門的分配問(wèn)題,可以被分解為基于出庫(kù)門j的獨(dú)立子問(wèn)題

求解出子問(wèn)題Lx和Ly得到卡車到越庫(kù)門的分配情況.

3)求解子問(wèn)題Lp(η)和Lq(η).

將求解子問(wèn)題Lx(μ,λ)和Ly(ν,γ)得到的xmi和ynj代入式(32)–(33),即

其中:m,m′=1,···,M,m≠=m′,n,n′=1,···,M,n≠n′.然后進(jìn)行車輛排序問(wèn)題的求解,即求解子問(wèn)題Lp(η)和Lq(η).

Lp(η)為關(guān)于決策變量Pm的子問(wèn)題是入庫(kù)卡車在每一個(gè)入庫(kù)門的排序問(wèn)題:

其中m,m′=1,···,M,m≠m′.

Lq(η)為關(guān)于決策變量Ln的子問(wèn)題是出庫(kù)卡車在每一個(gè)出庫(kù)門的排序問(wèn)題:

求解出子問(wèn)題Lp(η)和Lq(η)得到卡車在越庫(kù)門的排序.

3.3 次梯度算法

引入次梯度算法來(lái)求解拉格朗日對(duì)偶問(wèn)題,每次迭代過(guò)程中根據(jù)如下公式進(jìn)行拉格朗日乘子更新:

是貨物在越庫(kù)內(nèi)部的運(yùn)輸成本,而目標(biāo)函數(shù)(2)

是卡車在越庫(kù)門的等待時(shí)間.對(duì)兩個(gè)目標(biāo)函數(shù)進(jìn)行無(wú)量綱化處理并加權(quán)相加,得到一個(gè)統(tǒng)一的目標(biāo)函數(shù)[10]

3.4 構(gòu)造可行解

上述拉格朗日松弛的過(guò)程在大多數(shù)情況下得到的是目標(biāo)函數(shù)的下界及其對(duì)應(yīng)的不可行解.現(xiàn)采用拉格朗日啟發(fā)式算法,對(duì)上述傳統(tǒng)的拉格朗日算法進(jìn)行改進(jìn),獲得可行解.

拉格朗日啟發(fā)式算法共包含兩個(gè)過(guò)程:第1步,如上述過(guò)程采用次梯度法進(jìn)行優(yōu)化迭代計(jì)算;第2步,采用系數(shù)修正法對(duì)第一步得到的解進(jìn)行可行化.系數(shù)修正法是拉格朗日啟發(fā)式算法的一種形式,用于檢驗(yàn)用次梯度法求解的當(dāng)前解是否滿足各條被松弛的約束.若存在未被滿足的松弛約束,則選取出其對(duì)應(yīng)的目標(biāo)函數(shù)系數(shù)中的最小值di,并更新其對(duì)應(yīng)的拉格朗日λ(t+1)=λt+di,直到此條約束被滿足.直到當(dāng)所有的約束(無(wú)論是否被松弛)都被滿足時(shí),則當(dāng)前解為可行解.

3.5 拉格朗日松弛算法流程

步驟1初始化,令當(dāng)前迭代次數(shù)t=0,令所有拉格朗日乘子為0;

步驟2求解每個(gè)子問(wèn)題,目標(biāo)函數(shù)值加權(quán)相加,得到下界;

步驟3對(duì)松弛問(wèn)題的解通過(guò)系數(shù)修正法進(jìn)行可行化;

步驟4判斷是否符合次梯度法的停止準(zhǔn)則,若符合則算法停止,否則繼續(xù);

步驟5進(jìn)行拉格朗日乘子更新,返回步驟2[11].

4 實(shí)驗(yàn)與分析

本實(shí)驗(yàn)結(jié)果通過(guò)以下數(shù)據(jù)進(jìn)行衡量:1)每一組數(shù)據(jù)運(yùn)算的CPU時(shí)間;2)對(duì)偶間隙(%gap):

其中LP是每組實(shí)驗(yàn)通過(guò)拉格朗日松弛算法得到的目標(biāo)函數(shù)值下界,OPT是根據(jù)系數(shù)修正法得到的可行解;3)對(duì)比算法的偏移(%dev):

其中UB是每一組實(shí)驗(yàn)數(shù)據(jù)通過(guò)貪婪算法得到的目標(biāo)函數(shù)值上界.通過(guò)可行解和下界、上界比較得到了對(duì)偶間隙(%gap)和對(duì)比算法的偏移(%dev),這兩個(gè)參數(shù)是拉格朗日松弛算法重要的評(píng)價(jià)指標(biāo),反映了可行解的優(yōu)良程度和當(dāng)前算法的可靠性.設(shè)定最大迭代次數(shù)為500,次梯度優(yōu)化算法中取參數(shù)β=2[12].

本實(shí)驗(yàn)測(cè)試了所提出的拉格朗日松弛算法求解各種不同規(guī)模越庫(kù)調(diào)度問(wèn)題的性能.問(wèn)題實(shí)例數(shù)據(jù)取值如下:卡車數(shù)量M,N=5,6,7,8,9,10,11,12,15;貨物數(shù)量P=3,4,5,6;每種貨物的數(shù)量wk在[200,500]間隨機(jī)生成;臨時(shí)存儲(chǔ)區(qū)域的總量

其中:α分別取0.1,0.15,0.2,0.3;庫(kù)內(nèi)運(yùn)輸成本

每種貨物k的庫(kù)內(nèi)運(yùn)輸時(shí)間窗口在庫(kù)內(nèi)最長(zhǎng)運(yùn)輸時(shí)間的60%～100%間離散均勻分布產(chǎn)生.對(duì)于每種車–門數(shù)量組合,根據(jù)臨時(shí)存儲(chǔ)區(qū)域總量寬放α產(chǎn)生3–4種實(shí)驗(yàn)實(shí)例,一共產(chǎn)生49組實(shí)驗(yàn).

原模型內(nèi)雙目標(biāo)分別為庫(kù)內(nèi)運(yùn)輸成本之和以及卡車等待時(shí)間之和,兩個(gè)目標(biāo)數(shù)值差異較大,對(duì)最終結(jié)果的影響程度也相差較大.本實(shí)驗(yàn)用無(wú)量綱化加權(quán)的方法,將原模型內(nèi)的雙目標(biāo)轉(zhuǎn)換為單目標(biāo).經(jīng)過(guò)多次實(shí)驗(yàn),取b=0.95,此時(shí)統(tǒng)一的目標(biāo)函數(shù)為

此時(shí)兩個(gè)目標(biāo)的數(shù)值接近,對(duì)模型的影響程度相近.以問(wèn)題1為例,經(jīng)多次迭代,庫(kù)內(nèi)運(yùn)輸成本之和為11520,卡車等待時(shí)間之和為741,采用b=0.95的加權(quán)方法后兩目標(biāo)函數(shù)分別為576和704,符合預(yù)期.

采用貪婪算法作為對(duì)比算法:一方面通過(guò)貪婪算法得到每組實(shí)驗(yàn)?zāi)繕?biāo)函數(shù)的初始上界;另一方面與通過(guò)拉格朗日松弛算法得到的近優(yōu)解進(jìn)行對(duì)比,判斷解的質(zhì)量.對(duì)比貪婪算法思路如下:將每輛卡車的貨物由多至少進(jìn)行排列,按照此順序依次進(jìn)入越庫(kù),每輛卡車在入庫(kù)時(shí)選取當(dāng)前庫(kù)門剩余臨時(shí)存儲(chǔ)區(qū)域最大的入庫(kù)門進(jìn)入;入庫(kù)后,依然按照上述排列順序依次出庫(kù),每輛出庫(kù)卡車依次選取當(dāng)前庫(kù)門剩余臨時(shí)存儲(chǔ)區(qū)域最大的出庫(kù)門.

算法采用以下計(jì)算機(jī)配置進(jìn)行實(shí)現(xiàn):CPU:1.6 GHz Intel Core i5;內(nèi)存:4 GB;電腦系統(tǒng):Windows 7;編程語(yǔ)言:MATLAB.

實(shí)驗(yàn)結(jié)果如表1所示.

表1 不同規(guī)模問(wèn)題的拉格朗日松弛算法與貪婪算法的結(jié)果對(duì)比Table 1 Comparison of Lagrangian relaxation algorithm and greedy algorithm of different scale problems

從表1可以得出如下結(jié)論:

1)大多數(shù)情況下,對(duì)于每一對(duì)車–門數(shù)量組合,隨著臨時(shí)存儲(chǔ)區(qū)域?qū)挿诺脑黾?對(duì)偶間隙(%gap)會(huì)降低.因?yàn)榕R時(shí)存儲(chǔ)區(qū)域總量增加后,對(duì)卡車入庫(kù)的貨物容量約束會(huì)降低,貨物入庫(kù)的條件得以放松,因此解的質(zhì)量會(huì)有所提高;

2)大多數(shù)情況下,當(dāng)卡車數(shù)量不變,庫(kù)門數(shù)量增加時(shí),對(duì)偶間隙(%gap)會(huì)降低.因?yàn)榇藭r(shí),分配到每個(gè)門的卡車數(shù)量相對(duì)減少,卡車可停靠的庫(kù)門資源相對(duì)增加,卡車的排序問(wèn)題相對(duì)簡(jiǎn)化,因此解的質(zhì)量也會(huì)有所提高;

3)隨著實(shí)驗(yàn)實(shí)例的規(guī)模增加,目標(biāo)函數(shù)上界值(即對(duì)比貪婪算法的目標(biāo)函數(shù)值)相較于目標(biāo)函數(shù)近優(yōu)解的偏移(%dev)越來(lái)越大.因此隨著實(shí)驗(yàn)規(guī)模的增加,可行解數(shù)量的增多,拉格朗日松弛算法的優(yōu)勢(shì)逐漸顯現(xiàn),其解的質(zhì)量相對(duì)于貪婪算法愈發(fā)優(yōu)良;

4)本實(shí)驗(yàn)所有實(shí)例的平均對(duì)偶間隙和平均CPU時(shí)間分別為5.74%和990.67 s.因此,拉格朗日松弛算法能夠在合理的時(shí)間內(nèi)得到較為滿意的目標(biāo)函數(shù)下界和近優(yōu)可行解.

5 結(jié)論

針對(duì)以冷鏈物流為背景的越庫(kù)調(diào)度問(wèn)題,考慮到實(shí)際運(yùn)輸過(guò)程中貨物的冷藏條件,提出了帶有貨物時(shí)間窗口約束的越庫(kù)調(diào)度問(wèn)題,并對(duì)該問(wèn)題進(jìn)行描述,以最小化庫(kù)內(nèi)運(yùn)輸成本和卡車排序等待時(shí)間為目標(biāo),建立數(shù)學(xué)模型.繼而采用了拉格朗日松弛算法,根據(jù)重要的決策變量將原問(wèn)題分解為五個(gè)子問(wèn)題,并通過(guò)次梯度算法進(jìn)行模型的求解.實(shí)驗(yàn)分析了不同規(guī)模的越庫(kù)調(diào)度實(shí)例,并得到相應(yīng)結(jié)論.結(jié)果表明,拉格朗日松弛算法能夠在合理的時(shí)間內(nèi)得到較為滿意的目標(biāo)函數(shù)下界和近優(yōu)可行解.后續(xù)研究將考慮如何進(jìn)一步的提升解的質(zhì)量,并提高算法運(yùn)行速度.