算法爱好者导读
近期，美团公司的配送系统引发了广泛的关注，众多业内人士及公众对ETA算法产生了浓厚兴趣。尽管本文并非新作，却揭示了配送系统中采用的解决方案，主要通过结合业务规则来满足场景需求。一方面，它满足了业界同仁对热点事件的探求，另一方面，其方法也适用于其他场景，如打车派单等，相信对相关领域的从业者具有启发意义。
—————【以下是正文】—————
1.背景
预计送达时间，简称ETA，指的是用户下单之后，配送员需要多长时间将外卖送到消费者手中。这一预测结果会以“预计送达时间”的标签形式，在用户端显示出来，它是配送系统中一个至关重要的指标，它不仅影响着用户下单的决策，还关系到运力的合理调配、骑手的绩效评估，从而进一步影响到整个配送系统的成本控制和用户体验。
在整个配送体系中，预计到达时间不仅是其核心的接入点及全面的限制条件，同时也充当着整个系统的调控核心。具体表现在：
ETA在配送系统中作用
在这种多角度的限制条件下，对外卖配送预计到达时间的构建与预测过程将会变得更加繁复。相较之下，在打车情境中，外卖配送的预计到达时间所遭遇的困难主要包括：
外卖及打车中的ETA
下图中展示了骑手履行约定全过程的时序图，图中包含了众多时长数据。通过观察，我们可以发现存在十余个关键节点，其中七个尤为关键。这些时长参数涵盖了骑手（包括接单、取餐、送餐）、商户（制作餐食）以及用户（接收餐食）等多个方面。此外，还需在室内外不同场景间进行转换，这使得整个过程极具挑战性。在开展ETA建模工作时，我们不仅要进行基础的时间预测，更要进行全流程的时间预测，并且必须考虑到“订单量-运输能力-用户转化率”三者之间的协调与平衡。配送ETA的发展历程，涵盖了数据与特征层面的不断优化，以及模型层面的逐步演变，从LR、XGB、FM到最终的自定义模型结构。
ETA的探索与演变
2.业务流程迭代中的模型改进
2.1 基础模型迭代及选择
与众多CTR模型的更新轨迹相仿，该配送预计到达时间模型的业务迭代过程，历经了从线性回归到树形模型，再到一系列的针对性结构调整的演变。在特征方面，也持续地进行着迭代与完善。
在对比了Wide&Deep、AFM等常见模型之后，我们基于计算性能的考量，对当前版本模型进行了评估。
经过综合考量，我们最终确定了该模型作为基础版。在模型特征化处理完成后，我们基于FM模型，进一步引入了深度学习模块。这一模块对稀疏和稠密特征进行了有针对性的整合。在FM模块中，我们通过隐变量内积的方式实现了特征的一阶和二阶融合；而在DNN模块中，则通过Feed-学习实现了高阶特征的融合。在模型训练阶段，我们选用了衰减策略、剪辑方法、求解器配置以及激活函数的类型，这些细节在此不予详细展开。
2.2 损失函数
在ETA预测情境中，准时性和可信度是至关重要的业务评估标准。我们尝试将原本的损失函数替换为另一种损失函数，这种替换从直观上看，更符合对MAE（平均绝对误差）的严格要求，相较于ME（均方误差）而言。在合适的衰减率设定下，模型的结果能够实现收敛并保持稳定。
同时，在迭代过程中，需注意在相同的预计完成时间承诺下，若在N分钟内提前1分钟完成，则优于延迟1分钟完成。设计损失函数时，期望整体预估结果尽可能偏向提前。对于提前的部分，应适当减少数值惩罚；而对于延迟的部分，则应适当增加数值惩罚。经过多次调试和设计，最终确定以提前N分钟、延迟N分钟以及原点作为三个分段点。在原有函数优化的基础上，我们设计了前段斜率为1.2倍的函数，以及后段斜率为1.8倍的函数，这样的设计旨在使整体结果向中心聚集，并且预计能够使结果提前到达，同时，这一改进对ETA的各项指标都实现了显著提升。
损失函数
2.3 业务规则融入模型
当前的业务体系采用“模型+规则”的架构模式，模型首先估算出预计到达时间（ETA），随后针对不同的业务场景，会应用相应的业务规则进行时间上的叠加，以确保满足特定场景的具体需求。这些规则是通过业务指标的不断迭代与优化而形成的。模型与规则的整体优化出现了脱节现象，当模型与规则的时间分别进行优化时，即在模型训练阶段，无法兼顾规则时间的影响。而规则时间在一年中的不同时期会有所波动，经过一段时间的反复迭代，这种脱节现象会愈发严重。
经过多方探索和尝试，我们最终将整个规则体系成功嵌入到了TF模型之中，并在模型内部对规则参数进行了细致的调整。
通过调整多样化的拟合环节及相应参数，成功在TF模型内实现了多项规则。这最终显著提高了业务指标，并且，通过修改部分固定参数，模型也具备了一定程度的人工干预功能。
多目标补时结构
在此，整个体系结构被精简为针对多目标预测的架构，采纳了多任务架构中普遍使用的结构，并在训练过程中按照一定比例实施多样化的交替训练方法。在结构设计上，从底层模型的核心融合层开始，于TF内部分别实现了常规预测模块及多种规则时间模块，相应的标签依然来源于常规的历史数据与规则时间数据。这种设计考虑了以下因素：
模型结构在进行预估目标调整尝试中：
2.4 缺失值处理
在模型处理过程中，特征层面难免会出现一些缺失数据。当特征x被输入到TF模型进行判断时，若为缺失值，则调整w1参数；若非缺失值，则将其数值乘以w2。w1和w2被视为可学习参数，并一同纳入网络进行训练。此方法旨在替代使用均值或零值等处理缺失值的方式。
缺失值处理
3.长尾问题优化
3.1 模型预估结果+长尾规则补时
基础模型主要学习的是整体数据的统计规律，然而在处理某些边缘情况时，其学习效果并不理想。这表现在对边缘情形的预测时间上往往过于短暂——鉴于ETA系统具备对骑手进行考核的功能，这种预测的偏短对于骑手来说会造成极大的不利影响。因此，有必要将边缘情形分解为两个部分进行深入分析：
模型长尾因子
在上述分析的基础上，我们通过应用补时规则来纠正长尾预估时间过短的问题：具体而言，长尾规则所补充的时间是组合而成的。在这一组合中，业务长尾因子涉及距离、价格等业务相关因素，而模型长尾因子则是指RF标准差。因此，最终的预估到达时间（ETA）策略是将模型预估结果与长尾规则补时相加。
4.工程开发实践
4.1 训练部分实践
整体训练流程
对于线下训练，采取如下训练流程：
对Spark原始数据进行整合，进而通过Spark平台进行处理，随后进行数据的并行训练，接着在离线环境下利用GPU进行评估，最后通过CPU进行线上预测。
整个常规训练过程在处理亿级数据并经历多轮Epoch后，大约需要4个小时的时间。在此过程中，特别在的训练阶段，由于的实际计算效率并不理想，大量时间被数据输入输出所占据。通过利用Spark生成部分数据，我们可以将这一环节的速度提升大约3.6倍。此外，在数据并行训练方面，16张卡之间的并行度扩展基本呈线性增长，显示出良好的扩展能力。PS上的参数数量尚未达到单机难以承受的程度，因此尚未对参数在PS上进行分割。在离线GPU评估环节，这一步骤并非流程的必须环节。尽管在训练阶段，Chief可以设置Valid集合以获取某些指标，但对于整个离线全量数据，利用Spark数据进行GPU评估可以在短时间内完成整个流程，并且能够设定众多复杂且自定义的指标。
数据并行训练方式
模型训练是在美团的AFO平台上完成的，我们先后测试了分布式和单机多卡两种方案。鉴于生产效率和结果的一致性，目前我们在线上生产模型时，主要采用单机多卡方案进行常规训练。
运用TF内置的PS-架构，采取异步数据并行策略，通过tf.train.sion模块协调整个训练流程。模型参数集中保存在PS中，每个Step阶段，各节点并行提取数据以进行计算，并将计算得到的梯度反馈，以此实现参数的更新。当前模型每秒处理能力在1至2万次之间，处理亿级数据仅需几轮Epoch，整个过程耗时几小时即可完成。对模型在平台上的加速性能进行测试，结果显示，其加速比大致介于16块之间，计算力随卡数线性提升，超过16块后略有差异。在现有业务操作中，通常4至6块卡便能在较短时间内完成常规的训练作业。
在平台上实施PS-方案展现了良好的扩展潜力，然而，它亦存在不足之处。RPC通信方式易受其他任务干扰，导致训练过程受限于最慢的环节。此外，异步更新策略亦会对结果产生一定的不稳定性。鉴于此，在线上生产阶段，我们最终选择了单机多卡配置，虽然牺牲了部分扩展性，却换来了训练效果和速度的稳定提升。该方案在单机多卡配置下，通过手动指定操作符（OP）的方式，实现多个GPU之间的变量共享，随后，综合考量损失函数与梯度信息，最终将梯度更新至模型参数。
加速比曲线
TF模型集成预处理
在模型训练阶段，处理ID类特征时需借助Vocab词表进行低频信息的筛选，而对于连续型特征，则必须执行归一化操作。这一过程将生成众多预处理文件，而在线下的处理流程中，这些文件可便捷地通过Spark进行格式化处理，随后被导入模型以启动训练环节。然而，在进行线上预测时，必须在工程开发阶段导入多个词汇表以及连续型特征的标准化预处理文档，诸如平均/标准差值文件等；另外，鉴于模型每日更新，这也带来了不同日期版本之间的对齐难题。
为了降低工程开发过程中的复杂度，在模型训练阶段，我们计划将所有预处理文件整合进TF计算图中。这样一来，每次进行在线预测时，只需输入最原始的特征数据，无需经过预处理步骤，即可直接获得预测结果。
<p style='margin-bottom:15px;color:#555555;font-size:15px;line-height:200%;text-indent:2em;'> <pre style="box-sizing: border-box;overflow: auto;font-family: Courier, "Courier New", monospace;font-size: 10px;margin-bottom: 1rem;line-height: 1.42857;word-break: break-all;overflow-wrap: break-word;background: rgb(238, 238, 238);border-width: 1px;border-style: solid;border-color: rgb(238, 238, 238);border-radius: 4px;text-align: start;"><code style="box-sizing: border-box;font-family: Courier, "Courier New", monospace;font-size: inherit;color: rgb(230, 225, 220);background: rgb(35, 35, 35);border-radius: 0px;padding: 0.5em;white-space: pre-wrap;display: block;overflow-x: auto;">tf_look_up等价于将list_arr列表转换成tf.int64数据类型的tf.constant对象。<br /><br />table通过查找ph_vals的索引值，再加上idx_bias，得到ph_idx。<br /></code></pre></p>
<p style='margin-bottom:15px;color:#555555;font-size:15px;line-height:200%;text-indent:2em;'> <pre style="box-sizing: border-box;overflow: auto;font-family: Courier, "Courier New", monospace;font-size: 10px;margin-bottom: 1rem;line-height: 1.42857;word-break: break-all;overflow-wrap: break-word;background: rgb(238, 238, 238);border-width: 1px;border-style: solid;border-color: rgb(238, 238, 238);border-radius: 4px;text-align: start;"><code style="box-sizing: border-box;font-family: Courier, "Courier New", monospace;font-size: inherit;color: rgb(230, 225, 220);background: rgb(35, 35, 35);border-radius: 0px;padding: 0.5em;white-space: pre-wrap;display: block;overflow-x: auto;">constant_avg代表了一个常量，该常量由tf.constant函数创建，其值来源于feat_avg，数据类型被指定为tf.float32，形状为[feat_dim]，并且被命名为。<span style="box-sizing: border-box;color: rgb(165, 194, 97);">"avg"</span>)<br />constant_std等价于tf.constant(feat_std, 数据类型为tf.float32, 形状为[feat_dim], 命名为<span style="box-sizing: border-box;color: rgb(165, 194, 97);">"std"</span>)<br />ph_out 等于 (ph_in 减去 常数平均值) 除以 常数标准差。<br /></code></pre></p>
4.2 TF模型线上预测
该学习平台集成了模型管理功能，负责对算法训练所生成的模型进行集中化的管理和协调，对线上模型使用的版本进行维护，并允许进行版本更替和撤销操作，此外，还具备对节点上模型版本状态的监控能力。
ETA所采用的模型在训练过程中，需生成特定格式的模型，而这要求模型管理平台能够提供相应的格式支持。
实现方案 S 线上服务加载 模型有多种实现方案：
最终决定使用Java API在CPU上进行预测操作，当测试batch值为1时，预测所需时间短于1毫秒，因此我们决定采纳方案3作为我们的实施策略。
远程计算模式
Java API所依赖的C++动态链接库对++.so的版本有特定要求，它需要GCC的版本至少达到4.8.3。然而，目前我们线上服务的CPU机器，大多数系统默认安装的GCC版本仅为4.4.7。若要确保每台线上业务服务器都能进行本地计算，就必须将数千台服务器的GCC版本进行统一升级。这项工作不仅量大，而且可能带来额外的风险。
因此，我们决定重新购置数十台远程计算服务器，业务方只需将Input数据序列化，随后传输至集群。待集群完成计算任务后，再将序列化后的结果反馈给业务方。通过这种方式，我们仅需对这几十台计算服务器进行升级处理。
在线序列化
线上性能
模型部署后，为众多业务部门提供了算法支持，其远程集群的计算性能TP99指标稳定在5毫秒以下，完全能够满足各业务部门对计算效率的要求。
线上效果
总结与展望
模型成功部署并投入使用，显著提高了业务相关指标。未来，我们计划继续针对业务需求对模型进行优化，以期实现效果的持续增强。
- EOF - |
