基于居民出行起訖點分布特性的集中交付點選址方法

邊 軍，丁 喬，渠志云

（1.包鋼礦業有限責任公司，內蒙古 包頭 014000；2.內蒙古第一機械集團有限公司，內蒙古 包頭 014000）

0 引言

隨著電子商務的飛速發展，物流行業迎來難得機遇的同時也面臨著巨大的挑戰?？爝f業務量的急劇增長使得最后一公里配送成為難題。由于快遞員送貨與客戶收貨時間窗經常無法匹配，導致出現配送延遲遭客戶投訴以及多次配送增加配送工作量等問題。如何提高配送服務滿意度和配送效率成為亟待解決的難題。針對這一難題，有研究學者提出CDP 配送模式，如Song L[1]指出為了應對中國網絡購物市場的迅猛發展，最后一公里問題備受關注，但上門配送模式失敗后會導致運營成本增加。同時，也有研究學者對CDP 配送模式的接受程度進行了調查，如Yuen K F[2]以創新擴散理論（IDT）為基礎，分析了顧客是否愿意將CDP配送模式作為最后一公里交付方式，調查數據收集自164 名新加坡消費者，采用層次回歸分析方法進行分析，結果表明CDP 模式明顯優于其他最后一公里交付方式。CDP配送方式都能有效地解決上門配送中快遞員和客戶時間不一致問題，有效地緩解了最后一公里配送這一難題。隨著CDP模式不斷推廣，CDP選址是否合理，將直接影響到客戶使用的方便性、CDP的使用率、客戶滿意度及運營商收益等，因此，CDP選址成為亟待解決的問題，找到一種合適且高效的CDP 選址方法成為解決這一問題的關鍵。

1 研究現狀

針對物流設施選址問題，國內外學者進行了大量研究，黃風春[3]在傳統的最大覆蓋模型的基礎上，以快遞公司投放快遞柜后收益最大化為目標函數，建立數學模型，使用設計的BPSO 算法對模型求解，完成對智能快遞柜的選址。G R Sutanto，等[4]通過k-means 聚類算法確定設施位置并且完成對客戶的分配，然后使用三種聚類評估方法分別從選址結果的連通性、緊湊性、分離因子三個方面進行評價。黃濤[5]提出了一種結合地理空間信息的快遞自提點選址方法，通過對地理空間信息分析確定快遞自提點備選地址，利用距離懲罰成本函數對CFLP模型進行改進建立快遞自提網點選址模型，實現自提網點選址。Irawan，等[6]針對兩階段供應鏈中的多產品設施選址問題，以配送點的固定成本和運輸成本最小為目標函數，建立數學模型，并設計了一種結合聚集法和精確算法的求解方法對模型進行求解，并驗證了其建立模型和算法的有效性和優越性。Kedia，等[7]在消費者對CDP 可接受性研究中指出：CDP 與住宅和工作區的距離是影響CDP 接受度的一個重要因素。Esser和Kurte[8]在對CDP使用過程的調查中發現有80%的人更愿意把到CDP行程與其他出行行程相結合。

綜上可知，居民更傾向于把到CDP 取寄快遞和其他的行程相結合，比如，在上下班的路上順便到CDP 取寄快遞。所以，CDP 的選址應該結合居民的出行規律，盡可能使到CDP 取寄快遞的行程與居民的日常出行行程結合更為便利，但目前還沒有針對CDP這一特性的選址方法。

2 方法概述

在CDP 選址研究中充分考慮居民出行OD 點分布特性，便于居民將到CDP 的行程與日常行程進行關聯。如圖1（a）所示，將到CDP 行程作為日常行程一部分，避免了把CDP 單獨作為出行行程造成時間和距離的浪費，如圖1（b）所示。在對OD樣本點分析時，還應該考慮OD樣本點的相對位置關系，如：靠近住宅區要比靠近購物中心的OD 點對選址結果的貢獻更大，因此，需要根據OD 點對選址結果的貢獻度為其設置不同的權重值。計算權重值應考慮OD 點在一定范圍內包含POI 數量和各POI 與其的距離。然后，使用Mean Shift 聚類算法對不同權重值的OD點進行聚類分析，得到OD點聚類簇用于反映居民出行起訖點規律，聚類簇成員越密集，表示該區域居民日常訪問越頻繁，聚類簇中心表示CDP 設施地址的備選點。

