基于客戶出行規(guī)律的物流末端配送算法研究

劉定一，黃 慧，應 毅 （三江學院，江蘇南京210012）

LIU Dingyi, HUANG Hui, YING Yi (Sanjiang University, Nanjing 210012, China)

0 引 言

近年來，隨著電子商務的普及，快遞業(yè)務量迅猛增長，末端配送問題隨之也陷入困難的局面，受到物流行業(yè)的廣泛關注。由于末端配送模式以直接配送為主，且對配送過程的效率和質(zhì)量缺乏有效的控制，導致末端配送時間不確定性高，配送效率低下，常出現(xiàn)“二次投遞”的情況[1]。為了提高末端配送的效率問題，學者們展開了一系列的研究。文獻[2]基于工廠園區(qū)的物流數(shù)據(jù)，利用FlexSim 建立仿真模型，將運輸車輛的使用效率以及訂單的運輸時間作為研究指標，以降低末端配送的時間成本和人工成本。文獻[3]和文獻[4]利用FlexSim 可視化仿真技術，針對分揀系統(tǒng)進行建模以提升末端配送的效率。此外，學者們還從構建倉配一體化共同配送模式[5]、建立城市共用末端配送站[6]、創(chuàng)建多溫層共同配送[7]等方面來分析末端配送問題，都取得了一定的進展。

1 末端配送研究現(xiàn)狀及本文工作

隨著快遞業(yè)務的迅猛發(fā)展，末端配送問題成為學者們的研究熱點。為了降低末端配送的人工和時間成本，提高末端配送的效率，研究通常以“快遞公司”為主體，通過提升車輛運輸效率、優(yōu)化分揀算法等方式來改進末端配送模式[8-10]。然而，在末端配送的問題中，還有一個更為重要的主體——“客戶”，他們的出行規(guī)律在末端配送問題的研究中也起著不可或缺的作用。如果快遞公司掌握了客戶的出行規(guī)律，在每次配送時僅配送當前未外出的客戶，可極大地避免“二次投遞”的問題；同時，由于智能快遞柜容積有限，若配送時刻掌握了客戶已外出的信息，則可優(yōu)先配送未外出客戶的貨物，從而促進智能快遞柜的使用率。

針對以上問題，本文通過通信運營商獲取客戶基于時間序列的手機定位數(shù)據(jù)，通過對數(shù)據(jù)進行分析還原客戶現(xiàn)實生活活動軌跡，研究客戶的出行規(guī)律，提高末端配送的效率。本文的貢獻如下：

（1） 分析客戶的手機定位數(shù)據(jù)，獲取客戶的“停留點”，形成時空數(shù)據(jù)，研究基于時空數(shù)據(jù)的聚類算法，挖掘客戶在工作日的出行規(guī)律。

（2） 研究客戶停留在居住點的時間區(qū)域和快遞末端配送的時間區(qū)域的關系，形成可靠的末端配送方案。

（3） 結(jié)合天氣因素研究客戶周末的出行規(guī)律，提出基于天氣加權方法的聚類算法，提高配送成功率。

本文基于客戶出行的規(guī)律進行研究，提出基于客戶出行的末端配送算法（Terminal Delivery Algorithm based on Customer Travel，TD-CT），以提高快遞公司末端配送的成功率及效率。

圖1 基于TD-CT 算法的末端配送流程

2 TD-CT 算法

TD-CT 算法思想是基于客戶手機定位數(shù)據(jù)，研究客戶的出行規(guī)律，獲取用戶停留在家庭住址的時間段，根據(jù)配送時間決定最終是否為客戶進行配送。TD-CT 算法分為四個部分：針對客戶的經(jīng)緯度坐標進行聚類分析、獲取客戶家庭住址、獲取客戶停留在家庭住址的有效時間段、是否進行末端配送。算法流程如圖1 所示。

2.1 聚類分析

定義1：聚類（Clusteri）。設定距離閥值為ε，手機用戶的坐標點集合記為L=｛L1,L2,…,Ln｝，其中，每個Li是由經(jīng)度和緯度組成的坐標點。在連續(xù)的時間段內(nèi)，對于?Li，Lj∈L，若存在Dis（Li,Lj）≤ε，則稱Li和Lj屬于同一聚類。

定義2：坐標距離，表示為Dis（Li,Lj）。Dis（Li,Lj）為坐標Li和Lj的實際距離，且有公式：

其中：Er為地球平均半徑，值為6 371.004 km。

通過通信運營商獲取客戶手機定位數(shù)據(jù)如表1 所示。

表1 手機號為13******345 的客戶手機定位數(shù)據(jù)

針對客戶的經(jīng)緯度坐標進行聚類的算法思想分為四個步驟：

步驟一：按手機號對客戶分組，將同一客戶手機定位數(shù)據(jù)按時間先后排序。步驟二：根據(jù)用戶手機號創(chuàng)建首個聚類Cluster1UserTe［ ］l，該聚類的表達形式為{＜Time1，（緯度坐標1，經(jīng)度坐標1） ＞,…, ＜Timei，（緯度坐標I，經(jīng)度坐標i） ＞}，獲取客戶首條記錄的時間和定位坐標，設置為Cluster1UserTe［ ］l當前中心點坐標，同時將該坐標放入聚類中。

