菜鸟网络 浪迹 城市及末端揽配网络的智能化实践

CodeWarrior

2019/07/08 发布于 编程 分类

GIAC2019 

文字内容
1. 城市及末端揽配网络的智能化实践 吴黎霞(浪迹) 菜鸟⽹络 ⾼级算法专家
3. 智能化具体实践内容 l 智慧物流&快递员调度场景 l 物流下的大数据&挖掘 l Region Learning l 时效预测(DeepETA)及快递员工作演化模型(WEN) l 订单智能分配(派单模型) l Q&A
4. 智能决策驱动智慧物流发展 全局物流优化的基础:以数据&算法为支撑的决策引擎 库存管理 干 线 履行决策 网络规划 箱型推荐 机器人调度 路由/路径规划 Decision Process Optimization Engine 时空大数据 机器学习/运筹优化 快递员运力调度
5. 消费者对智慧物流的一些认知 背后是快递员的数字化、精细刻画与智能调度 裹裹寄件-上门取件 物流详情-查件
6. 裹裹寄件背后的业务技术 营销平台 需求接入 消 费 者 运力运营平台 包裹侠 城市网络规划 成本&效率&服务 供需匹配 需求中心 服 务 表 达 数 字 化 运力中心 时空约束 数 字 化 优化目标: 订单、运力、收益的最优匹配 调度策略 运力画像、 消费者画像、时空画像 运力调度引擎 收 益 管 理
7. 算法决策平台 - 调和剂 实时派单&定价 Demand Side Shared Supplier Side 机制设计( 网络规划) 运力在线化挖掘 提服务体验,增单量 提效率,降成本 优化目标 优化目标 用户触达增长 实时派单, 时空约束下的多目标优化 𝑦 = 𝑓(𝜆( ∗ 𝑓𝑒𝑎𝑡𝑢𝑟𝑒1 + 𝜆/ ∗ 𝑓𝑒𝑎𝑡𝑢𝑟𝑒2) 𝑥 = min{𝜆( ∗ 𝑙𝑜𝑠𝑠𝑓( + 𝜆/ ∗ 𝑙𝑜𝑠𝑠𝑓/ }
8. 城市与末端物流下的大数据 l 线上用户流量数据 主动Query/隐式意图 浏览 收货、评价反馈 点击 收藏、成交、支付 l 线下物流数据(以末端为例) 包裹与快递员的数字化 位置接单(派单到人) 轨迹 网点(卸货) 消费者地址 轨迹 轨迹 位置接单 位置接单 u 百万级的快递员轨迹 u 亿级的包裹地址 轨迹: 空间点时间序列[ (x1, y1, t1)….(xn,yn,tn)]
9. 轨迹数据管理平台 实时位置 查询服务 服 务 接 口 ETA 查询服务 。。。 通用接口 语义轨迹存储 轨 迹 挖 掘 层 轨 迹 标 注 层 。。。 • 带有语义标注的 移动行为序列 语义轨迹分析 (时空立方体、聚类、时序挖掘、深度学习 ) 路网 数据 POI 数据 • • 锚点匹配 • AOI服务 多源数据融合 包裹 数据 移动行为序列 语义区块标注 (空间连接 ) 一系列GPS轨迹点 (x, y, t) 结构化轨迹 轨迹计算策略 轨 迹 预 处 理 层 • • • 轨迹分段 轨迹预处理 轨迹停留/移动行为挖掘 原始轨迹 • 时间截断 • 空间分割 • 密度阈值 ...
10. Region Learning: 提出AOI(Area Of Interest)服务 空间地址离散区域化为AOI: 聚合成area, 还原真实配送情况, 降低复杂度 业务定制 高层级AOI Graph表征 低层级region&空间Graph 时空转移图 Map Segmentation RoadSegment 杭州市余杭区 城市路网 <LinkID, Type, (lon,lat),(lon,lat)..> 重要的挑战:如何合理表征AOI用于计算
11. Region Learning: AOI(Areas Of Interest)服务 l 从多源异构数据中学习AOI表征 Ø AOIs位置 Ø AOIs的空间近邻关系 Ø AOIs的属性 Ø 基于AOIs的轨迹序列转移关系 通用表征 l 方法 u u 编码异构数据 • 编码行为语义数据 • 编码其他信息… 采用Multi-View AutoEncoder框架融合异构数据 场景表征
12. Region Learning: AOI(Area Of Interest)服务 l 从轨迹中编码行为语义信息 Ø Ø 从skip-gram 到 sliding window Encoding Trajectories PMI矩阵分解 与 Word2Vec 内在一致性. PMI矩阵分解用AutoEncoder替换.
13. Region Learning: AOI(Area Of Interest)服务 l 从空间距离关系中编码信息 random surfing strategy重构PPMI矩阵 • Euclidean Graph • Adjacency Graph l Multi-View AutoEncoder框架 • PPMI views are trained with a dynamic weighting layer. • Each view is decoded separately 两点机制: • 参数共享 • 动态Weighting机制
14. Region Learning: AOI(Area Of Interest)服务 l 效果&各方法对比 • 数据: 快递员包裹配送行为轨迹&配送区域空间 Region Learning模型HETA与其他方法在ETA预测&AOI聚类两个场景上对比. • Clustering Task 将真实订单分配作为ground-truth类别. 可与Node2vecadj、Node2veceuc、Geohash、Deepwalkeuc、Deepwalkadj作对比 • • ETA Prediction Task 在末端配送的ETA预测 在DeepETA预测模型中用各种不同AOI Embedding作为空间特征 HENA 取得超过15%预测错误率的下降
15. “查包裹”物流详情 2小时时效&轨迹透出 挑战: l 类 似 工 作 ( Ta x i ) : 单 个 O D 的 时 效 预 测 末 端 包 裹 配 送 : 一 趟 Tr i p 包 含 多 个 社 区 , 多 个 包 裹 快递员每日几乎100个包裹 l 时效时间2部分: 路上的时间 + 社区/楼栋内的时间 易受实时影响: 实时配送路径、配送模式、负载要配送包裹…
16. 提 出 D e e p E TA 方 法 A Spa t i a l -t e m pora l Se que nt i a l Ne ura l Ne t work Mode l for E st i m a t i ng Ti m e of Arri va l i n Pa c ka ge De l i ve ry System Jointly Training and Prediction Fully Connected Layer 整体网络结构 Loss + 三模块组成: Latest Route Vector Time-unvariant Vector + Area Vector Spatial Encoder Embedding Area ID Time Deliver Status Distance Weather Time-variant route feature l Latest Route Encoder + Delivered Route Encoder Undelivered Route Encoder Frequent Route Selector Embed Area Vector Courier ID Distance Time-invariant feature Frequent Pattern Encoder Latest Route Representation Bi-direction LSTM Cells Historical Pattern Vector Package Info Date l F re q u e n t P a t t e r n Encoder l Prediction Module
17. D e e p E TA : L a t e s t R o u t e E n c o d e r 模块 Raw Trajectory AOI特征标注 Latest Route Vector Output Layer 语义标注 Concat LSTM LSTM ………… LSTM LSTM LSTM ………… LSTM Semantic Annotation Layer 网格匹配 Deliver route Forward Layer Backward Layer Deliver Graph Conv Layer t时刻 + Input Layer Embedding Area Encoding Time-variant Feature Time-invariant Feature t-1 ………… t-k LSTM LSTM ………… LSTM LSTM LSTM ………… LSTM Common Feature Embedding ScheduleId PackageInfo Date/Time Weather
18. DeepETA: F r e q u e n t P a t t e r n E n c o d e r 模 块 类比Attention机制 Historical Pattern Vector Output Layer + Delivered Pattern Vector Undelivered Pattern Vector Softmax Pattern Selector W W …… W W …… Route Encoder u Delivered route pattern Softmax W LSTM Layer …… W …… Time-variant Route Feature Latest Location 已派送路径、当前位置、预测包裹位置 相似历史配送路径 u To - b e - d e l i v e r e d p a t t e r n 未配送包裹数、当前位置、预测包裹位 置、相似未配送模式 DNN Layer Input Layer Latest Route Vector 二部分组成: Undelivered Set 30分钟区间, 各区间得分Softmax
19. 实 验 &模 型 对 比 数据: 北京, 331快递员的配送路径(从20180701到20180901) Pkgs Route Nodes Time AvgDt 80 2 20 8h 3.5h The performance of different baselines and DeepETA Methods RMSE (min) MAPE (%) LR 144.18 43.5 DNN 127.58 37.4 XGBoost 123.66 38.2 LSTM 110.37 34.9 DeepTTE 97.85 29.7 DeepMove 72.43 24.3 DeepETA 63.58 20.6 <DeepETA: A Spatial--temporal Sequential Neural Network Model for Estimating Time of Arrival in Package Delivery System>, Accepted AAAI2019
20. 快递员行为学习-WEN(工作演化模型) l 线上用户表现出的兴趣呈现出多样性&差异性, 随时间演化一样; 快递员工作模式(工作时间-活动范围)也会发生演化. l 特点: 工作类型部分兼职往全职方向演化. l 思考: 可否通过模仿学习(imitation learning), 从快递员偏好动态变化中学习 快递员数 单量 揽收时间 2 12 22 32 42 52 62 72 82 92 102 112 122 132 142 152 162 工作天数 一个运营区的快递员工作示意图 提出WEN(工作演化模型)
21. 快递员行为学习-WEN(工作演化模型) l 快递员工作演化流程 激励学习 行为偏好学习 动态分析 揽件列表 区域AOI化 l 快递员决策行为描述为一个Markov Decision Process(MDP) • State: • Action: Stay或者行驶到周边AOI区域 • Reward: Feature(单均间隔距离、距离截止时间等)的函数 实时的时空区域 + 负载订单 行为变更
22. 快递员行为学习-WEN(工作演化模型) l 前向问题: 给定Reward Function下, 利用MDP作行为决策. 可以采用: Reinforcement Learning(Q-Learning, Policy Gradient, DQN..) l 逆向问题: 给定快递员轨迹下, 找到Reward Function R(s, a) Inverse Learning • Apprenticeship Learning • Maximum Entropy IRL(Maxent IRL) a1 a2 [1]: Menghai Pan, Yanhua Li《Dissecting the Learning Curve of Taxi Drivers : A Data-Driven Approach》
23. 实时派单 Online Allocation Problem 可以描述为Bipartite Graph Wij Supply: 快递员 Demand: 订单 挑战: l 如何确定Demand与Supply间的权重 l 实时分配如何保证业务比例约束(保量)
24. DispatchNet l 提出DispatchNet来量化 l 两个问题: 𝑉< 𝑂𝑟𝑑𝑒𝑟, 𝐶𝑜𝑢𝑟𝑖𝑒𝑟 = 𝐸< [𝑟] • 优化目标: 多目标优化问题(及时揽收率、转单率、揽收距离..) • 数据特征: 强时空特性, 空间维度 + 时间维度 DispatchNet基于数据类型, 整合空间与时间信息 同质 空 间 维 度 扩 散 异质 文本地址 匹配 文本&空 间位置 空间距离 文本&实 时负载 时间维度 u 空间维度: 一个时间片状态 • 空间同质–匹配 • 空间异质–映射 u 时间维度: 各时间片连接, 序列学习 • 历史揽件行为 • 未来行为预测
25. DispatchNet l Baseline方法 (重点在 特征工程) 将时间/空间信息设计到特征中 Ø 大规模稀疏ID特征模型 Ø 强统计特征模型 (如GBDT/RF) l DispatchNet 重设计网络结构, 模型工程 • 常用Multi-Static Graph + LSTM处理 (高复杂度 + 缺少连续性) • Continuous-Time Dynamic Embedding. Spatio-Temporal Walk 𝑉H 𝑉H 𝑉E 𝑉/ T=5 𝑉( 𝑉G 𝑉/ T=5 T=2,S 𝑉F 𝑉G 𝑉E T=3,S 𝑉( T=6,S T=7,S 𝑉F
26. DispatchNet Score 学习目标 隐藏层K 隐藏层1 级联/合并 学习层 Spatio-Temporal Walk Spatio-Temporal Walk 订单空间关系图 历史活动图 C A B E D 表示层 K Word Embedding H F Context特征 G I 业务特征 业务特征 文本地址 文本地址 …
27. 带业务约束的Online Assignment l 无约束Online Assignment, 最大化目标收益 (多目标转单目标) l 往往有强业务约束, 如需保证各家快递公司的订单比例.. 类似于在线广告平台: Guaranteed Delivery模式 l 带约束Online Assignment: • Supply Constraints: 单量比例保证 • Demand Constraints: 订单必须有人履约 • 额外述求: 期望订单平稳
28. 带业务约束的Online Assignment 可采用的一些方法 l 启发式方法 Ø PID算法 (比例Proportion、积分Integral、微分Derivative) • PID参数调整比较关键 Ø HWM(High Water Mark)算法 • 在线调整参数 l Online LP解决方案 Ø DUAL Algorithm: 原问题转化成对偶问题
29. THANKS Q&A 关注公众号获得 更多案例实践