基于節約里程法的連鎖超市配送線路優化設計

○黃春蘭 李珊珊

（南京信息職業技術學院 江蘇南京 210046）

基于節約里程法的連鎖超市配送線路優化設計

○黃春蘭 李珊珊

（南京信息職業技術學院 江蘇南京 210046）

近年來，大大小小的連鎖超市在我國各地得到了長足的發展，連鎖超市之間的競爭激烈化程度開始加劇。連鎖超市要在激烈競爭的市場中取勝，必須改進物流現狀，重視配送中心的作用，降低物流成本以加強供應鏈的保障能力，快速響應顧客的需要。如何更好地設計或者優化現有的配送線路，成了一個難題，文章將對這個問題進行研究。

連鎖超市 配送線路 優化設計 節約里程法

一、問題的提出

物流配送是社會化大生產、國民經濟發展的客觀要求，它的發展狀況對城市經濟發展、商品流通和大眾消費起著重要的促進或制約作用。而好的配送方案，不僅能夠節約物流成本，提高商品運動的速度，而且還由于它能有效連接生產與消費，從而既有利于物流服務和商品附加價值的實現，又能有效促進生產商按需生產，真正使物流的管理建立在實需經營的基礎上。由于配送獨有的特點，合理規劃配送路線對配送成本的影響非常顯著，所以必須在全面計劃的基礎上，制定高效的配送路線，這也是整個配送系統優化的關鍵環節。

在配送路線選擇中，主要采取模型化方法進行路線確定。常見的模型有Tabu Search算法、SOM方法、遺傳算法、節約里程法等。節約里程法，又稱車輛運行計劃法（VSP-Vehicles Scheduling Program），適用于實際工作中要求得較優解或最優的近似解，而不一定需要求得最優解的情況。它的基本原理是三角形的一邊之長必定小于另外兩邊之和。當配送中心與用戶呈三角形關系時，由配送中心P單獨向兩個用戶A和B往返配貨的車輛運行距離必須大于以配送中心P巡回向兩用戶發貨的距離。那么，所計算的結果：2Lpa+2Lpb-（Lpa+Lpb+Lab）=Lpa+Lpb-Lab為巡回發貨比往返發貨的節約里程。

本文根據連鎖超市配送特征，選擇節約里程法模型進行配送路線設計。

二、研究對象的選取

根據中國連鎖經營協會數據顯示，2007年國內零售業巨頭蘇果超市的蘇果馬群物流配送中心占地面積17萬平方米，單體倉庫面積達4.2萬平方米，為華東地區第一，年配送額可達60億元，有效配送半徑為300公里。本文即選擇蘇果馬群物流配送中心為研究對象，基于節約里程法對配送中心到周邊若干門店的配送路線進行設計。

三、模型的假設

假設對于選定的一些超市進行分析，而不是對所有的超市進行分析；假設針對超市某一類的貨物分析而不是所有物品進行分析；假設每個客戶只能被訪問一次，每輛車其能服務一條路線，在配送中心裝貨后，在每一站依次卸貨；假定目標是使系統運作費用最小，為簡化，假設為配送的總路程最小。

四、用于分析的數據

本文選擇南京馬群周邊的12個蘇果超市（見表1）。

表1

表2 里程表（單位：千米）

表1中編號0代表的是蘇果馬群配送中心，之后的依次是12個門店。

接下來統計各門店之間的距離，本文借助的是百度地圖的距離查詢功能，依次查詢之后得到相互之間的距離：由于馬路的雙向性，所以往返的里程是不相同的。雖然差距并不會太大，但是我們還是把它們區別對待。最終，得出了里程表（表2）。

根據這個里程表，我們就可以使用節約里程法進行線路的優化設計。

五、使用節約里程法進行線路優化設計

節約里程法，又稱C-W算法，是由Clarke和Wright于1964年首次提出的。它的基本思想就是：對于配送中心以及兩個門店，關系如圖1所示。

圖1

如果車輛從 P-＞A-＞P-＞B-＞P，所需要的距離為 dis[P，A]+dis[A，P]+dis[P，B]+dis[B，P]，而如果我們把路線改為，P-＞A-＞B-＞P 的話，則總距離為 dis[P，A]+dis[A，B]+dis[P，B]，節約的路程為 dis[A，B]-dis[A，P]-dis[P，B]，我們把這個路程記作“節約值”s[A，B]。我們知道從A至B的距離一定存在一個先開到P點再開到B點的路程選擇，距離為dis[A，P]+dis[P，B]，但這個未必是最優的，換言 s[A，B]=dis[A，B]-dis[A，P]-dis[P，B]應該≥0。

據此，我們可以設計出具體的算法：

