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

1、物流系統(tǒng)優(yōu)化與設(shè)計(jì)題 目:基于節(jié)約算法的零部件售后物流配送線路優(yōu)化 姓 名: 瞿 偉 學(xué) 院: 工 學(xué) 院 專 業(yè): 物 流 工 程 班 級(jí): 物流 04班 學(xué) 號(hào): 31310434 2013年 6月 21日目 錄摘要1關(guān)鍵詞11背景介紹11.1研究?jī)?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個(gè)倉庫的基本情況表2表 2 cpd倉庫、6個(gè)發(fā)貨倉庫之間的距離4表 3 1號(hào)非發(fā)貨倉庫、6個(gè)發(fā)貨倉庫之間的距離4表 4 2號(hào)非發(fā)貨倉庫

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

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

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

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

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

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

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

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

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

11、問題構(gòu)成的網(wǎng)絡(luò)圖以g=v,a,c表示v=0,1,l 點(diǎn)集，表示旅行商需要經(jīng)過的地點(diǎn)a= (i, j) | i,j=0,1,l,ij 弧集，表示旅行商可能走過線路段集合c=cij|(i, j)a 費(fèi)用矩陣，cij表示旅行商經(jīng)過對(duì)應(yīng)路段(i, j)所花費(fèi)的費(fèi)用數(shù)學(xué)模型 3.2節(jié)約算法節(jié)約算法又稱c-w 算法，是由clarke和wright于1964年首次提出的。它的基本思想是首先把各點(diǎn)單獨(dú)與源點(diǎn)0相連，構(gòu)成1條僅含一個(gè)點(diǎn)的線路?？傎M(fèi)用為兩倍的從原點(diǎn)到各點(diǎn)的距離的費(fèi)用 。然后計(jì)算將點(diǎn)i和j連接在一條線路上費(fèi)用的“節(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連接在一起時(shí)總路程減少越多。構(gòu)造線路時(shí)，根據(jù)s(i,j)從大到小的順序進(jìn)行，實(shí)現(xiàn)時(shí)可在表上操作，具體步驟如下:step1: 計(jì)算節(jié)約值s(i,j) ，并按從大到小順序排列成表格形式;step2:考察表格中最大元素s(i,j) ;step3:考察s(i,j)對(duì)應(yīng)的點(diǎn)i和點(diǎn)j，檢查是否滿足下列條件:(1)若 點(diǎn) i 和點(diǎn)j均不在己構(gòu)成的線路上，則可連接點(diǎn)i和點(diǎn)j，得到線路段 0-i-j-0，轉(zhuǎn)步驟step4;(2)若 點(diǎn) i 或點(diǎn)j在已構(gòu)成的線路上，但不是線路的內(nèi)點(diǎn)(即不與源點(diǎn)0直接相連)， 則可

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

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