吳瑤

摘要： 對(duì)汽車零部件入廠物流循環(huán)取貨特點(diǎn)分析的基礎(chǔ)上，建立了有硬時(shí)間窗和容量約束的車輛路徑優(yōu)化模型，并采用改進(jìn)節(jié)約算法對(duì)該問(wèn)題進(jìn)行求解。通過(guò)算例驗(yàn)證，算法能獲得滿意解，且簡(jiǎn)明、操作性強(qiáng)。

關(guān)鍵詞： 零部件入廠物流；循環(huán)取貨；改進(jìn)節(jié)約算法

中圖分類號(hào)：U468 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2014）01-0023-02

0 引言

循環(huán)取貨（milk-run）模式作為汽車制造企業(yè)零部件集貨入廠的主要方式，它通常是由第三方物流企業(yè)（TPL）根據(jù)汽車制造商的生產(chǎn)計(jì)劃，按事先優(yōu)化好的路線到指定的多個(gè)供應(yīng)商處取貨，然后返回制造廠或區(qū)域分撥物流中心（RDC）。這種模式適合汽車零部件多品種、短周期、小批量、多頻次、準(zhǔn)時(shí)性供應(yīng)的特點(diǎn)，克服了供貨批量與頻次之間的矛盾。與傳統(tǒng)物料供應(yīng)相比，提高了物料供應(yīng)的敏捷性和柔韌性。在milk-run中，運(yùn)輸效率取決于車輛派遣和取貨的順序，屬于車輛路線問(wèn)題（VRP）[1]。國(guó)外已經(jīng)把VRP的研究成果應(yīng)用于milk-run中，國(guó)內(nèi)以上海通用為代表的汽車企業(yè)也嘗試使用VRP解決milk-run中車輛路線安排[2]。本文針對(duì)milk-run模式建立了時(shí)間窗和車輛能力約束的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)間的行駛時(shí)間，i，j∈N且i≠j。可支持RDC零部件集貨的規(guī)格相同容量為Q的車輛m輛，集合為K{k|1，2，…，m}，啟用的車輛均從RDC出發(fā)，在與供應(yīng)點(diǎn)約定的硬時(shí)間窗[ei，li]范圍內(nèi)到達(dá)取貨路徑上的每個(gè)供應(yīng)點(diǎn)，取貨完成后返回RDC。在時(shí)間點(diǎn)ei之前，提前到達(dá)供應(yīng)點(diǎn)的取貨車輛，因待交付的零部件可能尚未加工完成而無(wú)法裝載，等待會(huì)導(dǎo)致機(jī)會(huì)損失，因此車輛不可提前到達(dá)取貨點(diǎn)。在時(shí)間點(diǎn)li之后延遲到達(dá)的車輛，因錯(cuò)過(guò)供應(yīng)點(diǎn)的裝載服務(wù)時(shí)間，甚至可能會(huì)影響汽車制造企業(yè)的正常裝配計(jì)劃，因此車輛不可延遲到達(dá)供貨點(diǎn)。供應(yīng)點(diǎn)i的單次供貨數(shù)量為qi（qi？燮Q），裝貨時(shí)間為si，同一供貨點(diǎn)只能有一輛車前往取貨，車輛到達(dá)供貨點(diǎn)的時(shí)間為τi。在滿足車輛能力約束和取貨時(shí)間窗約束的情況下，建立以所有車輛取貨完成總時(shí)間最短為目標(biāo)的VRPTW模型。模型涉及的決策變量xijk表示為

目標(biāo)函數(shù)（1）為所有供貨點(diǎn)取貨完成車輛總時(shí)間最??；約束（2）表示啟動(dòng)車輛數(shù)量不超過(guò)車輛總數(shù)；約束（3）表示從RDC出發(fā)的車輛在完成取貨任務(wù)后必須返回RDC；約束（3）表示每個(gè)取貨點(diǎn)均有一輛車前往取貨；約束（4）為車輛路徑連續(xù)條件，即到達(dá)某供貨點(diǎn)的車輛數(shù)等于離開(kāi)該點(diǎn)的車輛數(shù)；約束（5）為車輛容量限制，即車輛集貨量不超過(guò)車輛容量；約束（6）為消除有子回路的路徑；約束（7）為車輛到達(dá)供應(yīng)點(diǎn)的時(shí)間表達(dá)式；約束（8）為車輛到達(dá)供應(yīng)點(diǎn)的時(shí)間窗約束；約束（9）、（10）為變量的整數(shù)性及非負(fù)性限制。

