隨機需求下的CDL系統(tǒng)多目標優(yōu)化

隨機需求下的CDL系統(tǒng)多目標優(yōu)化胡路;彭博;蔣陽升;張改【摘要】為了增強越庫配送對市場隨機需求的適應(yīng)性,兼顧總體利益和零售商門店的個體利益，充分考慮隨機需求、庫存、配貨和原始訂單等因素，以提高最終訂單滿足隨機需求的置信水平、增加配送車輛滿載率和降低總運營成本為目標，建立了多目標隨機規(guī)劃模型，構(gòu)建了正規(guī)化的多目標適應(yīng)度函數(shù)，設(shè)計了具有自適應(yīng)特點的遺傳算法，并進行了實例研究.結(jié)果表明:與原始訂單相比，最終訂單滿足隨機需求的置信水平、配送車輛滿載率分別增加了3.59%、12.71%,每天的總成本平均減少了631845元降低了13.73%.%Inordertoenhancetheadaptivityofcross-dockinglogistics(CDL)tostochasticmarketdemand,amulti-objectivestochasticprogrammingmodelwasestablished.Takingbothlocalandglobalinterestsintoaccountandconsideringthefactorssuchasrandomdemand,inventory,distribution,andoriginalorders,Thismodelaimsatimprovingtheconfidenceleveloffinalorderstomeetthestochasticdemand,increasingthevehicleloadingrate,andreducingthetotaloperationcost,andTosolvethemodel,amulti-objectivefitnessfunctionwasconstructedandnormalized,andanadaptivegeneticalgorithmwasdesigned.Theresultofacasestudyshowsthat,comparedwiththeoriginalorders,thefinalordersdealtwithbythismodelcanincreasetheconfidencelevelmeetingstochasticdemandandvehicleloadingrateby3.59%and12.71%,respectively,andreducetheaveragetotalcostperdayby631845yuan,adeclineof13.73%.【期刊名稱】《西南交通大學(xué)學(xué)報》【年(卷)，期】2011(046)004【總頁數(shù)】7頁(P688-694)【關(guān)鍵詞】CDL;隨機需求;多目標隨機規(guī)劃啟適應(yīng)遺傳算法【作者】胡路;彭博;蔣陽升漲改【作者單位】西南交通大學(xué)交通運輸與物流學(xué)院，四川成都610031;西南交通大學(xué)交通運輸與物流學(xué)院，四川成都610031;西南交通大學(xué)交通運輸與物流學(xué)院，四川成都610031;西南交通大學(xué)交通運輸與物流學(xué)院，四川成都610031【正文語種】中文【中圖分類】F253.4越庫配送(cross-dockinglogistics，CDL)作為一種先進的物流配送戰(zhàn)略和運作模式，在發(fā)達國家已獲得成功應(yīng)用.與其他配送戰(zhàn)略相比，CDL可以在時間、空間和成本上實現(xiàn)總體利益的優(yōu)化.文獻［1］采用基于禁忌搜索的啟發(fā)式算法，研究了CDL在供應(yīng)鏈中的車輛路徑優(yōu)化問題.文獻［2］建立了預(yù)測模型，分析了CDL對分散的零售供應(yīng)鏈的庫存影響.文獻［3］用整數(shù)規(guī)劃和CPLEX軟件優(yōu)化了兩階段CDL混合調(diào)度的完工時間.文獻［4］建立了具有臨時庫存的CDL系統(tǒng)進、出站車輛調(diào)度模型.文獻［5］把CDL環(huán)境下的商品定位問題抽象成最小費用流問題，提出一種新的運作方法.文獻［6］提出了一種新的啟發(fā)式評估體系，對供應(yīng)鏈網(wǎng)絡(luò)設(shè)計中的CDL配送中心進行定位.文獻［7］設(shè)計了在CDL流水線盡量縮短加工周期的分支定界算法.文獻［8］編寫了啟發(fā)式算法的程序，求解零庫存時CDL終端的車輛調(diào)度問題.文獻［9］提出一種啟發(fā)式逼近算法，求解CDL系統(tǒng)的車輛調(diào)度問題.文獻［10］通過優(yōu)化模型對CDL轉(zhuǎn)運的預(yù)分配成本與后分配成本進行了比較.上述文獻對CDL的研究大多局限于精確的市場需求預(yù)測下的車輛調(diào)度、商品定位、成本分析和設(shè)計評估方面，尚未見到在無法精確預(yù)測的市場隨機需求條件下實行CDL的相關(guān)研究報道.此外，現(xiàn)有的CDL配送中心匯總各零售商的原始訂單，直接形成最終訂單發(fā)送到供應(yīng)商信息中心［11］,沒有對原始訂單進行分析處理，這種方式滿足了零售商門店自身的利益，但有可能降低CDL配送車輛的滿載率，增加物流成本，同時市場需求的隨機變動也會導(dǎo)致訂單無法適應(yīng)市場需求，致使缺貨或庫存成本增加，使總體效益降低.因此，為了增強CDL對市場隨機需求的適應(yīng)性，兼顧零售商個體利益和總體利益，本文建立多目標隨機規(guī)劃模型，對原始訂單進行分析處理，協(xié)調(diào)最終訂單滿足市場隨機需求的置信度、CDL配送車輛的滿載率、零售商總成本三者之間的關(guān)系，并設(shè)計自適應(yīng)遺傳算法求解模型，并進行了實例分析.1多目標隨機規(guī)劃模型1.1問題描述在現(xiàn)有CDL配送流程［11］基礎(chǔ)上，面對隨機需求的CDL配送流程如圖1所示.圖1CDL物流配送流程Fig.1DistributionprocessofCDL由圖1可見：零售商從自身利益出發(fā)，根據(jù)銷售情況，對各種貨物采取相應(yīng)的存儲策略，制定原始訂單并通過網(wǎng)絡(luò)發(fā)送到CDL配送中心的信息中心.配送中心匯總所有零售商的原始訂單后，根據(jù)各訂單的隨機需求，從零售商總體利益出發(fā)對原始訂單進行分析處理，制定最終訂單，通過與供應(yīng)商共享的電子數(shù)據(jù)交換網(wǎng)絡(luò)向供應(yīng)商信息中心發(fā)送最終訂單.⑶供應(yīng)商獲取所有零售商的銷售終端(pointofsale,POS)相關(guān)歷史數(shù)據(jù)和實時數(shù)據(jù)并進行分析，在供應(yīng)商信息中心收到最終訂單并經(jīng)過準備后，向零售商配送中心的信息中心發(fā)送預(yù)先發(fā)貨通知(advancedshippingnote，ASN);然后，按照最終訂單發(fā)貨.⑷零售商CDL配送中心的信息中心接到ASN并進行收貨準備工作.收貨后根據(jù)最終訂單分揀、包裝商品，然后把商品配送到各零售商門店.CDL倉庫為商品的臨時存儲點，通常商品在CDL倉庫中停留時間較短，一般不超過12h.針對CDL運作模式的物品分揀方式，在給定條件(供應(yīng)商與配送中心、配送中心與零售商之間的距離和車輛運行時間;零售商門店的單位貨物庫存成本、固定訂貨費、貨物裝卸時間、庫存信息、每種貨物的市場隨機需求分布、原始訂單需求;CDL配送車輛的數(shù)目、最大裝載量、單位運輸成本、返空費用，固定派車費用等)下，通過制訂合理的訂貨周期、最終訂單和貨物裝載策略，使最終訂單在一定置信度水平下滿足隨機需求，提高車輛滿載率，降低零售商訂貨成本、庫存成本、缺貨成本和配送運輸成本，并保證最終訂單與原始訂單盡量相符.1.2模型假設(shè)零售商開設(shè)若干門店，CDL物流配送中心由零售商統(tǒng)一建設(shè)經(jīng)營；對零售商的各個門店j,Rij(t)是離散型隨機變量，即｛Rij(t),t20｝為離散型隨機過程供應(yīng)商和CDL配送中心均擁有足夠的車輛，能夠一次性滿足貨物運輸需求；⑷零售商門店的所有貨物均由同一家供應(yīng)商提供，且各門店貨物種類相同；⑸貨物在CDL倉庫中停留的時間很短，通常不超過12h，忽略貨物在CDL的倉儲成本;(6)各門店各種貨物均采用定期訂貨策略，即每隔1個周期訂1次貨，根據(jù)上一周期末貨物庫存量決定訂貨量.庫存量少，可以多訂貨，反之可以少訂或不訂貨.1.3符號說明(1)模型輸入?yún)?shù)J——門店數(shù)目，JUN*;I——貨物種類，IUN*;Rij(t)——門店j的貨物i在時間段［0,t］的市場需求率隨機變量，｛Rij(t),t20｝為相應(yīng)的隨機過程，i=1,2，…，I;j=1,2，…，J;Q0ij——門店j原始訂單中貨物i的初始數(shù)量，件Sij——CDL配送中心在制定最終訂單時，通過網(wǎng)絡(luò)獲得的當前門店j的貨物i的庫存量，件；t0——CDL配送中心制定最終訂單的時刻；ts——供應(yīng)商s從收到最終訂單到準備發(fā)貨的平均時間，h;ts0——從供應(yīng)商s到CDL配送中心0的車輛運行時間，h;t00——因CDL配送中心要對貨物進行分揀、包裝等一系列工作，而使貨物逗留的平均時間，h;t0j——從CDL配送中心0到門店j的車輛運行時間，h;tL——整個配送過程中各門店貨物需要的平均裝卸時間，h;d0j——從CDL配送中心0到門店j的距離，km;K—CDL配送中心的車輛總數(shù)，KUN*;Mk——車輛k(k=1,2，…，K)的最大裝載量，t;mi——單件貨物i的質(zhì)量，kg/件；C1——單位質(zhì)量貨物每小時的庫存成本，元/(切)；C2——單件貨物缺貨費用，元/件；C3——每車固定訂貨費用，元/車；C4——每車固定派車費用，元/車；C5——單位質(zhì)量貨物單位里程運輸成本，元/(t-km);C6——配送車輛服務(wù)門店后的返空費用，元/(t-km);C7——整個配送過程中單位質(zhì)量貨物的裝卸分揀包裝費用,元/t;Cgi——單件貨物i的成本，元/件P——庫存的最大容許度邛頃0,1);a缺貨的最大容許度，au(0,1);ws——經(jīng)驗權(quán)重，表示決策者的目標偏好值，s=1,2,3;Y——最終訂單偏離原始訂單的最大容忍度，Y^(0,1).(2)決策變量Qij——CDL配送中心將原始訂單匯總后，從全體零售商利益出發(fā)制定的最終訂單中門店j訂購貨物i的數(shù)量，i=1,2，…，I;j=1,2，…，J;qkij——配送車輛k裝載門店j最終訂單中貨物i的數(shù)量，件；rk——0-1變量，當配送車輛k裝有貨物時取1,否則為0,k=1,2，…，K;T——訂貨周期(TUN*),h.1.4模型建立1.4.1目標函數(shù)決策變量為:零售商門店的訂貨周期T;當前周期最終訂單中所需貨物i的數(shù)量Qij;車輛k運送門店j裝載的最終訂單中貨物i的數(shù)量qkij.優(yōu)化目標有3個:最終訂單訂貨量滿足隨機需求的置信度最大;CDL配送中心的配送車輛滿載率最高;零售商的運營總成本最低.(1)置信度目標函數(shù)為：式中:f1——最終訂單滿足隨機需求的置信度；tj——門店j備貨時間(常量)，即從CDL配送中心向供應(yīng)商發(fā)出最終訂單到門店收到貨物的時間，Rij(t0,t0+T+tj)——從CDL配送中心當前計劃周期制定最終訂單到下個計劃周期貨物i配送到門店j的時間［t0，t0+T+tj］內(nèi)，市場對門店j貨物i的需求隨機變量，它等于［0,t0+T+tj］內(nèi)的市場需求Rij(t0+T+tj)減去［0,t0］內(nèi)的市場需求Rij(t0);P(?)——最終訂單的訂購量Qij滿足隨機需求的概率(圓點代表式(1)中的具體表達式)，即分別將庫存和缺貨相對誤差控制在最大容許度P和a以內(nèi)的概率.庫存時間變化如圖2所示.(2)滿載率目標函數(shù)為：式中:f2―參與配送的車輛滿載率；rkj——0-1變量，當時，rkj=1，表明配送車輛k裝有門店j的貨物，車輛參與配送;當時，rkj=0，表明車輛k不參與配送.圖2某門店貨物的庫存變化Fig.2Timevariationofrandominventoryofsomegoodsinaparticularstore⑶總成本目標函數(shù)式中:f3―全體零售商門店每天的平均運營總成本；hl——訂貨成本，即訂購費(參與配送的車輛數(shù)與每車的固定訂貨費用之積)與貨物自身成本費用之和，即h2——平均庫存成本，等于單位貨物每小時庫存費用與庫存時間(即訂貨周期)、平均庫存噸數(shù)之積，即h3——平均缺貨成本，等于單位貨物缺貨費用與平均缺貨數(shù)量之積，即h4——配送運輸成本，等于整個配送過程中派車、運貨、貨物的裝卸分揀包裝與返空費用之和，即1.4.2約束條件載質(zhì)量約束:車輛裝載貨物的質(zhì)量不超過額定載質(zhì)量，即非負約束:每輛車裝載的貨物數(shù)量不可能為負數(shù)，即⑶配送車數(shù)量約束:參與配送的車輛數(shù)不小于貨物總質(zhì)量除以最大載質(zhì)量，即⑷訂單約束:最終訂單偏離原始訂單在一定容許范圍內(nèi)，從而保障零售商個體利益，即⑸載貨約束:參與配送的每輛車只為一個門店服務(wù)，若車輛k裝載了門店j1的貨物，則裝載其它門店貨物的數(shù)量就為零;反之則無任何約束，即配貨約束:配送的貨物必須滿足CDL制定的最終訂單，即整數(shù)約束:決策變量均為整數(shù)，即2自適應(yīng)遺傳算法設(shè)計上述模型決策變量數(shù)量龐大(1+IJ+KIJ，簡化后的維數(shù)為1+KIJ)，變量要求取整型實數(shù)值，目標函數(shù)和約束條件中包含決策變量的非線性函數(shù)，且存在隨機因素的影響.因此，該優(yōu)化問題是一個復(fù)雜的實數(shù)型數(shù)學(xué)規(guī)劃問題，采用常規(guī)的數(shù)學(xué)優(yōu)化算法很難求解.本文針對該模型的求解，設(shè)計了相應(yīng)的自適應(yīng)遺傳算法.為便于說明，對多目標隨機規(guī)劃模型中的貨物市場需求采用泊松隨機過程，即式中:入ij——門店j的貨物i在市場上單位時間的平均需求量.目標函數(shù)(1)可化簡為確定型目標：其它目標也轉(zhuǎn)化成相應(yīng)的確定型.2.1構(gòu)造染色體和初始種群由于優(yōu)化變量維數(shù)過高，如果采用二進制編碼，不僅編碼過長，占用較多計算機存儲空間，還會因算法計算量的增加，使算法的收斂速度降低，甚至無法接受.因此，用遺傳算法求解函數(shù)優(yōu)化問題時，一般必須考慮采用實數(shù)編碼技術(shù)，建立基于實數(shù)編碼的遺傳算法.用向量［x1x2…xl+KIJ］表示染色體G,其中x1為訂貨周期T,x2,x3，…，x1+KIJ為貨物裝載策略qkij(根據(jù)式(6),決策變量Qij用qkij統(tǒng)一表示，故無需編碼，這樣就同時將該約束的信息包含在內(nèi))，每條染色體代表一種可行方案，隨機產(chǎn)生一組非負整數(shù)的染色體G1,G2，…，Gu(這樣就把約束條件包含在內(nèi))，組成第一代種群(其中u為一代種群中的個體數(shù)).2.2設(shè)定適應(yīng)度函數(shù)為將模型目標函數(shù)的量綱統(tǒng)一化，并將有約束轉(zhuǎn)化為無約束，采用類似于外點法構(gòu)造懲罰函數(shù)的方法［12］,按照四大設(shè)計原則［13］設(shè)定正規(guī)化的多目標權(quán)重適應(yīng)度函數(shù)如下：其中:fsmax、fsmin——目標函數(shù)線性正規(guī)化過程中單目標條件下的最大值和最小值;M——很大的數(shù)，例如M=100000.經(jīng)驗權(quán)重ws為［0，1］區(qū)間的常數(shù)，表示決策者的目標偏好值，且滿足表明:當滿足約束條件時，指數(shù)項exp{?}為1,適應(yīng)度由目標函數(shù)值唯一地決定;反之，只要有—個不滿足約束條件，適應(yīng)度就會受到M的懲罰而趨于0；另外，式(17)使適應(yīng)度映射到［0,1］中的數(shù)，越接近1,適應(yīng)度越大，對應(yīng)的解就越趨于最優(yōu)解.對種群中每個染色體G1,G2，…，Gu,在滿足約束的情況下，求出相應(yīng)的可行解和目標函數(shù)值f1、f2和f3以及多目標權(quán)重適應(yīng)度函數(shù)f.2.3制定選擇策略采用比例選擇和精華模型相結(jié)合的選擇策略［14］，對每代種群的染色體按適應(yīng)度函數(shù)值排序.將適應(yīng)度最大的染色體復(fù)制后直接進入下一代，剩下的染色體用輪盤選擇法進入下一代種群中.這樣，首先保證最優(yōu)個體可以生存到下一代，既給了適應(yīng)度較大的個體更多機會進入下一代，又避免了個體之間因適應(yīng)值不同而被選入下一代的機會懸殊，使種群規(guī)模等于保留精華的個體數(shù)與交叉變異進入子代的個體數(shù)之和，維持種群規(guī)模的穩(wěn)定.2.4染色體交叉在每代種群中，采用改進的自適應(yīng)調(diào)整交叉率的方法［15］,對染色體進行中間重組取整(這里取整是為了使染色體始終滿足約束條件式(7)).子個體產(chǎn)生的方式如下：子個體=ent(父個體1+b(父個體2-父個體1)),b是一個隨機變動的比例因子，可由［-d,1+d］區(qū)間的均勻隨機數(shù)產(chǎn)生，一般選擇d=0.25.子代每個變量的值按該表達式計算，對每個變量要選擇一個新的b值，這樣就可以有效地避免早熟收斂現(xiàn)象.2.5染色體變異在產(chǎn)生子代的過程中按自適應(yīng)調(diào)整的變異率(這樣可提高群體中表現(xiàn)優(yōu)良的個體的變異率，使它們不會處于一種近似停滯不前的狀態(tài))采用如下變異算子，對每代種群進行染色體變異：式中:L―變量的取值范圍；X——變異前變量取值；X，——變異后變量取值；a(i)以概率1/v取1,以1-1/v取0,通常取v=20.2.6終止準則判斷是否收斂，若是，停止優(yōu)化，求出適應(yīng)度最大的染色體對應(yīng)的可行解作為優(yōu)化解；否則，重新設(shè)定迭代代數(shù)，繼續(xù)運行，直至收斂.3實例分析以某公司的CDL配送系統(tǒng)為例，統(tǒng)計分析各門店各種貨物的銷售情況，得出貨物市場需求為泊松過程，即各項參數(shù)為：根據(jù)前述自適應(yīng)遺傳算法的適應(yīng)度函數(shù)，該算法的編程求解需要對多目標隨機規(guī)劃模型中的3個目標函數(shù)歸一化處理，即在不考慮另夕卜兩個目標函數(shù)時求出各目標函數(shù)的最小值和最大值.用MATLAB優(yōu)化工具箱函數(shù)fmincon求得：根據(jù)自適應(yīng)遺傳算法,對以下兩種情況求解:最終訂單偏離原始訂單的最大容忍度Y=0.1，進行原始訂單分析處理;(2)y=0.0，不進行原始訂單分析處理.采用MATLAB編程求解，結(jié)果見表1.由表1可知，與原始訂單相比，經(jīng)過模型處理的最終訂單適應(yīng)度函數(shù)值、滿足隨機需求的置信水平、配送車輛滿載率分別增加了0.121、0.036、0.127;零售商全體門店平均每天的總成本降低631845元，降幅為13.73%；訂貨周期減少了1d.Y=0.1和Y=0.0兩種情況下的訂單對比如圖3所示.由圖3看出，最終訂單和原始訂單兩條曲線偏離很小，表明最終訂單接近原始訂單的要求.表1模型求解結(jié)果對比Tab.1Comparisonbetweentwosolutionsofthemodel進行原始訂單分析處理0.8530.5200.9783971335.0526不進行原始訂單分析處理0.7320.4840.8514603179.6397差值0.1210.0360.127631844.5871圖3初始訂單和最終訂單的對比Fig.3Comparisonbetweenoriginalordersandfinalorders4結(jié)束語為提高CDL系統(tǒng)對市場隨機需求的適應(yīng)性，彌補零售商門店只從自身利益出發(fā)制定原始訂單的缺陷，在充分考慮隨機需求、庫存策略、配貨限制和訂單要求等約束條件的情況下，從零售商總體利益出發(fā)，以提高最終訂單滿足隨機需求的置信水平、增加配送車輛滿載率和降低全體零售商總運營成本為目標函數(shù)，建立多目標隨機規(guī)劃模型，并設(shè)計了具有自適應(yīng)特點的遺傳算法.最后，將該模型和算法應(yīng)用到某汽車公司的CDL配送系統(tǒng)，利用MATLAB編程求解.結(jié)果表明，相對于原始訂單，該模型分析處理得到的最終訂單更適應(yīng)市場隨機需求，能大幅提高配送車輛滿載率，降低全體零售商門店平均成本，縮短訂貨周期，從而提高了總體效益;最終訂單能在很大程度上符合原始訂單的要求，保證零售商門店個體利益.本文模型和算法能夠較好地適應(yīng)市場隨機需求，兼顧局部利益和總體利益，為CDL系統(tǒng)的運營提供切實可行的指導(dǎo).由于模型有一些理想化的假設(shè)條件，如供應(yīng)商和CDL配送中心均擁有足夠的車輛、忽略貨物在CDL的倉儲成本，因此，對于考慮車輛資源、CDL倉儲成本等因素的優(yōu)化模型和算法，有待進一步研究.參考文獻：【相關(guān)文獻】LEEYH,JUNGJW,LEEKM.Vehicleroutingschedulingforcross-dockinginthesupplychain[J].ComputersandIndustrialEngineering,2006,51:247-256.WALLERMA,CASSADYCR,OZMENTJ.Impactofcross-dockingoninventoryinadecentralizedretailsupplychain[J].TransportationResearchPartE,2006,42:359-382.CHENF,SONGK.Minimizingmakespanintwo-stagehybridcrossdockingschedulingproblem[J].ComputersandOperationsResearch,2009,36(6):2066-2073.YUW,EGBELUPJ.Schedulingofinboundandoutboundtrucksincrossdockingsystemswithtemporarystorage[J].EuropeanJournalofOperationalResearch,2008,184:377-396.VISIFA,ROODBERGENKJ.Positioningofgoodsinacross-dockingenvironment[J].ComputersandIndustrialEngineering,2008,54:677-689.ROSSA,JAYARAMANV.Anevaluationofnewheuristicsforthelocationofcross-docksdistributioncentersinsupplychainnetworkdesign[J].ComputersandIndustrialEngineering,2008,55:64-79.CHENF,LEECY.