吳瑤

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

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

中圖分類號：U468 文獻標識碼：A 文章編號：1006-4311（2014）01-0023-02

0 引言

循環(huán)取貨（milk-run）模式作為汽車制造企業(yè)零部件集貨入廠的主要方式，它通常是由第三方物流企業(yè)（TPL）根據汽車制造商的生產計劃，按事先優(yōu)化好的路線到指定的多個供應商處取貨，然后返回制造廠或區(qū)域分撥物流中心（RDC）。這種模式適合汽車零部件多品種、短周期、小批量、多頻次、準時性供應的特點，克服了供貨批量與頻次之間的矛盾。與傳統物料供應相比，提高了物料供應的敏捷性和柔韌性。在milk-run中，運輸效率取決于車輛派遣和取貨的順序，屬于車輛路線問題（VRP）[1]。國外已經把VRP的研究成果應用于milk-run中，國內以上海通用為代表的汽車企業(yè)也嘗試使用VRP解決milk-run中車輛路線安排[2]。本文針對milk-run模式建立了時間窗和車輛能力約束的VRP模型，并采用改進節(jié)約算法進行優(yōu)化求解。

1 模型建立

在零部件供應商和RDC構成的物流網絡中，C{i|1，2，…，n}表示供貨點集合，0表示RDC，網絡中的所有節(jié)點用N=C∪{0}表示。cij為網絡中?。╥，j）的權重，表示網絡節(jié)點間的行駛時間，i，j∈N且i≠j?？芍С諶DC零部件集貨的規(guī)格相同容量為Q的車輛m輛，集合為K{k|1，2，…，m}，啟用的車輛均從RDC出發(fā)，在與供應點約定的硬時間窗[ei，li]范圍內到達取貨路徑上的每個供應點，取貨完成后返回RDC。在時間點ei之前，提前到達供應點的取貨車輛，因待交付的零部件可能尚未加工完成而無法裝載，等待會導致機會損失，因此車輛不可提前到達取貨點。在時間點li之后延遲到達的車輛，因錯過供應點的裝載服務時間，甚至可能會影響汽車制造企業(yè)的正常裝配計劃，因此車輛不可延遲到達供貨點。供應點i的單次供貨數量為qi（qi？燮Q），裝貨時間為si，同一供貨點只能有一輛車前往取貨，車輛到達供貨點的時間為τi。在滿足車輛能力約束和取貨時間窗約束的情況下，建立以所有車輛取貨完成總時間最短為目標的VRPTW模型。模型涉及的決策變量xijk表示為

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

2 改進節(jié)約算法

C-W節(jié)約算法[3]是一種常用的配送規(guī)劃近似算法，由Clark和Wright于1964年提出。其基本思想是在為每個客戶安排一輛車直接運輸的基礎上，依據運輸距離減小幅度最大的原則，依次將運輸中的兩個回路合并為一個回路。當車輛達到容量限制后進行下一輛車的優(yōu)化，最終使所有客戶的需求全部滿足。傳統的節(jié)約算法僅考慮運輸距離，不考慮客戶時間窗和調用車輛數量。

2.1 節(jié)約值的計算 此處節(jié)約值為運輸距離的節(jié)約值。配送中心“0”與各供應點i∈C直接相連，構成n條“0→i→0”初始路線，第i條線路的運輸費用為Ci=c0i+ci0。當第i，j兩條路線合并，即由同一輛車按路線“0→i→j→0”為其服務時，成本為Cij=c0i+cij+cj0，節(jié)約值為s（i，j）=ci0+c0j-cij。顯然，合并優(yōu)先級需按節(jié)約值從大到小依次排列。

2.3 改進節(jié)約算法

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

Step2：選擇集合Sdescend中的第一個元素s1（i，j），檢查其對應連接邊（i，j）端點i，j是否在初始化路徑上，若是，則轉Step5，否則轉Step3。

