基于郵政網絡的社區物流多中心m-TSP問題

錢小鳳，林國龍

(上海海事大學 物流研究中心，上海 201306)

0 引言

21世紀物流在迅速發展，物聯網這個新名詞也慢慢深入人心.業內專家早在十年前就提出了社區物流的發展，但十年來，社區物流一直處于停滯不前的地步.社區物流的發展整體都存在較大問題，包括理論認識方面、政策支持方面、服務手段、配套設施等方面.

袁伯友談到了物流企業應該合作來完成社區配送，但如果社區物流發展起來，并不是單單幾個企業合作就能完成，而且不同企業之間總會存在競爭，從這一點來講，郵政最適合來擔任這個角色［1］.黃鶯對開展社區服務的策略及措施等方面進行了研究［2］.

本文的思想是將郵政網絡視作密集的、隨處可取的配送中心，通過對有社區物流需求的區域進行分區規劃來完成社區物流的配送，并且最終達到配送車輛的里程、車載量等的均衡.

1 郵政網絡參與社區物流

1.1 社區物流

本文所提到的社區物流是指以某種方式集聚的社會人的物流需求的總稱.該物流需求各式各樣，包括以生活用品、快速消費品，家電設施等具備流通、加工、定制、存儲、配送、回收等物流業態要素的物流需求.從物流起點和終端，物流服務者，物流服務對象，物流需求，物流配送來說明，社區物流的特點如下［3］：

(1)社區是以有一定的區域，有一定的數量人口，以社區為物流服務對象的社區物流可以實現共同配送，可以實現配送數量的規模經濟;

(2)提供社區物流的企業或主體需具備資金充足、資源設備豐富、網點布置密集在社區居民和居委會中有一定的威信等特點才能擔起這份責任;

(3)社區物流對象包括空巢老人，小家庭，外來打工人員，因其行動不便，或時間原因，對配送要求很高，可能需要拆零、保鮮、冷凍運輸，但要求提供及時、可靠、準確的物流服務;

(4)社區物流配送需求數量比較穩定，需求品種變化不大，需求規律容易把握.

1.2 郵政參與社區物流的優勢［4］

郵政與社區密不可分，郵政服務是構成社區服務內容的重要組成部分，郵政進入社區服務市場具有明顯的優勢.

(1)網絡優勢 中國郵政同時具備了實物流，資金流和信息流三大功能，是其他物流企業所無法替代的核心能力.

(2)品牌優勢 自新中國建立以來，郵政的綠色幾乎是信譽可靠的代名詞，這種品牌號召力，成為中國郵政參與現代物流的巨大財富.

(3)政策優勢 我國政府在1998年成立國家郵政總局，當前中國還處于社會主義初級階段，郵政存在的意義很重要，政府會實行各種優惠政策來促進郵政的發展.

郵政發展至今，雖然在各類業務方面都有突破，但總體來講，郵政資源多數還是處于閑置狀態.物流已不新鮮，但是以人群集聚為特點并細化到生活中的各種需求的物流，即社區物流還是較新鮮的一個名詞，它的發展顯然涉及到一個社會和諧的問題，必定需要政府政策的扶持，同時重要的一點是它的發展必定要有配套的設施設備.郵政現有的密集網絡，相對于其他任何物流企業而言，它為社區物流的發展提供必要的設施設備是最合適不過.所以本文將在郵政網絡的基礎上來對社區物流做分區規劃.

2 社區物流多中心mTSP模型的建立

2.1 問題定義

經過對社區老年物流特點的總結可知，社區老年物流和其他各式物流存在較大的區別.所以作社區老年物流的分區規劃時會存在以下各種問題：比如配送的資源在何處，準備如何安排;配送中心在哪里，并做怎樣的安排;要給某個居民區的老年客戶們服務，有些服務對物流設備要求很嚴格，該安排什么樣的設備;物流需求量將如何計算;服務對象老年人，一般是一些文化程度低的人群，從其所需服務來看，對服務時間、質量要求很高，又該如何做才能滿足老年人的物流需求.解決社區老年物流配送區域劃分的同時，也必定要解決好這些問題.

針對社區老年物流配送區域劃分問題，作如下前提假設：

(1)按照調查，有需求的各種資源已經采購完畢，并且各個郵政網點均有存貨，所有郵政網點都是潛在的配送中轉站;

(2)某個存在物流需求的公寓大樓、居民院、單位等即算作是一個需求節點;物品都是單流向的，即都是由中轉站配送到各個需求節點;

(3)通過調研，各需求點數目、需求量、需求規律已知，需求單位按照物品的件數計算，為SKU;

(4)貨物的裝卸和交貨時間忽略不計(貨物送達某個需求點后，由該需求點的社區居委會負責分派到每個客戶手中)，只計算車輛行走的時間;

(5)每個郵政網點配有各種車型，且每次派出的車輛能滿足運輸線路上所有客戶的需求總量;

(6)模型中通過地圖按一定比例得到需求點的位置，以兩點之間歐式距離計算.