圖1 居民行程對比示意圖

2.1 均值漂移聚類分析

Mean Shift 是基于密度的非參數聚類算法，根據當前點與給定空間內樣本點的偏移向量計算出當前點的偏移均值，然后，按照該偏移均值向量更新當前點位置，并以此位置作為新的起點，重新計算偏移均值，以此方法迭代計算，直到滿足算法設定的終止條件。由于其計算速度快且具有較強的魯棒性，所以，本文選用此聚類算法完成對OD點的聚類分析。

假定d維空間Rd中的n個樣本點xi（i=1,2,...,n），對于任意一點x，其Mean Shift 偏移向量的形式為：

其中Sh表示在半徑為h的區域內樣本點的集合：

k表示落入Sh區域樣本點的數量。

將球心x沿著偏移向量更新：

其中xs為偏移后的球心。將終止條件設為Mh(x)≤ε，ε為容許誤差。

考慮到樣本點個體的差異性，不同的樣本點對Mh(x) 會產生不同的貢獻度，因此，在基本的Mean Shift 算法中引入核函數和樣本權重，偏移向量擴展形式為：

G(x)為單位核函數；H是一個正定的對稱d×d矩陣，一般稱之為帶寬矩陣；w(xi)≥0 為樣本點xi的權重值。

Mean Shift中，常用的兩類核函數為：

（1）單位均勻核函數，見式（6），如圖2（a）所示。

（2）單位高斯核函數，見式（7），如圖2（b）所示。

在本文聚類方法研究中，距離中心點越近則對偏移向量的貢獻度越大，表明不同的樣本點對偏移向量的貢獻度是不同的，而單位均勻核函數并不能反映這個特性，所以選擇單位高斯核函數，如圖2 所示。

圖2 單位核函數

Mean shift聚類基本流程如圖3所示：

圖3 Mean Shift算法流程圖

（1）在樣本空間隨機挑選一個未分類的樣本點x作為初始中心點。

（2）獲取滿足條件的樣本點集合，記為Sh。

（3）以初始點x為中心，以x為起點和Sh集合的點為終點分別作向量，根據式（4）計算Mh(x)。

（4）判斷Mh(x)是否滿足終止條件，若滿足，則結束循環，重新執行步驟（1）-（4），否則重復步驟（2）-（4）。

（5）直至所有樣本數據都完成分類，結束算法，輸出聚類分析結果。

2.2 居民日常出行樣本數據權重值設置

住宅區作為一種參與居民日常出行最頻繁的POI類型，距離住宅區的遠近將直接影響居民是否方便將CDP 行程與日常出行相結合，從而影響CDP 的使用率，所以在為每個OD 樣本點賦予權重值時，主要考慮樣本點在規定區域內所包含的住宅區POI 數量和距離，即樣本點在一定范圍內所包含的住宅區POI點越多且與這些POI點的距離越近，則該樣本點的權重值越大。具體計算公式見式（8）。

w(i)表示OD樣本點i的權重值；C(i)表示OD樣本點i在半徑R內所覆蓋住宅區POI 集合；Dij表示OD樣本點i與C(i)中住宅區j的距離。

式（8）表示樣本數據權重值由OD樣本點覆蓋的住宅區數量和與其距離決定。通過對OD 樣本數據進行聚類分析，聚類簇中心可以反映出居民出行OD點分布規律，同時也能保證對住宅區的覆蓋率，提高CDP使用的便利性和使用率。

