基于節(jié)約算法的零部件售后物流配送線路優(yōu)化

1、物流系統(tǒng)優(yōu)化與設(shè)計題 目:基于節(jié)約算法的零部件售后物流配送線路優(yōu)化 姓 名: 瞿 偉 學(xué) 院: 工 學(xué) 院 專 業(yè): 物 流 工 程 班 級: 物流 04班 學(xué) 號: 31310434 2013年 6月 21日目 錄摘要1關(guān)鍵詞11背景介紹11.1研究內(nèi)容 11.2研究方法11.3研究目的11.4研究意義12.案例分析23.優(yōu)化方法 33.1一般tsp模型33.2節(jié)約算法34. 優(yōu)化方案44.1案例數(shù)據(jù)分析 44.2配送線路優(yōu)化 55.總結(jié)5參考文獻(xiàn)5表 1 9個倉庫的基本情況表2表 2 cpd倉庫、6個發(fā)貨倉庫之間的距離4表 3 1號非發(fā)貨倉庫、6個發(fā)貨倉庫之間的距離4表 4 2號非發(fā)貨倉庫

2、、6個發(fā)貨倉庫之間的距離4表 5 表2的節(jié)約值 5表 6 表3的節(jié)約值 5表 7 表4的節(jié)約值 5基于節(jié)約算法的零部件售后物流配送路線優(yōu)化物流專業(yè)學(xué)生 瞿偉摘要：售后服務(wù)在獲取競爭優(yōu)勢、提高客戶忠誠度和獲取利潤等方面的重要性日益突出,作為其物質(zhì)支持的服務(wù)備件的物流管理也日益得到重視。售后服務(wù)中，響應(yīng)時間是服務(wù)水平的一個重要指標(biāo)，零部件售后物流配送作為汽車售后服務(wù)供應(yīng)鏈的重要一環(huán)，對其進(jìn)行優(yōu)化具有極其重要的現(xiàn)實和戰(zhàn)略意義。本文用節(jié)約算法對配送線路進(jìn)行簡單的優(yōu)化設(shè)計。關(guān)鍵字：物流配送、tsp、節(jié)約算法1 背景介紹1.1研究內(nèi)容隨著科技的發(fā)展，時代的進(jìn)步，當(dāng)今社會各個國家對外開放的程度比以往更加廣泛

3、，人們的需求更加多樣化、個性化。需求的變化使大批量、大規(guī)模、少品種的生產(chǎn)模式逐漸向多品種、小批量的生產(chǎn)模式轉(zhuǎn)變，大而全、小而全的企業(yè)經(jīng)營模式正逐漸被人們拋棄，通過市場交換的人、財、物、信息的量越來越大。全球經(jīng)濟一體化趨勢和市場競爭程度日益增加，現(xiàn)代物流的內(nèi)涵和外延也不斷地擴充和拓展，物流運動的新型模式物流配送也隨之形成和發(fā)展，并越來越多地受到重視。配送是物流中一個重要的直接與消費者相連的環(huán)節(jié)。配送一般定義為，將貨物從物流結(jié)點送達(dá)收貨人的過程。主要包括集貨作業(yè)、配貨作業(yè)、車載貨物的配裝、配送線路的確定四個環(huán)節(jié)。配送線路是整個配送網(wǎng)絡(luò)優(yōu)化的關(guān)鍵環(huán)節(jié)。合理確定配送路線就是用最少的動力，走最短的里程，

4、花最少的費用，經(jīng)最少的環(huán)節(jié)，以最快的速度把貨物運至用戶手中。合理規(guī)劃配送路線對配送成本的影響要比一般運輸大得多，所以必須在全面計劃的基礎(chǔ)上，制定高效的運輸路線，選擇合理的運輸方式和運輸工具。售后服務(wù)在獲取競爭優(yōu)勢、提高客戶忠誠度和獲取利潤等方面的重要性日益突出,作為其物質(zhì)支持的服務(wù)備件的物流管理也日益得到重視。售后服務(wù)中，響應(yīng)時間是服務(wù)水平的一個重要指標(biāo)，零部件售后物流配送作為汽車售后服務(wù)供應(yīng)鏈的重要一環(huán)，對其進(jìn)行優(yōu)化具有極其重要的現(xiàn)實和戰(zhàn)略意義。本文就汽車零部件售后物流配送的關(guān)鍵技術(shù)中的車輛調(diào)度問題進(jìn)行了研究，關(guān)鍵技術(shù)即是指集貨、配貨及車輛調(diào)度優(yōu)化。其中，重點研究了合理確定配送路線的問題，這

