电商的发展需要依赖高效而可靠的物流服务，如何通过大数据和人工智能技术提升物流小哥的配送效率是我们一直在深入研究的问题。在刚刚结束的数据挖掘顶会KDD2020中，这篇《Doing in One Go: Delivery Time Inference Based on Couriers' Trajectories》成为被收录的重磅论文之一。本期技术前沿，我们将介绍京东城市时空数据引擎JUST在物流场景中如何助力物流小哥减负增效。
题目：Doing in One Go: Delivery Time Inference Based on Couriers' Trajectories作者：Sijie Ruan, Zi Xiong, Cheng Long, Yiheng Chen, Jie Bao, Tianfu He, Ruiyuan Li, Shengnan Wu, Zhongyuan Jiang, Yu Zheng
问题背景电商的发展需要依赖高效而可靠的物流服务。配送员当前仍是解决物流配送“最后一公里”问题的主要方案。分配给配送员的包裹配送任务称为运单。它包含了客户的信息、包裹的信息以及包裹的配送状态。包裹的配送状态中记录了配送员交付该包裹给客户的时间（下文简称妥投时间）。该时间对运单的生命周期管理和运单状态追踪都非常有用。除此之外，其还能够用于推测客户在某时段内是否能够收货、评估配送行为、制定保险策略等场景（如图1所示）。
目前，妥投时间主要是通过配送员人工点击PDA设备上的“妥投”按钮来实现，如图2所示。物流运营人员要求配送员每投递一个包裹都要执行一次。由于配送员每天需要配送大量的包裹，这种额外的操作，增加了配送员的负担。
幸运的是，配送员在配送过程中的行动轨迹被PDA设备忠实地记录下来，根据他在配送包裹的过程中会在某地停留一段时间这个特征，我们有机会基于运单妥投地点周围的轨迹驻留点推测每个运单的妥投时间（如图3所示）。
于是，京东城市联合京东物流以及西安电子科技大学等机构，提出了一种基于配送员轨迹中的驻留点推测运单妥投时间的方法DTInf（Delivery Time Inference）。基于DTInf，配送员只需要在配送完成后提供极少数的投递失败的运单，所有投递成功的运单的妥投时间都能够从配送员轨迹数据中被一次性全部推测出来。
面临挑战
要解决这个问题有以下两个难点：首先，我们不能简单认为包裹收货地址地理编码（Geocoding）后的坐标（下文简称“编码坐标”）就是它的妥投地点。由于地理编码的精度问题和客户不同的收货方式，如图4所示，距离编码坐标最近的驻留点sp2可能并非包裹妥投造成的驻留点sp3。实际上，我们发现，运单确认妥投时配送员所在的驻留点，距离编码坐标有几十米的偏移（如图5所示）。如果我们直接使用编码坐标作为包裹的妥投地点，并选择最近的驻留点来推测妥投时间，推测误差可能就会比较大。
其次，由于配送员可能因为给客户打电话、等红绿灯、上门收货等多种别的原因产生驻留（如图6所示），即使我们选择了距离真实妥投地点最近的驻留点，我们也不能很确定地说，包裹一定是在该驻留点投递。
解决方案为解决以上两个难点，我们提出的方案DTInf如图7所示，包含三个模块：1）数据预处理，在这个模块中我们进行轨迹滤噪、驻留点检测并将运单和驻留点根据识别得到的配送行程进行划分；2）妥投地点修正，在这个模块中，我们基于历史上运单的妥投时间和驻留点，得到每个编码坐标到真实妥投地点的映射关系；3）基于妥投事件的匹配，这个模块以一趟配送行程中的驻留点和妥投成功的运单为输入，利用第二步挖掘得到的地点映射关系以及一个基于妥投事件建模的驻留点选择模型，推测每个成功妥投的运单的妥投时间。
（一）数据预处理在数据预处理模块中，我们首先对配送员轨迹数据进行轨迹滤噪和驻留点检测。检测得到的驻留点后续用于发现真实妥投地点和推测妥投时间。然后，为了模拟系统上线后，配送员在配送结束后才确认运单状态的行为，我们基于运单数据中的到货时间和妥投时间自动识别出每天的配送行程的时间段。每一个配送行程中的驻留点和妥投成功运单集合，即构成妥投时间推测问题的输入。（二）妥投地点修正在妥投地点修正模块中，我们通过挖掘历史的配送行程，得到每个编码坐标对应的真实妥投地点，使得在未来做妥投时间推测时，可以使用我们挖掘得到的妥投地点。这种方法行之有效的原因是很多编码坐标在历史上存在多次配送的情况（如图8所示），同时这些地点也很有可能在未来配送。图9显示最近一个月的运单里，有80%的编码坐标在过去4个月中曾经配送过。
得到编码坐标到真实妥投地点的映射关系的方法如图10所示。我们首先利用历史配送行程，构建编码坐标到配送该卖游戏账号平台地图编码坐标所产生驻留点集合的倒排索引。由于GPS传感器存在定位误差，我们取驻留点集合的质心作为该编码坐标对应的妥投地点。由于多个编码坐标可能存在共享妥投地点的情况，我们进一步将不同编码坐标得到的妥投地点进行空间聚类（迭代式地合并距离小于D米的妥投地点），减少最终输出的妥投地点的数量，提高后续妥投事件建模的准确度。
（三）基于妥投事件的匹配在基于妥投事件的匹配模块中，我们基于配送行程中的驻留点，推测每一个成功妥投的运单的妥投时间。方法上，我们先将运单按照第二步挖掘得到的映射关系，根据妥投地点进行分组，每组构成一个妥投事件，然后对于每个妥投事件，我们通过一个预先训练好的驻留点选择模型，选择妥投地点周围最有可能对应该事件的驻留点，最后我们将妥投事件里包含的运单的妥投时间推测为选中驻留点对应的时间。我们进行妥投事件级别的时间推测，而不是运单级别的时间推测有如下两个原因：
- 配送员按地点依次妥投。配送员通常对于一个妥投地点的包裹一次性妥投完毕，然后再前往下一个地点进行妥投。一个妥投事件中的每一个运单都对应一个妥投驻留点，我们把妥投事件中对应次数最多的驻留点称为该事件的主驻留点。图11显示，在D=3米的情况下，93.6%的运单都是在主驻留点进行妥投的。虽然有6.4%的运单在非主驻留点进行妥投，如直方图所示，它们距离主驻留点的时间差也较小。因此，进行妥投事件级别的推测，如果能够成功选择主驻留点，误差是可以接受的。
- 妥投事件与其主驻留点具有相关性。在同一地点妥投的包裹会影响主驻留点的特征。图12的箱线图显示了驻留点时长的分布和该妥投事件内客户数量的关系。我们可以很容易发现，要配送的客户数量越多，配送员停留的时间越长。
对于一个妥投事件，我们首先通过空间范围查询，找到其周围的驻留点作为匹配的候选。我们通过排序的形式选择驻留点：对于一个妥投事件以及一个候选驻留点，驻留点选择模型会输出一个匹配程度打分，分数最高的即为选择的驻留点。在训练时，我们采用二分类的形式，对于一个妥投事件以及一个候选驻留点，模型被要求判断候选驻留点是否是该事件的主驻留点。我们利用多层感知机（MLP）作为我们的驻留点选择模型，并且抽取了以下四类特征作为模型输入：1）妥投地点特征：妥投地点的POI类型；2）妥投事件特征：其包含的运单总数量、客户总数量、包裹总重量和包裹总体积；3）驻留点特征：驻留点的时长和面积；4）匹配特征：驻留点和妥投地点的空间距离。
实验结果我们在京东物流北京某配送站从2018年4月12日至2019年7月7日（将近15个月）的5个配送员轨迹数据和运单数据上验证了我们方法的有效性。挑选得到的轨迹数据包含593万个GPS点，平均采样频率在7.4秒，运单量约为27.4万。我们利用每个配送员前80%的配送行程进行模型的训练，之后10%的配送行程进行验证，最后10%的配送行程进行算法效果的对比。实验结果如图13所示。结果表明，DTInf妥投时间推测的平均绝对误差（MAE）为401秒，至少优于基准方法31.8%。
我们的妥投时间推测系统如图14所示。它基于京东城市自研的时空数据引擎JUST（JD Urban Spatio-Temporal Data Engine），详情可以访问https://just.urban-computing.cn/。
图14. 妥投时间推测系统.