基于3PL的汽車零部件循環(huán)取貨路徑研究

 循環(huán)取貨（milk-run）模式作為汽車制造企業(yè)零部件集貨入廠的主要方式，它通常是由第三方物流企業(yè)（TPL）根據(jù)汽車制造商的生產(chǎn)計(jì)劃，按事先優(yōu)化好的路線到指定的多個供應(yīng)商處取貨，然后返回制造廠或區(qū)域分撥物流中心（RDC）。這種模式適合汽車零部件多品種、短周期、小批量、多頻次、準(zhǔn)時性供應(yīng)的特點(diǎn)，克服了供貨批量與頻次之間的矛盾。與傳統(tǒng)物料供應(yīng)相比，提高了物料供應(yīng)的敏捷性和柔韌性。在milk-run中，運(yùn)輸效率取決于車輛派遣和取貨的順序，屬于車輛路線問題（VRP）[1]。國外已經(jīng)把VRP的研究成果應(yīng)用于milk-run中，國內(nèi)以上海通用為代表的汽車企業(yè)也嘗試使用VRP解決milk-run中車輛路線安排[2]。本文針對milk-run模式建立了時間窗和車輛能力約束的VRP模型，并采用改進(jìn)節(jié)約算法進(jìn)行優(yōu)化求解。
