覆蓋模型下的跨區域配送線路優化——以涼山煙草物流配送為例

涼山州煙草公司物流中心 葉嵐

煙草行業面對零售客戶的卷煙配送一直是煙草物流中心的重要環節，及時滿足客戶需求，實現卷煙配送的高效率和低成本，是卷煙物流配送環節中的重要部分。2012年煙草行業開展精益物流工作，應對不斷面臨的挑戰。但在卷煙配送過程中，零售客戶終端具有數量大，分布廣，需求量不定等特點，不同的送貨線路之間存在任務量不均衡問題，易造成配送車輛裝載率較低，配送資源浪費和一系列的服務質量問題，屬于大規模的車輛線路規劃問題（Vehicle Routing Problem,VRP），僅僅通過增加配送車輛和人員等滿足配送服務，不符合精益物流的基本要求，因此必須尋求新的方法對配送線路進行優化，從根本上解決配送問題。

而在卷煙配送實現在途管理的基礎上，卷煙配送線路的優化可通過構建電子地圖，確定零售客戶的位置及經濟可行距離，有助于將大量離散點客戶進行聚類分析，減少需求點的信息。通過選址模型能有效覆蓋所有需求點信息，促進線路優化的進行。因此，本文在以后在途管理系統和選址模型的理論基礎上，從選址角度提出優化配送線路模式。

隨著卷煙配送在煙草精益物流建設中的地位不斷提升，已有很多學者對優化煙草配送路線進行探討。陳子俠（2003）研究了城市卷煙配送線路的網格劃分算法；史亞蓉，萬迪昉等（2009）分析了基于GIS的物流配送線路規劃研究；吳耀華等（2011）研究了在GIS環境下基于P-種植模型的卷煙配送體系優化。上述研究成果對卷煙配送線路優化的具體實施具有重要意義。但是，卷煙配送只能通過物流配送中心統一進行管理配送，并且需求客戶數量大分散廣需求量不定，運用傳統VRP優化算法求解，復雜性高、計算耗時大，針對卷煙配送偏遠地區道路交通狀況差，配送成本高，不能及時送貨到戶等問題的研究方法較少，缺乏大范圍推廣及應用，對卷煙配送線路優化方法的探索研究尚顯不足。

據此，本文結合煙草物流自身理化屬性，通過研究涼山州煙草物流配送模式，以優化涼山州煙草物流配送線路為主要研究對象，運用電子地圖以及集合覆蓋理論建立模型，分析研究煙草物流配送的新方法，為煙草物流配送模式研究提供理論依據，促使跨區域配送在實踐中進一步合理的應用與推廣。

一、涼山煙草物流配送模式

涼山煙草公司目前在西昌市擁有6000多家卷煙零售網點，為滿足全州煙草發展需求，2009年在西昌市西寧建成卷煙物流配送中心，并配有20余輛不同種類的運輸車。基于涼山實際，配送中心將卷煙零售網點按區域劃分，制定65條配送線路，在配送方式上采用“一訪二分三送”，即采取一周一訪的形式在一天內收集卷煙零售戶需求訂單，第二天進行分揀到戶，第三天送貨到戶。零售卷煙客戶量多且分散廣泛，目前采用按區域劃分配送線路具有一定的局限性，并且存在線路運輸量過少或過多，容易造成配送車輛裝載率低或無法滿足客戶需求，不能及時完成卷煙配送，因此，如何及時滿足客戶需求和處理不同送貨線路的任務量，從而降低物流成本，提高配送效率，是涼山煙草實現煙草精益物急需解決流的主要課題之一。

二、覆蓋模型和算法

(一)覆蓋模型

覆蓋模型，是對于需求已知的一些需求點，確定一組服務設施來滿足這些需求點的需求。根據解決問題方法的不同，覆蓋模型可以分為兩種不同的主要模型：集合覆蓋模型，用最小數量的設施去覆蓋所有的需求點；最大覆蓋模型，在給定數量的設施下，覆蓋盡可能多的需求點。本文中通過尋找最少虛擬卷煙物流中轉站，可減少配送線路，提高裝載率和車輛利用率，減少資源浪費，提高配送效率，因此采用集合覆蓋模型。

圖1 集合覆蓋模型

圖2 最大覆蓋模型

(二)集合覆蓋模型的建立

目前，煙草物流配送體系為實現卷煙配送的全程跟蹤，建立城區地理信息系統（Geography Information System，GIS），并在每輛卷煙配送車輛上都進行安裝，因此：可確定卷煙配送網點中任意兩點間的經濟可行距離，即從物流中心或客戶需求點到另一客戶需求點的有效距離；根據城區的街道情況，將其劃分為兩個等級k={I，II}，I等級為一般道路，II等級為高速公路；在電子地圖中確定物流中心及所有客戶的地理位置、客戶的編號和需求量等。

卷煙物流配送涉及客戶數量大、范圍廣，在實際配送中將相對集中的客戶一次配送，符合實際優化情況，因此集合處于同一路段上的零售商客戶點形成需求點集，并滿足以下要求：相鄰需求點間的距離小設定固定值；按照就近原則，若某一路段需求點較少或相鄰需求點間距離過大，可選擇臨近路段的需求點集。因此，需求點集的定義如下：

其中C為零售商客戶點的集合，同一路段相鄰客戶點的距離G滿足G（Gi，Gi+1）;posc表示需求點集的中間位置，其中作為需求點集的長度，取點集中相鄰最遠點的距離；d表示需求點集的需求量，為點集中所有客戶的需求量總和。結合GIS將所有需求點集以及道路情況等信息通過圖形表示，如圖4所示：

