江苏龙网

  1. 首页 > 资讯 > 科技 > >

|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题( 三 )


不妨将司机位置（driver_location）和订单终点（order_finish_location）对应的状态分别记为 S 和 S^' ， 其对应的状态值分别为 V(S) 和 V(S^')， 则二分图中的边权 w 计算方式为：
|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图

其中 ， R 为订单对应的收益 ， t 为离散化后的订单时长 ，
|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图

为折扣因子 ，p 为订单的取消概率 。
订单取消概率和接驾距离、接驾时长等有关 ， 可以通过对官方提供的历史数据中订单取消概率建模 ， 得到对应的订单取消概率预测模型 ， 以便线上推断每个订单的取消概率 。
2.2.2 匹配
构图完成后 ， 得到剪枝后的二分图以及每条边的权重 ， 可以直接利用匈牙利算法进行匹配 。 在实际使用时 ， 团队发现 Scipy 提供的对应算法接口 (https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html) 效率较低 ， 导致超时（不能在 2 秒的时间窗内做出匹配） 。 如果直接使用贪心算法（完全贪心或
|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图

- greedy）分配订单 ， 则效果不佳 。 另外 ， 司机和乘客数量一般不等 ， 导致图中二分图顶点数目不均衡 。 综合以上因素 ， 我们使用 C++ 实现了高效的匈牙利算法（hungarian algorithm） ， 并编译成对应的 so 文件 ， 通过 Python 直接调用 ， 以解决容易超时的问题 。
2.2.3 更新
当订单分配完成后 ， 需要根据分配的结果更新对应的状态值 。 因官方未提供比赛环境对应的模拟器 ， 不能线下调参 ， 因此选择从简单模型入手 。 我们选取了单步在线策略更新的 SARSA 算法（state–action–reward–state–action） 。 对于每个订单的起点和终点 ， 它们均会同时激活多个不同粒度的状态表示 ， 记每个坐标位置离散化后的状态个数为 k 。
对于派单的车辆 ， 目标状态值为：
|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图

对于闲置的车辆 ， 目标状态值为：
|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图

计算得到状态值后 ， 对起点所对应的各状态 ， 按照如下公式更新：
|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图

其中 ，
|北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图

为学习率 。
联合团队也曾尝试基于深度强化学习的状态学习和更新方法 ， 但效果不佳；尝试基于动态规划、时序差分等方法 ， 通过历史数据在线下学习对应状态值 ， 作为线上状态的初值 ， 未能取得收益 。 也尝试了一系列方法 ， 以降低时序差分单步更新时可能引入的噪音 ， 仍未能取得更好的效果 。
因此 ， 针对真实场景下的大规模订单实时分配问题 ， 将强化学习和二分图匹配算法相结合 ， 在最大化当前收益的同时 ， 能够有效兼顾未来可能的收益 。 相比基线模型或其他选手方案 ， 本方案能够取得更大的收益 。


推荐阅读


上一篇：|太平洋又出新品！2020大公司终身重疾横向测评，哪款值得买？

下一篇：|李航等提出多粒度AMBERT模型，中文提升显著