節約里程法

出自 MBA智库百科(https://wiki.mbalib.com/)

節約里程法(Saving Algorithm)

　　節約里程法又稱節約演算法，是指用來解決運輸車輛數目不確定的VRP問題的最有名的啟髮式演算法。

　　節約里程法的基本思路如下圖,已知O點為配送中心,它分別向用戶A和B送貨。

　　設O點到用戶A和用戶B的距離分別為a和b。用戶A和用戶B之間的距離為c,現有兩種送貨方案,如圖下(a)和(b)所示。

　　在上圖(a)中配送距離為2(a+b)；圖上(b)中,配送距離為a+b+c。對比這兩個方案,哪個更合理呢？這就要看哪個配送距離最小,配送距離越小,則說明方案越合理。由上圖(a)中的配送距離,減去圖1(b)中的配送距離可得出:

　　2(a+b)－(a+b+c)=(2a+2b)－a－b－c=a+b－c(1)

　　如果把上圖(b)看成一個三角形,那麼a、b、c則是這個三角形三條邊的長度。由三角形的幾何性質可知,三角形中任意兩條邊的邊長之和,大於第三邊的邊長。因此,可以認定(1)式中結果是大於零的。

　　即:a+b－c＞0(2)

　　由(2)式可知,(b)方案優於(a)方案,節約了(a+b-c)的里程,這種分析方案的優劣式的思想,就是節約里程法的基本思想。

　　節約里程法核心思想是依次將運輸問題中的兩個迴路合併為一個迴路，每次使合併後的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優化。優化過程分為並行方式和串列方式兩種。

　　1.基本資料介紹

　　①寶潔公司是廣州配送中心最大的服務商,為其配送的客戶和貨量見下表,我們以廣州配送中心為例來說明有裝載限制的車輛調度的優化方法。公司客戶分佈在全國各地,這裡主要以廣東省內7家客戶及省外一家特殊客戶的一次配送為例。

　　城市和貨運量

　　②廣州配送中心為這次配送提供了三種車型,載重量分別為2噸、5噸和8噸,不同車型的運輸單價不一樣,具體見運輸單價表。配送中心的配送是由外協商提供車輛,因此汽車的數量沒有限制。

　　運輸單價表

　　2.步驟

　　第一步:各城市之間的距離見上表。

　　第二步:計算連接城市到同一線路上的距離節約值,具體見下表。

　　第三步:確定初始方案的運輸線路及運輸費用,現安排4輛2噸、4輛5噸的車給每個客戶送貨。運輸線路及運輸費用見下表所示。

　　運輸線路及運輸費用

　　第四步:進行線路第一次優化。

　　第一次修改後的車輛調度結果

　　第五步:繼續進行線路優化。

　　第二次修改後的車輛調度結果

　　從表中可以看出,廣州-惠州-揭陽-汕頭-漳州路線上的總貨運量達到7.9噸,再連接任何一個城市都將使貨運量超過最高限制(8噸),則不能繼續配載,所以可以首先確定的是這一條線路。然後在剩下的東莞、江門、陽江和汕尾重覆以上的優化步驟。得到最終配送計劃。

　　第六步:最終方案的確定。

　　最終修改後的車輛調度結果

　　通過對比初始方案與最終方案可知,通過優化可節約里程(1768-1047)=721(公裡),節約成本(4476.3-3384.55)=1091.75(元),僅8家客戶的一次配送就節約了物流配送成本1091.75。從這裡我們不難明白,中國的物流行業是一座金山。

　　只有利用先進的管理方法,不斷的提高效率,才可能大幅降低整個業務成本。