2 改進(jìn)節(jié)約算法

C-W節(jié)約算法[3]是一種常用的配送規(guī)劃近似算法，由Clark和Wright于1964年提出。其基本思想是在為每個(gè)客戶安排一輛車直接運(yùn)輸?shù)幕A(chǔ)上，依據(jù)運(yùn)輸距離減小幅度最大的原則，依次將運(yùn)輸中的兩個(gè)回路合并為一個(gè)回路。當(dāng)車輛達(dá)到容量限制后進(jìn)行下一輛車的優(yōu)化，最終使所有客戶的需求全部滿足。傳統(tǒng)的節(jié)約算法僅考慮運(yùn)輸距離，不考慮客戶時(shí)間窗和調(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ù)時(shí)，成本為Cij=c0i+cij+cj0，節(jié)約值為s（i，j）=ci0+c0j-cij。顯然，合并優(yōu)先級(jí)需按節(jié)約值從大到小依次排列。

2.3 改進(jìn)節(jié)約算法

Step1：計(jì)算供應(yīng)點(diǎn)對(duì)連接后的節(jié)約值s（i，j），并把節(jié)約值s（i，j）按從大到小排列，構(gòu)成集合Sdescend={s（i，j）|？坌i，j∈C}。

Step2：選擇集合Sdescend中的第一個(gè)元素s1（i，j），檢查其對(duì)應(yīng)連接邊（i，j）端點(diǎn)i，j是否在初始化路徑上，若是，則轉(zhuǎn)Step5，否則轉(zhuǎn)Step3。

Step3：檢查點(diǎn)i，j，是否其中一個(gè)在已構(gòu)成的路徑上且與RDC相連，另一個(gè)在初始化路徑上，若是，則轉(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)的裝載時(shí)間為0.5，車輛的平均行駛速度為45，承擔(dān)汽車零部件供應(yīng)任務(wù)的區(qū)域供應(yīng)商位置坐標(biāo)、供貨數(shù)量及取貨約定時(shí)間窗如表1所示。

采用本文所提的改進(jìn)節(jié)約算法，求得最優(yōu)實(shí)驗(yàn)結(jié)果如表2所示。

從計(jì)算結(jié)果可以看出，算法運(yùn)行結(jié)果滿足所有約束條件，可作為入廠物流循環(huán)取貨路徑安排的依據(jù)，具有一定的實(shí)用價(jià)值。

4 結(jié)論

本文以汽車零部件入廠物流為研究對(duì)象，分析了零部件循環(huán)取貨的特點(diǎn)，建立了基于硬時(shí)間窗和車輛容量約束的數(shù)學(xué)模型，構(gòu)建了改進(jìn)節(jié)約算法對(duì)該問(wèn)題進(jìn)行求解，最后通過(guò)算例驗(yàn)證了算法的可行性和有效性，為企業(yè)規(guī)劃循環(huán)取貨車輛路徑提供了參考。

參考文獻(xiàn)：

[1]Toth P， Vigo D. The Vehicle Routing Problem[M].Society for Industrial and Applied Mathematics， Philadelphia： SIAM， 2002.

[2]葉雷.循環(huán)取料在上海通用汽車零部件入廠物流中的應(yīng)用研究[D].上海：復(fù)旦大學(xué)，2005.

[3]G.Clarke， J. W. Wright. scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research， 1963， 11：568-581.

[4]張建勇，郭耀煌，李軍.一種具有模糊費(fèi)用系數(shù)的VSP的修正C-W節(jié)約算法[J].西南交通大學(xué)學(xué)報(bào)，2004，6（3）：281-284.endprint

