江苏龙网

  1. 首页 > 人文 > >

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


问题定义
本赛题的优化目标是最大化平台上司机一天内的平均总收益 ， 因此在派单时 ， 不仅要考虑最大化当前时间窗的收益 ， 还必须考虑未来的可能收益 。 同时 ， 当前的订单分配会影响车辆的位置和收益 ， 对未来产生影响 ， 是一个序列决策问题 ， 因此考虑通过强化学习解决 。 此情景下 ， 环境 (Environment) 包括订单、司机车辆信息位置等 ， 而参赛者需要定义智能体 (Agent)的学习和预测策略 ， 以最大化司机的收益 。 本问题中司机和车辆一一对应 ， 下文中如未特殊强调 ， 车辆和司机含义一般可以互换 。 状态 (State)、动作(Action) 和奖励 (Reward) 设计如下：
2.1.1 状态
联合团队使用车辆的地理坐标经过离散化后对应的 ID ， 来表示车辆的状态 ， 而不考虑时间因素 。 具体的 ， 团队同时使用了多种离散化策略 ， 使得每个地理坐标 ， 对应多个不同粒度的状态 ， 如主办方提供的六边形格子划分策略 ， 还可以是多种不同大小的四边形等 。 如下图所示 ， 对于图中的坐标点（红色圆点） ， 离散化后 ， 可以同时采用六边形、不同大小的四边形来标识该点对应的状态 。
北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题
本文插图
2.1.2 动作
智能体执行派单程序后 ， 会生成司机和订单的匹配列表 。 在不考虑取消订单的情况下 ， 成功匹配的司机将会进入服务 (serving) 状态: 司机会到达指定上车点 ， 接到乘客 ， 并运送到指定下车点 ， 拿到相应的奖励 。 而未能分配到订单的司机 ， 将会闲置(idle) ， 不能拿到任何收益 。
2.1.3 奖励
每次派单成功后 ， 司机会拿到相应订单的收益 ， 作为本次动作的奖励 。 本次比赛的目标 ， 即是最大化所有司机的平均收益 。
算法设计
每次智能体被调用时 ， 将接收到当前所有的候选订单信息 ， 并在 2 秒内做出司机和乘客的匹配 。 候选信息列表是候选订单的集合 ， 每个候选订单主要包含如下信息：
oorder_id 和 driver_id: 订单 ID 和司机 ID ， 用来唯一标识候选订单和司机；
odriver_location: 司机在当前时刻所处的地理位置 ， 本次比赛中地理位置信息均采用经纬度对来表示；该信息信息经过离散化后 ， 得到订单的起始状态标识；
oorder_finish_location：订单结束位置 ， 即订单的目的地；该信息经过离散化后 ， 得到订单的终点状态标识；
oduration：订单的预估时长；
oreward：订单带来的收益 。
此外 ， 还有当前时刻信息、订单起始位置（order_start_location）、接驾距离（司机和乘客的距离 order_driver_distance）、预估接驾时长（pick_up_eta）等 ， 可以根据此类信息推断订单取消概率 。
本方案整体策略为通过时序差分算法（Temporal Difference）学习状态值 ， 并通过二分图匹配算法最大化收益 。 具体的 ， 智能体接受到候选订单列表后 ， 将依次执行以下三个步骤：
1) 构图：通过候选订单信息 ， 将司机和乘客建模成二分图；并根据起止点对应的状态 ， 计算边权；
2) 匹配：通过二分图匹配算法 ， 将司机和乘客匹配 ， 并派单；
3) 更新：根据匹配结果 ， 通过时序差分算法的学习规则 ， 更新涉及到的状态对应的值 。
下面详细介绍每个步骤 。
2.2.1 构图
本文将订单 ID 和司机 ID 作为图的顶点 ， 并根据候选订单信息 ， 连接相应的订单和司机 ， 得到对应的图 。 因为订单之间、司机之间均不存在连接关系 ， 因此该图是二分图 。 另外 ， 为了保证更快的得到匹配效果 ， 加速后续匹配算法 ， 将二分图按如下策略剪枝：对于每个订单 ， 只保留接驾距离最小 K 个司机对应的边；在比赛中 ， K 取 11 。
不妨将司机位置（driver_location）和订单终点（order_finish_location）对应的状态分别记为 S 和 S^' ， 其对应的状态值分别为 V(S) 和 V(S^')， 则二分图中的边权 w 计算方式为：


推荐阅读


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

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