基于旅行商問題的循環(huán)取貨模式優(yōu)化

1、基于旅行商問題的循環(huán)取貨模式優(yōu)化研究黃永強作者簡介：黃永強，男，贛南師范學院商學院講師，研究方向：物流與供應鏈管理優(yōu)化；2志遠團隊：贛南師范學院商學院10物流本科班學生：羅漢平，張運福，唐玲，熊思英，陳貽紅。 志遠團隊（贛南師范學院 商學院，江西 贛州 341000）摘要：循環(huán)取貨是一種新型的供貨模式，貫穿于整個供應物流之中。文章主要立足于循環(huán)取貨入廠物流，通過對循環(huán)取貨的運作方式與特性進行分析，結(jié)合相關汽車物流企業(yè)的相關問題，提出相應的解決方案。在對供應商進行分類合理性分析之后，建立旅行商問題模型、運用軟件設計循環(huán)取貨初始路線，并結(jié)合企業(yè)相關情況，優(yōu)化初始路線。本文旨在通過對汽車零部件循環(huán)取

2、貨方式進行定性和定量的綜合分析,提出有效的優(yōu)化方案,為汽車制造行業(yè)的入廠物流實踐提供一些有意義的參考。關鍵詞：循環(huán)取貨 入廠物流 客戶價值循環(huán)取貨(Milk Run)，也稱為“牛奶取貨”“集貨配送 ”“多倉儲間巡回裝卸貨混載運送”“定時定點取貨”,是國內(nèi)最早是汽車制造業(yè)使用的一種物料集貨模式。其具有小批量、多頻次、定時性等特點。循環(huán)取貨的應用使得物料JIT供應成為可能。有效降低運輸過程中的運輸成本、倉儲成本等，保證了生產(chǎn)的連續(xù)性。本文是在安吉現(xiàn)以存在的汽車零部件入場物流循環(huán)取貨模式的基礎上，再度革新，針對運輸過程中的運輸成本高、裝載率低和運輸路徑復雜及環(huán)境的動態(tài)性問題，進行循環(huán)取貨的合理設計。

3、一、汽車零部件入場物流循環(huán)取貨模式現(xiàn)狀分析 本文中我們主要從國內(nèi)安吉汽車物流有限公司 安吉物流是國內(nèi)最大的汽車物流服務供應商，是全球業(yè)務規(guī)模最大的汽車物流服務供應商。中零部件入廠物流為例，對其循環(huán)期貨模式中出現(xiàn)的問題進行分析存在的問題主要有以下幾個方面：1. 運輸成本高公司引入循環(huán)取貨運作模式的目的在于對零部件供應商現(xiàn)有的運輸網(wǎng)路加以優(yōu)化，使之既能滿足生產(chǎn)波動的需求，同時又能將運營成本控制在一定范圍內(nèi)。但目前在運用的過程中，物流運作成本仍然偏高，在總的物流費用成本中運輸?shù)某杀具_到了44% ，如圖1-1所示：物流費用比例表存貨持有20%管理4%運輸44%客戶服務6%倉儲26%存貨持有管理客戶服務

4、倉儲運輸圖1-1物流費用構(gòu)成圖造成運輸成本費用高的一個重要的原因是循環(huán)取貨模式下的運輸車輛的路徑設計不合理。2. 路徑設計復雜運輸車輛的路徑安排要考慮各個供應商的出貨地址、嚴格的出貨窗口設置，需要確定一條Milk-run路徑要遍歷哪些供應商，針對整個供應商網(wǎng)絡需要設計多少條Milk-run路徑。當網(wǎng)絡規(guī)模較小時較易解決，但對于目前192個供應商的網(wǎng)絡，原有的運輸路徑就不能滿足。由于供應商不是每天固定不變提供貨物，主機廠的生產(chǎn)訂單每天的需求也不同，因此，運輸車輛的路徑設計就變得比較困難。3. 裝載率低實際運作過程中，通常采用的是在每條Milk-run路徑上安排無限的運輸車輛來實現(xiàn)貨物全部運輸完的