1 模型建立
在零部件供應(yīng)商和RDC構(gòu)成的物流網(wǎng)絡(luò)中，C{i|1，2，…，n}表示供貨點(diǎn)集合，0表示RDC，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)用N=C∪{0}表示。cij為網(wǎng)絡(luò)中?。╥，j）的權(quán)重，表示網(wǎng)絡(luò)節(jié)點(diǎn)間的行駛時間，i，j∈N且i≠j?？芍С諶DC零部件集貨的規(guī)格相同容量為Q的車輛m輛，集合為K{k|1，2，…，m}，啟用的車輛均從RDC出發(fā)，在與供應(yīng)點(diǎn)約定的硬時間窗[ei，li]范圍內(nèi)到達(dá)取貨路徑上的每個供應(yīng)點(diǎn)，取貨完成后返回RDC。在時間點(diǎn)ei之前，提前到達(dá)供應(yīng)點(diǎn)的取貨車輛，因待交付的零部件可能尚未加工完成而無法裝載，等待會導(dǎo)致機(jī)會損失，因此車輛不可提前到達(dá)取貨點(diǎn)。在時間點(diǎn)li之后延遲到達(dá)的車輛，因錯過供應(yīng)點(diǎn)的裝載服務(wù)時間，甚至可能會影響汽車制造企業(yè)的正常裝配計(jì)劃，因此車輛不可延遲到達(dá)供貨點(diǎn)。供應(yīng)點(diǎn)i的單次供貨數(shù)量為qi（qi？燮Q），裝貨時間為si，同一供貨點(diǎn)只能有一輛車前往取貨，車輛到達(dá)供貨點(diǎn)的時間為τi。在滿足車輛能力約束和取貨時間窗約束的情況下，建立以所有車輛取貨完成總時間最短為目標(biāo)的VRPTW模型。模型涉及的決策變量xijk表示為
目標(biāo)函數(shù)（1）為所有供貨點(diǎn)取貨完成車輛總時間最??；約束（2）表示啟動車輛數(shù)量不超過車輛總數(shù)；約束（3）表示從RDC出發(fā)的車輛在完成取貨任務(wù)后必須返回RDC；約束（3）表示每個取貨點(diǎn)均有一輛車前往取貨；約束（4）為車輛路徑連續(xù)條件，即到達(dá)某供貨點(diǎn)的車輛數(shù)等于離開該點(diǎn)的車輛數(shù)；約束（5）為車輛容量限制，即車輛集貨量不超過車輛容量；約束（6）為消除有子回路的路徑；約束（7）為車輛到達(dá)供應(yīng)點(diǎn)的時間表達(dá)式；約束（8）為車輛到達(dá)供應(yīng)點(diǎn)的時間窗約束；約束（9）、（10）為變量的整數(shù)性及非負(fù)性限制。
2 改進(jìn)節(jié)約算法
C-W節(jié)約算法[3]是一種常用的配送規(guī)劃近似算法，由Clark和Wright于1964年提出。其基本思想是在為每個客戶安排一輛車直接運(yùn)輸?shù)幕A(chǔ)上，依據(jù)運(yùn)輸距離減小幅度最大的原則，依次將運(yùn)輸中的兩個回路合并為一個回路。當(dāng)車輛達(dá)到容量限制后進(jìn)行下一輛車的優(yōu)化，最終使所有客戶的需求全部滿足。傳統(tǒng)的節(jié)約算法僅考慮運(yùn)輸距離，不考慮客戶時間窗和調(diào)用車輛數(shù)量。
2.1 節(jié)約值的計(jì)算 此處節(jié)約值為運(yùn)輸距離的節(jié)約值。配送中心“0”與各供應(yīng)點(diǎn)i∈C直接相連，構(gòu)成n條“0→i→0”初始路線，第i條線路的運(yùn)輸費(fèi)用為Ci=c0i+ci0。當(dāng)?shù)趇，j兩條路線合并，即由同一輛車按路線“0→i→j→0”為其服務(wù)時，成本為Cij=c0i+cij+cj0，節(jié)約值為s（i，j）=ci0+c0j-cij。顯然，合并優(yōu)先級需按節(jié)約值從大到小依次排列。
2.3 改進(jìn)節(jié)約算法
Step1：計(jì)算供應(yīng)點(diǎn)對連接后的節(jié)約值s（i，j），并把節(jié)約值s（i，j）按從大到小排列，構(gòu)成集合Sdescend={s（i，j）|？坌i，j∈C}。
Step2：選擇集合Sdescend中的第一個元素s1（i，j），檢查其對應(yīng)連接邊（i，j）端點(diǎn)i，j是否在初始化路徑上，若是，則轉(zhuǎn)Step5，否則轉(zhuǎn)Step3。
Step3：檢查點(diǎn)i，j，是否其中一個在已構(gòu)成的路徑上且與RDC相連，另一個在初始化路徑上，若是，則轉(zhuǎn)Step5，否則轉(zhuǎn)Step4。
Step4：檢查點(diǎn)i，j，是否分別在不同的已構(gòu)成路徑上，且均與RDC相連。若是，則轉(zhuǎn)Step5，否則轉(zhuǎn)Step7。
Step5：若連接點(diǎn)i，j，把點(diǎn)i，j原所在的不同路徑合并成一條路徑，合并后的路徑總?cè)∝浟縬■？燮Q，則轉(zhuǎn)Step6，否則轉(zhuǎn)Step7。
Step7：Sdescend=Sdescend＼s1（i，j），檢查Sdescend若為空，則算法結(jié)束，否則轉(zhuǎn)Step2。
3 算例分析
負(fù)責(zé)某汽車制造商入廠物流的第三方物流企業(yè)，現(xiàn)已知擁有統(tǒng)一容量為20單位的車輛若干輛，車輛在各供應(yīng)點(diǎn)的裝載時間為0.5，車輛的平均行駛速度為45，承擔(dān)汽車零部件供應(yīng)任務(wù)的區(qū)域供應(yīng)商位置坐標(biāo)、供貨數(shù)量及取貨約定時間窗如表1所示。
采用本文所提的改進(jìn)節(jié)約算法，求得最優(yōu)實(shí)驗(yàn)結(jié)果如表2所示。
從計(jì)算結(jié)果可以看出，算法運(yùn)行結(jié)果滿足所有約束條件，可作為入廠物流循環(huán)取貨路徑安排的依據(jù)，具有一定的實(shí)用價(jià)值。
4 結(jié)論
本文以汽車零部件入廠物流為研究對象，分析了零部件循環(huán)取貨的特點(diǎn)，建立了基于硬時間窗和車輛容量約束的數(shù)學(xué)模型，構(gòu)建了改進(jìn)節(jié)約算法對該問題進(jìn)行求解，最后通過算例驗(yàn)證了算法的可行性和有效性，為企業(yè)規(guī)劃循環(huán)取貨車輛路徑提供了參考。