2.3 最優聚類半徑選取

本文采用統計分析方法選取最優聚類半徑。首先，結合實際情況和參考文獻選取最大聚類半徑hmax和最小聚類半徑hmin，然后以Δh為間隔取多組聚類半徑hi，取每組聚類半徑hi將樣本點進行聚類分析。對每次聚類分析結果進行統計分析，將每次聚類后所得的聚類簇按照成員數量Ci進行降序排列，計算每個聚類簇成員數量在總樣本數據中的占比Pi，見式（9）。

其中Pi為第i個聚類簇所含成員數量在總樣本數據中的占比，Ci表示第i個聚類簇成員點個數，n表示形成聚類簇的數量。將Pi進行依次累加，見式（10），其中Pa為累加比例，k為累加的聚類簇數量。

若聚類簇成員較少，可判定該區域居民日常出行訪問的頻率較低，為了保證CDP 使用的便捷性和使用率，則此類聚類簇中心不適合作為CDP 選址點。故本文設置樣本數據占比PT對此類無效聚類簇進行清洗。Pa與Ck的關系示意如圖4 所示，即Pa=PT時，將對應第k個聚類簇成員數量Ck作為聚類簇的清洗條件，即當Ci≤Ck，則該聚類簇被清洗，反之保留。

圖4 Pa_Ck 關系示意圖

將每組聚類半徑依次進行聚類分析，統計每次聚類分析中的聚類半徑h和對應的Ck值，最后將h和Ck數值進行函數擬合，得到擬合函數曲線，通過數據特性分析確定Mean Shift算法的最優聚類半徑。

3 實例分析

3.1 數據準備

出租車作為一種重要的公共交通方式，其出行的起訖點完全由乘客決定，能夠非常貼切地反映居民出行的規律。出租車與其他出行方式相比，其軌跡更易收集且數據量大，因此，本文將出租車運行GPS 軌跡數據作為實例分析的樣本數據來源之一。選取山東省濟南市歷下區1 005 輛出租車一個星期的運營數據。數據的主要字段信息見表1，其中tflag表示是否有載客，即0表示空載，非0表示載客，將其數值由零變為非零或由非零變為零作為判定乘客上下車點的依據。將tflag數值突變時對應的經緯度進行提取，作為居民出行的OD 數據樣本點，用于聚類分析。

表1 字段信息表

公交車作為上班族通勤最常用的交通方式，所以其運營數據能夠充分體現上班族的出行規律，故選取了濟南市歷下區包含的共28個公交車站點的運營數據，根據乘客上下車刷卡信息，提取出乘客的上車點經緯度，與上面的出租車數據共同作為居民出行OD數據樣本點。

將OD樣本數據和歷下區638個住宅區POI數據分別通過分布圖和熱力圖直觀地展示在百度地圖上，如圖5和圖6所示，通過對比圖5（a）和6（a）可知：OD樣本點和住宅區POI點在千佛山等風景區區域中都沒有分布；從大明湖公園到千佛山景區之間主要分布有商業區以及娛樂場所，所以，該區域表現為OD樣本點熱區，但住宅區分布卻稀少。

由圖5（b）和圖6（b）可知，除了以上特殊區域，其余區域OD點熱力分布與住宅區POI熱力分布基本吻合。由此反映出OD點與住宅區分布具有相關性，以上特殊區域的分布情況也體現了二者也具有差異性。不同OD點對選址結果的影響不同，也證明了為OD點賦予不同權重值的必要性。

圖5 歷下區OD點分布情況

圖6 歷下區住宅區分布情況

3.2 聚類分析

根據肖卡飛[9]關于服務性公共設施服務半徑與客戶滿意度關系的研究，500m 為客戶普遍認為的最大可接受步行距離，超出這個距離客戶會產生抵觸心理，據此選取范圍半徑R=500m，代入式（8）計算每個OD 樣本點的權重值。設置聚類半徑系列hi，hmin=50m、hmax=800m和Δh=50m?？紤]現有普通民用GPS 精度約為10m，設置容許誤差ε=10m作為算法終止條件。分別完成對聚類半徑系列hi的聚類分析，獲取每次聚類分析后得到的Ck值，統計值見表2。

