○黃春蘭 李珊珊

（南京信息職業(yè)技術(shù)學(xué)院 江蘇南京 210046）

基于節(jié)約里程法的連鎖超市配送線路優(yōu)化設(shè)計(jì)

○黃春蘭 李珊珊

（南京信息職業(yè)技術(shù)學(xué)院 江蘇南京 210046）

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

連鎖超市 配送線路 優(yōu)化設(shè)計(jì) 節(jié)約里程法

一、問題的提出

物流配送是社會化大生產(chǎn)、國民經(jīng)濟(jì)發(fā)展的客觀要求，它的發(fā)展?fàn)顩r對城市經(jīng)濟(jì)發(fā)展、商品流通和大眾消費(fèi)起著重要的促進(jìn)或制約作用。而好的配送方案，不僅能夠節(jié)約物流成本，提高商品運(yùn)動(dòng)的速度，而且還由于它能有效連接生產(chǎn)與消費(fèi)，從而既有利于物流服務(wù)和商品附加價(jià)值的實(shí)現(xiàn)，又能有效促進(jìn)生產(chǎn)商按需生產(chǎn)，真正使物流的管理建立在實(shí)需經(jīng)營的基礎(chǔ)上。由于配送獨(dú)有的特點(diǎn)，合理規(guī)劃配送路線對配送成本的影響非常顯著，所以必須在全面計(jì)劃的基礎(chǔ)上，制定高效的配送路線，這也是整個(gè)配送系統(tǒng)優(yōu)化的關(guān)鍵環(huán)節(jié)。

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

本文根據(jù)連鎖超市配送特征，選擇節(jié)約里程法模型進(jìn)行配送路線設(shè)計(jì)。

二、研究對象的選取

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

三、模型的假設(shè)

假設(shè)對于選定的一些超市進(jìn)行分析，而不是對所有的超市進(jìn)行分析；假設(shè)針對超市某一類的貨物分析而不是所有物品進(jìn)行分析；假設(shè)每個(gè)客戶只能被訪問一次，每輛車其能服務(wù)一條路線，在配送中心裝貨后，在每一站依次卸貨；假定目標(biāo)是使系統(tǒng)運(yùn)作費(fèi)用最小，為簡化，假設(shè)為配送的總路程最小。

四、用于分析的數(shù)據(jù)

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

表1

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

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

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

根據(jù)這個(gè)里程表，我們就可以使用節(jié)約里程法進(jìn)行線路的優(yōu)化設(shè)計(jì)。

五、使用節(jié)約里程法進(jìn)行線路優(yōu)化設(shè)計(jì)

節(jié)約里程法，又稱C-W算法，是由Clarke和Wright于1964年首次提出的。它的基本思想就是：對于配送中心以及兩個(gè)門店，關(guān)系如圖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]，節(jié)約的路程為 dis[A，B]-dis[A，P]-dis[P，B]，我們把這個(gè)路程記作“節(jié)約值”s[A，B]。我們知道從A至B的距離一定存在一個(gè)先開到P點(diǎn)再開到B點(diǎn)的路程選擇，距離為dis[A，P]+dis[P，B]，但這個(gè)未必是最優(yōu)的，換言 s[A，B]=dis[A，B]-dis[A，P]-dis[P，B]應(yīng)該≥0。

據(jù)此，我們可以設(shè)計(jì)出具體的算法：

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

六、程序求解

對于這個(gè)算法，我們編寫對應(yīng)的C#程序進(jìn)行求解，運(yùn)行程序，得到節(jié)約里程表按從大至小的排序后如表3所示。

表3

而我們知道，未優(yōu)化的配送總距離215.2千米。

當(dāng)每車需承擔(dān)2個(gè)超市的時(shí)候，程序的計(jì)算過程為：車1：合并路線 0-＞6-＞4-＞0，總里程 33.8，節(jié)約里程 25.6；車 2：合并路線 0-＞8-＞5-＞0，總里程 37.0，節(jié)約里程 16.5；車 3：合并路線0-＞7-＞9-＞0，總里程 17.24，節(jié)約里程 16.36；車 4：合并路線0-＞11-＞12-＞0，總里程 17.9，節(jié)約里程 11.3；車 5：合并路線0-＞2-＞1-＞0，總里程8.53，節(jié)約里程7.37；車6：合并路線0-＞3-＞10-＞0，總里程 22.5，節(jié)約里程 1.1；總里程 136.97，比優(yōu)化前的215.2節(jié)約36.35%。

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

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

可以看出優(yōu)化后對于里程的節(jié)約還是十分顯著的，而當(dāng)我們知道不同容量的車行駛單位里程的價(jià)格以及根據(jù)實(shí)際情況，可以通過節(jié)約里程法找到最優(yōu)的結(jié)果。

七、結(jié)束語

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

[1]陳曉偉、張悟移、耿繼武：節(jié)約法在配送路線選擇中的應(yīng)用[J].昆明理工大學(xué)學(xué)報(bào)，2003（4）.

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