基于掃描法的連鎖超市生鮮配送路徑優化

浙江萬里學院 王鈺祥中國社科院財經戰略研究院 孫琪

?

基于掃描法的連鎖超市生鮮配送路徑優化

浙江萬里學院 王鈺祥
中國社科院財經戰略研究院 孫琪

摘 要：本文根據生鮮品自身的特點，以及連鎖超市在生鮮品配送中所面臨的管理問題，建立VRP數學模型，通過掃描算法對原有的配送路徑進行優化，得出最優的配送方案，為確保生鮮品質量安全、提高企業配送效率、滿足客戶高質量需求提供理論借鑒。

關鍵詞：連鎖超市 生鮮配送 掃描法 路徑優化

近年來，外國零售業在中國不斷發展，一方面為中國零售業的發展戰略提供了借鑒，另一方面加劇了本行業的競爭。隨著人們生活水平的提高，消費理念早已從過去的“吃得飽”轉變為如今的“吃得好”，生鮮行業逐漸成為眾多連鎖超市的主要盈利點。而生鮮品具有易腐、易損耗、生命周期短等特點。據資料顯示，一個細菌在常溫下15小時后可以滋生10億個細菌；而在10℃以下，15小時后只有1/4的細菌產生。因此，要保證生鮮品新鮮地抵達客戶手中，就必須盡可能地做到全程冷鏈，從采購預冷到冷藏車運輸，再到最后的制冷貨架，在配送模式方面要做到多品種，少批量，高頻次。綜上，生鮮配送線路是否合理直接影響到配送的時間、效率和效益，掃描法就是針對多目標的回路運輸問題，優化后的配送路徑不僅可以降低企業配送成本，提高配送效率，還能提升消費者的消費體驗，使得企業多盈利。

1　連鎖超市生鮮品配送面臨的問題

由于連鎖超市自身的地理位置，以及生鮮品自身易腐易爛的特點，連鎖超市的生鮮配送具有和其他消費品配送不一樣的特點，衍生出以下三個問題。

1.1公共資源方面

眾所周知，生鮮品的配送主要是汽車運輸，依靠的是道路資源，因此也受其限制和影響。首先，在我國某些特大城市，配送車輛都受到了嚴格的交通管制，影響調度安排；其次，與發達國家不同，我國的大型連鎖超市大部分處于城市人口密集地帶，交通狀況脆弱，車輛行駛速度變化大。因此，配送車輛的調度、作業在很大程度上受到交通管制和交通狀況的影響，這也影響著配送的準時性和配送成本。

1.2企業資源方面

一方面，國內連鎖超市的發展都是從單個小門店開始，然后擴大到廣領域、多門店，而配送車輛也面臨著舊有車輛和新型設備同時使用的狀況。另一方面，由于連鎖超市的門店大小各異，需求不同，產品種類多樣，也需要多車型的配送。因此，企業經常面臨多種類型運輸設備同時使用的情況。

1.3客戶需求方面

由于生鮮品講究一個“鮮”字，絕大部分消費者都希望自己能夠買到當天或者前一天的貨物，大部分人會選擇早市，但對于上班族來說只能去晚市，結果就只能買回一些剩余物品。如何保證所有的顧客都能買到新鮮的產品，這就要求生鮮配送要做到多品種、小批量、高頻率。最好可以做到前一天晚上下單，次日早上配送，早晨過后上午下單，當天下午配送。這就對配送速度和配送成本產生了壓力。

2　連鎖超市生鮮配送的VRP模型描述

分析上述問題發現，連鎖超市生鮮配送的問題主要來源于公共資源、企業資源、客戶個性化需求三個方面，而這三個方面的阻力都可以通過配送車輛的調度和路徑優化來削弱。

2.1多回路運輸問題