摘要： 對(duì)汽車零部件入廠物流循環(huán)取貨特點(diǎn)分析的基礎(chǔ)上，建立了有硬時(shí)間窗和容量約束的車輛路徑優(yōu)化模型，并采用改進(jìn)節(jié)約算法對(duì)該問(wèn)題進(jìn)行求解。通過(guò)算例驗(yàn)證，算法能獲得滿意解，且簡(jiǎn)明、操作性強(qiáng)。

關(guān)鍵詞： 零部件入廠物流；循環(huán)取貨；改進(jìn)節(jié)約算法

中圖分類號(hào)：U468 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2014）01-0023-02

0 引言

循環(huán)取貨（milk-run）模式作為汽車制造企業(yè)零部件集貨入廠的主要方式，它通常是由第三方物流企業(yè)（TPL）根據(jù)汽車制造商的生產(chǎn)計(jì)劃，按事先優(yōu)化好的路線到指定的多個(gè)供應(yīng)商處取貨，然后返回制造廠或區(qū)域分撥物流中心（RDC）。這種模式適合汽車零部件多品種、短周期、小批量、多頻次、準(zhǔn)時(shí)性供應(yīng)的特點(diǎn)，克服了供貨批量與頻次之間的矛盾。與傳統(tǒng)物料供應(yīng)相比，提高了物料供應(yīng)的敏捷性和柔韌性。在milk-run中，運(yùn)輸效率取決于車輛派遣和取貨的順序，屬于車輛路線問(wèn)題（VRP）[1]。國(guó)外已經(jīng)把VRP的研究成果應(yīng)用于milk-run中，國(guó)內(nèi)以上海通用為代表的汽車企業(yè)也嘗試使用VRP解決milk-run中車輛路線安排[2]。本文針對(duì)milk-run模式建立了時(shí)間窗和車輛能力約束的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ò)中弧（i，j）的權(quán)重，表示網(wǎng)絡(luò)節(jié)點(diǎn)間的行駛時(shí)間，i，j∈N且i≠j?？芍С諶DC零部件集貨的規(guī)格相同容量為Q的車輛m輛，集合為K{k|1，2，…，m}，啟用的車輛均從RDC出發(fā)，在與供應(yīng)點(diǎn)約定的硬時(shí)間窗[ei，li]范圍內(nèi)到達(dá)取貨路徑上的每個(gè)供應(yīng)點(diǎn)，取貨完成后返回RDC。在時(shí)間點(diǎn)ei之前，提前到達(dá)供應(yīng)點(diǎn)的取貨車輛，因待交付的零部件可能尚未加工完成而無(wú)法裝載，等待會(huì)導(dǎo)致機(jī)會(huì)損失，因此車輛不可提前到達(dá)取貨點(diǎn)。在時(shí)間點(diǎn)li之后延遲到達(dá)的車輛，因錯(cuò)過(guò)供應(yīng)點(diǎn)的裝載服務(wù)時(shí)間，甚至可能會(huì)影響汽車制造企業(yè)的正常裝配計(jì)劃，因此車輛不可延遲到達(dá)供貨點(diǎn)。供應(yīng)點(diǎn)i的單次供貨數(shù)量為qi（qi？燮Q），裝貨時(shí)間為si，同一供貨點(diǎn)只能有一輛車前往取貨，車輛到達(dá)供貨點(diǎn)的時(shí)間為τi。在滿足車輛能力約束和取貨時(shí)間窗約束的情況下，建立以所有車輛取貨完成總時(shí)間最短為目標(biāo)的VRPTW模型。模型涉及的決策變量xijk表示為

目標(biāo)函數(shù)（1）為所有供貨點(diǎn)取貨完成車輛總時(shí)間最?。患s束（2）表示啟動(dòng)車輛數(shù)量不超過(guò)車輛總數(shù)；約束（3）表示從RDC出發(fā)的車輛在完成取貨任務(wù)后必須返回RDC；約束（3）表示每個(gè)取貨點(diǎn)均有一輛車前往取貨；約束（4）為車輛路徑連續(xù)條件，即到達(dá)某供貨點(diǎn)的車輛數(shù)等于離開(kāi)該點(diǎn)的車輛數(shù)；約束（5）為車輛容量限制，即車輛集貨量不超過(guò)車輛容量；約束（6）為消除有子回路的路徑；約束（7）為車輛到達(dá)供應(yīng)點(diǎn)的時(shí)間表達(dá)式；約束（8）為車輛到達(dá)供應(yīng)點(diǎn)的時(shí)間窗約束；約束（9）、（10）為變量的整數(shù)性及非負(fù)性限制。