5、目標?？紤]運輸成本，往往是在有限運輸車輛的前提下，實現(xiàn)Milk-run與運輸車輛調(diào)度之間的協(xié)調(diào)，而安吉目前的裝載率遠沒有達到85%的理想狀態(tài)。4. 生產(chǎn)計劃和運輸變動性大在零部件物流配送過程中，由于各種原因造成生產(chǎn)商的緊急加單、減單和并單等超過當天零部件正常需求量的25%時；或當天氣、道路等出現(xiàn)異常情況時，就需要設計科學的應急運輸方案，進行合理決策，以控制運營成本。二零部件供應商分析1. 供應商分類概況本文根據(jù)安吉汽車物流有限公司在上海地區(qū)的零部件供應商數(shù)據(jù)信息（供應商編號為：10000，100001，11107，11108），可以按供應商、大區(qū)代碼、地區(qū)代碼、距離、地區(qū)描述和頻次這幾大類別對

6、供應商進行分類分組，分組情況如表1-1所示：表1-1 供應商的分類情況表序號分類標準分類結(jié)果數(shù)量1供應商（供應商中文名，提貨地點）10000,10001,10002,10008，11091，111081922大區(qū)代碼D1，D2，D3，D443地區(qū)代碼O1，O2，O8，S1，S2，S8164距離<10KM，10KM-20KM，150KM180KM155地區(qū)描述安亭及周邊金山干巷/奉賢西部/浦東川沙奉賢東部/南匯江陰周莊、張家港166頻次1,2,3,4,5,662.分類合理性分析2.1按照供應商（供應商中文名，提貨地點）分類安吉客戶的主機廠G有近15,000 種的零部件，其中國產(chǎn)零部件近萬種

7、，分布在江浙滬等10 余個省市的170多家國產(chǎn)零部件供應商, 而目前其供應商的范圍仍然在擴大。針對安吉零部件目前的循環(huán)取貨模式，該分類標準是將每個供應商作為單獨的個體進行整合分析，而每一個體難以形成完整區(qū)域，數(shù)量難處理，且劃分標準難以確立。因此，按照供應商分類是不合理的。2.2按照大區(qū)分類大區(qū)的分類是很明確的，即分為D1，D2，D3，D4四種。我們對每個大區(qū)進行篩選，發(fā)現(xiàn)這一分類和其他分類標準是有聯(lián)系的，例如和“距離”之間的聯(lián)系，如表1-2所示：表1-2 大區(qū)和距離之間的聯(lián)系表 距離供應商數(shù)量大區(qū)代碼距離供應商數(shù)量D1<10KM48D410KM20KM430KM50KM120KM30KM

8、5D210KM20KM1830KM50KM220KM30KM2750KM70KM5D320KM-30KM170KM-90KM430KM50KM2290KM-120KM650KM70KM32120KM-150KM870KM90KM17150KM-180KM8>90KM6 從表1-2中可以看出，雖然各大區(qū)有各距離分布，甚至大區(qū)之間的距離有交集，但供應商數(shù)量在各區(qū)還是有一個相對集中度，大區(qū)的分類是根據(jù)各個供應商和主機廠G之間的距離來劃分的，較近的為D1，較遠的為D4。這種分類可將相距近的點聯(lián)系在一起，方便采用循環(huán)取貨模式（不同大區(qū)之間交集的部分中，由于不同大區(qū)的點相距較遠，不會產(chǎn)生路徑計算影響

9、，如D3和D4交集的70KM90KM部分）?？芍朔诸惙绞捷^合理。2.3按照地區(qū)分類對安吉上海地區(qū)零部件供應商分析，對于地區(qū)的分類也很明確，緊接著大區(qū)的分類下來。因此，在考慮地區(qū)分類前，首先要確定地區(qū)所屬的大區(qū)，建立兩者之間的聯(lián)系，將地區(qū)和大區(qū)聯(lián)系起來考慮，二者聯(lián)系如表1-3所示：表1-3 地區(qū)大區(qū)之間的聯(lián)系表大區(qū)地區(qū)每個大區(qū)包括地區(qū)的數(shù)量D1S11D2S2，S32D3S4，S5，S6，S7，S85D4O1，O2，O3，O88不同地區(qū)隸屬于不同大區(qū)且沒有交集，可考慮按此分類對供應商進行分類。2.4按照距離分類根據(jù)安吉上海地區(qū)零部件供應商中“距離”一列給出的數(shù)據(jù)可知道，此距離是指供應商距主機廠

