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

机器之心专栏
作者：罗远飞
近日，全球顶级数据挖掘竞赛 KDD Cup 2020 已经正式画上圆满句号， KDD Cup 2020 RL Track 比赛结果也随之出炉，北京航空航天大学软件开发环境国家重点实验室童咏昕教授研究组与第四范式罗远飞组成的联合团队脱颖而出，斩获 KDD Cup 2020 强化学习挑战赛冠军。

本文插图
据主办方滴滴介绍，本次注册队伍达到了 1007 支，其中不乏普渡大学、南京大学、中国科学技术大学、中山大学、东南大学等国际顶尖高等院校以及电商巨头京东、出行巨头 Lyft、日本通信巨头 NTT DOCOMO 的身影。
作为全球数据挖掘领域最有影响力的赛事， KDD Cup 比赛由 ACM 协会的国际顶级会议 SIGKDD 举办，自 1997 年以来每年举办一次。 KDD Cup 多年来一直保持着很高的工业界参与度以及对解决实际问题的敏感度。与去年 KDD Cup 强化学习挑战赛的分类问题以及过往多应用在体育竞技类比赛性质不同，今年的强化学习赛道（RL Track）聚焦于更加真实且问题极为复杂的业务场景，旨在解决共享出行领域优化难题。在题目难度进一步增加的同时，也将强化学习的价值进一步放大。
以下内容为冠军团队在竞赛中的技术分享。
聚焦共享出行，题目难在哪？
如今，按需出行（MoD）或网约车平台已成为大众不可或缺的出行方式，对于网约车平台来说，高效率的按需出行系统可以为司机和乘客提供更好的用户体验：司机可以通过减少空转时间获得更高的收入，乘客等待时间会更短，满意度也会更高。因此，如何更有效地利用空置车辆，更快、更高效地匹配乘客需求、提高司机收入成为了网约车平台优化指标当中的重中之重。
按需出行系统的效率取决于时空中供需分布的协调程度。如果想要调整供给分布来更好地协调需求，从而优化运营效率，有两个重要的问题：车辆调度（vehicle repositioning）和订单分配（order dispatching）。订单分配负责把空闲的车辆分配给等待中的出行订单，并把乘客（和司机）运输到订单终点。车辆调度是一种更主动的策略，可以把闲置的车辆部署到预计未来会产生需求的特定位置。
因此，参赛者需要同时解决按需出行平台上订单分配（order dispatching）和车辆调度（vehicle repositioning）问题，通过主办方提供的真实场景数据和模拟器，基于强化学习设计一个智能匹配与调度算法，以最大化平台所有司机的平均日收入。
联合团队解释了赛题中的一些挑战：
真实场景，数据量大：历史数据包含西南某省会城市一个月时间内几百个 G 的数据记录；线上亦基于若干天的真实数据来评测；
因素多：影响司机收益的因素很多，如接驾距离、天气、路况信息、出行时间等，需要考虑复杂的环境因素；
实时性：在一天内，算法每 2 秒被调用一次，必须 2 秒内做出分配，且订单和司机信息每次不同，不能预分配；
调参难：官方并未提供模拟器，且已有数据不足以在线下搭建出高质量的模拟器，需要开发的算法具有较强的鲁棒性。
冠军团队如何破局？
为了最大化平台上所有司机日均收入，在计算每个订单的收益时，采用基于强化学习的方法，不仅能考虑当前时刻的收入，还能兼顾未来可能的收益。同时，结合剪枝与 C++ 实现的高效二分图匹配算法，能够在 2 秒的时限内，及时找到合适的订单分配方案，从而取得了更好的效果。
其解决方案整体框架如下：

本文插图
代码地址：https://github.com/maybeluo/KDDCup2020-RL-1st-solution