社區老年物流配送區域劃分問題定義如下：為在某個給定的行政區域內，將一棟大樓、居民區、單位凡有某種意義上圈在一起的人群集體視作一個需求節點，統計每個需求節點的社區老年物流需求(按照文中社區老年物流需求定義來統計);通過改進的K均值聚類算法對該區域所有需求點按工作量平衡的原則進行劃分聚類工作，使得劃分后的各分區中散落的需求節點滿足下面的要求：①每個需求節點只能被劃分在一個小分區內;②同一小分區內的節點應相對集中;③每一小分區內的車輛工作量應該盡量平衡;④劃分完成后，分別由距離每個小分區最近的郵政網點為其服務.

2.2 改進的K均值算法建立社區老年物流配送區域劃分模型

2.2.1 K 均值算法原理

設有 N 個模式樣本{X1，X2，…，Xn};

第一步：首先從N個模式樣品中選擇K個初始聚類中心，c1(1)，c2(1)，…，ck(1)，其中括號內的序號為聚類迭代運算的次序號.

第二步：逐個將需分類的其余模式樣本{Xi}按最小距離(歐氏距離)準則分配到K個聚類中，初始聚類工作完成得到C1(1)，C2(1)，…，Ck(1)點集.

第三步：重新計算各個聚類域的質心，即聚類域中樣本的均值向量，并確定為每個聚類域新的中心，c1(2)，c2(2)，…，ck(2).

第四步：重復二、三兩步，直到聚類中心不再變化.聚類工作完畢.

2.2.2 改進的K均值法應用

(1)K值的確定

假設需要劃分配送區域的客戶節點集C為整體，n個客戶有需求，總需求量為Wt，如果每輛車的載貨量最大為Wm，則理想的配送車輛數大致為：k=Wt/Wm.即只考慮每個配送區域由中轉站每天派一輛車來完成社區老年物流配送的情況下，應將整個配送區域劃分為K個子區域為合理.

(2)初始聚類的確定

這里選擇均勻選擇法來確定K個聚類中心，即將整個區域劃分為m行n列，K=m×n，K個聚類中心就定位在離每個小區域中心位置附近的需求點，需要注意的是當K是合數時，盡量選擇K的比較接近的兩個因數作為m和n的值.這種起始均勻狀態下的聚類結果也會盡量接近均勻.

Weighted-K-means算法引入了一個新公式，在計算其余需求點Xi到每個聚類中心的距離時，不再使用式(1)，而是采用與權重有關的式(2)來計算，使得形成的初始聚類考慮需求點權重因素.

式中，(xj，yj)這K個聚類中心的橫坐標與縱坐標;W(cj)表示聚類中心K的權重.對于剩余每個需求點 Xi，按照 Dik=min{dij}，判斷 Xi∈ Ck.初始聚類形成.

(3)聚類迭代計算

根據式(3)、(4)分別計算每個聚類點集Ck的權重質心的(xj，yj)，即新的聚類中心ck;Wi表示各個區域中的各需求點的權重，據式(5)可得每個聚類點集的總權重W(Ck)：

根據式(6)分別重新計算所有節點到K個新聚類中心ck的權重距離，并對全部的點進行重新聚類.對于每個節點Xi，按照Dik=min{dij}，判斷Xi∈Ck：

再次得到新的聚類結果，而且是考慮了每個需求點權重的聚類結果.

對聚類結果進行收斂判斷，達到收斂準則停止計算，否則重復步驟3，直至聚類收斂.收斂的判斷是通過觀察聚類權重質心和總權重的變化波動是否保持在某個范圍內來判斷的，是則收斂，否則反之.

2.2.3 基于平衡工作量的K均值聚類結果的調整

(1)TSP引用

TSP數學描述：?連通圖H，其頂點集V，設起點為A，同時也為終點.頂點間的距離為

其中式(8)是目標函數，使得所得路徑最短，式(9)、(10)分別保證每點的出度和入度均為1，(11)式為決策變量式，式(12)保證只形成一個閉環.

(2)平衡工作量的定義

通常普通的聚類方法不能合理地將所有的需求點均衡地劃分開來，所以對聚類劃分結果需要做進一步調整.

每個聚類的工作量Wk是指綜合考慮聚類Ck中所有需求點的車輛行駛距離、網點數目、需求權重三個因素，且工作量的求解公式如(13)：

式中，Sk是指聚類劃分確定以后的聚類Ck的TSP距離;Wi指Ck中每個需求點的需求權重;Nk表示Ck中需求點的數量;ρ1、ρ2、ρ3分別表示三個因素的權值，并且分別以所有聚類的車輛行駛距離均值倒數、網點數目均值倒數、需求權重均值倒數來表示.

工作量均衡是指事先設定一個初始值W0，若每個聚類Ck的工作量Wk滿足式(14)，則稱該次聚類工作滿足工作量均衡的條件.

(3)基于工作量均衡的聚類結果的調整

計算每個聚類Ck的工作量Wk，并按照式(14)判斷聚類Ck的工作量是否均衡：若均衡，則無需調整，說明此次聚類結果比較合理;若不均衡，對所有聚類結果按如下方式調整：

