滴滴 KDD CUP 2020 赛题详解
由滴滴主办的 KDD Cup 2020 强化学习挑战赛正式开赛，邀请全球算法高手共同挑战共享出行领域优化难题。本次比赛由数据竞赛网站 biendata.com 提供评测支持。
KDD Cup（国际知识发现和数据挖掘竞赛）由美国计算机协会知识发现与数据挖掘专委会（ACM SIGKDD）发起，从 1997 年开始，每年举办一次，是国际公认的数据挖掘领域的最高水平的赛事。该比赛同时面向企业界和学术界，每年都会吸引世界数据挖掘界的顶尖专家、学者、工程师、学生等参加，也被誉为是数据挖掘领域的「世界杯」。每年都有很多杰出的学术组织及科技申请承办 KDD Cup，但最终只有拥有深厚的学术积累和行业实践的机构能够脱颖而出。
今年 KDD Cup 2020 的 RL Track（强化学习赛道）最终由滴滴举办。在这一挑战赛中，滴滴邀请全球参赛团队聚焦按需出行平台，尝试应用机器学习解决方案来提出智能策略，在确保用户体验的基础上，进一步提高出行效率和司机收入。此次比赛滴滴共设计了订单分配和车辆调度两个任务，在派单分配任务中，参赛团队需设计开发算法来指定在派单窗口内的订单和司机的匹配；而在车辆调度任务中，参赛团队需设计开发调度算法指引一批空闲司机开往指定目的地。两个任务既可分别开发，也有联动的空间。
比赛将主要基于滴滴盖亚数据开放计划脱敏数据集，该数据集包含一定时间内滴滴平台专车和快车在成都市部分区域内的脱敏轨迹数据，此外还新增加了其他比赛辅助数据。参赛团队提交的方案会在测试环境中进行评估打分。
01
比赛背景
随着智能手机在我们日常生活中的普及，按需出行（MoD）或网约车平台已成为一种可行的解决方案，可以提供更及时和更个性化的运输服务。这样的平台包括滴滴、优步和 Lyft。这些平台可以把潜在的出行需求与合适的司机联系起来，从而更有效地利用空置车辆，满足日益增长的运输需求。高效率的按需出行系统可以为司机和乘客提供更好的用户体验：司机可以通过减少空转时间获得更高的收入，乘客等待时间会更短，满意度也会更高。
按需出行系统的效率取决于时空中供需分布的协调程度。如果想要调整供给分布来更好地协调需求，从而优化运营效率，有两个重要的问题：车辆调度（vehicle repositioning）和订单分配（order dispatching）。订单分配负责把空闲的车辆分配给等待中的出行订单，并把乘客（和司机）运输到订单终点。车辆调度是一种更主动的策略，可以把闲置的车辆部署到预计未来会产生需求的特定位置。
02
比赛任务
比赛参赛者需要同时解决按需出行平台上订单分配（order dispatching）和车辆调度（vehicle repositioning）问题。参赛团队可以解决这两个问题或其中之一。参赛者的算法将在一个模拟出行平台环境中进行评估。
比赛环境
测试环境中有所有车辆和出行订单的状态。每辆车同时只能为一个订单提供服务，即不考虑拼车。订单分配算法可以根据车辆和订单的状态，把闲置车辆分配给等待中的订单。车辆和订单都可以处于未被分配的状态。测试环境每两秒会调用一次订单分配算法并执行分配任务。被指派的车辆会根据分派指引接到订单乘客，并运输到目的地。如果某个订单没有在当前时间窗口内匹配到车辆，会被认为丢失。如果等待的时间过长，乘客可以取消订单。在乘客下车后，司机和车辆重新进入空置状态。在这种状态下，司机可以接受订单匹配。
参赛者还可以在测试环境中控制一组匿名车辆（5 辆）的重新定位。如果车辆的空置时间超过 L=5 分钟的阈值，就有资格接受调度。测试环境会定期向调度算法发送选中车组内可用车辆的状态信息，而调度算法会让司机把车开到某个特定的目的地。如果司机即将在当前位置附近逗留，他们会停留 L 分钟，直到另一个重定位请求被触发。在选中车组之外的车辆会依据一组通用转移概率完成空置移动。被重新定位的车辆的沿球面（也就是大圆距离上的）速度被设置为三米每秒。
任务1：订单分配
参赛团队会设计开发算法来指定在 2 秒窗口内的订单-司机匹配。在这个窗口内的所有未接订单和空闲车辆的状态信息会被传给算法。此算法模块会在一天模拟中的每个窗口被调用。评估模拟会跑多天，日均司机总收入（按奖励单元计算）会作为本任务的得分。
任务2：车辆调度
参赛团队会设计开发调度算法给一小部分（ 5 辆）事先设定的车辆。这些车辆的身份对于调度算法是未知的，所以调度算法不应依赖于调度车辆的身份。这些车辆在连续空闲 5 分钟后，会接受调度。模拟环境周期性的调用调度算法来指引这些空闲司机开往指定目的地。本任务的得分计算为受调度车辆司机的人均收入效率（单位时间的奖励单元收入）。
参赛团队的算法将在模拟环境中被评估分数，但参赛者无法访问模拟环境。参赛团队可以选择同时开发两个算法或其中的一个算法（比赛组织者会提供一个分数较低的样例代码）。
比赛的两个任务策略有相关性（即在同一个环境中测试），但是仍然是非常不同的任务，所以只专注一个任务并一定显著影像另一任务的得分。
本次比赛的设置贴近真实的业务应用场景。而在真实业务场景中，因为操作和财务上的风险，所以通常不可能直接在生产系统中直接训练模型，探索数据。不过，历史操作记录通常可以提供充足的数据。我们可以搭建模拟器来评估各种算法，但很难照顾显示生产系统中的所有细节。
03
比赛流程
开发阶段
比赛提供给每个参赛团队一个开发包，包括公开数据集，样本代码，和其他需要的信息。开发比赛任务算法并不一定需要开发模拟器，但评估环境动力学描述会提供给参赛团队参考使用。任务提交方式为代码提交，模块接口需符合任务要求。团队可在比赛论坛里讨论技术和支持问题。
方案验证
方案提交通过 zip 文件从平台提交，zip 文件内的文件夹结构需符合指定要求。每个团队每天最多可以提交 1 次到评估环境。评估会离线进行。每个成功的提交会得到两个得分，对应订单分配和车辆调度的评估指标。得分会在排行榜上更新。
决赛评估阶段
在开发阶段两个指标上的任意一个排名前 25 的团队会进入决赛评估阶段。开发阶段的最后一次提交代码会在一个不同的（开发阶段未见过的）测试评估环境中进行评估。在最终总得分中，开发阶段的最后得分占 40%，决赛评估阶段的得分占 60%。所有决赛队伍会在两个指标上分别排名。
04
参赛方式
🔍
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。