多回路運輸是現實配送中經常遇到的問題，特別是對于有諸多服務對象的大公司。針對此類配送問題，關鍵是對車輛進行正確調度。由此VRP（車輛路徑問題）模型隨之而生，成為解決多回路問題的一個重要方法。VRP模型在配送中的應用描述為：從物流配送中心同時向多個需求地（門店、客戶）配送貨物，每一個需求地的地理位置一定，需求量穩定，通過對運輸車輛合理調度和配送路徑優化，使得配送里程盡量短、時間盡量少、成本費用盡量低、車輛次數盡量少等。同時需要滿足以下幾個約束條件：（1）單條配送路線上需求地的總需求量小于等于每臺配送車輛的核準載重量； （2）單條配送路線的總長度小于等于每臺配送車輛的最大行駛距離； （3）每個需求地的需求必須滿足并且只能安排一臺車配送； （4）每臺配送車輛從離開配送中心開始到完成任務回到配送中心形成一個回路。

2.2生鮮配送與VRP模型

連鎖超市的生鮮配送是在配送中心允許的配送半徑內，根據各超市門店提供的訂貨信息，對生鮮產品進行采購、預冷、分揀包裝、冷藏運輸等作業。其目的是盡可能地加快生鮮配送速度，保證生鮮品質量，滿足客戶的需求期望從而提高企業利潤。

生鮮品的配送是一個典型的多回路運輸問題。生鮮品自身具有生命周期短、易腐爛、運輸損耗嚴重等特點，同時又是很常見的大眾消費品，其安全關乎人們的身體健康，因此，生鮮品的配送有以下幾點要求：配送環節少、速度快；配送設備齊全，從采購到入架全程冷鏈，保證安全；避免回收物流的出現，減少損耗，降低綜合成本。綜上，合理的配送至關重要，選擇合理化的配送路線、優化配送順序、降低配送成本具有重大的意義。VRP模型與其他的運輸模型不同之處在于：客戶群體大，單路徑無法滿足客戶的配送需求，同時它可以解決配送中主體選擇和配送順序的問題。此外VRP模型就是為了實現配送里程最短、準時性最高、勞動消耗最低、運力掌握最合理等目標，使用VRP模型來解決生鮮配送問題十分合理。

3　基于掃描法的連鎖超市生鮮品配送路徑設計

3.1掃描算法的描述

掃描算法是求解VRP算法的啟發式算法之一。其原理是：首先建立坐標系，以配送中心O為極坐標系的原點，以原點和任意客戶點連線定義為角度O，再給客戶群定義坐標。其次，從最小角度的客戶開始，建立一個小組，按逆時針的方向依次把剩余的客戶添加至小組中來，直到客戶的需求量超過了運輸車輛的載重量。建立新的小組，繼續依次進行下去，直到所有的客戶都被分完為止。最后，把各小組按照TSP（旅行商問題）模型的方法進行優化，選擇一條合理的線路。

3.2配送路徑優化設計案例

已知某連鎖超市以A點為基點，分別向B點、C點、D點、E點、F點、G點、H點、I點、J點9個地區門店配送生鮮，該公司標配的冷藏車載重量為6t，并有足夠多的車輛。設各個點之間的距離為C=｛Cij｜i，j=0，1，2…9｝，各點的需求量為Ni（i=1，2，…9），每臺冷藏車的行車里程為Li≤600km，以A為中心，門店點分別為B，C，…J，對應1，2，…9。根據某公司物流配送資料顯示，各個門店的生鮮需求量和配送距離及坐標值如表1所示。

表1　門店需求量及角坐標值

各個門店之間的距離及與配送中心之間的距離如表2所示。

表2　配送中心以及各個門店之間的距離

采用掃描算法對該公司配送路徑進行優化，步驟如下。

（1）以冷鏈配送中心A點為掃描中心點，逆時針為掃描方向，取C點為掃描初始點，其與A點的連線為零角度，建立極坐標系。

