基于客户出行规律的物流末端配送算法研究

刘定一，黄 慧，应 毅 （三江学院，江苏南京210012）

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

0 引 言

近年来，随着电子商务的普及，快递业务量迅猛增长，末端配送问题随之也陷入困难的局面，受到物流行业的广泛关注。由于末端配送模式以直接配送为主，且对配送过程的效率和质量缺乏有效的控制，导致末端配送时间不确定性高，配送效率低下，常出现“二次投递”的情况[1]。为了提高末端配送的效率问题，学者们展开了一系列的研究。文献[2]基于工厂园区的物流数据，利用FlexSim 建立仿真模型，将运输车辆的使用效率以及订单的运输时间作为研究指标，以降低末端配送的时间成本和人工成本。文献[3]和文献[4]利用FlexSim 可视化仿真技术，针对分拣系统进行建模以提升末端配送的效率。此外，学者们还从构建仓配一体化共同配送模式[5]、建立城市共用末端配送站[6]、创建多温层共同配送[7]等方面来分析末端配送问题，都取得了一定的进展。

1 末端配送研究现状及本文工作

随着快递业务的迅猛发展，末端配送问题成为学者们的研究热点。为了降低末端配送的人工和时间成本，提高末端配送的效率，研究通常以“快递公司”为主体，通过提升车辆运输效率、优化分拣算法等方式来改进末端配送模式[8-10]。然而，在末端配送的问题中，还有一个更为重要的主体——“客户”，他们的出行规律在末端配送问题的研究中也起着不可或缺的作用。如果快递公司掌握了客户的出行规律，在每次配送时仅配送当前未外出的客户，可极大地避免“二次投递”的问题；同时，由于智能快递柜容积有限，若配送时刻掌握了客户已外出的信息，则可优先配送未外出客户的货物，从而促进智能快递柜的使用率。

针对以上问题，本文通过通信运营商获取客户基于时间序列的手机定位数据，通过对数据进行分析还原客户现实生活活动轨迹，研究客户的出行规律，提高末端配送的效率。本文的贡献如下：

（1） 分析客户的手机定位数据，获取客户的“停留点”，形成时空数据，研究基于时空数据的聚类算法，挖掘客户在工作日的出行规律。

（2） 研究客户停留在居住点的时间区域和快递末端配送的时间区域的关系，形成可靠的末端配送方案。

（3） 结合天气因素研究客户周末的出行规律，提出基于天气加权方法的聚类算法，提高配送成功率。

本文基于客户出行的规律进行研究，提出基于客户出行的末端配送算法（Terminal Delivery Algorithm based on Customer Travel，TD-CT），以提高快递公司末端配送的成功率及效率。

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

2 TD-CT 算法

TD-CT 算法思想是基于客户手机定位数据，研究客户的出行规律，获取用户停留在家庭住址的时间段，根据配送时间决定最终是否为客户进行配送。TD-CT 算法分为四个部分：针对客户的经纬度坐标进行聚类分析、获取客户家庭住址、获取客户停留在家庭住址的有效时间段、是否进行末端配送。算法流程如图1 所示。

2.1 聚类分析

定义1：聚类（Clusteri）。设定距离阀值为ε，手机用户的坐标点集合记为L=｛L1,L2,…,Ln｝，其中，每个Li是由经度和纬度组成的坐标点。在连续的时间段内，对于∀Li，Lj∈L，若存在Dis（Li,Lj）≤ε，则称Li和Lj属于同一聚类。

定义2：坐标距离，表示为Dis（Li,Lj）。Dis（Li,Lj）为坐标Li和Lj的实际距离，且有公式：

其中：Er为地球平均半径，值为6 371.004 km。

通过通信运营商获取客户手机定位数据如表1 所示。

表1 手机号为13******345 的客户手机定位数据

针对客户的经纬度坐标进行聚类的算法思想分为四个步骤：

步骤一：按手机号对客户分组，将同一客户手机定位数据按时间先后排序。步骤二：根据用户手机号创建首个聚类Cluster1UserTe［ ］l，该聚类的表达形式为{＜Time1，（纬度坐标1，经度坐标1） ＞,…, ＜Timei，（纬度坐标I，经度坐标i） ＞}，获取客户首条记录的时间和定位坐标，设置为Cluster1UserTe［ ］l当前中心点坐标，同时将该坐标放入聚类中。

