作者： Hao Liu, Wenzhao Jiang, Shui Liu, Xi chen

机构： 香港科技大学（广州）、滴滴出行

发表： 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. （KDD 2023 Ads Track）

预计到达时间估计（Travel Time Estimation,TTE）旨在准确预测从出发地到目的地的预期行程持续时间。作为全球最大的网约车平台之一，滴滴每天回答数十亿条 TTE 查询。 TTE的质量直接决定客户的体验以及乘客与司机匹配的有效性。然而，现有研究主要将TTE视为确定性回归问题，并专注于提高单个标签的预测精度，忽略了各种动态上下文因素引起的行程时间不确定性。为此，本文提出了一个概率框架 ProbTTE，用于不确定性感知的旅行时间预测。具体来说，该框架首先将单标签回归任务转换为多类分类问题，以估计隐式旅行时间分布。此外，还提出了一种自适应局部标签平滑方案来捕获软旅行时间标签之间的有序类间关系。此外，构建了一个按路线对数正态分布正则化器，以从大规模历史旅行数据中吸收先验知识。通过明确考虑出行不确定性，所提出的方法不仅提高了 TTE 准确性，而且还提供了额外的出行时间信息，以有利于网约车的下游任务。对现实世界数据集的大量实验证明了所提出的框架与最先进的旅行时间预测算法相比的优越性。此外，ProbTTE已于2022年底在滴滴生产中部署，赋能各类订单调度服务，显着改善乘客和司机的体验。

预计到达时间估计（Travel Time Estimation,TTE）问题，大多数现有方法主要侧重于提高单标签预测精度（即实际出行时间），而忽视了各种动态上下文因素（例如意外事件引起的拥堵、临时交通管制）引起的出行时间的不确定性 ）。如图 1 所示，行程时间遵循长尾分布。在不同的交通状况下，每条路线的行车时间可能会有很大差异。在不考虑这种概率性质的情况下无缝预测单标签旅行时间可能会导致有偏差的预测。

图1滴滴出行平台2021年5月至2021年6月北京真实历史出行的长尾出行时间分布

为解决上述为题，主要有如下三大挑战：

(1) 首次尝试研究网约车平台的概率出行时间估计问题。 (2) 提出了一种概率框架ProbTTE，用于提高 TTE 服务的准确性和实用性。 ProbTTE 与预测模型无关，可以轻松地与现有的 TTE 替代方案集成。 (3)在滴滴打车平台部署了ProbTTE，成功提高了出行时间预测的准确性和订单调度质量。我们分享部署和集成经验，造福社区。 (4) 对现实世界 TTE 数据集和两个订单调度服务的广泛实验证明了我们提出的框架针对五个基线和之前的订单调度策略的有效性。

路网：\mathcal{G}=(V,E),其中v_i\in V表示路口,e_{ij}\in E表示v_i和v_j之间的路段。一条路线（route）表示为：r=\{e_1,e_2,...,e_k\}，k为一条路线中路段的中枢。

注：个人感觉模型图回归和分类两个模块反了，因为分类应该是离散的，回归是连续的，与图上标注不符

以往的TTE模型主要侧重于确定性单标签的指导下捕获特征和时空依赖性。这限制了模型的性能和实用性。在该模块中，首先将原始回归任务转换为多分类任务，其目标是预测离散行程时间分布作为一般(任意)分类。将真实值y\in \mathbb{R}_{>0}编码为one-hot向量。为了解决长尾分布问题，均匀划分时间间隔也可能让模型过度加强对少数类别的关注。考虑行程时间分布的情况下分割标签空间，如图3所示，通过持续时间和密度来定义每个旅行时间间隔的边界。