2 改進(jìn)節(jié)約算法

C-W節(jié)約算法[3]是一種常用的配送規(guī)劃近似算法，由Clark和Wright于1964年提出。其基本思想是在為每個(gè)客戶安排一輛車直接運(yùn)輸?shù)幕A(chǔ)上，依據(jù)運(yùn)輸距離減小幅度最大的原則，依次將運(yùn)輸中的兩個(gè)回路合并為一個(gè)回路。當(dāng)車輛達(dá)到容量限制后進(jìn)行下一輛車的優(yōu)化，最終使所有客戶的需求全部滿足。傳統(tǒng)的節(jié)約算法僅考慮運(yùn)輸距離，不考慮客戶時(shí)間窗和調(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ù)時(shí)，成本為Cij=c0i+cij+cj0，節(jié)約值為s（i，j）=ci0+c0j-cij。顯然，合并優(yōu)先級(jí)需按節(jié)約值從大到小依次排列。

2.3 改進(jìn)節(jié)約算法

Step1：計(jì)算供應(yīng)點(diǎn)對(duì)連接后的節(jié)約值s（i，j），并把節(jié)約值s（i，j）按從大到小排列，構(gòu)成集合Sdescend={s（i，j）|？坌i，j∈C}。

Step2：選擇集合Sdescend中的第一個(gè)元素s1（i，j），檢查其對(duì)應(yīng)連接邊（i，j）端點(diǎn)i，j是否在初始化路徑上，若是，則轉(zhuǎn)Step5，否則轉(zhuǎn)Step3。

Step3：檢查點(diǎn)i，j，是否其中一個(gè)在已構(gòu)成的路徑上且與RDC相連，另一個(gè)在初始化路徑上，若是，則轉(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)的裝載時(shí)間為0.5，車輛的平均行駛速度為45，承擔(dān)汽車零部件供應(yīng)任務(wù)的區(qū)域供應(yīng)商位置坐標(biāo)、供貨數(shù)量及取貨約定時(shí)間窗如表1所示。

采用本文所提的改進(jìn)節(jié)約算法，求得最優(yōu)實(shí)驗(yàn)結(jié)果如表2所示。

從計(jì)算結(jié)果可以看出，算法運(yùn)行結(jié)果滿足所有約束條件，可作為入廠物流循環(huán)取貨路徑安排的依據(jù)，具有一定的實(shí)用價(jià)值。

4 結(jié)論

本文以汽車零部件入廠物流為研究對(duì)象，分析了零部件循環(huán)取貨的特點(diǎn)，建立了基于硬時(shí)間窗和車輛容量約束的數(shù)學(xué)模型，構(gòu)建了改進(jìn)節(jié)約算法對(duì)該問(wèn)題進(jìn)行求解，最后通過(guò)算例驗(yàn)證了算法的可行性和有效性，為企業(yè)規(guī)劃循環(huán)取貨車輛路徑提供了參考。

參考文獻(xiàn)：

[1]Toth P， Vigo D. The Vehicle Routing Problem[M].Society for Industrial and Applied Mathematics， Philadelphia： SIAM， 2002.

[2]葉雷.循環(huán)取料在上海通用汽車零部件入廠物流中的應(yīng)用研究[D].上海：復(fù)旦大學(xué)，2005.

[3]G.Clarke， J. W. Wright. scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research， 1963， 11：568-581.

[4]張建勇，郭耀煌，李軍.一種具有模糊費(fèi)用系數(shù)的VSP的修正C-W節(jié)約算法[J].西南交通大學(xué)學(xué)報(bào)，2004，6（3）：281-284.endprint