Step3：檢查點i，j，是否其中一個在已構成的路徑上且與RDC相連，另一個在初始化路徑上，若是，則轉Step5，否則轉Step4。

Step4：檢查點i，j，是否分別在不同的已構成路徑上，且均與RDC相連。若是，則轉Step5，否則轉Step7。

Step5：若連接點i，j，把點i，j原所在的不同路徑合并成一條路徑，合并后的路徑總取貨量q■？燮Q，則轉Step6，否則轉Step7。

Step7：Sdescend=Sdescend＼s1（i，j），檢查Sdescend若為空，則算法結束，否則轉Step2。

3 算例分析

負責某汽車制造商入廠物流的第三方物流企業(yè)，現已知擁有統一容量為20單位的車輛若干輛，車輛在各供應點的裝載時間為0.5，車輛的平均行駛速度為45，承擔汽車零部件供應任務的區(qū)域供應商位置坐標、供貨數量及取貨約定時間窗如表1所示。

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

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

4 結論

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

參考文獻：

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

[2]葉雷.循環(huán)取料在上海通用汽車零部件入廠物流中的應用研究[D].上海：復旦大學，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]張建勇，郭耀煌，李軍.一種具有模糊費用系數的VSP的修正C-W節(jié)約算法[J].西南交通大學學報，2004，6（3）：281-284.endprint

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

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

中圖分類號：U468 文獻標識碼：A 文章編號：1006-4311（2014）01-0023-02

0 引言

循環(huán)取貨（milk-run）模式作為汽車制造企業(yè)零部件集貨入廠的主要方式，它通常是由第三方物流企業(yè)（TPL）根據汽車制造商的生產計劃，按事先優(yōu)化好的路線到指定的多個供應商處取貨，然后返回制造廠或區(qū)域分撥物流中心（RDC）。這種模式適合汽車零部件多品種、短周期、小批量、多頻次、準時性供應的特點，克服了供貨批量與頻次之間的矛盾。與傳統物料供應相比，提高了物料供應的敏捷性和柔韌性。在milk-run中，運輸效率取決于車輛派遣和取貨的順序，屬于車輛路線問題（VRP）[1]。國外已經把VRP的研究成果應用于milk-run中，國內以上海通用為代表的汽車企業(yè)也嘗試使用VRP解決milk-run中車輛路線安排[2]。本文針對milk-run模式建立了時間窗和車輛能力約束的VRP模型，并采用改進節(jié)約算法進行優(yōu)化求解。

1 模型建立

在零部件供應商和RDC構成的物流網絡中，C{i|1，2，…，n}表示供貨點集合，0表示RDC，網絡中的所有節(jié)點用N=C∪{0}表示。cij為網絡中?。╥，j）的權重，表示網絡節(jié)點間的行駛時間，i，j∈N且i≠j?？芍С諶DC零部件集貨的規(guī)格相同容量為Q的車輛m輛，集合為K{k|1，2，…，m}，啟用的車輛均從RDC出發(fā)，在與供應點約定的硬時間窗[ei，li]范圍內到達取貨路徑上的每個供應點，取貨完成后返回RDC。在時間點ei之前，提前到達供應點的取貨車輛，因待交付的零部件可能尚未加工完成而無法裝載，等待會導致機會損失，因此車輛不可提前到達取貨點。在時間點li之后延遲到達的車輛，因錯過供應點的裝載服務時間，甚至可能會影響汽車制造企業(yè)的正常裝配計劃，因此車輛不可延遲到達供貨點。供應點i的單次供貨數量為qi（qi？燮Q），裝貨時間為si，同一供貨點只能有一輛車前往取貨，車輛到達供貨點的時間為τi。在滿足車輛能力約束和取貨時間窗約束的情況下，建立以所有車輛取貨完成總時間最短為目標的VRPTW模型。模型涉及的決策變量xijk表示為

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

2 改進節(jié)約算法

