经典算法与深度学习在外卖物流调度中的应用
2020-02-27 1219浏览
- 1.经典算法与深度学习 在外卖物流调度中的应用 SPEAKER / 徐明泉 百度外卖首席架构师
- 2.引言：外卖配送的背后 2
- 3.引言：外卖订单调度系统要考虑的因素 1 订单相关 • • • 2 骑士相关 • • • • • • • 3 现有订单的配送路线 新增订单后配送路线的改变情况 历史取送餐速度 完成每个订单的预计时间 熟悉的区域 配送工具 装载情况.. 环境相关 • • 3 商户、用户位置 用户期望时间 预计出餐时间.. 当前配送的繁忙程度 天气情况..
- 4.提纲 一. 外卖订单的智能 调度系统 二. 智能调度系统的 大数据分析监控 4 三. 智能调度系统中 的人工智能
- 5.提纲 一. 外卖订单的智能 调度系统 二. 智能调度系统的 大数据分析监控 5 三. 智能调度系统中 的人工智能
- 6.外卖订单智能调度系统发展历程 调度 系统 1.0 调度 系统 2.0 调度 系统 3.0 调度 系统 4.0 人工派单模式 系统派单模式 云端分组派单模式 深度学习智能模式 订单云端分组 出餐时间预估 整体最优分配 深度学习智能 配送距离 骑士运力 订单相似度 期望送达时间 A 组 B 组 • 调度员根据订单地址和骑士 位置来进行订单分配 • 人力调度派单峰值为每人 800单/天 • 系统综合考虑配送距离、 骑士运力、期望送达时间 等因素来自动派单 • 系统综合考虑各因素进行 订单分组，然后再指派给 合适的骑士 6 • 出餐时间估算更准，缩短 骑士到店等待时间，节省 运力，提升用户等餐体验
- 7.外卖订单智能调度要解决的核心问题 5 1 调度系统算法 4 2 3 7
- 8.1 路线规划 • 动态规划最优配送路线，且合理 并单，以最低的配送成本最大化 满足用户配送体验。 • 考虑用户期望时间的TSP问题 • 构建模型综合评估用户体验与配 送成本打分 • 采用动态规划和模拟退火算法等 算法，求得最优路线 8
- 9.2 时间预估 开始配送 骑士到店 到店时间 骑士取餐 等餐时间 到达用户 送餐时间 完成交付 交付时间 交付时间预估 到达识别，交付时间计算 数据积累，异常数据剔除 用户下单 网格建立，分时段统计 商户接单 商户出餐 骑士速度预估 取餐/送餐分别回归拟合 出餐时间 9
- 10.2 时间预估 — 出餐时间预估 数据 & 特征工程 获取样本数据 • 特征 = 基础特征 + 组合特征 + 统计特征 + 稀疏特征 • 基础特征：订单信息，如商户id、菜品名称、下单时间、未出餐订单、前序订单误差等 • 组合特征：核心基础特征的组合 • 统计特征：订单信息的数据统计特征，如均值、方差 • 稀疏特征：采用one-hot编码，各个菜品、商户、周几等作为特征维，构造稀疏特征 • 降维：PCA降维，减少内存消耗并一定程度上避免过拟合 过滤数据 组合基础特征，构造组合特征 模型 • DNN模型 - DNN深度神经网络学习；通过引入非线性映射，并包含多层感知器，海量的出餐时间训练数据，DNN 更好地学习自身有用的特征 - DNN对特征工程要求较低，自身可以学习有用的特征，PCA降维影响较小，但时间复杂度较高 • 抽取基础特征 XGBoost模型 - 采用近似求解算法，找出可能的分裂点，避免选用贪心算法的过高时间复杂度 - 计算采用不同分裂点时，叶子打分函数的增益；并选择增益最高的分裂点，作为新迭代树的最终分裂 节点，构造新的迭代树 - 通过调节迭代树数目、学习倍率、迭代树最大深度、L2正则化参数等进一步避免过拟合 10 组合基础特征，构造组合特征 统计基础信息，构造统计特征 独热编码，构造稀疏特征 降维
- 11.3 决策模型 • 骑士体验 取餐距离、订单数量、订单组数 • 用户体验 订单剩余时间、骑士完成时间、 订单准时性 • 配送效率 等餐时间、空驶距离、空闲骑士、 商圈压力 距离的节省： 订单组与骑士打分： 根据商圈压力调整： 11
- 12.4 分配方案 Greedy + 多轮KM算法分配方案 KM求解骑士和订单全局最优的分配 • Greedy分配解决特殊业务需求相关 • 调度系统先对骑士和订单组（根据骑士的位置、身上的单量 等）进行打分，得到订单组和骑士的打分矩阵，然后根据业 务需求优先分配指定订单，其他的则根据KM算法找到骑士和 订单的最优分配方案 • KM算法找到其余全局最优的分配方案 KM算法 （1） 初始化可行标杆 （2） 用匈牙利算法寻找完备匹配 （3） 若未找到完备匹配则修改可行标杆 （4） 重复（2）（3）直到找到相等子图的完备匹配 订单 订单 骑士 骑士 12
- 13.5 供需平衡 5.1 配送时长预估模型 • 基于现有状况、订单增速、消 化速度、天气、当前手段等多 维特征，使用XGBoost模型回 归预测未来五分钟进单的平均 配送时长 • 分商圈、分时段、多模型的精 细化预估 • 分布式、多线程、并行计算最 佳分割点，满足海量数据的实 时性要求 • 在供需失衡之前，即实施调控 手段 13
- 14.5 供需平衡 5.2 单量调控模型 • 通过价格平衡未来的进单量 和系统可承载的单量 • 基于GBRT对未来进入单量的 实时预测 • 贪心算法求解系统最佳承载 单量 • 根据当前系统状态匹配最佳 的溢价手段使之回归至最大 可承载单量的调控模型 • 在供需失衡之时，实施最有 效的调控手段 14
- 15.总结—外卖订单智能调度要解决的核心问题 借助机器学习实现精准的配送时长预估，预 测不同价格杠杆的效果，满足用户体验的情 况下，最大化的承载适合的单量 5 1 调度系统算法 4 依据评价模型得出的订单和骑士匹配程 度，全局最优进行整体调度分配 动态规划最优配送路线，且合理并单，以最 低的配送成本最大化满足用户配送体验。 2 借助机器学习与深度学习实现，骑士到店时 间、等餐时间、骑士到用户时间、交付用户 时间等配送全流程节点时间预估 3 建立配送成本及用户体验的评估模型，并基于多 场景多维度权衡骑士和待分配订单匹配程度 15
- 16.提纲 一. 外卖订单的智能 调度系统 二. 智能调度系统的 大数据分析监控 16 三. 智能调度系统中 的人工智能
- 17.智能调度系统的分析监控 1 调度系统 • 云端虚拟队列，实现调度指派 • 提升物流效率 5 • 合理划分物流范围 • 节省调度运力，提升商户配送能力 2 寻宝系统 时光机 4 • 精准模拟实际订单分布情况 • 有效评估调度算法的改进效果 • 真实再现调度场景细节 • 回溯定位异常调度原因，诊断调试算法 3 仿真系统 实时监控 17 • 实时获取调度监控指标 • 及时预警引入人工干预
- 18.1 时光机系统—历史数据可视化分析 真实再现调度场景细节 回溯定位异常调度原因，诊断调试算法 18
- 19.2 实时监控系统—当前状况实时监控 实时获取调度监控指标 及时预警引入人工干预 19
- 20.3 仿真系统—未来效果仿真预测 精准模拟实际订单分布情况 骑士路线/ 任务规划 等待用 户时长 有效评估调度算法的改进效果 订单 在岗骑 士数量 调度 算法 骑士 速度 餐厅出餐 时间 20
- 21.4 寻宝系统—线下优化运营优化指导 精细化优化商户配送范围 分级配送缩短交付用户时长 根据仿真系统及历史 大数据精细模拟在不 同单量不同骑士数量 下配送体验，预估在 天气变化、运营活动 订单激增等情况下合 理骑士人数 综合分析商圈内用户、 商户及骑士，提供线 下运营方案指导 寻宝系统 根据不同POI的用户 交付时长及单量，测 算增加固定骑士进行 末端分级配送用户交 付成本和直接配送成 本，选取适合耳机配 送POI 精细化分析商户到每 个POI用户配送成本及 收益，指导商户配送 配送范围划分 商圈健康度诊断 精细指导骑士人数配置 21
- 22.总结—物流系统生态是保证用户良好物流服务体验的基石 调度系统 寻宝系统 指导业务 时光机 回顾过去 仿真系统 预测未来 实时监控 监控现在 22
- 23.提纲 一. 外卖订单的智能 调度系统 二. 智能调度系统的 大数据分析监控 23 三. 智能调度系统中 的人工智能
- 24.智能调度系统的自主学习能力 离线训练 Grid Search 搜索方式 Genetic Algorithm Gradient Descent 基础设施 优化 模型 求得 梯度 加载 数据 计算 偏导 仿真 调度 仿真系统 训练维度 分商圈 分时段 评估 结果 在线学习 预分配 在线预估 实时评价 24
- 25.智能调度系统对顾客等待时间的优化 平均等待时间显著缩短 数据分析和技术是减少肥尾从而 提高用户体验的最大贡献者，降 低客户流失的可能性 35% 30% 订 单 的 百 分 比 25% 20% 15% “长尾”的减少 10% 历史顾客等待时间分布 5% 当前顾客等待时间分布 历史顾客平均等待时间 0% 0 20 40 60 80 顾客等待时间 25 100 120 当前顾客平均等待时间
- 26.回顾 外卖订单的智能 智能调度系统的 调度系统 分析监控 智能调度系统的 26 自主学习
- 27.百度外卖技术团队 百度外卖技术团队对内、对外的沟通、交流和学习平台。更多优秀技术文章、 公开课、招聘信息等，欢迎关注。 欢迎扫码关注 27
- 28.
