劉定一，黃 慧，應(yīng) 毅 （三江學(xué)院，江蘇南京210012）

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

0 引 言

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

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

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

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

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

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

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

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

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

2 TD-CT 算法

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

2.1 聚類分析

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

定義2：坐標(biāo)距離，表示為Dis（Li,Lj）。Dis（Li,Lj）為坐標(biāo)Li和Lj的實(shí)際距離，且有公式：

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

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

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

針對(duì)客戶的經(jīng)緯度坐標(biāo)進(jìn)行聚類的算法思想分為四個(gè)步驟：

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

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

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

其中，步驟三中心坐標(biāo)點(diǎn)的計(jì)算公式為：

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

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

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

輸出：所有聚類

2.2 獲取客戶家庭住址

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

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

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

輸入：閥值δ

輸出：家庭住址對(duì)應(yīng)的坐標(biāo)

2.3 獲取家庭住址有效停留時(shí)間

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

2.3.1 工作日時(shí)間

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

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

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

輸入：閥值δ，家庭住址對(duì)應(yīng)的坐標(biāo)

2.3.2 周末時(shí)間

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

2.4 判斷是否進(jìn)行末端配送

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

3 實(shí) 驗(yàn)

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

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

4 總 結(jié)

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

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