（2）從角度為零的AC連線開始逆時針掃描，C的需求量load1=1.5t，繼續掃描，下一個即將被劃入小組的是A點，load1=1.5+2.5=4t＜6t，繼續掃描。下一個即將被劃入小組的是D點，如果D點被劃入小組，load1=1.5+2.5+3=7t＞6t，將超出冷藏車載重量，根據掃描法分組規則需要新建一個小組，這樣第一個小組有AB兩點。重復以上的分組過程，可以得出第二小組有DGH三點，load2=6t，第三小組有EF兩點，load3=4t，第四小組有IJ兩點，load4=3.5t，中止掃描。

（3）小組內的線路優化過程。這樣就利用掃描法將9個點分解成了四組單回路運輸問題，可以通過TSP方法求解，然而，對于數量較多的TSP問題，通常無法求得最優解，只能通過啟發式算法獲得較為接近的最優解。TSP的解決方法通常有枚舉法、最近點法和最近插入法。枚舉法的列舉次數一般為（n-1）！次（n表示門店的個數），工程量大一般不用，最近點法雖然計算快捷方便但是精確度極低，一般只用作計算初始解。下面使用最近插入法對四組單回路問題求解。

由上述分析可知第一組、第三組、第四組都只有兩個門店，由對稱性可得以上三組可直接構成三個回路。

對第二組進行優化，比較表2中從A點出發的所有路徑大小：

Min｛C0i｜i∈N，1≤i≤9，且i≠0｝=C17=83.5

這樣，有節點A，H構成了一個子回路，T=｛A，H，A｝，然后考慮剩下的節點D，G到A，H兩點的最近距離：

Min｛C0i，C7i｜i∈N，1≤i≤9，且i≠0，7｝=C73=20

這樣節點A，H，D就構成了一個新子回路，T=｛A，H，D，A｝，然后只剩下一個節點G有三個位置可以插入，現在分析將其插入哪個區間合適，θ表示加入G點多走里程：

插入到（A，D）之間，θ=C06+C63-C03=84+85-85=84；

插入到（A，H）之間，θ=C06+C67-C07=84+30-83.5=30.5；

插入到（D，H）之間，θ=C76+C63-C73=30+85-20=95。

比較上述三種情況的增量，插入到（A，H）之間增量最小，所以將G點插入（A，H）之間，結果為｛A，G，H，D，A｝。最終求得配送路徑如圖1所示。

圖1　最終配送路徑

4　結語

我國的超市生鮮配送業務最早出現在20世紀80年代的外資企業中。21世紀以來，略顯規范化的本土生鮮配送行業開始發展，特別是現如今冷鏈技術發展方興未艾，為生鮮配送提供了技術和設備支持。但是，在運行模式和物流管理方面，還與西方以及日本等發達國家存在較大差距，合理化的車輛調度和路徑優化設計具有重要的現實意義。解決車輛路徑問題的方法有很多，本文針對生鮮配送面臨的問題以及車輛路徑問題的特點，對車輛配送路徑和生鮮配送進行了交叉研究，使用掃描法對連鎖超市生鮮配送路徑進行優化設計，高效率完成連鎖超市生鮮配送服務，達到了節約物流成本的目的。

參考文獻

［1］ 何炳華.物流系統規劃設計與軟件應用［M］.北京：清華大學出版社，2012.

［2］ 呂俊杰，孫雙雙.基于鮮活農產品冷鏈物流配送的車輛路徑優化研究［J］.廣東農業科學，2013（9）.

［3］ 孔陽，陳珊.層次分析法在生鮮物流配送路徑選擇中的應用［J］.中國市場，2015（33）.

孫琪（1974-），男，浙江寧波人，中國社會科學院財經戰略

研究院博士后，浙江萬里學院商學院副教授，主要從事經濟管理等方面的研究。

中圖分類號：F252

文獻標識碼：A

文章編號：2096-0298（2016）06（c）-001-02

作者簡介：王鈺祥（1991-），男，河南洛陽人，浙江萬里學院在讀碩士，主要從事全球采購與供應鏈管理方面的研究；