b_{j}=\left\{\begin{array}{ll} j \cdot \Delta t, & \text { if } 0 \leq j \leq M \\ M \cdot \Delta t+j \cdot \Delta T, & \text { if } M+1 \leq j \leq N, \\ +\infty, & \text { if } j=M+N+1 \end{array}\right. \\

其中，\Delta t和\Delta T分别为普通行程时间间隔和长尾旅行时间间隔的预定义窗口大小，M和N控制普通和长尾行程时间的超参。现实中\Delta t \ll \Delta T，给定一个行程查询q和真实值y，可以推导出one-hot标签y\in \mathbb{R}^{|C|},C是行程时间类别的集合，其中c_j \in C,如果y\in[b_j,b_{j+1}]置为1，否则为0。预测的时间\hat y输出为： \hat{\mathbf{y}}=\frac{e^{\mathbf{w}_{i}^{\top} \mathbf{x}}}{\sum_{j=1}^{|C|} e^{\mathbf{w}_{j}^{\top} \mathbf{x}}} 其中w_i是第i类可学习参数，损失函数为交叉熵： L_{cla}==\frac{1}{|Q|}\sum_{i=1}^{|Q|}y_i \cdot log(\hat y_i)

DTTE的优势主要有2个：（1）多分类目标在模型训练过程中保留了更多的信息，提高了行程时间预测的准确率。（2）分布输出提供了额外的信息，例如预测的置信度，这在下游任务中很有用。

one-hot编码可能使得模型对于目标类过于自信。为了缓解该问题，采用标签平滑（LS），将软标签除正确的分类外，每个类设置为\frac{\epsilon}{|C|-1},将真实概率从1降低到1-\epsilon。但是，简单地为每个类分配同等重要性会忽略多类旅行时间预测问题中的类间关系。为了解决上述限制，对于行程查询 q，我们修改了|C|维one-hoe向量y如下， y[j]=\left\{\begin{array}{ll} p,&\text{if} |j-c|=0,\\ \frac{1-p}{2\tau}, &\text{if} 1\le|j-c|\le\tau\\ 0,&\text{else}, \end{array}\right. \\

其中 y[ j] 表示 y 的第 j 类，c 表示真实行程时间分类，p 是控制标签平滑度的超参，\tau 是控制局部分布支持宽度的另一个超参。ALLS 的主要修改是软标签仅分配给具有真实值类位置感知的 2\tau 最近邻类。设定为： \tau=\frac{y\cdot\alpha}{\Delta t},p=\frac{\Delta t}{\Delta t+y\cdot\beta} 其中\alpha和\beta是从历史行程数据经验得出的先前行驶时间分布的参数。\alpha和\beta满足\frac{1-p}{2\tau}\le p,化简为： \beta\le2\alpha 通过这种方式，模型被强制使用自适应时间窗口更加关注真实值周围的附近类。

每条路径的概率行驶时间分布可能会有所不同。上图说明了实际旅行路线的多样化分布。在之前的研究中，由于数据稀疏性，很难量化这种路线分布。滴滴作为全球最大的网约车平台之一，积累了大规模的出行数据，这为提升概率出行时间预测提供了新的机会。为此，本文提出了一个额外的正则化模块来整合这种路线先验知识。引入了参数化对数正态分布来拟合路线长尾先验 Y_{i} \sim p_{i}(y)=\frac{1}{y \sqrt{2 \pi \sigma_{i}^{2}}} \exp \left(-\frac{\left(\log y-\mu_{i}\right)^{2}}{2 \sigma_{i}^{2}}\right) logY_i的均值\mu_i和方差为\sigma^2_i

\mathrm{p}_{i}[j]=\left\{\begin{array}{ll} p_{i}\left(\frac{b_{j}+b_{j+1}}{2}\right) \cdot\left(b_{j+1}-b_{j}\right), & \text { if } 0 \leq j \leq|C|-2 \\ p_{i}\left(\frac{2 b_{j}+\Delta T}{2}\right) \cdot \Delta T, & \text { if } j=|C|-1 \end{array}\right. \\

其中p_i[j]表示p_i第j个元素，p_i是连续分布p_i(y)的连续表示。最小化\hat y_i和p_i的交叉熵获取最接近模型输出分布的对数正态分布。 \operatorname*{min}_{\mu_{i},\sigma_{i}}{\mathcal{L}}_{\rho r i o r}=-{\hat{y}}_{i}\cdot\log(\mathbf{p}_{i}). 上式是一个光滑凸问题，最优解满足 \nabla L_{prior} = 0，求解得到解析解 \mu_{i}={\hat{y}}_{i}\cdot\log({\mathsf{b}}),\ \sigma_{i}^{2}={\hat{y}}_{i}\cdot\left(\log({\mathsf{b}})-\mu_{i}\cdot\mathbf{1}_{|C|}\right)^{2} 其中\mathbf{b}=\left({\frac{b_{0}+b_{1}}{2}},\ldots,{\frac{b_{|C|-2}+b_{|C|-1}}{2}},{\frac{2b_{|C|-1}+\Delta T}{2}}\right),\boldsymbol 1_{|C|}表示大小为|C|的全1向量。通过估计的对数正态分布，我们可以直接获得最可能的行程时间和预期的行程时间 \hat{y}_{i}^{max}:=\arg\operatorname*{max}_{y}p_{i}(y)=e^{\mu_{i}-\sigma_{i}^{2}}, \\ \hat{y}_{i}^{exp}:=\mathbb{E}[Y_{i}]=e^{\mu_{i}+\sigma_{i}^{2}/2}=\hat{y}_{i}^{m a x}\cdot e^{\frac{3}{2}\sigma_{i}^{2}}. \\ \hat{y}_{i}^{m a x}和\hat{y}_{i}^{exp}均可以作为预测结果，\hat{y}_{i}^{exp}表示为放大后的理想校准，为\hat y ^{max}的e^{\frac{3}{2}\sigma^2}倍。这在极端条件下（例如，交通拥堵）下更能防止行驶时间低估问题。在实践中，选择期望 \hat{y}_{i}^{exp}作为概率预测模型的联合输出之一。引入新的损失函数，让模型能在最可能的行驶时间和校准后的行驶时间之间自我适应平衡。 {\mathcal{L}}_{e x p}={\frac{1}{|Q|}}\sum_{i=1}^{[Q]}|{\dot{y}}_{i}^{e x p}-y_{i}|. \\

结合前文所使ProbTTE的联合损失函数为： {\cal L}={\cal L}_{r e g}+\lambda_{1}{\cal L}_{c l a}+\lambda_{2}{\cal L}_{e x p}, 其中\mathcal{L}_{reg}是回归损失，\mathcal{L}_{cla}是分明类损失。\mathcal{L}_{exp}是平衡损失。

展示了ProbTTE的两个应用，（1）行程时间的基本预测（2）行程分布分数的评估。第一个应用程序在路线规划中起着重要作用，第二个应用程序为订单调度服务提供了有效的指标。

\hat{y}_{i}^{\widehat{\jmath}}=\lambda\hat{y}_{i}+(1-\lambda)\hat{y}_{i}^{e x p} \\

分布分数通过利用 ProbTTE 分布输出中编码的附加信息来反映行驶时间预测的不确定性。直观地说，最大概率越高、单调性越好的最集中分布，最大概率两侧的分布得分就越大，表明旅行时间不确定性越小。因此，订单调度服务可以直接采用分配分数，以过滤掉具有较高取件时间不确定性的潜在司机，并防止调度行程时间不确定性较高的订单。

\begin{array}{c}{{s(\hat{\mathbf{y}})=\displaystyle\sum_{0\leq i数据集信息

在两个数据集上，ProbTTE性能最佳，其中ProbTTE与滴滴TTE服务目前使用的WDR模型相比，在不修改原有神经网络架构的情况下，实现了持续改进。WDR在多个指标方面优于最先进的HierETA（KDD 22，笔者也做了解读：2022 [KDD] 多视图解释轨迹：用于预计到达时间的层次自注意网络），这是因为WDR在生产环境中进行了高度优化。这也证明了机器学习系统工程优化对于实际部署的重要性。

（1） ProbTTE -WoSR去除了自适应局部标签平滑（ALLS）和路由先验正则化模块。

（2） ProbTTE -WLS 将本地自适应标签平滑替换为原版标签平滑方案。

（3） ProbTTE -WoR 删除了路由上的先验正则化模块。

（4） ProbTTE -WND 用常规正态分布代替对数正态分布。

除了旅行时间预测的实验外，还进一步证明了所提出的概率预测框架对下游任务的实用性。具体来说，从 2022 年 9 月 16 日至 2022 年 9 月 29 日在五个城市进行了在线 A/B 测试，共涉及 300 万个订单发送请求。比较了滴滴部署的两种网约车服务（即业务I和服务II）的当前无分配评分（WoDS）的无分配分数（WoDS）的优化订单调度策略。在实验中，将乘车请求随机抽样到不同的订单调度策略，以考虑公平性。

本文提出了ProbTTE，一种用于不确定性感知旅行时间估计的概率预测框架。通过明确量化出行时间分布并将其纳入现有的TTE服务，该框架提高了出行时间预测的准确性，有利于各种下游网约车任务。具体来说：

相关阅读：