步骤三：设置距离阀值ε 为200 米。遍历客户的下一条手机定位数据，计算该条数据与聚类中心点坐标的坐标距离。若Dis（Li,Lj）≤ε，则将该坐标加入上一个聚类，并重新设置聚类的中心坐标点，中心坐标点的设置方法为将当前所有的点按时间段长度的比重求和得到；若Dis（Li,Lj）＞ε，则创建一个新的聚类，并将该坐标加入新的聚类中，同时设置该坐标为新聚类的中心坐标点。

步骤四：判断是否还有未处理的客户手机定位数据，如有，则读取并转到步骤三；否则，结束聚类过程。

其中，步骤三中心坐标点的计算公式为：

Center纬度为一个聚类的纬度中心坐标，Center经度为一个聚类的经度中心坐标；i表示一个聚类中不同的坐标点个数；Timei表示一个聚类中客户停留在某个坐标点的时长；TotalTime表示一个聚类中所有坐标点的总时长；Coordinate纬度表示第i个坐标点的纬度坐标；Coordinate经度表示第i个坐标点的经度坐标。

算法1：针对客户的经纬度坐标进行聚类，算法为GetClusterByUserLocation，其伪代码如下：

输入：客户手机定位数据，距离阀值ε

输出：所有聚类

2.2 获取客户家庭住址

算法思想：人为设置夜间时间段为晚8：00 至次日早8：00，将该时间段记为NightInterval，若客户在该时间段停留时间超过6 小时，且停留率（StayRatio）超过阀值δ，则将客户在该停留段时间对应的坐标设置为“家庭住址（HomeAddress）”。

其中：夜间单个坐标点停留在家庭住址6 小时以上作为一次停留，记作SingleStay；夜间停留6 小时以上的不同坐标点总次数记做TotalStay。停留率的公式如下：

算法2：获取客户的家庭住址的算法为GetUserAddress，其伪代码如下：

输入：阀值δ

输出：家庭住址对应的坐标

2.3 获取家庭住址有效停留时间

算法判断分为工作日和周末时间，若为工作日时间，则根据家庭住址停留时间段和总家庭住址停留时间计算家庭住址有效停留时间；否则，通过天气加权法的方式计算家庭住址有效停留时间。

2.3.1 工作日时间

若是工作日时间，则依次遍历该客户的每个聚类，若Dis（HomeAddress, Center ）≤200m，Center 为聚类的中心点坐标，则标记该聚类为“家庭住址聚类（HomeAddressCluste）r”，同时记录聚类的起始时间和结束时间，记为HomeStayInterval。若发现HomeStayInterval 总是成周期性的出现，则将该时间段设置为有效停留时间，记为ValidStayInterval。可依据式（5） 判断是否为ValidStayInterval。

其中：COUNT（StayInterval）表示符合此时间段内停留在家庭住址的次数，Total为聚类集合中符合此时间段的总次数。若StayIntervalRatio的值超过阀值δ，则可标记该时间段为有效停留时间，即ValidStayInterval。

算法3：家庭住址有效停留时间算法为GetValidStayInterval，其伪代码如下：

输入：阀值δ，家庭住址对应的坐标

2.3.2 周末时间

若是周末时间，则表1 中添加字段天气，根据时间字段的值，获取对应的天气信息。获取有效停留时间与算法3 相同，但是StayIntervalRatio的计算则需要考虑天气情况。其中：OutInterval表示外出的时间段，w表示雨雪天外出的概率。则可依据式（6） 判断是否为ValidStayInterval。同理，当StayIntervalRatio的值超过阀值δ 时，则设置该时间段为ValidStayInterval。

2.4 判断是否进行末端配送

若快递员配送的时间点包含在有效停留时间段内，则提示配送，否则提示暂缓配送。

3 实 验

以某小区的丰巢智能快递柜为例，记录了200 个智能快递箱共计7 天的投递情况，如表2 所示。

通过实验表明，TD-CT 算法有助于提高智能快递柜的使用率，尤其在周末时间，使用率得到显著提高，说明本文提出算法的有效性。

4 总 结

本文基于客户的出行规律提出了一种末端配送算法，简称TD-CT 算法。该算法根据客户的手机定位数据获取家庭住址信息，进而判断客户在家庭住址的有效停留时间，从而给出配送策略。实验表明，本文提出的算法可以很大程度上提高智能快递柜的使用效率。

表2 智能快递柜7 天使用情况