10、的距離，標注出來將呈現(xiàn)以主機廠為圓心，距離為半徑的呈多環(huán)狀的同心圓狀。依據(jù)本分析和循環(huán)取貨系統(tǒng)在實際操作中的經(jīng)驗可知，按照此標準分類的方式，達不到最優(yōu)化的效果。2.5按照地區(qū)描述分類對安吉上海地區(qū)零部件供應商中的16種地區(qū)描述進行分類，可知供應商分布在主機廠G的各個方位。另外，上海市內(nèi)及周邊的供應商有分布在相同方位的（比如位于西北或者南部），因為分布在不同的大區(qū)或地區(qū)，所以也有明顯的區(qū)分?？梢钥紤]按此分類對大量的供應商進行分類。分類結(jié)果如表1-4所示：表1-4 地區(qū)描述分類結(jié)果表所屬范圍內(nèi)的地區(qū)描述隸屬大區(qū)、地區(qū)位于主機廠G方位上海市內(nèi)及周邊安亭及周邊D1 ，S1西北寶山大場、顧村/嘉定北部、

11、東部/青浦東北部D1， S1西奉賢東部/南匯D3 ，S8南嘉定西部、城區(qū)D2， S3西北金山干巷/奉賢西部/浦東川沙D3， S7南浦東康橋、金橋、張江/閔行南部/松江西南部/青浦西南部D3 ，S6東市中心區(qū)D3 ，S5松江/閔行北部/寶山D3 ，S4西南上海市以外城市昆山/太倉D4 ，O2江陰周莊、張家港D4 ，O6昆山花橋D4 ，O1蘇州工業(yè)區(qū)D4 ，O4蘇州市西D4 ，O5太倉西北D4 ，O3無錫D4 ，O7無錫西部、常州/靖江/湖州D4 ，O82.6按頻次分類無論按大區(qū)或地區(qū)分類，都存在1,2,3,4,5,6六種不同頻次的配送情況，如表1-5所示。結(jié)合實際，在整個物流取貨系統(tǒng)中，某個供應

12、商的零件需求數(shù)量可能大于或小于車輛的最大裝載量，大于最大裝載量的可以采取直送的方式，或者分成幾批次運行，參與到Milk-run中。既能根據(jù)供應商的實際需求以及主機廠的需求確定路線，保證生產(chǎn)，同時也減少了運輸總公里數(shù)，提高了車輛的裝載率，將成本控制在一定范圍內(nèi)?？梢?，按此方式對供應商進行分類以設計循環(huán)取貨的優(yōu)化路徑是很合理的。表1-5 各區(qū)頻次分類結(jié)果表大區(qū)地區(qū)頻次D1S11，2，3，4，5，6D2S2，S31，2，3，4，5，6D3S4，S5，S6，S7，S81，2，3，4，5，6D4O1，O2，O3，O81，2，3，4，5，6本方案將先選取一個大區(qū)的供應商按頻次分類方式對供應商進行分類, 以

13、設計循環(huán)取貨的優(yōu)化路徑。三 循環(huán)取貨路徑和時間安排1.路徑優(yōu)化的假設根據(jù)安吉上海地區(qū)零部件供應商分析，我們選擇按大區(qū)分類的D2大區(qū)進行車輛的路線設計，首先按頻次分類方式對供應商進行分類,然后分別對D2大區(qū)中6個頻次（1,2,3,4,5,6）的路線進行展開設計及優(yōu)化。在實際運作過程中，循環(huán)取貨的路徑設計往往要考慮的因素很多，由于案例已給信息的局限性及數(shù)據(jù)收集的難度很大，在設計路徑之前做出如下合理假設：v 主機廠。本方案中，所有循環(huán)取貨的零部件都送到主機廠，且僅存在單一的主機廠，位置確定，零部件到達主機廠的時間沒有限制。v 供應商。所有供應商的位置已知，供應商對于取貨時間沒有限制，原則上服從Mil