根據式(15)選取聚類Cf，并對Cf聚類進行調整.選取Cf聚類中權重距離最大的節點，將其彈出，并將此節點加入到其離K個聚類中心權重距離次小的聚類.這樣操作就降低了Cf的整體工作量，接近工作量平衡的效果.

為了防止某個數據點被反復彈出，對被彈出點進行標記，當下次再次需要彈出該點時，對該點不做處理，而是選擇次遠點［8］.

在調整之后，重復步驟3再次對新得的聚類結果作工作量均衡檢驗，如此反復迭代，直至區域劃分后每個小分區的工作量差異在可允許的范圍內.

聚類及調整過程算法如圖1，圖2.

此種改進的兩階段算法添加了工作量均衡的思想，其優點總結為三點：

(a)選擇初始點，沒有采用隨機選擇方式，而采用均勻法.與傳統隨機方式相比，它能夠使初始聚類中心分散開來，使得結果更易收斂;

圖1 聚類算法流程圖

(b)在第一階段的K均值聚類迭代過程中，雖然添加了工作量均衡的思想，但K均值算法，研究至今，已經進入成熟階段，不會因為距離計算方法的變化而有太大變化，故實現起來比較容易;

(c)在算法的第二階段引入了外部約束工作量均衡的條件來判斷各個聚類的工作量是否均衡，再利用彈出機制對已完成好的聚類進行調整，使得算法更貼近實際，配送工作也更人性化.

圖2 聚類結果調整流程圖

2.2.4 郵政網點的選取

聚類結果形成以后，關鍵是選擇送貨的中轉站郵政網點，那么整個社區末端的老年物流配送才算真正完成.

圖3 郵政網點選取的算法流程

將該行政區域內所有的具有配送能力的郵政網點位置在地圖上表示出，并按地圖比例確定它們的位置坐標.對于每個聚類分區，遍歷每個郵政網點，計算包括一個郵政網點在內的該聚類分區的TSP距離，找出TSP距離最短的那個郵政網點為該聚類的末端配送中轉站，而相應的TSP距離即為該聚類的車輛行駛路線.算法如圖3.

3 實例分析

為了驗證算法的有效性，本文設計了如下算例進行論證.假設郵政速遞要利用現有網點對某區域內的42個居民小區進行配送.通過一定的比例換算，這些點集位置如圖4.

各點的需求量(單位為SKU)表如表1所示.需求總量為6428SKU，假設一輛普通的車輛的最大載貨量是800SKU，此時可得K=9，則當天用于配送的車輛為9輛.

圖4 地理坐標信息模擬圖(各需求點標號)

表1 各節點的需求量

利用matlab編程，對算例進行求解，結果如圖5.圖5顯示了42個需求點經過上面算法的求解后得到的聚類圖，共得到9類.如圖所示，改進的算法充分考慮了工作量均衡的問題，每一類中所包含的需求點的數量大致相等，而且相對集中;將就近的郵政網點，每一類的配送中心考慮進去，從而得到每個聚類的最短路線圖.

聚類結果中每個聚類包含的點集、及相應的車載量、里程數據如表2所示.從表中可以看到，車載量大致相同，車載率也相應比較高，Uk大致相等，符合算法中提出的工作量均衡的要求.改進的k均值算法使得配送區域劃分更合理，車輛配送更合理.

圖5 配送區域劃分圖(三角形表示郵政網點，虛線圈表示類別號)

表2 改進的K-means聚類分析數據顯示

4 結論

本文基于一些合理化假設，對社區物流進行了研究，首先是對社區物流作了一些解讀，并解釋了利用郵政資源的目的。在此基礎上，利用工作量均衡標準，通過聚類算法和TSP問題，研究了社區物流配送區域劃分的問題，并用matlab對算法進行求解.該模型的建立可以同時解決在社區物流分區規劃時，對配送車載量、車里程量等幾個方面的提出的均衡要求.最后通過算例，驗證算法的有效性.

社區物流是一塊還未開墾的荒地，其各方面的研究還處于初級階段，還沒有形成完善的結構體系，需要對其進行更加深入的研究.隨著電子商務和物聯網的發展，社區物流也必將會迎來一個更快的發展階段.

［1］袁伯友.基于社區物流的物流企業配送策略探討［J］.物流技術，2009，28：2-4.

［2］黃鶯.郵政參與社區服務市場的研究［J］.郵政研究，2003，19：17-19.

［3］姜燕寧.基于社會管理創新的社區物流發展對策研究［J］.商業時代，2011，28：4-6.

［4］薛君.中國郵政發展現代物流的可行性分析與策略建議［J］.西安郵電學院學報，2003，8：14-17.

［5］王勇，毛海軍.帶時間窗的物流配送區域劃分模型及其算法［J］.東南大學學報，2010，40：1077-1083.

［6］謝可.物流配送系統中聚類算法的研究與應用［D］.浙江：浙江大學，2006.

［7］朱培芬，漢吉慶.基于改進K-means算法的煙草配送區域劃分［J］.物流工程與管理，2009，31：84-85.

［8］谷偉，張群.基于改進K-means聚類的物流配送區域劃分方法研究［J］.中國管理信息化，2010，13：60-63.