圖3 需求點集及道路情況信息

圖中各點集點由編號（點集需求量，到物流中心距離，道路狀況）進行表示，道路情況由（需求點集間距離）進行說明。

本文卷煙配送線路優化中，尋找盡量少的虛擬物流配送中轉站，因此數學模型目標函數為：

數學模型為：

其中：

N—根據路段劃分的客戶需求點集的集合；

M—需求點集中可稱為虛擬物流中轉站點集的集合；

—第i個需求點集的需求量；

—虛擬物流中轉站j可提供的供給量；由于卷煙配送均由配送車輛配送，每個配送車輛都有額定裝載量L，因此虛擬物流中轉站可提供的最大供給量為配送車輛額定裝載量的倍數，即：由于涼山煙草物流中心現配備配送車輛有15量，額定裝載量為100件/車，根據實際卷煙配送情況可知，若客戶需求點距離物流中心較近，可進行一天兩次配送，為方便研究，本文根據需求點集的道路情況確定虛擬物流中轉站的供給量分別為：k=I；k=II。

—虛擬物流中轉站j可覆蓋的需求點集i點的集合；

—可覆蓋需求點集i的虛擬物流中轉站j點的集合；

—0-1變量，表示在j點建立虛擬物流中轉站，表示不在j點建立；

—需求點集i點需求中被分配給虛擬物流中轉站j的比例；

—物流中心到虛擬物流中轉站j的距離；

—客戶需求點集i到虛擬物流中轉站j的距離；

—最佳經濟配送半徑，依據道路等級k={I，II}確定，遵循依托一般道路k=I的送貨半徑為，依托高速公路k=II的送貨半徑為。

(三)模型求解

Step 1：初始化。令所有的，并根據道路狀況和到物流中心距離確定集合和。如表3-1所示:

表3-1 初始化

Step 2：選定一個虛擬物流中轉站。在M中選擇，且的規模為最大的點為虛擬物流中轉站，即，令，并在M集合中剔除節點，即。

Step 3：確定虛擬物流中轉站的配送范圍。如果將中的元素按的規模從小到大的順序指派給，直至的容量為或為空。其中對于且，將i支配給的方法為：

若，則令，

在和N中剔除需求點i。

若，則令。

Step 4：若N或M為空，則停止；否則，更新需求點集集合和虛擬物流中轉站集合，轉第二步。

Step 5：選取任一虛擬物流中轉站M0，以物流中心作為出發點，采用Edmonds算法使配送到虛擬物流中轉站覆蓋的離散點客戶距離最短：首先根據覆蓋區域內的地理位置分布，繪制出地理結構圖G如圖5，如果圖中所有頂點都是偶點，則從任一頂點出發每條邊僅需經過一次，如果圖中含有奇點則將圖中所有奇點提出，并將任意兩頂點相連構造新圖G*，G*中邊{Vi，Vj}的值為G中頂點Vi到Vj的最短距離。其次在G*中找一個最小值完美匹配M’，使G*中每個點與M’中的邊關聯，且M’的值最小。最后在G中將相互匹配的奇點用最短路徑相連，得出G的最小新增邊集。

圖4 虛擬物流配送中轉站內需求點的地理結構圖

圖中P為卷煙物流中心，各頂點表示某一虛擬物流中轉站中需求客戶，每條邊的數字為道路長度，由于卷煙配送過程中，配送車輛需將貨物配送到所有零售客戶手中，完成配送后再返回郵局，因此通過Ed?monds算法可得出虛擬物流中轉站內所需走的重復道路，選出最優配送路線。

(四)模型應用分析

以涼山州煙草專賣局（公司）所有卷煙零售網點的分布情況、道路情況以及需求量信息等為依據，通過模型的計算分析，最終得出65個虛擬物流中轉站，同時對所有卷煙零售網點的配送路線重新規劃，配送線路優化實施前后效果對比如表1所示。

表1 優化效果對比圖

通過對比表明，覆蓋模型下的跨區域配送線路優化能有有效整合人力資源，增強物流中心的管控力度，提高送貨及時率和配送服務質量，在擴大配送范圍的同時能減少物流資源的浪費。

三、結束語

本文基于涼山煙草物流配送體系，通過采用集合覆蓋模型，提出針對卷煙零售終端配送優化的新模型。通過模型建立，尋找虛擬卷煙物流配送中轉站作為新的配送線路，最終達到提高配送車輛裝載率，優化配送線路，降低物流成本，提高配送效率。

文章在優化配送線路中采用新的模型算法，從選址角度對離散多點客戶進行聚類劃分，與前人的研究相比，針對偏遠地區道路交通狀況差，配送成本高，不能及時送貨到戶等問題的方法研究方面進行了突破，研究方法和思路上有很大的突破，對解決大規模網點的問題上有很大的研究價值和推廣前景。

[1]陳子俠.城市卷煙配送線路的網格劃分算法[J].上海交通大學學報,2003

[2]史亞蓉,萬迪昉,李雙燕,呂珍玉.基于GIS的物流配送路線規劃研究[J].系統工程理論與實踐,2009

[3]胡耀華,谷吉祥,李定軍.從“1十 4 ”到“1 十3”——GIS環境下基于P－中值模型的卷煙配送體系優化研究[J].湖南煙草,2011