14、k-run規(guī)劃所設定的取貨時間窗。v 車輛。車輛數(shù)量足夠多，所有車輛都必須從主機廠出發(fā)，并最終返回，且不允許超載，所有車輛的行駛速度認為相同。v 車輛的行駛平均速度為40km/h,在每一個供應商的料箱裝貨平均時間為30min,司機每天工作時間不得超過8h。v 考慮汽車零部件特點，一般滿載情況下，零部件載重量不超過汽車載重限制。v 道路。所有的供應商之間、供應商與RDC 之間均存在可連通的道路。不考慮道路的實際交通情況，運輸時間僅取決于運輸距離和車輛行駛速度。車輛行駛時暫時不考慮特殊情況，如堵車、天氣因素、交通管制等，應急方案將在后文詳述。2. 路徑優(yōu)化的基本原則 安吉零部件在循環(huán)取貨的運營過程

15、中，本著安全性、可靠性和及時性的思想，為了實現(xiàn)安吉低成本運營、信息化共享，循環(huán)取貨路徑的設計及優(yōu)化應強調(diào)以下幾個原則：v 控制“成本”。通過對裝載率、行使路線、應急措施等制定從源頭上控制物流運作成本。3PL可通過提高車輛利用率來降低用車總數(shù)（循環(huán)次數(shù)每增加一倍，用車總數(shù)可以少一半）。因此，3PL應在充分分析生產(chǎn)線實際需求基礎上，合理設計運輸?shù)娜萘?、?shù)量和頻度。v 盡量“配載”。只有進行充分的配載，才使得循環(huán)取貨模式具備成本控制的優(yōu)勢，涉及到運輸工具的配載問題，具體原則將在后文配載原則中闡述。v 提高“頻次”。高運輸頻次是降低零件庫存的根本方法，同時也為配載提供充分的可行性。v 強調(diào)“準時”。循

16、環(huán)取貨模式下的運作是準時運行，準點到達，既是保障生產(chǎn)順利進行的要求，也是精益物流管理的要求。v 充分“應急”。只有考慮充分且方案成熟的應急準備，才能最大程度在各種意外情況下保障生產(chǎn)的順利進行。v 帶動“空箱”?？障涞念I取和交付業(yè)務貫穿循環(huán)取貨運作的整個流程，對取貨的平穩(wěn)運行具有極其重要的意義。3. 制定循環(huán)取貨路線3.1模型的建立旅行商問題（Traveling Salesman Problem,TSP）是一個經(jīng)典的組合優(yōu)化問題,問題描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發(fā)，需要經(jīng)過所有城市后，回到出發(fā)地。應如何選擇行進路線，以使總的行程最短（或時間、費用等最少）。從

17、圖論的角度來看，該問題實質(zhì)是在一個帶權完全無向圖 給定一個完全無向帶權圖G，其每一條邊有一個非負的整數(shù)權值。目的是要找出G的一條經(jīng)過每個頂點一次且僅經(jīng)過一次的回路，使回路的總權值最小。中，找一個權值最小的Hamilton回路。循環(huán)取貨模式與旅行商問題類似，因此，循環(huán)取貨的路線設計問題可以轉(zhuǎn)化為旅行商問題的求解，使總的行程最短，時間、費用最少。l 旅行商問題的數(shù)學模型為一個帶權圖，為頂點集，為邊集。為頂點到頂點的距離，其中且，同時，則經(jīng)典TSP（Classical TSP，CTSP）的數(shù)學模型為： （1-1） （1-2） （1-3） （1-4） （1-5）其中S為圖S的頂點數(shù)。式（1-1）為CT

18、SP的目標函數(shù)，求經(jīng)過所有頂點的回路的最小距離式（1-2）至式（1-4）限定回路上每個頂點僅有一條入邊和一條出邊。式（1-5）限定在回路中不出現(xiàn)子回路。模型實質(zhì)上是在一個帶權圖中求一條Hamilton回路。若對所有，不等式均成立，則稱該問題是滿足三角不等式的。由于該問題的可行解是所有頂點的全排列，隨著頂點數(shù)的增加，會產(chǎn)生組合爆炸，它是一個NP完全問題。本方案采用Logware軟件求解ROUTESEQ指令程序的ROUTESEQ旅行商問題，求解過程將在下文闡述。3.2. 初始路線求解及路線的優(yōu)化 根據(jù)目前車輛路線安排存在的問題與不足，考慮供應商的出貨地址和嚴格的窗口時間設置進行運輸車輛的路徑設計，