C-W節(jié)約算法[3]是一種常用的配送規(guī)劃近似算法，由Clark和Wright于1964年提出。其基本思想是在為每個客戶安排一輛車直接運輸的基礎上，依據運輸距離減小幅度最大的原則，依次將運輸中的兩個回路合并為一個回路。當車輛達到容量限制后進行下一輛車的優(yōu)化，最終使所有客戶的需求全部滿足。傳統的節(jié)約算法僅考慮運輸距離，不考慮客戶時間窗和調用車輛數量。

2.1 節(jié)約值的計算 此處節(jié)約值為運輸距離的節(jié)約值。配送中心“0”與各供應點i∈C直接相連，構成n條“0→i→0”初始路線，第i條線路的運輸費用為Ci=c0i+ci0。當第i，j兩條路線合并，即由同一輛車按路線“0→i→j→0”為其服務時，成本為Cij=c0i+cij+cj0，節(jié)約值為s（i，j）=ci0+c0j-cij。顯然，合并優(yōu)先級需按節(jié)約值從大到小依次排列。

2.3 改進節(jié)約算法

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

Step2：選擇集合Sdescend中的第一個元素s1（i，j），檢查其對應連接邊（i，j）端點i，j是否在初始化路徑上，若是，則轉Step5，否則轉Step3。

Step3：檢查點i，j，是否其中一個在已構成的路徑上且與RDC相連，另一個在初始化路徑上，若是，則轉Step5，否則轉Step4。

Step4：檢查點i，j，是否分別在不同的已構成路徑上，且均與RDC相連。若是，則轉Step5，否則轉Step7。

Step5：若連接點i，j，把點i，j原所在的不同路徑合并成一條路徑，合并后的路徑總取貨量q■？燮Q，則轉Step6，否則轉Step7。

Step7：Sdescend=Sdescend＼s1（i，j），檢查Sdescend若為空，則算法結束，否則轉Step2。

3 算例分析

負責某汽車制造商入廠物流的第三方物流企業(yè)，現已知擁有統一容量為20單位的車輛若干輛，車輛在各供應點的裝載時間為0.5，車輛的平均行駛速度為45，承擔汽車零部件供應任務的區(qū)域供應商位置坐標、供貨數量及取貨約定時間窗如表1所示。

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

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

4 結論

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

參考文獻：

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

[2]葉雷.循環(huán)取料在上海通用汽車零部件入廠物流中的應用研究[D].上海：復旦大學，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]張建勇，郭耀煌，李軍.一種具有模糊費用系數的VSP的修正C-W節(jié)約算法[J].西南交通大學學報，2004，6（3）：281-284.endprint

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

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

中圖分類號：U468 文獻標識碼：A 文章編號：1006-4311（2014）01-0023-02

0 引言

循環(huán)取貨（milk-run）模式作為汽車制造企業(yè)零部件集貨入廠的主要方式，它通常是由第三方物流企業(yè)（TPL）根據汽車制造商的生產計劃，按事先優(yōu)化好的路線到指定的多個供應商處取貨，然后返回制造廠或區(qū)域分撥物流中心（RDC）。這種模式適合汽車零部件多品種、短周期、小批量、多頻次、準時性供應的特點，克服了供貨批量與頻次之間的矛盾。與傳統物料供應相比，提高了物料供應的敏捷性和柔韌性。在milk-run中，運輸效率取決于車輛派遣和取貨的順序，屬于車輛路線問題（VRP）[1]。國外已經把VRP的研究成果應用于milk-run中，國內以上海通用為代表的汽車企業(yè)也嘗試使用VRP解決milk-run中車輛路線安排[2]。本文針對milk-run模式建立了時間窗和車輛能力約束的VRP模型，并采用改進節(jié)約算法進行優(yōu)化求解。

1 模型建立