5、是整個配送網(wǎng)絡(luò)優(yōu)化的關(guān)鍵環(huán)節(jié)。合理確定配送路線就是用最少的動力，走最短的里程，花最少的費用，經(jīng)最少的環(huán)節(jié)，以最快的速度把貨物運至用戶手中。合理規(guī)劃配送路線對配送成本的影響要比一般運輸大得多，所以必須在全面計劃的基礎(chǔ)上，制定高效的運輸路線，選擇合理的運輸方式和運輸工具。零部件售后配送過程中，根據(jù)零部件的特殊性，充分考慮了貨車裝載量的約束以實現(xiàn)運輸?shù)膬?yōu)化。1.2研究方法在研究過程中，通過選取案例企業(yè)的某一配送區(qū)域，就配送系統(tǒng)的優(yōu)化問題用數(shù)學(xué)方法進(jìn)行了定量分析和研究，建立了數(shù)學(xué)模型，通過分析計算得出該配送區(qū)域的最優(yōu)配送路線。1.3研究目的對案例企業(yè)的物流配送系統(tǒng)進(jìn)行分析，得出優(yōu)化方案，節(jié)約物流成本，

6、從而提高企業(yè)的利潤。同時也是通過對案例企業(yè)的研究，進(jìn)一步了解物流配送中、配送路線優(yōu)化對節(jié)約企業(yè)成本的重要影響，對提高勞動生產(chǎn)率、提高經(jīng)濟效益、實現(xiàn)物流科學(xué)化、促進(jìn)社會發(fā)展和經(jīng)濟建設(shè)的重要作用。企業(yè)只有改進(jìn)物流環(huán)節(jié)，重視配送優(yōu)化，才能降低物流成本，減少運營費用，提高配送效率，從而取得優(yōu)勢。1.4研究意義現(xiàn)代物流作為一種先進(jìn)流通方式管理技術(shù)在世界廣泛范圍內(nèi)得到高度的重視，并在生產(chǎn)、流通、服務(wù)領(lǐng)域得到廣泛應(yīng)用而獲得快速發(fā)展，正在成為改變經(jīng)濟運行方式和企業(yè)發(fā)展模式的重要手段。特別是供應(yīng)鏈物流管理技術(shù)的出現(xiàn)和發(fā)展，更是提升了物流的發(fā)展水平和加快了物流的集成化程度。隨著全球經(jīng)濟的一體化的發(fā)展，由于集成化物

7、流的理念得到進(jìn)一步的推廣，物流系統(tǒng)比以往任何時候都要復(fù)雜，技術(shù)的應(yīng)用和管理具有很強的系統(tǒng)性，如何降低各個環(huán)節(jié)企業(yè)的物流成本，提高物流服務(wù)水平，最大限度地滿足客戶需求，具有積極而現(xiàn)實的意義。物流系統(tǒng)解決方案中，運輸與配送問題占有很重要的地位，主要原因是運輸和配送過程的成本占物流總成本的很大比重，根據(jù)現(xiàn)有的研究成果，大約在70%90%之間。解決運輸成本的合理化，集中體現(xiàn)在運輸過程的合理組織與安排上，通過路徑的優(yōu)化來體現(xiàn)這種對降低運輸成本具有重要作用的管理工具與具體物流活動的運作，是安排合理運輸、解決運輸與配送問題的重要手段，也是實現(xiàn)物流管理科學(xué)化和合理化的重要途徑。本文重點通過節(jié)約啟發(fā)式算法，求解