摘要： 對(duì)汽車零部件入廠物流循環(huán)取貨特點(diǎn)分析的基礎(chǔ)上，建立了有硬時(shí)間窗和容量約束的車輛路徑優(yōu)化模型，并采用改進(jìn)節(jié)約算法對(duì)該問(wèn)題進(jìn)行求解。通過(guò)算例驗(yàn)證，算法能獲得滿意解，且簡(jiǎn)明、操作性強(qiáng)。

關(guān)鍵詞： 零部件入廠物流；循環(huán)取貨；改進(jìn)節(jié)約算法

中圖分類號(hào)：U468 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2014）01-0023-02

0 引言

循環(huán)取貨（milk-run）模式作為汽車制造企業(yè)零部件集貨入廠的主要方式，它通常是由第三方物流企業(yè)（TPL）根據(jù)汽車制造商的生產(chǎn)計(jì)劃，按事先優(yōu)化好的路線到指定的多個(gè)供應(yīng)商處取貨，然后返回制造廠或區(qū)域分撥物流中心（RDC）。這種模式適合汽車零部件多品種、短周期、小批量、多頻次、準(zhǔn)時(shí)性供應(yīng)的特點(diǎn)，克服了供貨批量與頻次之間的矛盾。與傳統(tǒng)物料供應(yīng)相比，提高了物料供應(yīng)的敏捷性和柔韌性。在milk-run中，運(yùn)輸效率取決于車輛派遣和取貨的順序，屬于車輛路線問(wèn)題（VRP）[1]。國(guó)外已經(jīng)把VRP的研究成果應(yīng)用于milk-run中，國(guó)內(nèi)以上海通用為代表的汽車企業(yè)也嘗試使用VRP解決milk-run中車輛路線安排[2]。本文針對(duì)milk-run模式建立了時(shí)間窗和車輛能力約束的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)間的行駛時(shí)間，i，j∈N且i≠j?？芍С諶DC零部件集貨的規(guī)格相同容量為Q的車輛m輛，集合為K{k|1，2，…，m}，啟用的車輛均從RDC出發(fā)，在與供應(yīng)點(diǎn)約定的硬時(shí)間窗[ei，li]范圍內(nèi)到達(dá)取貨路徑上的每個(gè)供應(yīng)點(diǎn)，取貨完成后返回RDC。在時(shí)間點(diǎn)ei之前，提前到達(dá)供應(yīng)點(diǎn)的取貨車輛，因待交付的零部件可能尚未加工完成而無(wú)法裝載，等待會(huì)導(dǎo)致機(jī)會(huì)損失，因此車輛不可提前到達(dá)取貨點(diǎn)。在時(shí)間點(diǎn)li之后延遲到達(dá)的車輛，因錯(cuò)過(guò)供應(yīng)點(diǎn)的裝載服務(wù)時(shí)間，甚至可能會(huì)影響汽車制造企業(yè)的正常裝配計(jì)劃，因此車輛不可延遲到達(dá)供貨點(diǎn)。供應(yīng)點(diǎn)i的單次供貨數(shù)量為qi（qi？燮Q），裝貨時(shí)間為si，同一供貨點(diǎn)只能有一輛車前往取貨，車輛到達(dá)供貨點(diǎn)的時(shí)間為τi。在滿足車輛能力約束和取貨時(shí)間窗約束的情況下，建立以所有車輛取貨完成總時(shí)間最短為目標(biāo)的VRPTW模型。模型涉及的決策變量xijk表示為

目標(biāo)函數(shù)（1）為所有供貨點(diǎn)取貨完成車輛總時(shí)間最?。患s束（2）表示啟動(dòng)車輛數(shù)量不超過(guò)車輛總數(shù)；約束（3）表示從RDC出發(fā)的車輛在完成取貨任務(wù)后必須返回RDC；約束（3）表示每個(gè)取貨點(diǎn)均有一輛車前往取貨；約束（4）為車輛路徑連續(xù)條件，即到達(dá)某供貨點(diǎn)的車輛數(shù)等于離開(kāi)該點(diǎn)的車輛數(shù)；約束（5）為車輛容量限制，即車輛集貨量不超過(guò)車輛容量；約束（6）為消除有子回路的路徑；約束（7）為車輛到達(dá)供應(yīng)點(diǎn)的時(shí)間表達(dá)式；約束（8）為車輛到達(dá)供應(yīng)點(diǎn)的時(shí)間窗約束；約束（9）、（10）為變量的整數(shù)性及非負(fù)性限制。

