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

本文插图
其中， R 为订单对应的收益， t 为离散化后的订单时长，

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

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

本文插图
对于闲置的车辆，目标状态值为：

本文插图
计算得到状态值后，对起点所对应的各状态，按照如下公式更新：

本文插图
其中，

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