表2 hi-Ck 值實驗數據結果

利用MATLAB 分析軟件將得到的hi-Ck數據進行曲線擬合，擬合函數使用三階多項式函數。所得擬合函數見式（11），擬合曲線如圖7所示。

由圖7可知，Ck隨著hi整體呈遞增趨勢，但在不同hi范圍，函數的斜率不同，反映了Ck隨hi變化的快慢，當擬合函數的一階導數為零時，表示函數變化趨于穩定，即此時hi小幅度變化，Ck變化量很小，故選擇擬合函數一階導數為零時的hi作為最優聚類半徑。通過計算求得當擬合函數一階導數為零時對應的hi分別為h1=249.5m和h2=450.4m。以這兩個聚類半徑分別進行聚類分析，得到的聚類結果見表3。通過將聚類結果進行對比分析，可知這兩個聚類半徑下聚類簇數量相差多達153 個，但對500m 范圍內住宅區覆蓋率相差很小，僅2.50%?？紤]對物流體系建設成本的控制，故選擇450.4m為最優聚類半徑，可以較低的成本，實現對住宅區較高的覆蓋率。

圖7 hi-Ck 擬合曲線

表3 聚類結果數據對比

3.3 選址結果對比分析

將最優聚類半徑下的聚類簇中心通過百度地圖進行可視化展示，如圖8（a）所示，將該結果與不為OD樣本點賦予權重值的聚類簇分布結果進行比較，如圖8（b）所示，可知加權值的聚類簇中心更加趨向于住宅區密集區域，極大地提高了對住宅區的覆蓋率，滿足本文CDP 選址的需求。不加權重值的聚類簇分布趨于平均分布，即使在沒有住宅區分布的商業娛樂區依然有聚類簇中心點分布，違背了本文選址需求的初衷，也從側面反映出賦予權重值的必要性。

圖8 聚類結果分布圖

根據Liu C[10]提出的趨近于便利店和交通便利區域的調整原則，將不合理的CDP 設施地址備選點進行局部調整后，得到CDP 選址點91 個。菜鳥驛站作為目前我國最后一公里服務的典型代表，主要為消費者提供多元化的最后一公里配送業務，故選取了本文選址區域內所有菜鳥驛站站點，共93個，與本文選址結果進行數據對比分析，二者站點分布圖如圖9所示，對住宅區覆蓋率對比數據見表4。經對比分析可知，本文選址結果中選址點的數量與菜鳥驛站站點數量相差不大，但相較菜鳥驛站本文選址結果對住宅區具有更高的覆蓋率。

圖9 選址點分布對比圖

表4 住宅區覆蓋率對比表

4 結語

本文通過使用濟南市出租車和公交車的運營數據作為分析居民日常出行OD分布規律的試驗數據，結合POI 分布進行了Mean Shift 聚類分析，最終實現濟南市歷下區的CDP地址的選取。本文將居民日常出行OD分布規律與CDP選址相結合，提高CDP的使用率，節約居民日常出行時間和行程。通過將本文的選址結果與菜鳥驛站網點分布情況進行對比，在相同的服務半徑條件下，得到本文選址結果對POI的覆蓋率更高，選址點數量也更少。最后，通過調整不合理的聚類簇中心點，在不改變聚類中心數量的情況下，提高了POI覆蓋率，確定CDP選址點。

本文為最后一公里集中交付點選址提供了新的思路，也存在不足之處，同時也是以后致力要實現的，由于缺少相關數據的支撐，本文沒有對CDP選址點容量進行研究，因為CDP 的容量和它所覆蓋區域POI使用人數和頻率的數據有關，本文尚未涉及相關數據。