19、確定一條Milk-run路線上的供應商以及整個網(wǎng)絡中的Milk-run路線，以提高配送效率，滿足客戶需求。選取上海大眾汽車一廠作為主機廠，利用谷歌地圖確定各個供應商、主機廠的經(jīng)緯度，再利用百度地圖確定他們之間的相對位置，以及供應商兩兩之間的距離、各供應商與主機廠之間的距離。Logware求解時以(31°N、121°E)為原點，為方便點與點之間的區(qū)分和計算，對其經(jīng)緯度擴大到原來的10倍，各供應商與主機廠之間的相對位置如圖1-2所示：圖1-2 各供應商與主機廠的相對位置分布圖根據(jù)整理出的D2大區(qū)的資料，各頻次的供應商的情況如表1-6所示：表1-6 各頻次下對應的供應商表頻次序號

20、頻次1頻次2頻次3頻次4頻次5頻次61100021002310001100001024910118210032102241001910024108731016431059010225100371003410267410635102961008010129107455107751008610137610949101191014871105010169101878102021055191030210726101065310820111066510826121080910956131090714109301511012l 初始路線求解n 頻次1的循環(huán)取貨路線由附件12中D2大區(qū)的供應商資料可知，如表

21、1-6所示，頻次1、2、5、6的供應商數(shù)目小，運用Logware軟件可以直接得到Milk-run路線圖，圖1-6，圖1-7、圖1-8為頻次1的Milk-run路線圖。（因篇幅所限，其他頻次的循環(huán)取貨初始路線圖詳見附件二）。圖1-2 頻次1各供應商數(shù)據(jù)輸入圖圖1-3 Logware路徑求解結(jié)果顯示圖(Total route distance不作參考)圖1-4 頻次1路線結(jié)果圖根據(jù)公式：行駛時間=總行程/40（km/h）裝卸時間=供應商個數(shù)*30/60總時間=行駛時間+裝貨時間因此，頻次1、2、5、6的路線如表1-7所示：頻次供應商數(shù)量/個Milk-run路線總行程/km行駛時間/h裝貨時間/h總

22、時間/h頻次14主機廠-10635-10002-10032-10590-主機廠87.62.1924.19頻次27主機廠-10949-10296-10224-10775-10023-10225-11050-主機廠48.51.213.54.71頻次52主機廠-10249-10873-主機廠38.10.9511.95頻次64主機廠-10267-10118-10164-10745-主機廠822.0524.05表1-7 頻次1、2、5、6路線表n 頻次3的循環(huán)取貨路線由表1-6可知，其供應商數(shù)量有十五個，為避免工作時間超過8小時，根據(jù)總行程最短，根據(jù)Logware軟件求得的路線（如圖1-5所示），將供應

23、商分成兩組，安排不同的車進行取貨。圖1-5 頻次3路線結(jié)果圖分組情況為：（11012,10653,10665,10169,10080,10086,10930,10302）（10037,10907,10001,10809,10202,10119,10019）整理得表1-8：表1-8 頻次3路線表頻次供應商數(shù)量/個Milk-run路線總行程/km行駛時間/h裝貨時間/h總時間/h頻次38主機廠-11012-10653-10665-10169-10080-10086-10930-10302-主機廠88.32.2146.217主機廠-10037-10907-10001-10809-10202-1011

24、9-10019-主機廠110.62.773.56.27n 頻次4的循環(huán)取貨路線由表1-6可知，供應商數(shù)量也過多，為避免工作時間超過8小時，根據(jù)Logware軟件求得的路線（如圖1-6所示），將供應商分成兩組，安排不同的車進行取貨。圖1-6 頻次4路線結(jié)果圖分組情況為：（10956,10187,10826,10000,10551,10129,10820,10148）（10726,10034,10137,10024）整理得表1-9：表1-9 頻次4路線表頻次供應商數(shù)量/個Milk-run路線總行程/km行駛時間/h裝貨時間/h總時間/h頻次48主機廠-10956-10187-10826-10000