在零部件供應商和RDC構成的物流網絡中，C{i|1，2，…，n}表示供貨點集合，0表示RDC，網絡中的所有節(jié)點用N=C∪{0}表示。cij為網絡中?。╥，j）的權重，表示網絡節(jié)點間的行駛時間，i，j∈N且i≠j。可支持RDC零部件集貨的規(guī)格相同容量為Q的車輛m輛，集合為K{k|1，2，…，m}，啟用的車輛均從RDC出發(fā)，在與供應點約定的硬時間窗[ei，li]范圍內到達取貨路徑上的每個供應點，取貨完成后返回RDC。在時間點ei之前，提前到達供應點的取貨車輛，因待交付的零部件可能尚未加工完成而無法裝載，等待會導致機會損失，因此車輛不可提前到達取貨點。在時間點li之后延遲到達的車輛，因錯過供應點的裝載服務時間，甚至可能會影響汽車制造企業(yè)的正常裝配計劃，因此車輛不可延遲到達供貨點。供應點i的單次供貨數量為qi（qi？燮Q），裝貨時間為si，同一供貨點只能有一輛車前往取貨，車輛到達供貨點的時間為τi。在滿足車輛能力約束和取貨時間窗約束的情況下，建立以所有車輛取貨完成總時間最短為目標的VRPTW模型。模型涉及的決策變量xijk表示為

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

2 改進節(jié)約算法

C-W節(jié)約算法[3]是一種常用的配送規(guī)劃近似算法，由Clark和Wright于1964年提出。其基本思想是在為每個客戶安排一輛車直接運輸的基礎上，依據運輸距離減小幅度最大的原則，依次將運輸中的兩個回路合并為一個回路。當車輛達到容量限制后進行下一輛車的優(yōu)化，最終使所有客戶的需求全部滿足。傳統的節(jié)約算法僅考慮運輸距離，不考慮客戶時間窗和調用車輛數量。

2.1 節(jié)約值的計算 此處節(jié)約值為運輸距離的節(jié)約值。配送中心“0”與各供應點i∈C直接相連，構成n條“0→i→0”初始路線，第i條線路的運輸費用為Ci=c0i+ci0。當第i，j兩條路線合并，即由同一輛車按路線“0→i→j→0”為其服務時，成本為Cij=c0i+cij+cj0，節(jié)約值為s（i，j）=ci0+c0j-cij。顯然，合并優(yōu)先級需按節(jié)約值從大到小依次排列。

2.3 改進節(jié)約算法

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

Step2：選擇集合Sdescend中的第一個元素s1（i，j），檢查其對應連接邊（i，j）端點i，j是否在初始化路徑上，若是，則轉Step5，否則轉Step3。

Step3：檢查點i，j，是否其中一個在已構成的路徑上且與RDC相連，另一個在初始化路徑上，若是，則轉Step5，否則轉Step4。

Step4：檢查點i，j，是否分別在不同的已構成路徑上，且均與RDC相連。若是，則轉Step5，否則轉Step7。

Step5：若連接點i，j，把點i，j原所在的不同路徑合并成一條路徑，合并后的路徑總取貨量q■？燮Q，則轉Step6，否則轉Step7。

Step7：Sdescend=Sdescend＼s1（i，j），檢查Sdescend若為空，則算法結束，否則轉Step2。

3 算例分析

負責某汽車制造商入廠物流的第三方物流企業(yè)，現已知擁有統一容量為20單位的車輛若干輛，車輛在各供應點的裝載時間為0.5，車輛的平均行駛速度為45，承擔汽車零部件供應任務的區(qū)域供應商位置坐標、供貨數量及取貨約定時間窗如表1所示。

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

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

4 結論

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

參考文獻：

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

[2]葉雷.循環(huán)取料在上海通用汽車零部件入廠物流中的應用研究[D].上海：復旦大學，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]張建勇，郭耀煌，李軍.一種具有模糊費用系數的VSP的修正C-W節(jié)約算法[J].西南交通大學學報，2004，6（3）：281-284.endprint