2 改進(jìn)節(jié)約算法

C-W節(jié)約算法[3]是一種常用的配送規(guī)劃近似算法，由Clark和Wright于1964年提出。其基本思想是在為每個(gè)客戶安排一輛車直接運(yùn)輸?shù)幕A(chǔ)上，依據(jù)運(yùn)輸距離減小幅度最大的原則，依次將運(yùn)輸中的兩個(gè)回路合并為一個(gè)回路。當(dāng)車輛達(dá)到容量限制后進(jìn)行下一輛車的優(yōu)化，最終使所有客戶的需求全部滿足。傳統(tǒng)的節(jié)約算法僅考慮運(yùn)輸距離，不考慮客戶時(shí)間窗和調(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ù)時(shí)，成本為Cij=c0i+cij+cj0，節(jié)約值為s（i，j）=ci0+c0j-cij。顯然，合并優(yōu)先級(jí)需按節(jié)約值從大到小依次排列。

2.3 改進(jìn)節(jié)約算法

Step1：計(jì)算供應(yīng)點(diǎn)對(duì)連接后的節(jié)約值s（i，j），并把節(jié)約值s（i，j）按從大到小排列，構(gòu)成集合Sdescend={s（i，j）|？坌i，j∈C}。

Step2：選擇集合Sdescend中的第一個(gè)元素s1（i，j），檢查其對(duì)應(yīng)連接邊（i，j）端點(diǎn)i，j是否在初始化路徑上，若是，則轉(zhuǎn)Step5，否則轉(zhuǎn)Step3。

Step3：檢查點(diǎn)i，j，是否其中一個(gè)在已構(gòu)成的路徑上且與RDC相連，另一個(gè)在初始化路徑上，若是，則轉(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)的裝載時(shí)間為0.5，車輛的平均行駛速度為45，承擔(dān)汽車零部件供應(yīng)任務(wù)的區(qū)域供應(yīng)商位置坐標(biāo)、供貨數(shù)量及取貨約定時(shí)間窗如表1所示。

采用本文所提的改進(jìn)節(jié)約算法，求得最優(yōu)實(shí)驗(yàn)結(jié)果如表2所示。

從計(jì)算結(jié)果可以看出，算法運(yùn)行結(jié)果滿足所有約束條件，可作為入廠物流循環(huán)取貨路徑安排的依據(jù)，具有一定的實(shí)用價(jià)值。

4 結(jié)論

本文以汽車零部件入廠物流為研究對(duì)象，分析了零部件循環(huán)取貨的特點(diǎn)，建立了基于硬時(shí)間窗和車輛容量約束的數(shù)學(xué)模型，構(gòu)建了改進(jìn)節(jié)約算法對(duì)該問(wèn)題進(jìn)行求解，最后通過(guò)算例驗(yàn)證了算法的可行性和有效性，為企業(yè)規(guī)劃循環(huán)取貨車輛路徑提供了參考。

參考文獻(xiàn)：

[1]Toth P， Vigo D. The Vehicle Routing Problem[M].Society for Industrial and Applied Mathematics， Philadelphia： SIAM， 2002.

[2]葉雷.循環(huán)取料在上海通用汽車零部件入廠物流中的應(yīng)用研究[D].上海：復(fù)旦大學(xué)，2005.

[3]G.Clarke， J. W. Wright. scheduling of vehicles from a central depot to a number of delivery points [J]. Operations Research， 1963， 11：568-581.

[4]張建勇，郭耀煌，李軍.一種具有模糊費(fèi)用系數(shù)的VSP的修正C-W節(jié)約算法[J].西南交通大學(xué)學(xué)報(bào)，2004，6（3）：281-284.endprint