25、-10551-10129-10820-10148-主機廠822.0546.054主機廠-10726-10034-10137-10024-主機廠781.9523.95l 路線優(yōu)化以上為初步確定的循環(huán)取貨路線，如頻次5的取貨路線，明顯存在不合理處。路線內(nèi)雖然只需為兩個供應商取貨，但其時間和車輛的裝載率沒有得到合理利用，容易造成浪費，因此需要對其進行路線優(yōu)化，頻次5的零部件取貨由頻次1和頻次4共同完成，并用Logware軟件求解，得出優(yōu)化后的循環(huán)取貨路線。綜上，我們整理可得優(yōu)化后的Milk-run線路表，見表1-10表1-10 優(yōu)化后的Milk-run線路表頻次供應商數(shù)量/個Milk-run路線總行

26、程/km行駛時間/h裝貨時間/h總時間/h頻次16主機廠-10635-10249-10002-10032-10873-10590-主機廠802.0835.08頻次27主機廠-10949-10296-10224-10775-10023-10225-11050-主機廠48.51.273.54.77續(xù)表3-10頻次38主機廠-11012-10653-10665-10169-10080-10086-10930-10302-主機廠88.32.2146.217主機廠-10037-10907-10001-10809-10202-10119-10019-主機廠110.62.773.56.27頻次49主機廠-1

27、0956-10187-10826-10249-10000-10551-10873-10129-10820-主機廠68.21.714.56.215主機廠-10148-10726-10034-10137-10024-主機廠110.12.752.55.25頻次64主機廠-10267-10118-10164-10745-主機廠822.0524.05如圖1-7、圖1-8所示，分別為頻次1和頻次2的循環(huán)取貨路線圖。 圖1-7 頻次1路線圖 圖1-8 頻次2路線圖3.3安排車輛運行時間 定線、定時的取貨路線是循環(huán)取貨的主要特征之一。設計好的路線作為路線的參照模板，在Milk-run中直接調(diào)用安排。行車時間設

28、定應注意以下幾個事項:v 車輛到達主機廠的時間分布控制要平衡車輛到廠的時間分布，盡量避免車輛在同一時間段內(nèi)集中到達主機廠，以免給主機廠的收貨工作帶來很大的壓力。v 頻次間的間隔一般要求1.5小時及以上，并且要能夠為DD-JIT送貨預留訪問點。原則上各供應商應服從主機廠安排的任何取貨時間窗，并且一般不可變。實際也可能遇到特殊的交通及供應商特殊狀況等因素，使原有路線在時間窗的約束下做出調(diào)整。 v 另外，考慮到取貨的平順化，對于某個供應商來講，零部件也不可隨意地拆分，而是按照路徑的運作頻次有效拆分。 由Logware軟件求得的各頻次的循環(huán)取貨路線，我們繪制了從主機廠出發(fā)到各供應商取貨再回到主機廠的行

29、車時刻表，本文只列舉出頻次1的車輛運行時間，其余各頻次可根據(jù)同樣方法進行車輛安排。供應商編號 公司名稱距離/km行駛時間窗口時間 第一循環(huán)到達時間出發(fā)時間從主機廠出發(fā)07:0010635上海華中沖壓件制品廠 7.400:1200:3007:1207:4210249上海海華傳感器有限公司 5.500:0900:3007:5108:2110002上海勞倫茨橡膠制品有限公司2.900:0500:3008:2608:5610032上海汽車股份有限公司-中國彈簧廠 14.200:2200:3009:1809:4810873上海日安電子有限公司15.700:2400:3010:1210:4210590上海索菲瑪汽車濾清器有限公司 20.800:3200:3011:1411:44回到主機廠13.500:21-12:05 總計8002:0503:00參考文獻1.葉雷.循環(huán)取料在上海通用汽車零部件入廠物流中的應用研究.D復旦大學管理學院,20052.張東.TSP問題的算法與應用的研究.D上海大學計算機應用技術，2007【Abstract】 Milk-run is a new mode of supply throughout the entire supply logistics.Th