北航与第四范式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冠军方案：解密共享出行场景中的优化问题】因此 ， 针对真实场景下的大规模订单实时分配问题 ， 将强化学习和二分图匹配算法相结合 ， 在最大化当前收益的同时 ， 能够有效兼顾未来可能的收益 。 相比基线模型或其他选手方案 ， 本方案能够取得更大的收益 。
推荐阅读
- 东方网|第四届“中国创翼”创业创新大赛上海选拔赛决赛举行
- 金涛说球|八村塁第四，姚明力压易建联，NBA亚洲前十球星排名：周琦第九
- 小罐茶大师获权威认证 张成仁荣列第四批“中国制茶大师”
- 海南将增加第四张离岛免税牌照|海南将增加第四张离岛免税牌照 目前有多家企业参与竞争
- 「海南将增加第四张离岛免税牌照」海南将增加第四张离岛免税牌照 目前有多家企业参与竞争
- 金秀儿2020 第四届优生节启动会暨备孕白皮书发布会隆重举行
- 伊朗|伊朗拒购歼-10战机？ 已敲定百架第四代战机 美军售禁令彻底失效
- 特斯拉|每经15点丨陈薇：重组新冠疫苗能有效覆盖病毒变异；海南第四张离岛免税牌照呼之欲出；创业板成交额超3500亿元
- 离岛免税|每经15点丨陈薇：重组新冠疫苗能有效覆盖病毒变异；海南第四张离岛免税牌照呼之欲出；创业板成交额超3500亿元
- 国际军事|伊朗拒购歼-10战机？ 已敲定百架第四代战机 美军售禁令失效