步驟三：設置距離閥值ε 為200 米。遍歷客戶的下一條手機定位數(shù)據(jù)，計算該條數(shù)據(jù)與聚類中心點坐標的坐標距離。若Dis（Li,Lj）≤ε，則將該坐標加入上一個聚類，并重新設置聚類的中心坐標點，中心坐標點的設置方法為將當前所有的點按時間段長度的比重求和得到；若Dis（Li,Lj）＞ε，則創(chuàng)建一個新的聚類，并將該坐標加入新的聚類中，同時設置該坐標為新聚類的中心坐標點。

步驟四：判斷是否還有未處理的客戶手機定位數(shù)據(jù)，如有，則讀取并轉(zhuǎn)到步驟三；否則，結(jié)束聚類過程。

其中，步驟三中心坐標點的計算公式為：

Center緯度為一個聚類的緯度中心坐標，Center經(jīng)度為一個聚類的經(jīng)度中心坐標；i表示一個聚類中不同的坐標點個數(shù)；Timei表示一個聚類中客戶停留在某個坐標點的時長；TotalTime表示一個聚類中所有坐標點的總時長；Coordinate緯度表示第i個坐標點的緯度坐標；Coordinate經(jīng)度表示第i個坐標點的經(jīng)度坐標。

算法1：針對客戶的經(jīng)緯度坐標進行聚類，算法為GetClusterByUserLocation，其偽代碼如下：

輸入：客戶手機定位數(shù)據(jù)，距離閥值ε

輸出：所有聚類

2.2 獲取客戶家庭住址

算法思想：人為設置夜間時間段為晚8：00 至次日早8：00，將該時間段記為NightInterval，若客戶在該時間段停留時間超過6 小時，且停留率（StayRatio）超過閥值δ，則將客戶在該停留段時間對應的坐標設置為“家庭住址（HomeAddress）”。

其中：夜間單個坐標點停留在家庭住址6 小時以上作為一次停留，記作SingleStay；夜間停留6 小時以上的不同坐標點總次數(shù)記做TotalStay。停留率的公式如下：

算法2：獲取客戶的家庭住址的算法為GetUserAddress，其偽代碼如下：

輸入：閥值δ

輸出：家庭住址對應的坐標

2.3 獲取家庭住址有效停留時間

算法判斷分為工作日和周末時間，若為工作日時間，則根據(jù)家庭住址停留時間段和總家庭住址停留時間計算家庭住址有效停留時間；否則，通過天氣加權法的方式計算家庭住址有效停留時間。

2.3.1 工作日時間

若是工作日時間，則依次遍歷該客戶的每個聚類，若Dis（HomeAddress, Center ）≤200m，Center 為聚類的中心點坐標，則標記該聚類為“家庭住址聚類（HomeAddressCluste）r”，同時記錄聚類的起始時間和結(jié)束時間，記為HomeStayInterval。若發(fā)現(xiàn)HomeStayInterval 總是成周期性的出現(xiàn)，則將該時間段設置為有效停留時間，記為ValidStayInterval?？梢罁?jù)式（5） 判斷是否為ValidStayInterval。

其中：COUNT（StayInterval）表示符合此時間段內(nèi)停留在家庭住址的次數(shù)，Total為聚類集合中符合此時間段的總次數(shù)。若StayIntervalRatio的值超過閥值δ，則可標記該時間段為有效停留時間，即ValidStayInterval。

算法3：家庭住址有效停留時間算法為GetValidStayInterval，其偽代碼如下：

輸入：閥值δ，家庭住址對應的坐標

2.3.2 周末時間

若是周末時間，則表1 中添加字段天氣，根據(jù)時間字段的值，獲取對應的天氣信息。獲取有效停留時間與算法3 相同，但是StayIntervalRatio的計算則需要考慮天氣情況。其中：OutInterval表示外出的時間段，w表示雨雪天外出的概率。則可依據(jù)式（6） 判斷是否為ValidStayInterval。同理，當StayIntervalRatio的值超過閥值δ 時，則設置該時間段為ValidStayInterval。

2.4 判斷是否進行末端配送

若快遞員配送的時間點包含在有效停留時間段內(nèi)，則提示配送，否則提示暫緩配送。

3 實 驗

以某小區(qū)的豐巢智能快遞柜為例，記錄了200 個智能快遞箱共計7 天的投遞情況，如表2 所示。

通過實驗表明，TD-CT 算法有助于提高智能快遞柜的使用率，尤其在周末時間，使用率得到顯著提高，說明本文提出算法的有效性。

4 總 結(jié)

本文基于客戶的出行規(guī)律提出了一種末端配送算法，簡稱TD-CT 算法。該算法根據(jù)客戶的手機定位數(shù)據(jù)獲取家庭住址信息，進而判斷客戶在家庭住址的有效停留時間，從而給出配送策略。實驗表明，本文提出的算法可以很大程度上提高智能快遞柜的使用效率。

表2 智能快遞柜7 天使用情況