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

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

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

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

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

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

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

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

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

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

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

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

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

14、個發貨倉庫進行補貨。4.1案例數據分析數據來源百度地圖。123456cpd6.43.23.93.735212.71.73.132.34.422.13.933.82.132.832.82.5432.45537.36表2 cpd倉庫、6個發貨倉庫之間的距離123456非11.33.22.21.831.84.612.71.73.132.34.422.13.933.82.132.832.82.5432.45537.36表3 1號非發貨倉庫、6個發貨倉庫之間的距離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號非發貨倉庫、6個發貨倉庫之間的距離4.2配送線路優化用節約算法計算出節約值，如下表數據所示：123456cpd 126.938.654734.859.14.46.16.3643.13.40.7-0.3表5 表2的節約值1234560121.831.83.3401.11.25-0.21.21.21.261.55.74.31.4-0.9表6 表3的節約值1234560121.132.4243.93.14.552.91.42.766-0.12.22.12.5-1.6表7 表4的節約值cpd倉庫的最有集貨路線為 cpd-4-5-1-3-2-61號非發貨倉庫補貨的最優路線為 1-3-6-2-5-4 或 4-5-3-6-2-12號非發貨倉庫補貨的最優路線為 1-4-5-3-6-25 總結配送線路通過節約算法進行優化設計后，倉庫可以走最少的線路，最快的時間，及時發貨補貨，降低了運輸成本，提高了利潤。這只是節約里程算法的簡單運用，我們也應看到，在現實的企業配送過程中，要考慮的配送點會更多、分布更廣，線路會更復雜，同時還要綜合考慮配送時間的限制、車輛的保養維修、人力成本、交通路況等諸多因素。因此節約法簡便易行,但也有一些弊端，一是過于強調節約里程，沒有考慮時間、路況等因素，二是不能對客戶需求作出靈活多變的處理。在配送路線選擇決策時