8、物流配送優(yōu)化路徑的問題，通過理論與實踐的結(jié)合，尋求降低物流成本與提高物流效率的重要途徑。2 案例分析安吉零部件售后倉庫有9個，這9個倉庫中一個是上海大眾配件中央總庫cpd，另外8個為外庫，其中2個外庫為非發(fā)貨倉庫，其余6個外庫均為發(fā)貨倉庫。除其中一個非發(fā)貨倉庫建在浙江昆山市之外，其他8個倉庫都建在了上海嘉定區(qū)，這些外庫均為中央總庫cpd服務(wù)。8個外庫與cpd倉庫間距離因建庫的地址不同而遠(yuǎn)近不等，近的約2km左右，遠(yuǎn)的則35km。上海大眾負(fù)責(zé)零部件的采購，將采購的能滿足一段時間銷售數(shù)量的零部件存放在7個發(fā)貨倉庫中，由于發(fā)貨倉庫面積不足和庫存數(shù)量過大等原因會將采購的其他的零部件存放在2個非發(fā)貨倉庫

9、中，當(dāng)發(fā)貨倉庫的庫存不足時，非發(fā)貨倉庫要向發(fā)貨倉庫及時補充零部件，每個發(fā)貨倉庫儲存一定種類和數(shù)量的零部件，同時7個發(fā)貨倉庫儲存的零部件的種類各不相同。根據(jù)這種零部件儲存方式，當(dāng)安吉零部件的sap系統(tǒng)接到4s店或分中心的訂單后會根據(jù)訂單要求向訂單中涉及到的發(fā)貨倉庫發(fā)送零部件配送要求，然后接到訂單請求的發(fā)貨倉庫會根據(jù)規(guī)定的發(fā)貨流程，外庫（發(fā)貨倉庫）會將訂單中的零部件集齊后用載重量為5t的欄板車(每個發(fā)貨外庫配備一輛5t的欄板車）將零部件短駁至cpd倉庫，cpd倉庫集齊訂單上的零部件后再統(tǒng)一向4s店或分中心配送。類別倉庫名稱倉庫編號地址面積m2距cpd路程(km)發(fā)貨倉庫cpdcpd上海嘉定區(qū)園汽路

10、1000號42,00011101上海嘉定區(qū)民豐路24號 3,6006.4 21102上海嘉定于塘路379號15,0003.2 31103上海嘉定區(qū)園工路1169號 1,0003.9 41104上海嘉定區(qū)園國路1366號 14,5003.7 51105昆山市淀山湖鎮(zhèn)北苑路288號 25,00035.0 69106上海嘉定區(qū)泰豐路225號 2,1182.0 非發(fā)貨倉庫11001上海市嘉定區(qū)安亭鎮(zhèn)墨玉北路98號 5,0005.3 21002上海市嘉定區(qū)和靜東路318號 9,0004.1 表1 9個倉庫的基本情況表3 優(yōu)化方法3.1一般tsp模型設(shè)城市0為旅行商出發(fā)城市需要訪問的城市編號為1、l旅行商

11、問題構(gòu)成的網(wǎng)絡(luò)圖以g=v,a,c表示v=0,1,l 點集，表示旅行商需要經(jīng)過的地點a= (i, j) | i,j=0,1,l,ij 弧集，表示旅行商可能走過線路段集合c=cij|(i, j)a 費用矩陣，cij表示旅行商經(jīng)過對應(yīng)路段(i, j)所花費的費用數(shù)學(xué)模型 3.2節(jié)約算法節(jié)約算法又稱c-w 算法，是由clarke和wright于1964年首次提出的。它的基本思想是首先把各點單獨與源點0相連，構(gòu)成1條僅含一個點的線路?？傎M用為兩倍的從原點到各點的距離的費用 。然后計算將點i和j連接在一條線路上費用的“節(jié)約值”: s(i,j)=c0i+ ci0+ c0j+ cj0-(c0i+ cij+ c

12、j0)= c0i+ c0j-cijs(j,i)=cij+coi-cijs(i,j) 越大，說明把i和i連接在一起時總路程減少越多。構(gòu)造線路時，根據(jù)s(i,j)從大到小的順序進(jìn)行，實現(xiàn)時可在表上操作，具體步驟如下:step1: 計算節(jié)約值s(i,j) ，并按從大到小順序排列成表格形式;step2:考察表格中最大元素s(i,j) ;step3:考察s(i,j)對應(yīng)的點i和點j，檢查是否滿足下列條件:(1)若 點 i 和點j均不在己構(gòu)成的線路上，則可連接點i和點j，得到線路段 0-i-j-0，轉(zhuǎn)步驟step4;(2)若 點 i 或點j在已構(gòu)成的線路上，但不是線路的內(nèi)點(即不與源點0直接相連)， 則可

13、以連接，連接后得到線路段0i-j-0或0-i-j-0 ，轉(zhuǎn)步驟step4; (3)若 點 i 和點j位于己構(gòu)成的不同線路上，且均不是內(nèi)點，則連接后的得到線路段 0-i-j-0，轉(zhuǎn)步驟step4;(4)若 點 i和 點j位于已構(gòu)成的同一條線路上，則不能再進(jìn)行連接，轉(zhuǎn)步驟step3；step4:劃去第i行和第j列，即i點不能再到其他點，而j點也不能由其他點到達(dá);step5:若所有元素均被劃去，則己得到完整線路，算法終止;否則，在沒被劃去的元素中選擇最大元素，轉(zhuǎn)步驟step3。4 優(yōu)化方案cpd倉庫和2個非發(fā)貨倉庫都配備一輛5t的欄板車。cpd倉庫發(fā)車將6個發(fā)貨倉庫的零部件集齊。2個發(fā)貨倉庫發(fā)車對6

14、個發(fā)貨倉庫進(jìn)行補貨。4.1案例數(shù)據(jù)分析數(shù)據(jù)來源百度地圖。123456cpd6.43.23.93.735212.71.73.132.34.422.13.933.82.132.832.82.5432.45537.36表2 cpd倉庫、6個發(fā)貨倉庫之間的距離123456非11.33.22.21.831.84.612.71.73.132.34.422.13.933.82.132.832.82.5432.45537.36表3 1號非發(fā)貨倉庫、6個發(fā)貨倉庫之間的距離123456非21.91.92.25.133.32.412.71.73.132.34.422.13.933.82.132.832.82.543

15、2.45537.36表4 2號非發(fā)貨倉庫、6個發(fā)貨倉庫之間的距離4.2配送線路優(yōu)化用節(jié)約算法計算出節(jié)約值，如下表數(shù)據(jù)所示：123456cpd 126.938.654734.859.14.46.16.3643.13.40.7-0.3表5 表2的節(jié)約值1234560121.831.83.3401.11.25-0.21.21.21.261.55.74.31.4-0.9表6 表3的節(jié)約值1234560121.132.4243.93.14.552.91.42.766-0.12.22.12.5-1.6表7 表4的節(jié)約值cpd倉庫的最有集貨路線為 cpd-4-5-1-3-2-61號非發(fā)貨倉庫補貨的最優(yōu)路線為 1-3-6-2-5-4 或 4-5-3-6-2-12號非發(fā)貨倉庫補貨的最優(yōu)路線為 1-4-5-3-6-25 總結(jié)配送線路通過節(jié)約算法進(jìn)行優(yōu)化設(shè)計后，倉庫可以走最少的線路，最快的時間，及時發(fā)貨補貨，降低了運輸成本，提高了利潤。這只是節(jié)約里程算法的簡單運用，我們也應(yīng)看到，在現(xiàn)實的企業(yè)配送過程中，要考慮的配送點會更多、分布更廣，線路會更復(fù)雜，同時還要綜合考慮配送時間的限制、車輛的保養(yǎng)維修、人力成本、交通路況等諸多因素。因此節(jié)約法簡便易行,但也有一些弊端，一是過于強調(diào)節(jié)約里程，沒有考慮時間、路況等因素，二是不能對客戶需求作出靈活多變的處理。在配送路線選擇決策時