Step 1：讀入兩兩之間的距離，填入dis數組中；Step 2：求出所有門店之間的節約值s[A，B]；Step 3：然后按節約的值從大至小排序；Step 4：從第一輛車開始設計，對于每輛車；Step 4.1：初始路線為空；Step 4.2：找到最節約的s[A，B]，構造路線 0-＞A-＞B-＞0（0為配送中心）；Step 4.3：在s中劃去從A出發的以及到達B的元素，即劃去s[A，X]與 s[X，B]，X 為任意值；Step 4.4：若當前的路線為0-＞X-＞……-＞Y-＞0，我們找到最節約的 s[A，B]，使得B=X或A=Y，對于構造出路線0-＞B-＞X-＞……-＞Y-＞0或 0-＞X-＞……-＞Y-＞A-＞0；Step 4.5：在 s中劃去從A出發的以及到達B的元素，即劃去s[A，X]與s[X，B]，X為任意值；Step 4.6：如果當前車承載的超市數已達上線轉Step4重新設計下一輛車；Step 4.7：轉Step4.4；Step 5：設計好每輛車的配送路線，算法結束。

六、程序求解

對于這個算法，我們編寫對應的C#程序進行求解，運行程序，得到節約里程表按從大至小的排序后如表3所示。

表3

而我們知道，未優化的配送總距離215.2千米。

當每車需承擔2個超市的時候，程序的計算過程為：車1：合并路線 0-＞6-＞4-＞0，總里程 33.8，節約里程 25.6；車 2：合并路線 0-＞8-＞5-＞0，總里程 37.0，節約里程 16.5；車 3：合并路線0-＞7-＞9-＞0，總里程 17.24，節約里程 16.36；車 4：合并路線0-＞11-＞12-＞0，總里程 17.9，節約里程 11.3；車 5：合并路線0-＞2-＞1-＞0，總里程8.53，節約里程7.37；車6：合并路線0-＞3-＞10-＞0，總里程 22.5，節約里程 1.1；總里程 136.97，比優化前的215.2節約36.35%。

當每車需承擔3個超市的時候，程序的計算過程為：車1：合并路線 0-＞6-＞4-＞0，總里程 33.8，節約里程 25.6；合并路線0-＞6-＞4-＞5-＞0，總里程 37.3，節約里程 24.1；車 2：合并路線0-＞8-＞9-＞0，總里程 26.8，節約里程 16.4；合并路線0-＞8-＞9-＞7-＞0，總里程 27.47，節約里程 15.63；車 3：合并路線0-＞11-＞12-＞0，總里程17.9，節約里程11.3；合并路線0-＞10-＞11-＞12-＞0，總里程 21.9，節約里程 7.9；車 4：合并路線 0-＞2-＞1-＞0，總里程 8.53，節約里程 7.37；合并路線 0-＞2-＞1-＞3-＞0，總里程 14.43，節約里程5.8；總里程101.10，比優化前的215.2節約53.02%。

當每車需承擔4個超市的時候，程序的計算過程為：車 1：合并路線 0-＞6-＞4-＞0，總里程33.8，節約里程 25.6；合并路線0-＞6-＞4-＞5-＞0，總里程37.3，節約里程24.1；合并路線0-＞6-＞4-＞5-＞8-＞0，總里程 49.2，節約里程 14.0；車 2：合并路線 0-＞7-＞9-＞0，總里程 17.24，節約里程 16.36；合并路線 0-＞1-＞7-＞9-＞0，總里程17.24，節約里程 8.4；合并路線 0-＞1-＞7-＞9-＞2-＞0，總里程 17.34，節約里程 7.4；車 3：合并路線 0-＞11-＞12-＞0，總里程 17.9，節約里程11.3；合并路線0-＞10-＞11-＞12-＞0，總里程21.9，節約里程7.9；合并路線 0-＞3-＞10-＞11-＞12-＞0，總里程32.5，節約里程1.1；總里程99.04，比優化前的215.2節約53.98%

可以看出優化后對于里程的節約還是十分顯著的，而當我們知道不同容量的車行駛單位里程的價格以及根據實際情況，可以通過節約里程法找到最優的結果。

七、結束語

節約里程法并不是計算的最優的路線，而是一個較優的路線，計算最優的路線是一個NP完全問題（Non-deterministic Polynomial complete problem），無法在多項式的時間內找到結果（NP完全問題未必沒有多項式算法，只是目前均沒有找到），即使摒棄搜索算法而改使用高效的動態規劃算法，時間復雜度依舊是指數級別的，這對于現實問題中配送中心需要配送門店的數目大量時候求解時間漫長到幾年、幾十年甚至更長，而節約里程法可以在極快的時間內求出一個比較優秀的結果，比起耗費大量人力物力而不切實際的求解最優解，使用節約里程法就顯得更為經濟有效了。

[1]陳曉偉、張悟移、耿繼武：節約法在配送路線選擇中的應用[J].昆明理工大學學報，2003（4）.

[2]李如姣：“節約里程法”在某物流公司配送中心的實際運用[J].科技資訊，2008（28）.